Bu soruyu acikcasi biraz kaba kuvvet kullanarak cozdum. Ilk once fibonacci sayilarini yaratan bir fonksiyon olusturdum. Fibonacci sayilarini ureten naiv bir fonksiyon soyle gorunurdu
def fib(n):
if n==0:
return 1
elif n==1:
return 1
elif n>1:
return fib(n-1)+fib(n-2)
else:
print("HATA negatif fibonacci sayilari tanimli degil bu programda")
return -1
Ancak bu ozyinelemeli (recursive) program, kuyruk ozyinelemeli (tail recursive) degil. Programin ihtiyaci olan hafiza miktari her kendini yeniden cagirisinda artiyor. Bunu teorik olarak fibonacci fonksiyonunu kuyruk ozyinelemeli olarak yazip cozebiliriz.
def fib(n, a = 1, b = 1):
if n == 0:
return a
if n == 1:
return b
return fib(n - 1, b, a + b);
Dikkat ederseniz bu kod parcasinda en son cagirdigim fonksiyon, fib fonksiyonu. Bir onceki kod parcasinda en son cagirdigim fonksyion, + fonksiyonu idi. Bu bizi her ne kadar teorik olarak hafiza kullaniminin ussel olarak artmasindan kurtarsa da, Python kuyruk ozyineleme optimizasyonunu garanti etmiyor. O yuzden bunu elle yapmamiz gerekiyor
def fib(n):
a ,b = 0,1
while(n >= 0 ):
n,a,b=n-1,b,a+b
return a
Bize aslinda tek bir fibonacci sayisi gerekmiyor, 4 milyondan kucuk olan butun fibonacci sayilarini istiyoruz. Burada python generatorler lerini kullanabiliriz.
def fib(n): ## n den kucuk fibonacci sayilarini hesaplayan fonksiyon
i,j=0,1 ## fib(0) = fib(1) = 1
while(i<n):
i,j = j,i+j ## fib(n) = fib(n-1) + fib(n-2)
yield(i) ## yield sayesinde generator yaratiyoruz
Bundan sonrasi cift olanlari ayirmak ve toplamaktan ibaret.
def hesapla():
fibs = fib(4e6) ## 4 milyondan kucuk fibonacci sayilarini yaratan bir generator olustur
#Burayi da kullanabilirsiniz ama asagidaki daha verimli
#cift_fibs = filter(lambda x : x%2==0,fibs) ## cift fibonacci sayilarini filtrele
#toplam = sum(cift_fibs) ## sonuc
toplam = sum(i for i in fibs if i%2==0)
return toplam
Butun kodlar ve olcum programi.
def fib(n): ## n den kucuk fibonacci sayilarini hesaplayan fonksiyon
i,j=0,1 ## fib(0) = fib(1) = 1
while(i<n):
i,j = j,i+j ## fib(n) = fib(n-1) + fib(n-2)
yield(i) ## yield sayesinde generator yaratiyoruz
def hesapla():
fibs = fib(4e6) ## 4 milyondan kucuk fibonacci sayilarini yaratan bir generator olustur
cift_fibs = filter(lambda x : x%2,fibs) ## cift fibonacci sayilarini filtrele
toplam = sum(cift_fibs) ## sonuc
return toplam
def fib2(n):
a ,b = 0,1
while(n >= 0 ):
n,a,b=n-1,b,a+b
return a
def fib3(n, a = 1, b = 1):
if n == 0:
return a
if n == 1:
return b
return fib3(n - 1, b, a + b);
def fib4(n):
if n==0:
return 1
elif n==1:
return 1
elif n>1:
return fib4(n-1)+fib4(n-2)
else:
print("HATA negatif fibonacci sayilari tanimli degil bu programda")
return -1
if __name__ == '__main__':
import timeit
print("Cevap : ", hesapla() ,
"Zaman : ",timeit.timeit("hesapla()", setup="from __main__ import hesapla",number=10000)
)
print("fib(10946) :",list(fib(10946)),"Zaman : ",
timeit.timeit("list(fib(20))", setup="from __main__ import fib",number=10000))
print("fib2(20) :",fib2(20),
"Zaman : ",timeit.timeit("fib2(20)", setup="from __main__ import fib2",number=10000))
print("fib3 :",fib3(20),
"Zaman : ",timeit.timeit("fib3(20)", setup="from __main__ import fib3",number=10000))
print("fib4(20) :",fib4(20),
"Zaman : ",timeit.timeit("fib4(20)", setup="from __main__ import fib4",number=10000))
Zaman sonuclari :
Cevap : 4613732
Zaman : 0.09922051592729986
fib(20) : [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946]
Zaman : 0.013569902046583593
fib2(20) : 10946
Zaman : 0.0265231590019539
fib3 : 10946
Zaman : 0.04998972895555198
fib4(20) : 10946
Zaman : 42.689910300890915