درخواست کمک برای نوشتن برنامه فیبوناچی برای اعداد بزرگ + کد

سلام به همگی

این کد برنامه فیبوناچی رو ببینید...

کد:

---

#include<iostream.h>
int fib(int);
void main()
{
        int n;
        cout<<"enter a numbers ";
                cin>> n;
                if(n<0)
                        cout<<"error";
                else
        cout<<fib(n)<<endl;
       
}

int fib(int x)
{

  if(x<=1)
          return x;
  else
          return fib(x-1) + fib(x-2);
}

---

این برنامه به ازای n های بالاتر از 45 خیلی طول میکشه...مثلا رو سیستم من با سی پی یو چهار هسته ای و دو گیگ رم برای عدد 41 حدود ده ثانیه طول میکشه و برای از 50 به بالاتر هم میزنه طرفهای چند ساعت...

تو رشته کامپیوتر و درس طراحی الگوریتم در مورد الگوریتم فیبوناچی صحبت شده و از نوعی از برنامه نویسی به کمک آرایه صحبت شده که دیگه نیازی نیست مثل الگوریتم بالا فیبوناچی عددی مثل 3 چندین بار در زمان اجرای برنامه محاسبه بشه و وقت اجرای برنامه افزایش پیدا کنه بلکه این مقدار یکبار محاسبه شده و در آرایه ذخیره میشه و برنامه از آرایه برای محاسبه فیبوناچی اعداد استفاده میکنه که نسبت به کدی که من نوشتم خیلی خیلی سریعتر هست..

من اون کد رو میخواستم اگه محبت کنید..

ممنونم:11:

کد:

---

#include<iostream>
usingnamespace std;
double fib(int n);
void main()
{
int n;
cout<<"enter a numbers ";
cin>> n;
if(n<0)
cout<<"error";
else
{
cout.precision(0) ;
cout << fixed << endl;
cout<<fib2(n)<<endl;
}
cin>>n;
}
double fib2(int n)
{
double x1=0;
double x2=1;
double t;
int count=2;
while(count<=n)
{
t=x1+x2;
x1=x2;
x2=t;
count++;
}
return x2;
}


---

سلام.
به این نوع الگوریتم که داده ها و مقدار های محاسبه شده رو توی یک آرایه ذخیره می کنند و زمان اجرای برنامه رو در ازای مصرف مقداری حافظه پایین می آرن می گن الگوریتم داینامیک(dynamic) یا پویا

و من فکر می کنم که این کد از کدی که به عنوان جواب ارائه شده داینامیک تره (در اصل به این کد اصلن داینامیک نیست (هست؟) این کد تنها فرقی که با کد اولیه داره اینه که از تابع بازگشتی استفاده نکرده)
درسته که زمان اجرای برنامه ی ایشون با کد من برای یک بار اجرا برابره ولی وقتی که این تابع قراره چند بار توی یک برنامه تکرار بشه این کد زمان اجرای سر شکن شده ی کمتری داره

در ضمن من یه سوال دارم:
چرا تابع فیبوناچی تونو از نوع double تعریف کردید؟ همون int جواب نمی ده؟

پ.ن: من syntax استفاده از اشاره گر رو دقیق یادم نیست (از اولشم درست یاد نگرفتم)

کد:

---

#include<iostream.h>
int fib3(int,int*);
int main()
{
int n,f[100]={0};
cin>>n;
if(n<0)
    cout<<"error";
else
    cout<<fib3(n,&f[0]);
retun 0;
}

int fib3(int n,*f)
{
    for(in i=1;i<n;i++)

        if(&f[i]==0)
            &f[i]=&f[i-1]+&f[i-2];

}

---