دوستان لطفا نظر تون رو در مورد سوال زیر بفرمایید
رابطه بازگستی زیر داده شده
[tex]G_{0}=1 ,G_{1}=2 ,G_{2}=4[/tex]
[tex]G_{n}==G_{n-1} 2G_{n-2} G_{n-3}[/tex]
برای n>=3 کدام گزینه بهترین جواب این رابطه است
[tex]1- G_{n}\leq 2^{n}[/tex]
[tex]2- G_{n}\leq 4^{n}[/tex]
[tex]3- G_{n}\leq 2^{n 1}[/tex]
[tex]4- G_{n}\leq 4^{n 1}[/tex]
به این صورت هست که:
Gn=Gn-1+2*Gn-2+Gn-3
که عبارت:
Gn-1+2*Gn-2+Gn-3<Gn-1+2*Gn-1+Gn-1<4*Gn-1
حالا اگر معادله‌ی مشخصه رو بنویسیم برابر می شه با:r=4
و
G0=1 then c1*4^0=1
c1=1
در نتیجه جواب گزینه‌ی ۲ می شه!و
G0=1 then c1*4^0=1
c1=1
راستش من هم بر عقیده شمام اما آقای یوسفی گزینه ۴ رو زدن
بازم ممنون که وقتتون رو گذاشتین
(۰۱ آبان ۱۳۹۰ ۰۶:۵۴ ب.ظ)ahmadnouri نوشته شده توسط: راستش من هم بر عقیده شمام اما آقای یوسفی گزینه ۴ رو زدن
بازم ممنون که وقتتون رو گذاشتین
اگر از رو کتاب پوران پژوهش می خونین این کتاب خیلی اشتباه داره!از رو یه کتاب تست دیگه هم چک کنین!
نظر من هم گزینه ۴ هستش.
اگه درخت بازگشتی رو بصورت درخت پر فرض و ترسیم کنیم و حداکثر تعداد فراخوانی‌ها رو در نظر بگیریم {بصورت تقریبی}
و سطح ریشه رو صفر فرض کنیم، اونوقت در مورد این رابطه بازگشتی داریم:
[tex]\LARGE G(n)<4^{n 1}[/tex]
(۰۱ آبان ۱۳۹۰ ۰۹:۵۸ ب.ظ)yaali نوشته شده توسط: نظر من هم گزینه ۴ هستش.
اگه درخت بازگشتی رو بصورت درخت پر فرض و ترسیم کنیم و حداکثر تعداد فراخوانی‌ها رو در نظر بگیریم
و سطح ریشه رو صفر فرض کنیم، اونوقت در مورد مرتبه این رابطه بازگشتی داریم:
[tex]\LARGE T(n)<4^{n 1}[/tex]
من چک کردم!تو کتاب مقسمی گزینه‌ی ۲ رو انتخاب کرده!
دوستان دیگه نظر بدن لطفا!