محاسبه باز گشتی Fibonacci Series از مرتبه لگاریتم (n)

[B-Vedadian]

با سلام،

آیا کسی الگوریتمی دارد که عناصر سری فیبوناچی را بصورت بازگشتی محاسبه کند و مرتبه این الگوریتم O[Log(n)]j باشد؟

اگر دارید لطف کنید مرا بی خبر نگذارید.

[الهام تفریشی]

این الگوریتمش هست

Function Fibonacci (N: integer)

Begin

If N < 0 then raise an exception
Else if N = 0 or 1 then return 1
Else return Fibonaccci(N-1)+Fibonacci(N-2) End if

End Fibonacci

[B-Vedadian]

با سلام و تشکر،

الگوریتمی که شما داده اید از رتبه n است، منظور من الگوریتمی از رتبه لگاریتم (n) بود شبیه الگوریتم FFT.

ممنون میشوم اگر مرا راهنمایی کنید.

[Kambiz]

فقط الگوریتم تکراری (itterative) دارای زمان اجرای <span dir=ltr>O(n)</span> است.
الگوریتمهای مختلف و زمان اجرای هر کدوم در لینک زیر موجوده:
http://people.msoe.edu/~durant/courses/cs285/bigO.cpp

[B-Vedadian]

سلام،

من الگویتم رو با روش زیر امتحان کردم:

یک متغیر عمومی استفاده کردم، هردفعه که یک دستور اجرا میشد یکی به اون اضافه کردم، بعد با شروع صفر الگوریتم رو اجرا کردم برای هر عددی که به عنوان ورودی دادم مقدار اون متغیر عمومی خود عدد ورودی بود. برای همین احساس کردم رتبه n باشه.

اگه تو روش کار اشتباه کردم لطفا بگید، راه درستش رو هم بگید. (البته منظورم بدون محاسبه و با آزمایشه)

ممنون.

[Kambiz]

موضوع زیر رو ببین:
http://www.barnamenevis.org/forum/viewtopic.php?t=2909

[B-Vedadian]

آقای خجسته عزیز سلام،

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

در مورد الگوریتم بازگشتی ارائه شده توسط خانم تفرشی هم اگر فرصت دارید لطف کنید راه محاسبه مرتبه آنرا بگویید (به نظر روش تقسیم و تسخیر نمی آید)

با عرض شرمندگی :oops: ممنون

[Kambiz]

ببخشدید، متوجه وجود پست جدید نشدم.

نماد O بزرگ (Big O) تقریبی از زمان اجرای الگوریتم رو در اختیار می‌گذاره نه زمان اجرای دقیق الگوریتم رو.

به عنوان نمونه٬ در الگوریتمی که توسط خانم تفریشی ذکر شده٬ تابع به ازای هر n بزرگتر از 1 الگوریتم دو بار فراخوانی میشه یا به عبارتی برای هر n دفعات فراخوانی تابع تقریبا" <span dir=ltr>2^n</span> است.

حال اگر برای آزمایش تعداد واقعی فراخوانی‌ها٬ همانند روشی که شما بکار بردید، مقدار یک شمارنده را در اولین خط این تابع افزایش دهیم٬ این شمارنده در خاتمه مقداری کمتر از <span dir=ltr>2^n</span> را نشان می‌دهد که البته در هر حال مقدار حاصل بیانگر افزایش توانی تعداد فراخوانی‌ها بر اساس اندازه‌ی ورودی مسئله هست.

اجازه دهید دلیل برابر نبودن مقدار نهایی شمارنده با <span dir=ltr>2^n</span> را با یک مثال ببینیم. فرض کنید که مقدار n ورودی عدد 4 باشد.

فراخوانی n = 4
[list:6ed9736a02] فراخوانی n = 3
[list:6ed9736a02] فراخوانی n = 2
[list:6ed9736a02] فراخوانی n = 1
فراخوانی n = 0 فراخوانی n = 1[/list:u:6ed9736a02] فراخوانی n = 2 فراخوانی n = 1
فراخوانی n = 0[/list:u:6ed9736a02][/list:u:6ed9736a02]همانطور که در این مثال می‌بینید٬ تعداد فراخوانی‌ها به جای مقدار محاسباتی <span dir=ltr>2^4 = 16</span>برابر مقدار 9 شد. دلیل این امر این است که برای هر بار فراخوانی، اندازه مسئله اصلی به دو اندازه‌ی نابرابر n-1 و n-2 تقسیم می‌شوند و لذا هر چقدر مقدار n بزرگتر باشه بین مقدار محاسباتی و مقدار واقعی فراخوانی‌ها اختلاف بیشتری بوجود میاد. اگر اندازه تقسیمات برابر بود٬ مقدار واقعی با مقدار محاسباتی برابر می‌شد.

[مهدی فهمیده غلامی]

کتاب طراحی الگوریتم نوشته نو پو لیتن و یا طراحی الگوریتم دکتر نقیب زاده رو یه نگاهی بکن

[raha_hakhamanesh]

با سلام

دوستان
من سه الگوریتم برای فیبوناچی می شناسم
1- همان فیبو بازگشتی هست با مرتبه زمانی (O(1.61^n
2- الگوریتم چرخشی(itration) با مرتبه (O(n
3- الگوریتم شبیه سازی شده الگوی کاری آقای فیبوناچی که دارای زمان لگاریتم n است اما ضرایب بزرگی دارد که در نماد O پنهان می شود.
اگر این الگوریتم سوم را خواستید به کتاب زیر مراجعه کنید
Algorithmics theory ad practice by brassard
ضمنا شنیدم آقای مهدس جم پور ترجمه این کتاب رو تحت عنوان طراحی و تحلیل الگورتم ها وارد بازار کرده اند انتشارات اون رو نمی دونم

موفق باشید

[el_abdollahi]

سلام.
باز هم همون سوال اول

با سلام،

آیا کسی الگوریتمی دارد که عناصر سری فیبوناچی را بصورت بازگشتی محاسبه کند و مرتبه این الگوریتم O[Log(n)]j باشد؟

اگر دارید لطف کنید مرا بی خبر نگذارید.

کسی جوابی داره؟

[pesar irooni]

این الگوریتم که مینویسم از نوع تکراریه و فکر نکنم الگوریتم بازگشتی از این مرتبه وجود داشته باشه

function fib(n)
i=1; j=0; k=0; h=1;
while n>0 do
if n is odd then
t=jh;
j=ih+jk+t;
i=ik+t;
t=h^2;
h=2kh+t;
k=k^2+t
n=n div 2;
return j

[el_abdollahi]

خیلی ممنون
فقط اگر یه توضیحی هم درباره الگوریتمش بدین، که منطقش چه جوریه خیلی خوب میشه.
این هم از کدش به زبان C++:


int fib(int n)
{
int i,j,k,h,t;
i=1; j=0; k=0; h=1; j=0;
while (n>0)
{
if (n%2==1)
{
t=j*h;
j=i*h+j*k+t;
i=i*k+t;
}
t=h*h;
h=2*k*h+t;
k=k*k+t;
n=n / 2;
}
return j;
}

[pesar irooni]

واقعا نمیدونم منطقش چیه و چه رابطه منطقی بین i j h و اینا برقراره. اما با مطالعه شاید بشه فهمید. اما اینکه ایده اولیه به ذهن طراحش رسیده واقعا جای تحسین داره