Research Space for Linear Algebra & Discrete Mathematics
首先對於 n=2^k 我們知道答案, 比如 T(2)=T(1)+1, T(4)=T(2)+1=T(1)+2, 我假設 T(1)=0, 這樣你會發現如果 n=2^k, T(n)=k. 另外; T(n) 是 nondecreasing 而且是整數, 而在 T(2^k)=k 和 T(2^{k+1})=k+1 中間沒有其他的整數, 所以如果 2^k < n < 2^{k+1} 的話, T(n) 不是 k 就是 k+1. 可是我們知道 T(2)=1,T(3)=2,T(4)=2, 所以答案應該就是 T(n)=CEIL{log_2 n}. 接著你可以用 induction 去證明這個就是答安. 如果題目是 T(n)=T(FLOOR{n/2})+1 的話也可以用同樣的方法, 所以可以猜到答案應該是 FLOOR{log_2 n}.
另外; 我回覆了你爬樓梯的問題.ps. google blog 當討論區的話不能最新 po 的文章置頂 >.<
謝謝解答，我懂了還有樓梯問題，我也知道生成函數怎麼用了這樣解出來真的會把所有狀況涵蓋進去謝謝解答...我又學到了一招^^另外，我所謂的整數解，並不是去求它的方法數，而是把真的解列出來(其實是暴力法，我記得高中是這樣解的)，例如x+2y+3y=8，有一組解就是(0，4，0)那麼他的方法數就是4!/4!，依序將所有的解都列出來(用討論的方法)，例如z只可能等於0或1或2，然後去分項討論，不過這樣有點不切實際，我之所以會有這樣的想法，是因為高中都是這樣解(因為當時只能走一步或兩步，狀況較少)，但還是可以解的出來。
你說的沒錯. 所以窮舉法當然不適用於 general case.
張貼留言
5 則留言:
首先對於 n=2^k 我們知道答案, 比如 T(2)=T(1)+1, T(4)=T(2)+1=T(1)+2, 我假設 T(1)=0, 這樣你會發現如果 n=2^k, T(n)=k. 另外; T(n) 是 nondecreasing 而且是整數, 而在 T(2^k)=k 和 T(2^{k+1})=k+1 中間沒有其他的整數, 所以如果 2^k < n < 2^{k+1} 的話, T(n) 不是 k 就是 k+1. 可是我們知道 T(2)=1,T(3)=2,T(4)=2, 所以答案應該就是 T(n)=CEIL{log_2 n}. 接著你可以用 induction 去證明這個就是答安.
如果題目是 T(n)=T(FLOOR{n/2})+1 的話也可以用同樣的方法, 所以可以猜到答案應該是 FLOOR{log_2 n}.
另外; 我回覆了你爬樓梯的問題.
ps. google blog 當討論區的話不能最新 po 的文章置頂 >.<
謝謝解答，我懂了
還有樓梯問題，我也知道生成函數怎麼用了
這樣解出來真的會把所有狀況涵蓋進去
謝謝解答...我又學到了一招^^
另外，我所謂的整數解，並不是去求它的方法數，而是把真的解列出來(其實是暴力法，我記得高中是這樣解的)，例如x+2y+3y=8，有一組解就是(0，4，0)那麼他的方法數就是4!/4!，依序將所有的解都列出來(用討論的方法)，例如z只可能等於0或1或2，然後去分項討論，不過這樣有點不切實際，我之所以會有這樣的想法，是因為高中都是這樣解(因為當時只能走一步或兩步，狀況較少)，但還是可以解的出來。
你說的沒錯. 所以窮舉法當然不適用於 general case.
張貼留言