Здравствуйте! Имеется следующая рекурсивная функция: $$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

изменен 8 Июл '13 17:13

Deleted's gravatar image


126

Следует понимать так, что нужна программа? Тогда это несложно, и не обязательно нужна формула n-го члена.

(6 Июл '13 19:30) Anatoliy

Да, вы правильно понимаете! Просто я не знаю, каким боком подойти к формуле суммы без использования значения n-ого члена, сейчас памяти жрет немерено и времени тратит много, что неудивительно. Буду очень благодарен Вам, если поможете!

(6 Июл '13 19:34) Sevak_Avet
10|600 символов нужно символов осталось
1

Здесь непосредственные вычисления могут потребовать очень много времени. У Вас найдена формула общего члена, и далее можно просуммировать получившиеся геометрические прогрессии. Это даёт общую формулу для суммы первых $%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

10|600 символов нужно символов осталось
1

Попробуйте так: $$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

изменен 6 Июл '13 19:56

Спасибо большое! :) Я вот еще что заметил: если n - четное, то суммой k членов будет f(k+1) - 1, иначе f(k+1)

(6 Июл '13 20:13) Sevak_Avet
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×27

задан
6 Июл '13 19:21

показан
1333 раза

обновлен
7 Июл '13 2:03

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru