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

[mansoree]

سلام بچه ها به دادم برسید یه سوال گیجم کرده

 

[zeinab64]

سلام. خوب چه سوالی؟!!!!!!!!!!

 

[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=1 ............... n=1

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

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

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


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

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


یا


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