|
Вопрос # 3 412/ вопрос открыт / |
|
Здравствуйте, не могли бы вы мне помочь
есть такая задача:
вывести последние восемь цифр n-ого числа фиббоначи, отбрасывая незначащие нули
n вводится с клавы
есть одна проблема
n - до 10^18 степени!
и чтобы расчеты укладывались в сек
пример: n=10
ответ: 89
то есть если просто складывать - то в секунду не уложится!(
подсказывали такой алгоритм:
возвести матрицу
|1 1|
|1 0|
в степень n - и получим матрицу
|что-то Fn |
|Fn что-то|
вот вывести последние 8 цифр числа Fn
можете подсказать, как реализовать так, чтобы в секунду уместились расчеты?
что то не могу догадаться, как так прописать(
алгоритм взял с википедии
здесь самое главное, чтобы расчеты укладывались в секунду!
n от 1 до 10^18
вывести последние 8 чисел n-ого числа фиббоначи!
заранее спасибо!
 |
Вопрос задал: Ruslan (статус: 1-ый класс)
Вопрос отправлен: 17 ноября 2009, 00:04
Состояние вопроса: открыт, ответов: 0.
|
Мини-форум вопроса
Всего сообщений: 2; последнее сообщение — 21 ноября 2009, 00:17; участников в обсуждении: 2.
|
Вадим К (статус: Академик), 17 ноября 2009, 00:33 [#1]:
на той же википедии читаем
Цитата:
Последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом 60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом 300, последние три цифры — с периодом 1500, последние четыре — с периодом 15000, последние пять — с периодом 150000 и т. д.
то есть, если бы надо было узнать только последнюю цифру, то просто заданное число делим на 60 (это быстренько). а для чисел от 0 до 59 задача работает быстро. даже для последних пять задача очень легко решается указанным методом.
Смотря на порядок цифр, подозреваю, что для последних 8 цифр это буде порядка 150000000, что вполне решаемо.
Галочка "подтверждения прочтения" - вселенское зло.
|
|
|
Ruslan (статус: 1-ый класс), 21 ноября 2009, 00:17 [#2]:
program Project1;
{$APPTYPE CONSOLE}
uses
SysUtils;
const p=100000000;
var f0,f1,f2,i,c:longint;
n,lol,k:int64;
input,output:text;
s:string;
begin
assign(input,'input.txt');
reset(input);
assign(output,'output.txt');
rewrite(output);
f0:=0;
f1:=1;
c:=0;
read(input,s);
lol:=1;n:=0;
for i:=length(s) downto 1 do
begin
n:=n+(ord(s[i])-ord('0'))*lol;
lol:=lol*10;
end;
k:=n mod 150000000;
// это улучшенный алгоритм нахождения k-ого числа фибоначчи
repeat
f2:= (f0+f1) mod p;
f0:=f1;
f1:=f2;
c:=c+1;
until (c>=k) or (f0=0) and (f1=1);
if c<k then
begin
k:=k mod c;
for i:=1 to k do
begin
f2:=(f0+f1) mod p;
f0:=f1;
f1:=f2;
end;
end;
write(output,f1);
close(input);
close(output);
по времени не проходит
как еще увеличить скорость нахождения 150000000 числа фибоначчи - и вообще правильный ли алгоритм, можете сказать?
|
Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.
|
