Последние 40 цифр числа Фибоначчи - Форум «Всё о Паскале»

Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи

Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

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

Опции

Гость	14.03.2006 21:30 Сообщение #1
Гость	Вот недавно встертил интересную задачку: Нужно вывести последние 40 цифр n-ого числа фибонначи, где n<10^18, вот и все

Ответов

Lapp	17.03.2006 6:59 Сообщение #2
Уникум Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: 159	Altair, ты гений! Про формулу Бине я однозначно забыл [жжет лист бумаги, собирает пепел и посыпает голову]... А она ведь дает точное значение до последнего знака! Но с нахрапа все равно не получается взять. Там фигурирует n-ая степень выражения, содержащего Sqrt(5). Если бы был просто корень из пяти, без слагаемых - то просто поделил n на два, потом дихотомией вычислить 5^(n/2). При этом n должно быть четным, но это ерунда - нечетное ЧФ вычислим по двум боковым четным. Вычислять в лоб (брать корень, прибавлять 1, делить пополам и возводить в степень дихотомическим умножением) нельзя, т.к. вычислять корень придется с точностью до 10^18 знаков.. Думаем.. [скрип мозгов за кадром] -------------------- я - ветер, я северный холодный ветер я час расставанья, я год возвращенья домой