Изменения

Перейти к: навигация, поиск

Карлукова M32342 временная статья

31 байт добавлено, 01:53, 1 июня 2020
Нет описания правки
Сложим все равенства и получим
:<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + \\ + (a_{k - 1} - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^k c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex>
Для всех <tex>n \geqslant k</tex> выполняется равенство <tex>a_n = \sum\limits_{i = 1}^k c_i \cdot a_{n - i}</tex>, поэтому в правой части все коэффициенты при степенях, начиная с <tex>k</tex>, обнулятся, а равенство будет выглядеть следующим образом:
:<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_{k - 1} - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.
Заметим, что второй множитель в левой части равен в точности <tex>Q(t)</tex>, а степень правой части не превосходит <tex>k-1</tex>. Получили требуемое построение.
'''Замечание.''' Многочлен <tex>P(t)</tex> можно найти по формуле <tex>A(t) \cdot Q(t)</tex> как числитель получившейся дроби. К результату можно применить взятие его по модулю <tex>t^k</tex>. Это действие не испортит многочлен, так как его степень строго меньше <tex>k</tex>. При этом мы сократим число операций при вычислении <tex>P(t)</tex>, поскольку достаточно найти только <tex>k</tex> первых членов результирующего ряда, а для этого можно обойтись только первыми <tex>k</tex> слагаемыми степенных рядов, соответствующих производящим функциям производящей функции <tex>A(t)</tex> и столькими же для <tex>Q(t)</tex>.
<!-------Для того чтобы сократить число операций, все действия могут быть выполнены по модулю <tex>t^k</tex>.-------->
693
правки

Навигация