Yazılım | Fibonacci Sorusu
-
Selamlar, şöyle bir soruyu nasıl çözmek lazım? Ben dart ile uğraşıyorum da yapamadım. Mantığı anlatarak çözüm yapsanız tatlı olur. Teşekkürler.
Soru : Soru Link
Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
#Dart Dilinde Cevap:
int fib(int sayi) {if (sayi <= 2) {return sayi;} else {return fib(sayi - 1) + fib(sayi - 2);}}
int sayi=0;int toplam=0;while (fib(sayi) < 4000000) {if(toplam>=4000000){break;}else if(fib(sayi)%2==0){toplam+=fib(sayi);}sayi++;}
print("TOPLAM : $toplam");Şöyle bir de video bırakayım sonradan gelen için : -
Hocam verilen n değeri için fibonacci(n) değerini hesaplayan bi metod yazarak başlayabilirsin.
fib(1) = 1
fib(2) = 2
fib(5) = 8
fib(10) = 89... gibi.
Bu arada Fibonacci ve Factorial hesabı yapma, recursive fonksiyonları anlatırken bolca kullanılan güzel iki örnektir. Dilersen yazacağın metodu recursive yazabilirsin yani.
Sonra 1'den itibaren, n'i 1 artıra artıra, fib(n) 4.000.000 değerinden küçük olduğu sürece devam eden bir döngü oluşturup,
Döngü içinde de fib(n) tek sayı mı çift sayı mı diye kontrol edersin. Eğer sayı çift ise en başta 0 olarak tanımladığın toplam değerine eklersin bu sayıyı.
Döngü bittikten sonra elindeki toplam değeri de aradığın yanıt oluyor zaten.
Tabii bu yöntemlerden sadece bir tanesi. Daha birçok farklı şekilde de yapılabilir. Her yiğidin yoğurt yiyişi farklı sonuçta.
Yukarıda anlattığım yöntemi Java ile yazmıştım ben daha önce, örnek olsun bakarım dersen linki bırakayım buraya da:
-
buradaki formulle sum in 4 milyondan kucuk oldugu surece loopa sokarak ve ilgili formulu kullanarak bulabilirsin diye dusunuyorum
-
java yazdim sana.
burayi kullanarak karaladim biseyler oyle; https://www.jdoodle.com/online-java-compiler/
public class MyClass {
public static void main(String args[]) {
int[] fiboArray = new int[10000];
fiboArray[0]=1;
fiboArray[1]=2;
for (int i=1; fiboArray[i-1]<4000000;i++)
{
fiboArray[i+1] = fiboArray[i]+fiboArray[i-1];
System.out.println("Fibo Num = " + fiboArray[i-1]);
}
int total=0;
for (int j=0;j<fiboArray.length;j++)
{
if(fiboArray[j]!=0){
if (fiboArray[j]%2==0) {
System.out.println("Adding to sum; " + fiboArray[j]);
total=total+fiboArray[j];
}
}
}
System.out.println("Toplaminiz: " + total);
}
}public class MyClass { public static void main(String args[]) { int[] fiboArray = new int[10000]; fiboArray[0]=1; fiboArray[1]=2; for (int i=1; fiboArray[i-1]<4000000;i++) { fiboArray[i+1] = fiboArray[i]+fiboArray[i-1]; System.out.println("Fibo Num = " + fiboArray[i-1]); } int total=0; for (int j=0;j<fiboArray.length;j++) { if(fiboArray[j]!=0){ if (fiboArray[j]%2==0) { System.out.println("Adding to sum; " + fiboArray[j]); total=total+fiboArray[j]; } } } System.out.println("Toplaminiz: " + total); } }
-
project euler akar diyorsun :)
-
neyse.
@JPriest anlatmismis zaten, aynen o sekilde.
ilk once fibolari hesapliyorsun, her seferinde 4 milyondan buyukmu diye check edip, degilse arraye attim.
sonra arrayi loop edip, 2ye bolunebiliyorsa (cift) ilk basta sifir atadigim total degerine ekliyorum.
loop bitince zaten totaldaki deger senin istedigin deger oluyor.
-
bu konuyu çok sevdim ben. ^^`
-
bakıyorum hocular teşekkürler
-
Recursive yapabilrsin ama daha yavaş çalışır, fibonacci hesaplarken en hızlı çözüm (senrayoya göre değişebilir) iteratif çözmektir. Recursive yapacaksan da daha önce hesapladığın değerleri tutup kullanmak daha efektif olur. Ne demek istiyorum?
Döngüye 1'den başladın F_1, F_2 diye tek tek hesaplatacaksın.fib(1) : F_1 = 1
fib(2) : F_2 = 2
fib(3) = fib(2) + fib(1) : 1 + 2 = 3
fib(4) = fib(3) + fib(2) = (fib(2) + fib(1)) + fib(2)Daha 4.yü hesaplarken 2.yi 2 kere boş yere çağırdın halbuki önceden hesaplamıştık o değeri kullanabilrsin (bu şekilde dinamik programlamada önceden hesaplanan yöntemleri kullanarak sonraki değerleri tekrar hesaplamaya gerek kalmadan kullanmaya memoziation denir.
Tabi bu yöntemde memory kullanımı artıyor haliyle. (İteratife göre)
Düz recursion ile çözümün python kodu:
def fib(n): if n == 1 or n == 2: return n else: return fib(n-1) + fib(n-2) sum, a, n = 0, 1, 1 while a <= 4000000: if a % 2 == 0: sum += a a = fib(n) n += 1 print(sum)
Memoization ile şöyle yapabilirsin:
fib_table = {1:1, 2:2} def fib2(n): if n in fib_table: return fib_table[n] else: fib_table[n] = fib2(n-1) + fib2(n-2) return fib_table[n] sum, a, n = 0, 1, 1 while a <= 4000000: if a % 2 == 0: sum += a a = fib2(n) n += 1 print(sum)
Iteratif yöntemele gelirsek çok daha sade, hızlı ve az memory kullanarak halledebilirsin.
Python kodu şöyle:
sum, a, b = 0, 1, 2 while a <= 4000000: if a % 2 == 0: sum += a a , b = b, a+b print(sum)
Bir de bu kodlar için bir benchmark yaptım.
Düz recursive olan 3.59 saniye de hesapladı. Memoization kullanan 65 mikrosaniyede iteratif olansa 29 mikrosaniyede hesapladı.
4 milyonu 40 milyon yapınca da sonuçlar şöyle:
Recursive: 48sn Memoization: 96 mikrosaniye Iteratif: 38 mikrosaniye
Sadece iteratif ve memoizationı biraz daha zorlarsak:
(4 milyar) Memoization: 60-100 mikrosaniye Iteratif: 20-40 mikrosaniye(40 trilyon) Memoization: ~100 mikrosaniye Iteratif: ~50 mikrosaniye
fibonacci kendinden önceki iki sayının toplamı gırh yapar yazilim soru algoritma