# مهندسی نرم افزار > مباحث مرتبط با مهندسی نرم‌افزار > الگوریتم، کامپایلر، هوش مصنوعی و ساختمان داده ها >  سری فیبوناچی

## va_sha_114

آقا اگه کسی بتونه بگه این الگوریتم برای تابع بازگشتی چه جوریه ممنون میشم

----------


## اَرژنگ

> آقا اگه کسی بتونه بگه این الگوریتم برای تابع بازگشتی چه جوریه ممنون میشم


http://www.brpreiss.com/books/opus4/html/page73.html
بدونه بازگشتی چطور؟
اصلاًفیبوناچی  بازگشتی تعریف شده

----------


## mohandese_hiclass

این شبه کدشه
if n=0 or n=1 return n
else if
return fib(n-1)+fib(n-2)

----------


## Arash_j13

البته این کد بالایی بدترین حالت برای نوشتن سری فیبوناچی به روش بازگشتی هست چون با اون برای محاسبه جمله بالاتر از 40 زمان زیادی گرفته می شه به طروی که زمان محاسبه جمله صد وحشتناکه
این جوری بهرته تو این روش به جای اینکه از جمله n ام شروع کنیم و به جمله ی اول برسیم از جمله اول شروع می کنیم و به جمله n می رسیم تا هر جمله فقط یه بار محاسبه بشه

long int helpfibo(long int n,long int current, long int f1,long int f2)
{
	if(n<=0 || current <=0)
   	 return -1;
   if (n==1 || n==2 )
   	return 1;
   if (current==n)
   	return f1+f2;

   return helpfibo(n,current+1,f1+f2,f1);

}

long int fibo(long int n)
{
	return helpfibo(n,3,1,1);
}



یه راه دیگه هم اینکه مقادیر بدست اومده رو توی ارایه ذخیره کنید


long int helpfibo(long int n,long int *a)
{
    if (n==1|| n==2 )
    	return 1;
    if(!a[n-1])
    	a[n-1]=helpfibo(n-1,a);

    return a[n-1]+a[n-2];


}

long int fibo(long int n)
{
   if (n<=0)
   	return -1;
	long int * buffer=new long int[n+1],result;
   if(buffer)
   {
   	buffer[1]=buffer[2]=1;
   	result=helpfibo(n,buffer);
   }
   else
   	return -1;
   delete buffer;
   return result;
}

----------


## mohandese_hiclass

مرسی آرش جان البته اون موقع که من اون کد نوشتم به خاطر کمبود وقت زیاد ننوشتم توضیحات شما کامله اینم از من داشته باش محاسبه فیبو ناتچی فقط با دو متغیر 
i=1,j=0
for k=1 to n 
j=j+i
i=j-i
return j
این کد دیگه آخر دینامیک پروقرمینگه
هزینشم o(n)

----------


## اَرژنگ

ای بابا، آقایه مهندس جواب اون بنده خدا را درست داد، ولی اگر قراره به سرعت جواب اشکال بگیریم من چند تا گله دارم
۱_ جواب آقایه مهندس برایه اینکه کاره اون بندهٔ خدا را راه بندازه کامل بود.
۲_ جواب شما اون بنده خدا را که تازه کاره را به وحشت میندازه، ولی برایه بقیه خوبه.
۳_ اگر مشکل به سرعته، چرا از الگریتمه بازگشتی استفاده میکنیم، الگریتمهایه 
بازشگتی از حافظه کم میکنند. اگریتمهایی هستند که زمانشان c هست.
آرشجان مرجع الگریتمهایی را که فرستادید لطف کنید متشکر میشم.
مهندسجان در پست آخرتان گفتید که آخر داینامیک پرمینگه، منظورتان را از "آخر" متوجه نشدم. بیزحمت یک توضیح بدید ممنون میشم.

----------


## Arash_j13

در مورد اشکال اول و دوم حق با شماست ببخشید
در مورد سومی هم خب یه مسئله ای هست که الگوریتم ها بازگشتی خواناتر از غیر بازگشتی هاست و مرتبه زمانی هر دوی این الگوریتم ها با غیر بازگشتی برابره

منبع خاصی هم نداره

دومی رو استادمون سر کلاس گفت اولی رو خودم نوشتن

----------


## mohandese_hiclass

آرژنگ جان معمولا تو برنامه نویسی دینامیک پروقرمینگ ما ابتدا الگوریتم بر اساس آرایه پیاده سازی می کنیم بعد واسه بهینه سازی مسئله می یایم آرایرو فشرده سازی می کنیم به این ترتیب که خونه های آرایرو که در محاسبات ما تاثیر نداره محاسبه نمی کنیم با این کار باطبع آرایه فشرده تر می شه منظور از کلمه آخر هم که من به کار بردم این بود که از این بهینه تر از لحاظ فضا نمیشه به قول خودمون endeshe

----------


## mohandese_hiclass

> در مورد اشکال اول و دوم حق با شماست ببخشید
> در مورد سومی هم خب یه مسئله ای هست که الگوریتم ها بازگشتی خواناتر از غیر بازگشتی هاست و مرتبه زمانی هر دوی این الگوریتم ها با غیر بازگشتی برابره
> 
> منبع خاصی هم نداره
> 
> دومی رو استادمون سر کلاس گفت اولی رو خودم نوشتن


دوست عزیز اشتباه نکن فیبوناتچی غیر بازگشتی پیچیدگیش عدد طلایی به توان n هستش ولی غیر بازگشتیاش همش از مرتبه n هستن

----------


## Arash_j13

توی اون روشی که شما نوشتید بله ولی جوری که نوشتم نه می تونید بشیندی حساب کنید مرتبه ی زمانیش  O(n)  هست

----------


## اَرژنگ

حالا چرا مهم نیست که الگریتمی وجود داره که رتبه زمانیش ثابته؟

----------


## mohandese_hiclass

درسته پیچیدگیش هول و هوشه n البته گذرا نگاه کردم حساب نکردم ولی خودتون بگید n الگوریتم من با مال شما یکی

----------

