დინამიკური პროგრამირება (ფიბონაჩის რიცხვები)

დინამიკური პროგრამირება პროგრამირების ერთ-ერთი ეფექტური მეთოდია. მეთოდის უპირატესობა მდგომარეობს იმაში, რომ გარკვეული პასუხის მისაღებად არ გვჭირდება ყოველი მნიშვნელობის გამოთვლა, რადგან ერთხელ გამოთვლილ მნიშვნელობებს ვიმახსოვრებთ.

მეთოდი რომ უკეთ გავიგოთ განვიხილოთ ერთ-ერთი ცნობილი ამოცანა ფიბონაჩის რიცხვების შესახებ. ფიბონაჩის რიცხვების გამოსათვლელად ამოცანის რამდენიმე ინტერპრეტაცია არსებობს, თუმცა ამ შემთხვევაში ვისარგებლოთ მზა ფორმულით. ყველასთვის ცნობილია ფიბონაჩის მიმდევრობის პირველი რამდენიმე რიცხვი. ესენია : 1 , 1 , 2 , 3 , 5 , 8 , 13 ,  ანუ ზოგადი ფორმულა ასეთია F[n] = F[n-1] + F[n-2] ; ანუ თითოეული წევრი უდრის წინა ორი წევრის ჯამს.

ახლა განვიხილოთ როგორ შეიძლება ამ ამოცანის კომპიუტერზე რეალიზება. ერთ-ერთი მეთოდია რეკურსია. თუმცა დიდი რიცხვებისთვის დავრწმუნდებით რომ რეკურსია გამოუსადეგარია, რადგან ამ რიცხვის გამოთვლას კომპიუტერი ძალიან დიდხანს უნდება, ხოლო დინამიკური პროგრამირების მეთოდით შეგვიძლია გამოვიყენოთ მონაცემთა სტრუქტურა ვექტორი. ანუ შევქმნათ ვექტორი და გამოთვლილი რიცხვები შევინახოთ ვექტორში. ცხადია, რომ პროგრამის ნებისმიერ გაშვებაზე, ეს რიცხვები შენახული იქნება და პროგრამას 1 წამზე ნაკლები დრო დასჭირდება გამოსათვლელად. ამის დასანახად განვიხილოთ ორი კოდი C++ -ზე დაწერილი და გამოვითვალოთ ფიბონაჩის 95-ე რიცხვი.

რეკურსიული :

#include <iostream>
#include <vector>
using namespace std;

long long Fibo (int n)
{
if (n==1 || n == 2 )
return 1;
else
return Fibo(n-1)+Fibo(n-2);

}

int main ()
{
int n;

cout<<“Enter the number “<<endl;

cin>> n;

cout<<“The “<<n<<“th Fibbonacci number = “<<Fibo(n)<<endl<<endl;

system(“PAUSE”);
return 0;
}

დინამიკური პროგრამირების მეთოდი :

#include <iostream>
#include <vector>
using namespace std;

long long Fibo (int n)
{
vector <int> v(n+1);
v[0] = 1;
v[1] = 1;

for (int i = 2; i <= n; i++ )
v[i] = v[i-1] + v[i-2];

return v[n];
}

int main ()
{
int n;

cout<<“Enter the number “<<endl;

cin>> n;

cout<<“The “<<n<<“th Fibbonacci number = “<<Fibo(n)<<endl<<endl;

system(“PAUSE”);
return 0;
}

 

 

Leave a Reply / უპასუხე

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / შეცვლა )

Twitter picture

You are commenting using your Twitter account. Log Out / შეცვლა )

Facebook photo

You are commenting using your Facebook account. Log Out / შეცვლა )

Google+ photo

You are commenting using your Google+ account. Log Out / შეცვლა )

Connecting to %s