الگوریتم بهینه محاسبه یک مقدار خاص در تابع فیبوناتچی - وبسایت دکتر امیر مرتضی سعیدی

الگوریتم بهینه محاسبه یک مقدار خاص در تابع فیبوناتچی

جمعه 91/3/19
12:25 عصر
amirsaeedi
نظر
الگوریتم بهینه محاسبه یک مقدار خاص در تابع فیبوناتچی
همونطور که میدونید برای محاسبه فیبوناتچی یک عدد از یک حلقه for یا تابعی بازگشتی استفاده میشه که اگه از تابع بازگشتی اون برای مقادیر بالا مثلا 20 به بالا بخواهید استفاده کنید زمان محاسبه اون به تدریج خیلی بالا میره ، می تونید برای تمرین و فهم زمان بد محاسبه اون از کد زیر که ساده ترین کد برای تابع بازگشتی فیبوناتچی هستش استفاده کنید.
کد:
#include <iostream>
using namespace std;
long int fibo(long int n)
{
    if(n<=0)
        return 0;
    if(n==1||n==2)
        return 1;
    else
        return fibo(n-1)+fibo(n-2);

}

int main()
{
    int n;
    cout<<"please ente a number:";
    cin>>n;
    cout<<fibo(n);
    return 0;
}

ولی در این بین برای بهینه کردن این الگوریتم از قانون بهره ترکیبی استفاده می کنیم که بیان این قانون به این صورت می باشد که اگر در جریان محاسبات تابع بازگشتی به یک عمل چندین بار مراجعه می شود بهترین کار این است که برای اولین بار که به آن عمل مراجعه شد نتایج آن در جایی ذخیره شود و در جریان فراخوانی های بعدی از همان مقداری که در مرحله قبل برای آن عمل محاسبه شده استفاده کرد و دوباره همان عمل تکراری را محاسبه نکرد یا به عبارت دیگر یک تابع بازگشتی باید از نتایج ضمنی تولید شده توسط مراحل قبلی برای کوتاهی محاسبات استفاده کند .اینم کد بهینه شده برای این الگوریتم که اگه با کد قبلی مقایسه کنید حتما متوجه اهمیت این قانون بسیار مهم می شوید.
کد:
#include <iostream>
using namespace std;
long int fibo(long int n,long int x=3,long int b=1,long int c=1)
{
    if(n<=0)
        return 0;
    if(n==1||n==2)
        return 1;
    if(n==x)
        return b+c;
    else
        return fibo(n,x+1,b+c,b);

}

int main()
{
    int n;
    cout<<"please ente a number:";
    cin>>n;
    cout<<fibo(n);
    return 0;
}
 
 



ادامه مطلب
طراح صفحات وب - برنامه نویس تحت سی پلاس پلاس و دلفی و ویبی - طراح نرم افزار های تبلیغاتی - تدریس خصوصی - ارائه پروپوزال و پایان نامه - ارائه مقالات علمی (برای ارتباط نظر بگذارین)
تمامی حقوق این وب سایت متعلق به وبسایت دکتر امیر مرتضی سعیدی است. || طراح قالب avazak.ir