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)

—————————

Yorumlar

  1. Tolpp

    Rod-cutting problem, Knapsack problem,Matrix-chain multiplication gibi problemlerde de dynamic programming kullanılabiliyor. Algoritması oturtulduğunda işe yarar bir yöntem.

  2. cbasaranoglu Article Author

    Ezgi Hanım sorunuzun cevabı şu şekilde ;

    ?View Code CSHARP
    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

Bir Cevap Yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir


5 − iki =