Yazan: Şadi Evren ŞEKER
Bir problem tahlil ve çözüm yöntemi olan dinamik programlama yapı olarak parçala fethet yöntemine benzer. Tek farkı problemi parçalara böldükten sonra aynı problemin tekrarı olan parçaları bir kerede çözüp her tekrar için ayrı bir çözüm yapmamasıdır.
Örneğin fibonacci serilerini ele alalım, Bu seriyi üreten örnek kod aşağıda verilmiştir:
int fibonacci(int n)
{
if (0 == n) {
return 0;
} else if (1 == n) {
return 1;
} else {
return fibonacci(n - 2) + fibonacci(n - 1);
}
}
Yukarıda verilen bu recursive (kendi kendini çağıran) koda bakıldığında ve kodun tahlili yapıldığında aşağıdaki fonksiyon iç içe çağırma ağacı (recursion tree ) fark edilir:
fibonacci(4)
+------------------------------
| |
fibonacci(2) fibonacci(3)
+----------------- +---------------
| | | |
fibonacci(0) fibonacci(1) fibonacci(1) fibonacci(2)
+-----------
| |
fibonacci(0) fibonacci(1)
yani yukarıdaki örnekte, fibonacci(4) fonksiyonu için çağırma işlemleri sırasıyla gösterilmiştir. Dikkat edilirse fonksiyonlar açıldğında kendisinden önceki iki sayının toplamını bulmakta, bu işlemi yaparken de ortak elemanlar kullanmaktadır. Örneğin fibonacci(2) fonksiyonu ağacın iki farklı yerinde bulunmaktadır ve iki farklı kere içi hesaplanmıştır. İşte dinamik programlamada amaç bunu kaldırarak bir kerede çözüme ulaşmaktır.
Dinamik programlamada aşağıdaki adımlar takip edilebilir:
Verimli bir çözüm için problemin yapsınının çıkarılması
Kendini çağıran bir şekilde (Recursive) verimli çözüme değer atanması
Verimli çözümün değerini aşağıdan yukarı (bottom-up) olarak hesaplanması
Hesaplanan bu çözümle daha verimli bir çözüm varsa aranıp üretilmesi
(4. adım şayet tek çözüm varsa kullanılmaz)
Örnek problemler:
En uzun Ortak Küme (longest common subsequence, Lcs)
—————————
hocam bu fibonacciyi dinamik programlamada(c#) nasıl yapılandırabilriz?
yani tekrarlanan alt değerleri değerleri dizide mi tutarız?
saygılar
evet, bir kere çözdüğümüz ihtimali bir daha çözmemek için, çözülmüş halini hafızada (problemin tipine göre bir dizi olabilir) tutuyoruz.
Rod-cutting problem, Knapsack problem,Matrix-chain multiplication gibi problemlerde de dynamic programming kullanılabiliyor. Algoritması oturtulduğunda işe yarar bir yöntem.
Ezgi Hanım sorunuzun cevabı şu şekilde ;
using System; namespace FibonacciDinamikProgramlama { class DinamikProgramlama { #region "Degiskenler" static int DinamikSayisi = 0;//counter atadik static int RecursiveSayisi = 0;//counter atadik static int SayiDegeri=0; #endregion #region "Main Fonksiyonu" public static void Main() { DinamikProgramlama programNesnesi = new DinamikProgramlama();//nesne olusturduk SayiDegeri = Convert.ToInt32(Console.ReadLine());//sayi degerini kullanicidan aldik Console.WriteLine(FibonacciDinamikProgramlama(SayiDegeri)); Console.WriteLine(RecursiveSayisi(SayiDegeri)); Console.WriteLine("Dinamik Programlama Çalisma Sayisi " + DinamikSayisi + "nRecursive fynksiyonun çalisma sayini " + Recursive Sayisi); } #endregion #region "Dinamik Programlama ve Recursive fonksiyonu" public static int FibonacciDinamikProgramlama(int SayiDegeri)//fonksiyon olusturduk { DinamikSayisi++; int[] SayilarDizisi = new int[SayiDegeri + 2]; for (int i = 0; i < = SayiDegeri; i++) if (i == 0 || i == 1) { SayilarDizisi[0] = 0; SayilarDizisi[1] = 1; } else { SayilarDizisi[i] = SayilarDizisi[i - 1] + SayilarDizisi[i - 2]; } return SayilarDizisi[SayiDegeri]; } public static int RecursiveFiboniacciFonksiyonu(int SayiDegeri) { RecursiveSayisi++; if (SayiDegeri == 0) return 0; if (SayiDegeri <= 2) return 1; return RecursiveFiboniacciFonksiyonu(sayi - 1) + RecursiveFiboniacciFonksiyonu(sayi - 2); } #endregion } }Umarım yardımcı olur iyi çalışmalar
Bu site gerçekten harika. Algoritma dersiyle ilgili tüm aradıklarımı bulabiliyorum.
gerçekten çok yararlı bir site. tebrikler ve teşekkürler