Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
2 beğenilme 0 beğenilmeme
2.7k kez görüntülendi
Degeri 4 milyonu gecmeyen cift fibbonacci sayilarinin toplamini bulun
Veri Bilimi kategorisinde (1.6k puan) tarafından 
tarafından düzenlendi | 2.7k kez görüntülendi

5 Cevaplar

3 beğenilme 0 beğenilmeme
Çift olanların $f_{3n}$ olduğunu gördükten sonra gerisi kolay.

(1) fibonacciye kaşılık gelen kokleri biliyoruz.
(2) bunlarin kuplerini alip minimal polinomuna bakarsak $g_n := f_{3n}$ için $g_1=2$, $g_2=8$ ve $n\ge 1$ için $$g_{n+2}=4g_{n+1}+g_n$$ eşitliini elde ederiz.
(3) Aslinda bu dizinin nasil olduğu değil karşılık gelen kökleri önemli.

Bu kökleri bulunca
(a) Genel formül ile üst sınıra en yakın $n$ değeri bulunur
(b) kuvvet toplamı (geometrik seri) ile istenen toplam bulunur.
(25.5k puan) tarafından 
Bunun isleri hizlandiracagini dusunuyorum. Bilgisayarci bir arkadasimiz kod olarak yazip icerigi genisletirse sevinirim.
Koklerden gelen bir hata payi olacaksa bunu moduler aritmetik ile kurtarmak da mumkun.
Ust $n$ degerini bulurken bir terimin boyu $1$den kucuk oldugundan kuvveti dramatik bir bicimde azalacak. Bu nedenle sadece bir kokun logartimasini kullanmak da hizli bir ters alma olabilir.
hocam direkt n-inci fibonacci terimini veren bir formülümüz olsaydı daha hızlı hesaplanırdı sanırım.
Direkt veren bir formul var.
bu yontemin gercekten en estetik cozum ve en verimli calisan kod olacagini dusunuyorum. Aranan cevap bence bu. Biraz daha acik yazip mumkunse kod ornegi paylasabilir misiniz ? Boylece hem zamanini olcebiliriz hem de elimizde bir cozum daha bulunur.
direk veren formul maalesef bilgisayardaki reel sayi gosterimi nedeni ile hatalara sebep oluyor.
ikinci ve ucuncu yorumum bu hatalari duzeltmek adina...

Bir $n$ degeri icin bilgisayar $\lceil(2+\sqrt5)^n\rceil$ hesaplamasinda ne kadar hata yapabilir? Gelen ic ifade de $a+b\sqrt 5$ formunda.

Hatayi azaltmak istersek diret $a$ ve $b$ icin tam sayili  formulu de yazabiliriz.
Aradaki yorumlarinizi okumadan atlamisim, haklisiniz.
Ben pek programlardan anlamadigimdan kod paylasmadim.
Yakinda tekrardan python ogrenmeye baslarim. Elime alip nerelerde nasil hatalar yapiyor diye bakma firsatim olmadi.
2 beğenilme 0 beğenilmeme

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

 

(1.6k puan) tarafından 
tarafından düzenlendi
Python'da yield() ne işe yarar?
1 beğenilme 0 beğenilmeme
def hizliFib(n, memo={}):
    '''n'nin negatif olmayan bir tam sayi oldugunu varsayar
    memo yalnizca özyineleme de kullanilir
    n'inci Fibonacci sayisini verir'''
    if n == 0 or n == 1:
        return 1
    # yinelemeler cok vakit kaybettiribilir, ayni
    # hesabi tekrar tekrar yapmamak icin hesapladik mi diye kontrol edecegiz
    # (memoization)
    try:
        return memo[n]
    # baktik ki hesaplamamisiz
    except KeyError:
        # hesaplayalim o halde
        result = hizliFib(n-1,memo) + hizliFib(n-2, memo)
        # bir daha ihtiyacimiz oldugunda kullanmak icin saklayalim
        memo[n] = result
        return result

 

(3.7k puan) tarafından 
tarafından düzenlendi

kodunuzu calistiramadim. Galiba fastFib fonksiyon cagirisini hizliFib cagirisi ile degistirmeniz gerekiyor.

Jupyter notebookumdan copy paste edip açıklamaları türkçeye çevirmiştim ama dediğin yeri atlamışım. Teşekkür ederim.

kodunuz verilen cevaplar arasinda en hizli calisan oldu benim bilgisayarimda.

try : .. except: ...  blogunu if n in memo.keys(): ... else : ... degistirmenizi oneririm. Hem daha okunur, hem de try: sonucunda gelen beklenmedik yan etkilerden yok.

1 beğenilme 0 beğenilmeme
Soruya gir çık aklıma daha kolay bir yol geldi.

(1) İstenen $f_{3}+f_{6}+f_{9}+\cdots+f_{3n}$ toplamı.
(2) $f_1+f_2=f_3$, $f_4+f_5=f_6$ olduğundan istenen $f_{1}+f_2+\cdots+f_{3n}$ toplamının yarısı olur.
(3) Bu toplam da $f_{3n+2}-1$ değerine eşit.
(25.5k puan) tarafından 
Guzel cozum. Istenen sonuc $\dfrac{f_{3n+2}-1}{2}$ olur  ve $n=11$ icin ($11.$ terim cift ve $4$ milyondan kucuk) dogru sonucu veriyor.
Soru: Verilen ust sinir icin $n$ nasil bulunacak?
Karakteristik polinomun koklerinin $1$den buyuk olani alip logaritma ile hesaplayabiliriz.
Wolframa floor[log_{2+sqrt5}(sqrt5(4*10^6))] yazinca 11 degerini verdi.
Ayrica (ceil(((1+sqrt5)/2)^35/sqrt5)-1)/2 degeri de istenen sonucu veriyor.
0 beğenilme 0 beğenilmeme
(fib = Fibonacci[Range@40];
  Pick[fib, (EvenQ[#] && # < 4000000 &) /@ fib] // 
   Total) // AbsoluteTiming

{0.0001402, 4613732}


Veya her 3. terim cift oldugundan

(fib = Fibonacci[Range[3, 39, 3]];
  Pick[fib, # < 4000000 & /@ fib] // Total) // AbsoluteTiming

{0.0000758, 4613732}

 

(2.9k puan) tarafından 
20,260 soru
21,785 cevap
73,460 yorum
2,352,372 kullanıcı