PDA

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



B-Vedadian
چهارشنبه 10 دی 1382, 09:17 صبح
با سلام،

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

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

الهام تفریشی
چهارشنبه 10 دی 1382, 13:39 عصر
این الگوریتمش هست

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
شنبه 13 دی 1382, 08:25 صبح
با سلام و تشکر،

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

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

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

B-Vedadian
یک شنبه 14 دی 1382, 09:02 صبح
سلام،

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

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

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

ممنون.

Kambiz
یک شنبه 14 دی 1382, 12:42 عصر
موضوع زیر رو ببین:
http://www.barnamenevis.org/forum/viewtopic.php?t=2909

B-Vedadian
شنبه 04 بهمن 1382, 21:44 عصر
آقای خجسته عزیز سلام،

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

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

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

Kambiz
سه شنبه 07 بهمن 1382, 00:56 صبح
ببخشدید، متوجه وجود پست جدید نشدم.

نماد 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 بزرگتر باشه بین مقدار محاسباتی و مقدار واقعی فراخوانی‌ها اختلاف بیشتری بوجود میاد. اگر اندازه تقسیمات برابر بود٬ مقدار واقعی با مقدار محاسباتی برابر می‌شد.

مهدی فهمیده غلامی
شنبه 22 فروردین 1383, 23:05 عصر
کتاب طراحی الگوریتم نوشته نو پو لیتن و یا طراحی الگوریتم دکتر نقیب زاده رو یه نگاهی بکن

raha_hakhamanesh
دوشنبه 04 تیر 1386, 16:22 عصر
با سلام

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

موفق باشید

el_abdollahi
سه شنبه 18 فروردین 1388, 01:46 صبح
سلام.
باز هم همون سوال اول

با سلام،

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

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

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

pesar irooni
چهارشنبه 19 فروردین 1388, 01:55 صبح
این الگوریتم که مینویسم از نوع تکراریه و فکر نکنم الگوریتم بازگشتی از این مرتبه وجود داشته باشه

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
چهارشنبه 19 فروردین 1388, 18:03 عصر
خیلی ممنون
فقط اگر یه توضیحی هم درباره الگوریتمش بدین، که منطقش چه جوریه خیلی خوب میشه.
این هم از کدش به زبان 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
پنج شنبه 20 فروردین 1388, 01:24 صبح
واقعا نمیدونم منطقش چیه و چه رابطه منطقی بین i j h و اینا برقراره. اما با مطالعه شاید بشه فهمید. اما اینکه ایده اولیه به ذهن طراحش رسیده واقعا جای تحسین داره