سری فیبوناچی

[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 الگوریتم من با مال شما یکی