|
Здравствуйте! Имеется следующая рекурсивная функция: $$F(1) = F(2) = 1;$$ $$F(n) = F(n-1) + 2*F(n-2);$$ Мне нужно найти сумму k членов последовательности по модулю m, $%1 <= k <= 1-000-000-000$% Получил формулу n-ого члена данной последовательности (без рекурсии), вот она: $$F(n) = (1/3) * (-(-1)^n + 2^n);$$ задан 6 Июл '13 19:21 
Sevak_Avet |
|
Здесь непосредственные вычисления могут потребовать очень много времени. У Вас найдена формула общего члена, и далее можно просуммировать получившиеся геометрические прогрессии. Это даёт общую формулу для суммы первых $%k$% членов. Она оказывается равна $%(2^{k+1}-1)/3$% при нечётных $%k$% и $%(2^{k+1}-2)/3$% при чётных $%k$%. Поэтому достаточно найти значение $%2^{k+1}$% по модулю $%3m$%. Для этого надо использовать алгоритм быстрого возведения в степень. Число операций логарифмически зависит от $%k$%. Последовательно находятся значения $%2^1$%, $%2^2$%, $%2^4$%, $%2^8$%, ..., $%2^{2^s}$% по модулю $%3m$%, где предыдущее число возводится в квадрат, и далее берётся его значение по модулю $%3m$%. А затем, пользуясь двоичным разложением числа $%k+1$%, представляем $%2^{k+1}$% в виде произведения уже найденных чисел. Например, $%2^{13}=2^{8}\cdot2^{4}\cdot2^{1}$%. Число шагов здесь не превосходит $%2s$%, где $%s$% примерно равно $%\log_2(k+1)$%. отвечен 7 Июл '13 2:03 
falcao |
|
Попробуйте так: $$pr1:=1;pr2:=1;S:=pr1+pr2;$$ $$for\quad i:=3\quad to\quad 1000000000\quad do$$ $$begin \quad Fi:=2*pr1+pr2;\quad pr1:=pr2;\quad pr2:=Fi;\quad S:=S+Fi\quad end$$ Тип данных для $%i$% - $%longint$% (в Паскале, да и в других языках программирования есть что-то подобное). отвечен 6 Июл '13 19:56 
Anatoliy Спасибо большое! :) Я вот еще что заметил: если n - четное, то суммой k членов будет f(k+1) - 1, иначе f(k+1)
(6 Июл '13 20:13)
Sevak_Avet
|
Следует понимать так, что нужна программа? Тогда это несложно, и не обязательно нужна формула n-го члена.
Да, вы правильно понимаете! Просто я не знаю, каким боком подойти к формуле суммы без использования значения n-ого члена, сейчас памяти жрет немерено и времени тратит много, что неудивительно. Буду очень благодарен Вам, если поможете!