本文鏈接：http://www.cnblogs.com/xxNote/p/3965739.html ? 第一次遇到漢諾塔問題時我瞬間就被搞蒙了之后果斷扔下不管了，今天再次遇到這個問題被搞蒙again，在網(wǎng)上搜了好久愣是沒讓我找到證明漢諾塔問題可解和推導公式過程的資料，于是花了幾個小時（誰讓咱不太聰明呢，嘿嘿），最后終于想通了，記錄下來希望對像我一樣不聰明的人有所幫助。

證明可解漢諾塔問題：

我用的是數(shù)學歸納法，假設圓盤的個數(shù)為n，圓盤編號從上到下依次為1，2，3，4，……n，證明如下

①當?n = 1?時，從?A?移動到?C?顯然能夠完成，設需要移動的次數(shù)是a₁。

? ??

②當?n = 2?時，由①可知從把?1?號盤子從?A?移動到?B能夠完成（B?和?C?是等效的）此時移動次數(shù)為a₁。

之后把2號盤子移動到C上面此時移動次數(shù)為a_1?+ 1。

這時把1號盤子從B移動到C和①是等價的，

移動后總的移動次數(shù)是a_2?= a_1?+ 1 + a₁。

③當n = 3時，由②可知移動成下圖的效果是可以實現(xiàn)的，

此時移動的次數(shù)是a2，接著把3號盤子移動到C上面

此時移動的次數(shù)是a_2?+ 1，這時把1和2號盤子移動到C上面（移動過程中3號盤子始終不會動）和②等效的，移動完成之后如下

移動的總次數(shù)是a_3?= a_2?+ 1 + a₂

④當n=4時，由③可知移動成下圖的效果是可以實現(xiàn)的，

此時移動的次數(shù)是a₃

把4號盤子從A移動到C

此時移動的次數(shù)是a_3?+ 1

接下來把123號盤子從B移動到C的過程又和③等效了移動之后如下

移動的總次數(shù)是a₄?= a_3?+ 1 +?a₃

假設當n= k時，從A移動到C是可以實現(xiàn)的，那么當n=k+1時，可以移動到A上面只剩k+1號盤子，B上面依次是1，2，3，.....，k號盤字，此時移動次數(shù)是a_k??

把k+1號盤子移動到C上面，這時移動次數(shù)是a_k?+ 1

接下來和n=k時移動過程等效，移動完成后移動總次數(shù)是a_k+1?= ?a_k?+ 1+ a_k

?

可以得知移動k+1個盤子需要的次數(shù)與移動k個盤子的次數(shù)之間的關系是：

a_k+1?=? a_k?+ 1+ a_k?= 2a_k?+ 1

所以a_k+1?+ 1 ?=?2*（a_k?+ 1）【這是個等比數(shù)列高中學過的】

即a_k?+ 1 = ?（a1?+1）* 2^n-1?= 2ⁿ?因此a_k?= 2ⁿ?- 1

至此，證明完畢。

轉載于:https://www.cnblogs.com/xxNote/articles/3965739.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的证明并推导汉诺塔（河内之塔）问题公式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。