試題詳解

49. (河內塔問題)傳說越南河內某間寺院有三根銀棒，上串64個金盤，小盤在大盤之上。寺院裡的僧侶移動這些盤子，每 次只能移動一個圓盤且大盤不能疊在小盤上面，當這些盤子從第一根銀棒完全移置於第二根銀棒時，世界就會滅亡。 假設有n個金盤所需移動數為T(n)，則其遞迴式為？
(A) T(n) = 2T(n − 1) + 1
(B) T(n) = T(n − 1) + T(n − 2)
(C) T(n) = T(n − 1) + 2T(n − 2)
(D) T(n) = T(n − 1) + T(n − 2) + T(n − 3)