Как можно найти n-элемент и S(n)-сумму чисел Фибоначчи

а в чем проблема?
если совсем просто, то в виде рекурсивной функции, при вычислении накапливать
или вопрос в оптимизации?

2 maxim1000

Da, vopros v optimizatsii. U nas prosto pamyat i vremiya ogranichena. Time limit: 0,2 s Memory limit: 600 Kb. Nash kod takoy:

Код

program p123_3; {$APPTYPE CONSOLE} uses  SysUtils; var k,s,i,f1,f2:integer; begin readln(k); s:=0; f1:=1; f2:=1; s:=2; for i:=3 to k do if odd(i) then f1:=f1+f2 else f2:=f1+f2; if odd(k) then s:=2*f1+f2-1 else s:=2*f2+f1-1; Writeln(s); readln; end.

есть один интересный подход:
рассмотрим числа Фибоначчи, как состояние динамической дискретной системы
x - последнее число
y - предпоследнее
(x,y)->(x+y,x) данное преобразование линейное, а значит, описывается матрицей (2*2)
(1 1)
(0 1)
первоначальный вектор (1,1)
для получения n-го числа Фибоначчи нуно возвести матрицу в n-ю степень и подействовать ней на (1,1) (одна из координат и будет ответом)
возведение матрицы в n-ю степень занимает порядка log n операций

теперь о сумме:
для вычисления суммы в состояние системы можно ввести еще один параметр - сумма
(x,y,s)->(x+y,x,s+x)
в этому случае матрица получается 3*3:
(1 1 0)
(0 1 0)
(1 0 1)
теперь просто надо возвести в степень ее...
Добавлено @ 15:13
ну и немного о возведении матрицы в степень n за время порядка log n

Код

matrix MatrixPower(matrix A,int n) {  if(n%2==0)    return MatrixPower(A*A,n/2);  else    return A*MatrixPower(A*A,n/2); }

тип matrix использовал для понятности, должен поддерживать операцию умножения и конструктор копии

maxim1000
Дай координаты этого подхода. Где взял?

Если не возбраняется вещественная арифметика, то
s5=Sqrt(5)
F(n)=((1+s5)^n-(1-s5)^n)/(2^n*s5)
или
F(n)=Round(Fi^n/s5)
где Fi - золотое сечение, (1+s5)/2


Что же касается суммы, то
S(n)=F(n+2)-1

Цитата(podval @ 22.11.2004, 19:54)

maxim1000 Дай координаты этого подхода. Где взял?

когда-то в лицее рассказывали в виде таких формул:

Цитата(MBo @ 23.11.2004, 07:28)

Если не возбраняется вещественная арифметика, то s5=Sqrt(5) F(n)=((1+s5)^n-(1-s5)^n)/(2^n*s5) или F(n)=Round(Fi^n/s5) где Fi - золотое сечение, (1+s5)/2

а когда я вспомнил числа Фибоначчи после того, как изучил линейную алгебру и теорию управления динамическими системами, придумал такой подход к этим формулам (там просто надо расписать матрицу в n-й степени)