Biasanya algoritma yang digunakan sbb :
------------------------------------------------------------------------------
fungsi fibo(masukan N{ berjenis long/longint} ) keluaran {berjenis long/longint}
mulai
jika {if} (N=1) maka fibo=0
tetapi jika {else if} (N=2) maka fibo=1
selain itu {else} maka fibo=fibo(N-1)+fibo(N-2);
selesai
------------------------------------------------------------------------------
Deret Fibonacci sbb : 0 1 1 2 3 5 8 13 21 34 55 ... dst
untuk N>2 jika dimisalkan
a=F(N+1)/F(N) ................. //persamaan 1
sesuai dengan rumus fibonacci : F(N+1)=F((N+1)-1)+F((N+1)-2)
maka F(N+1)=F(N)+F(N-1), sehingga didapat dari persamaan 1
a=( F(N)+F(N-1) )/F(N) ....//persamaan 2
jika pers.1 dan pers.2 dihubungkan maka
( F(N)+F(N-1) )/F(N)=F(N+1)/F(N).....//pers.3
jika ditelusuri lagi F(N)/F(N-1) nilai nya akan mendekati F(N+1)/F(N)
dapat dibuktikan dengan
utk N=5, maka
F(5)/F(5-1) = 3/2 = 1,5
F(5+1)/F(5) = 5/3 = 1,66666....
untuk N=6, maka
F(6)/F(6-1) = 5/3 = 1,666666.....
F(6+1)/F(6) = 8/5 = 1,6
untuk N=8, maka
F(8)/F(8-1) = 13/8 = 1,625
F(8+1)/F(8) = 21/13 = 1,615
dari sedikit pembuktian diatas dapat kita rumuskan
bahwa karena F(N)/F(N-1) nilai nya akan mendekati F(N+1)/F(N)
sehingga rumus pers.3 ( F(N)+F(N-1) )/F(N)=F(N+1)/F(N) dapat diganti,
menjadi
( F(N)+F(N-1) )/F(N)=F(N)/F(N-1)
Jika dimisalkan F(N)=a dan F(N-1)=b , maka
(a+b)/a=a/b
perkalian silang pada persamaan diatas akan menghasilkan
= (a+b)*b=a^2 ..... //pers.4
= ab+b^2=a^2
= a^2 - ab - b^2
misalkan a sbg x , sehingga persamaan menjadi
= x^2 - bx - b^2
dengan menggunakan rumus abc maka didapat
x=( -b±akar(b^2-4ac) )/2a
x=( -(-b)±akar( b^2-4(1)(-b^2) ) )/2(1)
x=( b±akar( b^2+4(b^2) )/2
x=( b±akar( 5(b^2) )/2
x=( b±b*akar( 5 )/2
x= b ((1±akar(5) /2 )
dimisalkan ((1±akar(5) /2 ) sebagai y
maka
x=by
lalu kembalikan x menjadi a
a=by
subtitusikan a ke pers.4
(a+b)*b=a^2
(by + b)*b=(by)^2
(b^2)(y+1)=(b^2)(y^2)
y+1=y^2
y^2 - y - 1=0
maka didapat dengan rumus abc y=((1±akar(5) /2 )
bilangan inilah yang sering disebut sebagai rasio emas atau golden ratio.
jika dihitung secara pembagian biasa ((1+akar(5) /2 ) = 1,6180339...
Lalu apa hubungan nya dengan Algoritma Fibonacci ???
Ya, saya akan menjelaskan sebuah metode baru dalam menemukan bilangan fibonacci ke-N dimana N>2 tanpa harus menggunakan cara lama anda F(N)=F(N-1)+F(N-2)
Dari pembuktian diatas nilai bilangan fibonacci memiliki rasio sebesar rasio emas (1,618...)
Untuk menemukan bilangan ke-N dari sebuah bilangan Fibonacci dapat menggunakan F(N+1)=F(N)*[konstanta rasio emas] , dimana hasil dari F(N+1) dibulatkan ke bilangan terdekat.
misalkan :
N=4, maka F(4)=F(4-1)*1,618=1,6 (jika dibulatkan sama dengan 2)
N=5, maka F(5)=F(5-1)*1,618=3,2 (jika dibulatkan sama dengan 3)
N=7, maka F(7)=F(7-1)*1,618=8,0 (jika dibulatkan sama dengan 8)
N=10, maka F(10)=F(10-1)*1,618=33,9 (jika dibulatkan sama dengan 34)
maka dari sedikit pembuktian diatas dapat dibuat algoritma sebagai berikut :
------------------------------------------------------------------------------------------------------
fungsi bulat(masukan N {berjenis float/real} ) keluaran {berjenis integer} // fungsi ini untuk membulatkan sebuah bilangan pecahan ke bilangan terdekat nya
fungsi fibo(masukan M,N,R{integer}) keluaran {integer}
deklarasi variabel lokal
X {float/real}
mulai
jika (N=1) maka fibo=0
tetapi jika (N=2) maka fibo=1
selain itu
X=M*y;
jika N=(R+2) maka fibo=M
selain itu fibo=fibo(bulat(X),N,R+1);
selesai
konstanta y=1,618
deklarasi variabel global
N {integer}
program utama
masukan(N);
keluaran(fibo(1,N,0));
selesai
------------------------------------------------------------------------------------------------------
berikut contoh algoritmanya (Pascal) http://ideone.com/TMltAX
Credit : Rio Ch R
Tidak ada komentar:
Posting Komentar