میشه رابطه بازگشتی زیر رو حل کنید؟
سلام.
این سوال رو راحت میشه با جایگذاری و پیدا کردن چند مقدار اولیه بدست اورد و بعد از اون هم راحت حدس زد که دنباله به چه صورتی هست.
T0 = 0
T1 = 1
T2 = 3
T3 = 7
T4 = 15
T5 = 31
...
با بررسی کردن مقادیر بدست اومده متوجه میشیم که دنباله از رابطه ی [tex]T(n) = 2^{n} -1[/tex] هست و در نتیجه [tex]T(n) = \Theta (2^{n})[/tex] است.
(۳۰ مهر ۱۳۹۲ ۱۱:۳۱ ب.ظ)atenaa نوشته شده توسط: میشه رابطه بازگشتی زیر رو حل کنید؟
صفحه ۷۲ کتاب الگوریتم مقسمی حل شده.میشه :۱-(۲ به توان n )
با جایگذاری راحت حل میشه
سلام این معادله برج های هانوی هستش
چند باری تا الان ازش سوال اومده
حلش اینطوری که
[tex]T(n)=2T(n-1)+1=2(2T(n-2)+1)+1=2^{2}T(n-2)+2^{1}+2^{0}=2^{n-1}+2^{n-2}+...+2^{1}+2^{0}=1*(2^{n}-1)/2-1=2^{n}-1\epsilon O(2^{n})[/tex]
تو تستای جدید سعی کردن قوانین جابجایی دیسک را تغییر بدن مثلا اینکه شما حق جابجایی دیسک از A به B و B به A رو ندارید.....
