Последние 40 цифр числа Фибоначчи, (Олимпиадная задача) Опции

[Гость]

Вот недавно встертил интересную задачку:
Нужно вывести последние 40 цифр n-ого числа фибонначи,
где n<10^18, вот и все

[klem4]

Гость , я думаю вам поможет FAQ : Длинная арифметика, числа > LongInt

Сообщение отредактировано: klem4 - 15.03.2006 13:44

[Lapp]

я думаю вам поможет Длинная арифметика

klem4, тут дело не в этом. Или не совсем в этом. Я уже второй день думаю над этой задачей..
Первое поползновение - прикинуть количество операций для расчета 10^18-го числа Фибоначи. Собственно, тут и прикидывать не надо. Положим, что на сложение двух предыдущих уходит один цикл (что явно неверно для длинной арифметики, но это есть оценка снизу). Далее, берем машину, работающую на 3 ГГц. В час она выполнит 10^9*3*3600 сложений, что приблизительно есть 10^13. Получается, что нужно 10^5 часов. Будем считать, что в году 10000 часов (приблизительно). И получится, что на расчеты нам потребуется 10 лет.. А на длинную арифметику нужно как минимум десятку накинуть! Сто лет..
Но самое интересное не в этом. На хранение одного только последнего числа уйдет количесво памяти, сравнимое с произведенным на данный момент на всей Земле..

Конечно, можно считать только последние 40 знаков, тогда вопрос с памятью отпадает, но вопрос с временем остается.. Я долго думал, и придумал, что должна быть периодичность в младших разрядах. Стал вычислять - и действительно ее обнаружил. Но только это не решает проблемы, поскольку период растет медленно.. Будем думать дальше!

Разделено в отдельную тему, т.к. в ПЕРВОМ ЖЕ ПОСТЕ прикрепленной темы русским языком написано:

Внимание!
В этой теме публикуем только сами задачи и их решения... Обсуждения - в отдельных темах!!!

Сообщение отредактировано: volvo - 16.03.2006 13:40