Доказательство алгоритма вычисление многочлена

[Gts]

iifat в сообщении #988678 писал(а):

Gts в сообщении #988223 писал(а):

Как же это я такое написал

Что именно? Сумма от нуля до минус единицы — совершенно добропорядочная сумма по пустому множеству индексов. Она равна нулю.

О, не знал такого.
А я там написал, мол сумму мы считаем от 0 до -1, когда нужно было от 0 до $i-1$, где $i=1$. Именно эта ошибка вызвало моё удивление.

[iifat]

Gts в сообщении #988680 писал(а):

А я там написал

А я ж срасу примерно по этому поводу написал

iifat в сообщении #987157 писал(а):

Ну, в данном случае суммы совпадают, так что не очень важно

Зря, наверное: суммы-то совпадают, но такие мелочи лучше не пропускать

[Gts]

iifat в сообщении #987254 писал(а):

Попробуйте аналогично с вашей.

Нашёл, что рекуррентную формулу можно представить в замкнутом виде с помощью производящих функций.
Решение рекуррентных соотношений
Вот что у меня получилось:

Цитата:

Записать рекуррентное соотношение и начальные данные для него в следующем виде

$P_n = A_n$
$P_i = P_{i+1} x + A_i$

Цитата:

Домножить каждую строчку на $z$ в соответствующей степени и просуммировать строчки для всех $n \ge 0$.

$1 \cdot P_n = A_n \cdot 1$ (1)
$z^i P_i = (P_{i+1}x + A_i) z^i$ (2)
$P_n + z^i P_i = A_n + (P_{i+1}x + A_i) z^i$ (3)

Цитата:

В полученном уравнении привести все суммы $\sum$ к замкнутому виду. Получить уравнение для производящей функции.

$\underbrace{P_n + \sum \limits_{i=n-1}^{0} z^i P_i}_{G(x)} = A_n + \sum \limits_{i=n-1}^{0} (P_{i+1}x + A_i) z^i$

Вторая сумма.
$\sum \limits_{i=n-1}^{0} (P_{i+1}x + A_i) z^i = x(\underbrace{\sum \limits_{i=n}^{0} P_{i}z^i + P_n}_{G(x)} - P_n) + \sum \limits_{i=n+1}^{0} A_{i} z^i =\\ =x(G(x) - P_n) + \sum \limits_{i=n+1}^{0} A_{i} z^i $
И дальше не знаю что делать с $\sum \limits_{i=n+1}^{0} A_{i} z^i$

И ещё, есть ли более простое решение? У меня впечатление, что решение на поверхности, но я его не вижу.

-- 11.03.2015, 18:00 --

Ну и блок-схему с частичными условиями приложу:

[iifat]

Gts в сообщении #988774 писал(а):

Нашёл, что рекуррентную формулу можно представить в замкнутом виде с помощью производящих функций

Эк вас, извиняюсь, расколбасило.
От вас требуется одно очень простое действо: вот последовательность
$a_n$
$a_nx+a_{n-1}$
$(a_nx+a_{n-1})x+a_{n-2}$
и так далее. Надо написать $i$-й член. Безо всяких на то ограничений. Повторюсь, поскольку писать ответ запрещают правила: очень простым способом.

[Gts]

iifat в сообщении #989095 писал(а):

Gts в сообщении #988774 писал(а):

Нашёл, что рекуррентную формулу можно представить в замкнутом виде с помощью производящих функций

Эк вас, извиняюсь, расколбасило.

(Оффтоп)

Всё ок. :) Уже не первый раз бывает, когда я не вижу простой ответ, а ищу что-то архисложное.

По поводу запрета давать ответ - это очень отличное правило. Тут кто-то писал, что мол научатся студенты решать шаблонные задачи, а чуть отступление в сторону и стопорятся. Я уже давно не студент, но надеюсь сейчас всё же научиться самому искать решения, которые для других плёвое дело.

Пока ищу ответ на исходную задачу, попутно задам ещё один вопрос.
Есть вот такой код для возведения в степень:

Используется синтаксис C

k = 0;
b = 1;
while (k != n)
{
    b *= a;
    k++;
}
 

Всегда думал, что инвариант цикла тут будет $b = a^k$, но теперь, когда вы показали построение инварианта с помощью условий, я несколько в затруднении написания инварианта.
Вот что получается:

Таким образом, инвариант будет таким:
$k \ge 0 \wedge k \le n \wedge (b=\prod \limits_{i=0}^{k - 1}a \vee b = 1)$
Условие $b = 1$ предназначено для случая, когда $n = 0$ и у нас получается произведение пустого множества. Я верно рассуждаю?

-- 12.03.2015, 12:37 --

iifat в сообщении #989095 писал(а):

От вас требуется одно очень простое действо: вот последовательность
$a_n$
$a_nx+a_{n-1}$
$(a_nx+a_{n-1})x+a_{n-2}$
и так далее. Надо написать $i$-й член. Безо всяких на то ограничений. Повторюсь, поскольку писать ответ запрещают правила: очень простым способом.

А вот если так:
$(\dots (a_nx + a_{n-1}) \dots)x + a_i$

[iifat]

Gts в сообщении #989187 писал(а):

Условие $b = 1$ предназначено для случая, когда $n = 0$ и у нас получается произведение пустого множества. Я верно рассуждаю?

Опять усложняете. $\prod_{i=0}^{-1}a=1$ — пустое произведение равно единице. Так что на его месте, ради бога, пишите $b=a^k$ (в 5 условии $b=a^{k+1}$)

Gts в сообщении #989187 писал(а):

А вот если так

Ну, по мне так это слишком нестрого, хотя и не уверен. Таки скобочки, имхо, раскройте.

[Gts]

iifat в сообщении #989606 писал(а):

Gts в сообщении #989187 писал(а):

Условие $b = 1$ предназначено для случая, когда $n = 0$ и у нас получается произведение пустого множества. Я верно рассуждаю?

Опять усложняете. $\prod_{i=0}^{-1}a=1$ — пустое произведение равно единице. Так что на его месте, ради бога, пишите $b=a^k$ (в 5 условии $b=a^{k+1}$)

Ааа, теперь ясно. Я сходу решил, что $\prod \limits_{i=0}^{k-1}a= a^{k-1}$ и не понял, что это ложное утверждение. Не сразу понял, что раз у нас произведение $k-1$ элементов включая $0$ элемент, то итого у нас $k$ элементов. :) Спасибо. :)

iifat в сообщении #989606 писал(а):

Gts в сообщении #989187 писал(а):

А вот если так

Ну, по мне так это слишком нестрого, хотя и не уверен. Таки скобочки, имхо, раскройте.

$p_n = a_n$
$p_{n-1} = a_nx + a_{n-1}$
$p_{n-2} = a_nx^2 + a_{n-1}x + a_{n-2}$
$p_{n-k} = a_nx^k + a_{n-1}x^{k-1} + a_{n-2}x^{k-2} + \dots + a_{n-k}$

Заменим $n-k$ на $i$. В тоже время $k=n-i$.

$p_i = a_nx^{n-i} + a_{n-1}x^{n-i-1} + a_{n-2}x^{n-i-2} + \dots + a_i$

$ p_i = \sum \limits_{k=0}^{i} a_{n-k} x^{n-i-k}$
Что скажете?

[iifat]

Так нормально.

[Gts]

iifat, большое спасибо за помощь. :)
У меня к Вам последний вопрос: где вы прочитали/узнали о таком замечательном способе построения инварианта?

[iifat]

Да уж и не вспомню. У Дийкстры есть где-то в книжке, попробую вспомнить, в какой именно.

[iifat]

Вот, нашёл.

[Gts]

Ещё раз большое спасибо!