- 7 Şub 2012
- 5,018
- 22
Merhabalar herkese, ikinci algoritma yarışması ile yeni bir konuda buluşuyoruz.
Algoritma, "bir sorunun çözümü için tasarlanan işlemler" diye tanımlanabilir. Yazılım dünyasında ise algoritma denildiğinde "akış diyagramı" ndan ziyade, veri yapıları üzerinde yapılan işlemler akla gelir. Örneğin graph gezme algoritmaları, tree algoritmaları, sıkıştırma algoritmaları, görüntü işleme, machine learning, kriptoloji algoritmaları vs vs..
Bu liste çok uzun.
Optimizasyon ise, bir algoritmanın daha performanslı (hem hız, hem bellek açısından) çalışmasını sağlama işlemidir.
Bu konumuzda çok hoş olacağını düşündüğüm bir algoritma ve optimizasyon sorusu soracağım, sonrasında ise çözümünü anlatacağım.
Sorumuz "Fibonacci" üzerine.
Öncelikle fibonacci serisi nedir onu bir göstereyim :
0 1 1 2 3 5 8 13 21 34 55 89 144 . . . . . . .
diye devam eden bir seri.
Serinin hesaplanması ise şöyle. Başlangıç sayılarımız = 0 1
Bu sayılardan başlayarak kendisinden bir önceki sayı ile toplayarak devam ediyoruz.
0 1
0 + 1 = 1
0 1 1
1 + 1 = 2
0 1 1 2
1 + 2 = 3
0 1 1 2 3
şeklinde devam ediyor.
Sanırım burası anlaşıldı.
Soru şu şekilde : "Fibonacci(x) denildiğinde en kısa adım sayısı ve en az bellek kullanımı ile bu sayıyı hesaplayan algoritmayı herhangi bir dil ile yazın"
Not :
Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(10) = 55
Not 2 :
Programlama dillerinin hazır fibonacci kütüphanesi ile yapmak yasaktır. Soruda istenen şey algoritmayı sizin implement etmenizdir.
Soru gayet açık. Bu akşam 00:00 da çözümü açıklayacağım.
Katılan arkadaşlara başarılar.
Dipnot : Bu tarz algoritma soruları programlama yeteneğinizin ve algoritma kabiliyetinizin artmasını sağlar, bana ne faydası olacak diye soran kişilere istinaden bunu belirtiyorum.
Çözüm :
Recursive fibonacci hesaplamasında, (dynamic programming genelde recursive metodlar ile işler) memoization denen bir işlem uyguluyoruz. Yani daha önce hesapladığımız adımları tekrar hesaplamak yerine bir bufferdan/cache den getiriyoruz. Normal fibonacci hesaplamasına göre çok daha performanslı.
Normal fibonacci kodu :
Normal fibonacci hesabında recursive yapıda oluşan node lar :
Memoization işlemi yaptıktan sonra hesaplanacak node lar :
Gördüğünüz gibi oldukça performans sağlıyor, işlem sayısını azaltıyor.
Bu konunun amacı dynamic programming ve memoization işlemini anlatmaktı, fibonacci mantığı anlamak için güzel bir örnek, gerçi fibonacci hesaplaması için matematiksel başka yöntemlerde olduğundan biraz eksik bir örnek gibi gözükebilir fakat görselleri ve kodu inceledikten sonra mantığı anlamanız yeterli. Önemli olan "alt parçalara ayrılabilen problemleri" analiz edip çözebilmek.
Algoritma, "bir sorunun çözümü için tasarlanan işlemler" diye tanımlanabilir. Yazılım dünyasında ise algoritma denildiğinde "akış diyagramı" ndan ziyade, veri yapıları üzerinde yapılan işlemler akla gelir. Örneğin graph gezme algoritmaları, tree algoritmaları, sıkıştırma algoritmaları, görüntü işleme, machine learning, kriptoloji algoritmaları vs vs..
Bu liste çok uzun.
Optimizasyon ise, bir algoritmanın daha performanslı (hem hız, hem bellek açısından) çalışmasını sağlama işlemidir.
Bu konumuzda çok hoş olacağını düşündüğüm bir algoritma ve optimizasyon sorusu soracağım, sonrasında ise çözümünü anlatacağım.
Sorumuz "Fibonacci" üzerine.
Öncelikle fibonacci serisi nedir onu bir göstereyim :
0 1 1 2 3 5 8 13 21 34 55 89 144 . . . . . . .
diye devam eden bir seri.
Serinin hesaplanması ise şöyle. Başlangıç sayılarımız = 0 1
Bu sayılardan başlayarak kendisinden bir önceki sayı ile toplayarak devam ediyoruz.
0 1
0 + 1 = 1
0 1 1
1 + 1 = 2
0 1 1 2
1 + 2 = 3
0 1 1 2 3
şeklinde devam ediyor.
Sanırım burası anlaşıldı.
Soru şu şekilde : "Fibonacci(x) denildiğinde en kısa adım sayısı ve en az bellek kullanımı ile bu sayıyı hesaplayan algoritmayı herhangi bir dil ile yazın"
Not :
Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(2) = 1
Fibonacci(3) = 2
Fibonacci(10) = 55
Not 2 :
Programlama dillerinin hazır fibonacci kütüphanesi ile yapmak yasaktır. Soruda istenen şey algoritmayı sizin implement etmenizdir.
Soru gayet açık. Bu akşam 00:00 da çözümü açıklayacağım.
Katılan arkadaşlara başarılar.
Dipnot : Bu tarz algoritma soruları programlama yeteneğinizin ve algoritma kabiliyetinizin artmasını sağlar, bana ne faydası olacak diye soran kişilere istinaden bunu belirtiyorum.
Çözüm :
Kod:
def mfib(n):
cache = [-1 for x in range(n+1)]
cache[0] = 0
cache[1] = 1
return fib(n, cache)
def fib(n, cache):
if cache[n] != -1:
return cache[n]
else:
cache[n] = fib(n - 1, cache) + fib(n - 2, cache)
return cache[n]Recursive fibonacci hesaplamasında, (dynamic programming genelde recursive metodlar ile işler) memoization denen bir işlem uyguluyoruz. Yani daha önce hesapladığımız adımları tekrar hesaplamak yerine bir bufferdan/cache den getiriyoruz. Normal fibonacci hesaplamasına göre çok daha performanslı.
Normal fibonacci kodu :
Kod:
def nfib(n):
if n <= 1:
return n
return nfib(n - 1) + nfib(n - 2)Normal fibonacci hesabında recursive yapıda oluşan node lar :
Memoization işlemi yaptıktan sonra hesaplanacak node lar :
Gördüğünüz gibi oldukça performans sağlıyor, işlem sayısını azaltıyor.
Bu konunun amacı dynamic programming ve memoization işlemini anlatmaktı, fibonacci mantığı anlamak için güzel bir örnek, gerçi fibonacci hesaplaması için matematiksel başka yöntemlerde olduğundan biraz eksik bir örnek gibi gözükebilir fakat görselleri ve kodu inceledikten sonra mantığı anlamanız yeterli. Önemli olan "alt parçalara ayrılabilen problemleri" analiz edip çözebilmek.
Son düzenleme:
