مشکل ساختمان داده

mansoree

عضو جدید
رابطه بازگشتی ب.م.م به مشکل برخوردم ببینید واسه اونایی که بخش پذیرین مثل )(3و15) جواب را کوچکترین میده

B if(b≤a) and (a mode b)=0
G(b,a) a<b
G(b.amod b) else
و یه سوال دیگه مرتبه اجرایی سری فیبوناچی چه جوری حساب میشه (تو رابطه بازگشتی)
 

dzzv_13

مدیر مهندسی فناوری اطلاعات
مدیر تالار
رابطه بازگشتی ب.م.م به مشکل برخوردم ببینید واسه اونایی که بخش پذیرین مثل )(3و15) جواب را کوچکترین میده

B if(b≤a) and (a mode b)=0
G(b,a) a<b
G(b.amod b) else
و یه سوال دیگه مرتبه اجرایی سری فیبوناچی چه جوری حساب میشه (تو رابطه بازگشتی)

سوال اول
خب نوشتین b کوچکتر از a بود و اون and درست بود b رو نمایش بده
این یعنی کوچیکترین رو نشون میده اگر بخش پذیر باشه ... علامت خط اول رو برعکس کنید و بنویسید b>=a

سوال دوم:

تابع بازگشتی فیبوناچی :
اگر 2,Fib(n)=1 ............... n=1

اگر Fib(n)= fib(n-1)+ fib(n-2) ............. n>2

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

T(n)=T(n-2)*T(n-2(
مرتبه اجرایش میشه
O(2[SUP]n/2[/SUP])


2 که در پایه نوشتم تعداد n-1 هست که دوتا هست
توی توان هم اون دو که زیر خط کسری هست بخاطر وجود دو هست که اگر بجای دو سه باشه زیر خط کسری سه و هر چی باشه اون رو میزاریم

مثلا
T(n)=T(n-1)*T(n-1)
مرتبه اجرایش میشه
O(2[SUP]n/1[/SUP])


یا


T(n)=T(n-3)*T(n-3)
مرتبه اجرایش میشه
O(2[SUP]n/3[/SUP])
 
آخرین ویرایش:

Similar threads

بالا