دوستان عزیز به نظر شما گزینه درست کدومه؟!
![[تصویر: O_90_91.jpg]](http://dl.dropboxusercontent.com/u/73158448/Question/Bah_FinalWeek/O_90_91.jpg)
اشکال من اینه که به ازای n های زیر من این جوابو بدست آوردم:
n=0 جواب ۱
n=1 جواب ۳
n=2 جواب ۷
n=3 جواب ۷
n=4 جواب ۱۵
....
نمی دونم کجارو بد دارم حساب می کنم!اما طبق این محاسبه جواب تو گزینه ها نیست و نزدیکترین جواب میشه گزینه۳!اما جواب طراح گزینه ۴ هستش!من با این گزینه موافقم اما اگه دستور چاپ توی Else نوشته بشه!
من اشتباه می کنم؟!
ممنون میشم راهنمایی کنید.
اگر T رو بگیریم تعداد ستاره های چاپ شده:
[tex]T(n) = 2 T(n/2) 1[/tex]
چون هر بار یک ستاره چاپ میکنه و دو بار n/2 رُ صدا میزنه
حالا اگر n رُ بگیریم ۲^m تابع جدید میشه:
[tex]F(m) = 2 F(m-1) 1[/tex]
که ریشه معادله مشخصه میشه ۲ و:
[tex]F(m) = a2^{m} b[/tex]
و: چون تغییر متغیر دادیم:
[tex]n= 2^{m} \rightarrow m=log (n)[/tex]
با جاگذاری:
[tex]T(n)= a'2^{logn} b'[/tex]
که با احتساب شرایط اولیه فرمول کلی گزینه آخر میشه[/align]
منم همون هایی تو گذاشتی رو بدست می آرم
(۱۷ بهمن ۱۳۹۱ ۱۱:۱۴ ق.ظ)pkpooria نوشته شده توسط: اگر T رو بگیریم تعداد ستاره های چاپ شده:مرسی دوست عزیز اما این رابطه اولی که بدست اوردید که من بدست میارم مرتبه n میشه!هرچند سوال تعداد رو خواسته
[tex]T(n) = 2 T(n/2) 1[/tex]
چون هر بار یک ستاره چاپ میکنه و دو بار n/2 رُ صدا میزنه
حالا اگر n رُ بگیریم ۲^m تابع جدید میشه:
[tex]F(m) = 2 T(m-1) 1[/tex]
که ریشه معادله مشخصه میشه ۲ و:
[tex]F(m) = a2^{m} b[/tex]
و: چون تغییر متغیر دادیم:
[tex]n= 2^{m} \rightarrow m=log (n)[/tex]
با جاگذاری:
[tex]T(n)= a'2^{logn} b'[/tex]
که با احتساب شرایط اولیه فرمول کلی گزینه آخر میشه
اما من همه سوالا رو با این روش تونستم حل کنم اما اینو نمیشه!
من بازم فکر می کنم که یه else کم داره!!!
بهرحال ما با هر روشی مرتبه رو بدست بیاریم این مرتبه ها باید با عدد گذاری تایید بشه نه اینکه رد بشه!موافق نیستید بامن؟!
دقت کنید:
ما تو این سوال دنبال مرتبه نیستیم بلکه دنبال جواب رابطه بازگشتی هستیم، که اونم با بدست آوردن معادله مشخصه و اعمال شرایط اولیه به دست میاد.
اگه else بذاره و توی اون چاپ کنه، فقط وقتی مقدار ورودی کمتر از صفر باشه ستاره چاپ میشه اونوقت برای بدست آوردنش باید درخت بکشید و به راحتی تعداد برگ ها رُ بررسی کنید
اما این الگوریتم تو هر فراخانی یک بار ستاره چاپ میکنه و دو بارم تابع رُ به ازای n/2 صدا میزنه یعنی:
[tex]T(n)=2T(n/2) 1[/tex]
حالا یه رابطه بازگشتی داریم که باید جواب کُلیشُ به دست بیاریم، که به دست آوردنش همونطور که بالا گفتم با تغییر متغییر و معادله مشخصه...
(۱۷ بهمن ۱۳۹۱ ۰۲:۴۷ ب.ظ)۸Operation نوشته شده توسط:(17 بهمن ۱۳۹۱ ۱۱:۱۴ ق.ظ)pkpooria نوشته شده توسط: اگر T رو بگیریم تعداد ستاره های چاپ شده:مرسی دوست عزیز اما این رابطه اولی که بدست اوردید که من بدست میارم مرتبه n میشه!هرچند سوال تعداد رو خواسته
[tex]T(n) = 2 T(n/2) 1[/tex]
چون هر بار یک ستاره چاپ میکنه و دو بار n/2 رُ صدا میزنه
حالا اگر n رُ بگیریم ۲^m تابع جدید میشه:
[tex]F(m) = 2 T(m-1) 1[/tex]
که ریشه معادله مشخصه میشه ۲ و:
[tex]F(m) = a2^{m} b[/tex]
و: چون تغییر متغیر دادیم:
[tex]n= 2^{m}
ightarrow m=log (n)[/tex]
با جاگذاری:
[tex]T(n)= a'2^{logn} b'[/tex]
که با احتساب شرایط اولیه فرمول کلی گزینه آخر میشه
اما من همه سوالا رو با این روش تونستم حل کنم اما اینو نمیشه!
من بازم فکر می کنم که یه else کم داره!!!
بهرحال ما با هر روشی مرتبه رو بدست بیاریم این مرتبه ها باید با عدد گذاری تایید بشه نه اینکه رد بشه!موافق نیستید بامن؟!
شما اشتباه حساب کردین. جواب میشه ۴n-1 که نزدیکترین جواب همون گزینه چهار هست درستش اینه
[tex]2^{log(n)) 2}-1=4n-1[/tex]
که با مثالهای شما درسته اما ای کاش عددای بزرگتر هم تست می کردین تا همه چی دستتون میومد
n=2,7
n=4,15
n=8, 31
n=16,63
یه نکته دیگه زمانی جواب دو به توان n هست که ارتفاع درخت n باشه اما در اینجا میبینیم که ارتفاع متناسب با log هست. پس میشه دو به توان log
همچنین اگه آخر برنامه else داشت جواب میشد ۲n که باز هم از مرتبه n هست