Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Числа Фибоначчи

Автор: politex 22.11.2004, 13:44

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

Автор: maxim1000 22.11.2004, 14:21

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

Автор: politex 22.11.2004, 14:55

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.

Автор: maxim1000 22.11.2004, 15:09

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

теперь о сумме:
для вычисления суммы в состояние системы можно ввести еще один параметр - сумма smile

(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 использовал для понятности, должен поддерживать операцию умножения и конструктор копии

Автор: podval 22.11.2004, 20:54

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

Автор: MBo 23.11.2004, 08: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

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

Автор: maxim1000 23.11.2004, 11:57

Цитата(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-й степени)