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

證明可解漢諾塔問(wèn)題：

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

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

? ??

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

之后把2號(hào)盤(pán)子移動(dòng)到C上面此時(shí)移動(dòng)次數(shù)為a_1?+ 1。

這時(shí)把1號(hào)盤(pán)子從B移動(dòng)到C和①是等價(jià)的，

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

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

此時(shí)移動(dòng)的次數(shù)是a2，接著把3號(hào)盤(pán)子移動(dòng)到C上面

此時(shí)移動(dòng)的次數(shù)是a_2?+ 1，這時(shí)把1和2號(hào)盤(pán)子移動(dòng)到C上面（移動(dòng)過(guò)程中3號(hào)盤(pán)子始終不會(huì)動(dòng)）和②等效的，移動(dòng)完成之后如下

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

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

此時(shí)移動(dòng)的次數(shù)是a₃

把4號(hào)盤(pán)子從A移動(dòng)到C

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

接下來(lái)把123號(hào)盤(pán)子從B移動(dòng)到C的過(guò)程又和③等效了移動(dòng)之后如下

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

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

把k+1號(hào)盤(pán)子移動(dòng)到C上面，這時(shí)移動(dòng)次數(shù)是a_k?+ 1

接下來(lái)和n=k時(shí)移動(dòng)過(guò)程等效，移動(dòng)完成后移動(dòng)總次數(shù)是a_k+1?= ?a_k?+ 1+ a_k

?

可以得知移動(dòng)k+1個(gè)盤(pán)子需要的次數(shù)與移動(dòng)k個(gè)盤(pán)子的次數(shù)之間的關(guān)系是：

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

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

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

至此，證明完畢。

轉(zhuǎn)載于:https://www.cnblogs.com/xxNote/articles/3965739.html

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

總結(jié)

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

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