T(n)=2T(n-1)+1
T(1)=1
向下帶
2[2T(n-2)+1]+1
=> 4T(n-2)+2
=> 4[2T(n-3)+1]+2
=> 8T(n-3)+3
找到相關性 XT(n-y)+Z 發覺 Z=3 Y=3 X=2^Z
2^(n-1)T(n-(n-1))+n-1
因為n-(n-1)=1
我的答案會是2^(n-1)+n-1
而不是解答中的2^n-1
請問我是哪裡觀念出了問題 有些題目我嘟用這個觀念下去找解
突然錯了 整個悶起來...未來的路怎走下去阿~
10 則留言:
你的這步算錯
向下帶
2[2T(n-2)+1]+1
=> 4T(n-2)+2
^ 是3
下面觀念正確，遞迴的代入法要仔細算
2[2T(n-2)+1]+1 ....2x1 =2 + 1 =3
豁然
謝謝
修正觀念後
T(n)=2T(n-1)+1
T(1)=1
向下帶
2[2T(n-2)+1]+1
=> 4T(n-2)+2+1
=> 4[2T(n-3)+2]+2+1
=> 8T(n-3)+2+2+1
觀察是 2*3 -1
前面代成2^(n-1)
變成 2^(n-1)T(n-(n-1))2(n-1)-1
這樣觀念對嗎?
我發覺我算的跟老師不一樣耶
爾且到這裡就卡住了
同學可不可以請你算仔細一點..
恩
有些錯誤我修改一下
T(n)=2T(n-1)+1
T(1)=1
向下帶
2[2T(n-2)+1]+1
=> 4T(n-2)+2+1
=> 4[2T(n-3)+2]+2+1
=> 8T(n-3)+2+2+1
\
觀察看成 2*3 -1 = 5 , 2+2+1=5
前面代成2^(n-1) , T(n-(n-1))=T(1)
==> 2^(n-1)T(1)+2(n-1)-1
你又算錯了，在T(n-2)到T(n-3)那邊，下面是正確的
T(n)=2T(n-1)+1
=2^2T(n-2)+2+1
=2^3T(n-3)+4+2+1
知道自己少了哪一項了嗎
2^3T(n-3)+4+2+1
下一項是
8[2T(n-4)+1)+4+2+1
==>我的下一項是這樣嗎
2^3T(n-4)+8+4+2+1
謝謝你的回答
後面的常數項沒錯，前面的次方錯了：
應該是2^4*T(n-4)+8+4+2+1。
同學，你在計算時真的要仔細一點，不然觀念正確卻計算錯誤，考試的時候很吃虧。
謝謝~助教
張貼留言