19 Mayıs 2011 Perşembe

Fibonacci Dizisini Dinamik Programlama Kullanarak Hesaplama #1 C++

Merhabalar,

Bu dönem aldığım algoritma dersinde bahsi geçen dinamik programlama nedir ne değildir diye araştırırken bu yöntemin Fibonacci Dizisi'ni hesaplarken oldukça işe yaracağını öğrendim.

Ekşisözlükte dinamik programlama için:

"bir problemi en küçük parçasından başlayarak daha büyük parçalarını çözerek yiyip bitirmek."
  tanımı girilmiş. "Küçük parçalarından elde edilen bilgiler (memolar) büyük parçaya ulaşırken kullanılır" diye de ekleyelim.



En basit şekliyle tanımını yaptıktan sonra (ayrıntılı bilgi isteyenleri  wikipedia sayfasına yönlendirip) fibonacci dizisi hesaplamasında dinamik programlamanın nasıl kullanılacağına geçelim.

Not: Aşağıdaki kod C++ programlama dili ve STL/map kütüphanesi kullanılarak yazılmıştır.


fibonacci sayısını hesaplayan fonksiyonumuz. küçük parçalardan elde ettiğimiz memoları daha sonraki işlemlerde kullanmak üzere map'imizin içine koyuyoruz. map'e koydugumuz ilk sayı kaçıncı fibonacci sayısı olduğu, ikinci sayı ise o fibonacci sayısının değeri.
0. fibonacci 0
1.fibonacci 1
bilgilerini main'in içinde initialize ediyoruz.

Konsoldan input'umuzu aldıktan sonra, fibonacci fonksiyonuna gönderip hesaplatıyoruz. yukardaki "mymap.insert" ile başlayan iki satır fibonacci dizisinin ilk iki elemanını map'imize yerleştirerek map'i initialize ediyor.

Kodda gördüğünüz hata veya önerilerinizi yazarsanız sevinirim. Bir sonraki yazımda aynı kodu python ile yazacağım ve dinamik programlama kullanarak fibonacci dizisi hesaplamada ne kadar hızlandığımızı (complexity  hesaplarını) anlatacağım.

Kalın sağlıcakla.


Hiç yorum yok:

Alakalı:

Related Posts Plugin for WordPress, Blogger...