Требуется найти n-ое число Фибоначчи. Напомним, что последовательность Фибоначчи это:
F(1) = 1; F(2) = 1; F(n) = F(n - 1) + F(n - 2);

на вход n. при том ,что n до 15000 !!!!!!!

Выделено в отдельную тему

Это сообщение отредактировал(а) podval - 23.11.2005, 09:49

Я с этим как то эксперементировал. Там помоему больше n=100 последовательность вываливается за пределы большого целого типа для 32 разрядных машин. Если хочеш получать результаты, то придется самому создавать тип больших чисел и всю обработку онных. У меня было 32 байтовое число.

модуль длинной арифметики

Код

var a,b,c : TLong;     n,i : integer; begin    readln(n);    a[0] := 1;a[1] := 1;    b[0] := 1;b[1] := 1;    for i := 3 to n do       begin          SumLongTwo(a,b,c);          a := b;          b := c;       end;    WriteLong(c); end.

Если не нужна абсолютная точность, можно воспользоваться тем, что
F(n) ~= (f ^ n) / sqrt(5), где f - золотое сечение (sqrt(5) + 1) / 2.
Уже при n = 10 погрешность порядка 1E-5.

А можно получить и точную формулу -- решив рекуррентное уравнение.
Проблема в том, что эта формула при больших n будет тоже не особо полезна из-за погрешностей вычисления с плавающей точкой.

Вот две функции для нахождения последовательности Фибоначчи. Рекурсивный и иттеративный методы.

Код

public class fibonacci { static int count_rek=0;     public static void main(String[] args){                int a = 5;         //Itterativ         System.out.println("fib("+a+") = " + fibonacci_ittertiv(a));         System.out.println("----------------------------------------------------");         //Rekursiv         System.out.println("fib("+a+") = " + fibonacci_rek(a));         System.out.println("Die rekursive Funktion wurde " + count_rek + " Mal aufgerufen.");     }          private static int fibonacci_ittertiv(int a){         int i = 1;         int tmp;         int currentFib = 0;         int nextFib = 1;         while (i <= a){           tmp = nextFib;           nextFib = currentFib + nextFib;           currentFib = tmp;           System.out.println(i+":"+currentFib);           i = i + 1;         }          return currentFib;     }          private static int fibonacci_rek(int a){         int b;         count_rek++;         if (a==1||a==2) b=1;         else b=fibonacci_rek(a-1)+fibonacci_rek(a-2);         return b;     }      }

Версия на Smalltalk (VisualWorks):

Скрипт:


Оцениваем время выполнения для 15000:


Собственно ответ:
7640011776582151245744177142980959147166721084303255251382115234872074717
9264490871426016093096388778961860503668562301189698257112086502875033583
2236275951846930996522305442389409561481850060899899167484440160791854913
4824461935712300766140140378359865720441140828272612510054914394265157668
8387908341760654278651829512060310974884157942896875812116865830019523236
2055441300681254506848459584325757859029594753256021793859396033936406086
5457811653850832730615222871678275245231470228755068518250884944139446499
7789892753895986214298582558909306505460837638057578780368744903709989242
8339263569175225330071241626840302488305089225238420029493347566924297001
1425949470984453053724030167244682825907638642664942250638542712223965973
9839432383614805694820172574866232061559723239487788160951760319083764253
0809344915801568845212654841516822116932248562554654906609482913615316731
8226015735770205676971833969147138562457847726275194442192930459034858942
3355190585146309690665678349454140970497441835924882049175833968751867467
8840886587776286695431623016857727558213260331499087038340870482272689040
4161363940883069888434885442506756510164008384134069161359636108082166726
2430012984697256875370525740516995468268036286350521915473873166499908476
2516213341322183677288393696852562163743469852720822616501202204312866808
7554514078438969465708203731583305682917508942963701807795508959986989216
8727681579013590537043295720438109411647958677722162162765556297584342652
1660717220427445759936739701874898816386468304843828869558764247957112306
7652211041008987262514431584028601258320604677202217934954414872188793839
7798936332412002028186886271213073561398066415249558922509159228534299843
6211497836421653181660089901309603560410572257601665673656661412345241152
6896288971187068896521326874593253894462268639883878674937905442552530569
2220759779149689216110510904790233167544972560917155417309604422192258857
5436762735890710293112098818325171235620598663507071818753033079875929672
5721795111436550353453041654825111222338795728670886262828267100949774876
8310525128055417698341700920113725032569301572854018821056503490407261855
6639915585008239253365450706754352681533398600403338213001374741929006185
8434162949128855461783892162861568449035775721759688167789359303318836214
6468797238039431409475660343754939422343367207096654001996199322358147830
9452540531816600855216406899354441287453527108123042578816495412997209996
2685872695255445374955210178977827310879569919340750464761199649013934345
6977459936025806172326533990199245505154448532338263605234399877274897171
1914800613090777029523132983883191685658776862698071831299269254766954574
7721622352260191702849679194871662289158082724744652478304992366051143196
1047971091385960246296783372351086692487900115669596735035946592042925720
7953237399490626761158153493168423330531430192075170397757051179216285062
0061243429981704174069142565834834016535906745683175341338563188055501335
7397590091512286832546334018179916215163463922289334031378609655709582547
7453944721106293321669837718294251232944581504809199279572280740303268750
590168124648555537908916558057550666891545917188941557751925573470001

Это сообщение отредактировал(а) nostromo - 7.4.2006, 17:26

Какие сложние решения. Есть же формула(привожу без вывода, ибо он большой.):

Вывод формулы не большой, ну да ладно.

Автор темы, насколько я понял, просил получить все цифры результата и расчет по замкнутом формуле (приведенной Вами)
требует у программного комплекса наличие арифметики с плавающей точкой неограниченной точности.
Эта вещь встречается гораздо реже, чем целочисленная арифметика неограниченной точности, встроенная по умолчанию во многие языки и среды программирования.

Такая арифметика с плавающей точкой есть во многих математических пакетах типа Maple, Mathematica.

Для языков программирования можно посмотреть
здесь.

Расчет по замкнутой формуле, конечно, эффективнее,
но в перспективе работы с более сложными последовательностями, формул в замкнутом виде для которых получить не удается,
рассмотрение реализаций итеративных подходов совсем не лишнее.

Вроде бы золотое сечение это

(корень(5) -1) / 2.

Нет, это:
(1-sqrt(5))/2

отрицательное число?

По определению, два числа находятся в отношении золотого сечения,
если большее относится к меньшему как сумма к большему.
В этом смысле $E := (\sqrt{5} + 1)/ 2$ --- золотое сечение.
Но e := (\sqrt{5} - 1)/ 2 = 1/E.

Ну мы же еще в квадрат возводим.