Patrzysz na posty znalezione dla hasła: Liczby fibonaciego





Temat: Liczby Fibonacciego

Użytkownik Amon <mic@friko5.onet.plw wiadomości do grup dyskusyjnych
napisał:385672ee.11330@news.polsl.gliwice.pl...

On Mon, 13 Dec 1999 15:13:22 GMT, "Wojciech Kluba"
<woj@ernie.icslab.agh.edu.plwrote:

| A swoją drogą, jaki znacie najszybszy algorytm na obliczenie n-tej liczy
| Fibonacciego?

| Wojtek

Dynamicznie mniej wiecej tak:

Var Fib : Array[0..100] of Comp;
      n   : byte;

begin
  Fib[0] := 1;
  Fib[1] := 1;
  For n := 2 to 100 do Fib[n] := Fib[n-1] + Fib[n-2];
end;

Dziala chyba w czasie liniowym;


Najszybszy to jest taki:
po prostu skorzystaj ze wzoru na obliczenie n-tej liczby Fibonaciego:

F(n)=(O1^n-O2^n)/sqrt(5)

gdzie O1=(1+sqrt(5))/2
         O2=(1-sqrt(5))/2

O1 i O2 sa literkami grackimi, ale nie znalazlem takowych na klawiaturze....
a zreszta nawet nie wiem jak je nazwac. O1 wyglada ja symbol zbioru pustego,
a O2 ja symbol zbioru pustego z "trojkatnym daszkiem".

Wzor ten mozna znalezc w "Wprowadzenie do algorytmow" s 60.

Predkosc zalezy od implementacji potegowania i pierwiastkowania, ale dla
duzych n powinno sie oplacic.

Zobacz więcej odpowiedzi



Temat: Liczby Fibonacciego
W dniu Tue, 14 Dec 1999 21:30:10 +0100,
Milo<milo@priv1.onet.pl
wyprodukował następujący tekst:


Najszybszy to jest taki:
po prostu skorzystaj ze wzoru na obliczenie n-tej liczby Fibonaciego:

F(n)=(O1^n-O2^n)/sqrt(5)

gdzie O1=(1+sqrt(5))/2
        O2=(1-sqrt(5))/2


Było już wczoraj albo przedwczoraj.


O1 i O2 sa literkami grackimi, ale nie znalazlem takowych na klawiaturze....
a zreszta nawet nie wiem jak je nazwac. O1 wyglada ja symbol zbioru pustego,
a O2 ja symbol zbioru pustego z "trojkatnym daszkiem".


A jaka to różnica jak nazwiesz zmienne ? Czy jeżeli nazywałyby się one
dupa1 i dupa2 to wynik by się zmienił ?


Predkosc zalezy od implementacji potegowania i pierwiastkowania, ale dla
duzych n powinno sie oplacic.


Musi się opłacić ;)

Pozdrawiam
PS: Cytaty się przycina.

Zobacz więcej odpowiedzi



Temat: fajne zadanko
No to automatyczny algorytm łopatologiczny
/poszukaj czegoś bardzoej wyrafinowanego mnie się nie chce /
(liczby w systemie Fib będe zapisywał z _f  w dziesiątkowym _d )
z liczby a_f robimy a_d , z b_f robimy b_d dodajemy a_d + b_d =c_d
z c_d robimy liczbę c_f

Jak zamienić z a_f na a_d no bardzo prosto
Mamy System Fib. oparty na  :
f0=0
f1=1
f2=1
f3=2  ....
mamy na przykład
101001001000_f  = 0*0+0*1+0*1+1*2+.......+1*89 =133_d
10010100_f  = 0*0+1*0+1*1+....+1*13= 17_d
ok ??
teraz 13_d +133_d = 150_d
no i zamieniamy 150_d na system _f
szukamy liczby fibonaciego takiej aby była jak największa ale nie większa
niż nasza liczba  **
dla 150 mamy największą 144  int(150/144) =1
Mod(150,144) =6  (reszta z dzielenia 150 przez 144 )
dla 6  mamy spełniającą warunek **liczbę  5
liczymy Int(6/5) = 1
Mod(6,5) =1
dla 1 mamy  1
Int(1/1) =1
Mod(1/1) =0
no i prosto zapisujemy naszą nowo otrzymaną liczbę jako bagatela :D
1000000100100_f

tara ..


Swoja droga fajne zadanko jak na II kolokwium z programowania na I
semestrze
infy ....


Swoją drogą to powinieneś umieć robić takie rzeczy na drugim sprawdzianie na
I-ym semestrze ale liceum ....

Zobacz więcej odpowiedzi

Cytat


I uboga matka ma złote serce. Regulski Antoni
Factum est - stało się.
I niepotrzebni są potrzebni. Stanisław Jerzy Lec (pierw. de Tusch - Letz, 1909-1966)
Dobro i Zło mają to samo oblicze, wszystko zależy jedynie od momentu, w którym staną na drodze człowieka. P. Coelho
Finis coronat opus - koniec wieńczy dzieło, dzieło koronuje cel. Owidiusz

\