значение n-го числа - Помощь студентам

Rusl92 · 16.11.2009, 23:25

Здравствуйте, не могли бы вы мне помочь
есть такая задача:
вывести последние восемь цифр n-ого числа фиббоначи, отбрасывая незначащие нули
n вводится с клавы
есть одна проблема
n - до 10^18 степени!

пример: n=10
ответ: 89

то есть если просто складывать - то в секунду не уложится!(

подсказывали такой алгоритм:

возвести матрицу

|1 1|
|1 0|

в степень n - и получим матрицу

|что-то Fn |
|Fn что-то|

вот вывести последние 8 цифр числа Fn
что то с реализацией не получается

можете подсказать, как реализовать, так чтобы в секунду уместились расчеты?
заранее спасибо!
да - этот алгоритм может быть и неверным
его взяли с википедии
здесь самое главное, чтобы расчеты укладывались в секунду!
n от 1 до 10^18
вывести последние 8 чисел n-ого числа фиббоначи!

LeBron · 17.11.2009, 00:06

Быстрое возведение матрицы в степень - вот и весь алгоритм. Есть на алголисте. Советую посмотреть книгу Порубльова "Алгоритмы и программы: решение олимпиадных задач". На страницах 119-121 есть разбор именно этой задачи и куски кода.

16.11.2009, 23:25	#1
Rusl92 Форумчанин Регистрация: 30.03.2008 Сообщений: 392	значение n-го числа Здравствуйте, не могли бы вы мне помочь есть такая задача: вывести последние восемь цифр n-ого числа фиббоначи, отбрасывая незначащие нули n вводится с клавы есть одна проблема n - до 10^18 степени! пример: n=10 ответ: 89 то есть если просто складывать - то в секунду не уложится!( подсказывали такой алгоритм: возвести матрицу \|1 1\| \|1 0\| в степень n - и получим матрицу \|что-то Fn \| \|Fn что-то\| вот вывести последние 8 цифр числа Fn что то с реализацией не получается можете подсказать, как реализовать, так чтобы в секунду уместились расчеты? заранее спасибо! да - этот алгоритм может быть и неверным его взяли с википедии здесь самое главное, чтобы расчеты укладывались в секунду! n от 1 до 10^18 вывести последние 8 чисел n-ого числа фиббоначи! Программирование - это великое искусство... Такое же как например и живопись! Последний раз редактировалось Rusl92; 16.11.2009 в 23:53.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Как числа в двоичном виде вывести в столбик по 4 числа?	Equalizer	Общие вопросы C/C++	11	27.09.2009 14:15
2 столбец для того, чтобы автоматически создавались числа, которые позволяли уравнивать числа в 3 столбце	ppv	Microsoft Office Excel	37	05.08.2009 21:19
Даны натуральные числа m,n. Посчитать сумму m последнего числа n.	лялька	Паскаль, Turbo Pascal, PascalABC.NET	6	25.12.2008 15:22
сумма всех начальных членов ряда, значение которых не меньше заданного числа e, 0<e<1	Арчи	Помощь студентам	2	20.12.2008 12:39
ДАНЫ 4 ЧИСЛА X Y Z W составит программу найти произведение все положительные нечетные числа	Woland-itn	Паскаль, Turbo Pascal, PascalABC.NET	3	23.03.2008 21:49

17.11.2009, 00:06	#2
LeBron Форумчанин Регистрация: 10.10.2009 Сообщений: 680	Быстрое возведение матрицы в степень - вот и весь алгоритм. Есть на алголисте. Советую посмотреть книгу Порубльова "Алгоритмы и программы: решение олимпиадных задач". На страницах 119-121 есть разбор именно этой задачи и куски кода.