۰
subtitle
ارسال: #۱
  
تست (روابط بازگشتی) طراحی الگوریتم سال ۸۴
دوستان لطفا نظر تون رو در مورد سوال زیر بفرمایید
رابطه بازگستی زیر داده شده
[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]
رابطه بازگستی زیر داده شده
[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]
۰
ارسال: #۲
  
RE: سوال الگوریتم سال ۸۴ مربوط به روابط بازگتشی
به این صورت هست که:
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
۰
ارسال: #۳
  
سوال الگوریتم سال ۸۴ مربوط به روابط بازگتشی
راستش من هم بر عقیده شمام اما آقای یوسفی گزینه ۴ رو زدن
بازم ممنون که وقتتون رو گذاشتین
بازم ممنون که وقتتون رو گذاشتین
ارسال: #۴
  
RE: سوال الگوریتم سال ۸۴ مربوط به روابط بازگتشی
۰
ارسال: #۵
  
سوال الگوریتم سال ۸۴ مربوط به روابط بازگتشی
نظر من هم گزینه ۴ هستش.
اگه درخت بازگشتی رو بصورت درخت پر فرض و ترسیم کنیم و حداکثر تعداد فراخوانیها رو در نظر بگیریم {بصورت تقریبی}
و سطح ریشه رو صفر فرض کنیم، اونوقت در مورد این رابطه بازگشتی داریم:
[tex]\LARGE G(n)<4^{n 1}[/tex]
اگه درخت بازگشتی رو بصورت درخت پر فرض و ترسیم کنیم و حداکثر تعداد فراخوانیها رو در نظر بگیریم {بصورت تقریبی}
و سطح ریشه رو صفر فرض کنیم، اونوقت در مورد این رابطه بازگشتی داریم:
[tex]\LARGE G(n)<4^{n 1}[/tex]
ارسال: #۶
  
RE: سوال الگوریتم سال ۸۴ مربوط به روابط بازگتشی
(۰۱ آبان ۱۳۹۰ ۰۹:۵۸ ب.ظ)yaali نوشته شده توسط: نظر من هم گزینه ۴ هستش.
اگه درخت بازگشتی رو بصورت درخت پر فرض و ترسیم کنیم و حداکثر تعداد فراخوانیها رو در نظر بگیریم
و سطح ریشه رو صفر فرض کنیم، اونوقت در مورد مرتبه این رابطه بازگشتی داریم:
[tex]\LARGE T(n)<4^{n 1}[/tex]
من چک کردم!تو کتاب مقسمی گزینهی ۲ رو انتخاب کرده!
دوستان دیگه نظر بدن لطفا!
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close