تالار گفتمان مانشت

دوستان لطفا نظر تون رو در مورد سوال زیر بفرمایید
رابطه بازگستی زیر داده شده
[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]

به این صورت هست که:

راستش من هم بر عقیده شمام اما آقای یوسفی گزینه 4 رو زدن
بازم ممنون که وقتتون رو گذاشتین

(01 آبان 1390 06:54 ب.ظ)ahmadnouri نوشته شده توسط: [ -> ]راستش من هم بر عقیده شمام اما آقای یوسفی گزینه ۴ رو زدن
بازم ممنون که وقتتون رو گذاشتین

اگر از رو کتاب پوران پژوهش می خونین این کتاب خیلی اشتباه داره!از رو یه کتاب تست دیگه هم چک کنین!

نظر من هم گزینه 4 هستش.
اگه درخت بازگشتی رو بصورت درخت پر فرض و ترسیم کنیم و حداکثر تعداد فراخوانی‌ها رو در نظر بگیریم {بصورت تقریبی}
و سطح ریشه رو صفر فرض کنیم‌، اونوقت در مورد این رابطه بازگشتی داریم:

[tex]\LARGE G(n)<4^{n 1}[/tex]

(01 آبان 1390 09:58 ب.ظ)yaali نوشته شده توسط: [ -> ]نظر من هم گزینه ۴ هستش.
اگه درخت بازگشتی رو بصورت درخت پر فرض و ترسیم کنیم و حداکثر تعداد فراخوانی‌ها رو در نظر بگیریم
و سطح ریشه رو صفر فرض کنیم‌، اونوقت در مورد مرتبه این رابطه بازگشتی داریم:

[tex]\LARGE T(n)<4^{n 1}[/tex]

من چک کردم!تو کتاب مقسمی گزینه‌ی 2 رو انتخاب کرده!
دوستان دیگه نظر بدن لطفا!