如何推導(dǎo)漢諾塔的公式？

求汗諾塔N個(gè)盤子須幾次移動(dòng)時(shí)得到了下面的遞推公式： a[1] = 1; a[n] = a[n-1] * 2 + 1; 請(qǐng)教通項(xiàng)公式？ a[1] = 1; a[n] = a[n-1] * 2 + 1; 可得a[i]= 2^i-1; 證明，采用數(shù)學(xué)歸納法： 1、猜想a[i]= 2^i-1 2、當(dāng)i=1時(shí)，顯然成立。 3、假設(shè)i=k時(shí)成立，即 a[k] = 2^k - 1;則： 由a[n] = a[n-1] * 2 - 1;得 a[k+1] = a[k] * 2 - 1 = 2^k * 2 - 1 = 2^(k-1) - 1 故得證。 同時(shí)：： 漢諾塔問題（又稱河內(nèi)塔問題）是根據(jù)一個(gè)傳說形成的一個(gè)問題： 有三根桿子A，B，C。A桿上有N個(gè)(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規(guī)則將所有圓盤移至C桿： 1. 每次只能移動(dòng)一個(gè)圓盤； 2. 大盤不能疊在小盤上面。 提示：可將圓盤臨時(shí)置于B桿，也可將從A桿移出的圓盤重新移回A桿，但都必須尊循上述兩條規(guī)則。 問：如何移？最少要移動(dòng)多少次？ 一般取N=64。這樣，最少需移動(dòng)264-1次。即如果一秒鐘能移動(dòng)一塊圓盤，仍將需5845.54億年。目前按照宇宙大爆炸理論的推測(cè)，宇宙的年齡僅為137億年。 在真實(shí)玩具中，一般N=8；這將需移動(dòng)255次。如果N=10，需移動(dòng)1023次。如果N=15，需移動(dòng)32767次；這就是說，如果一個(gè)人從3歲到99歲，每天移動(dòng)一塊圓盤，他僅能移動(dòng)15塊。如果N=20，需移動(dòng)1048575次，即超過了一百萬次。 先看hanoi(1, one, two, three)的情況。這時(shí)直接將one柱上的一個(gè)盤子搬到three柱上。注意，這里one柱或three柱到底是A、B還是C并不重要，要記住的是函數(shù)第二個(gè)參數(shù)代表的柱上的一個(gè)盤被搬到第四個(gè)參數(shù)代表的柱上。為方便，將這個(gè)動(dòng)作記為： one =》three 再看hanoi(2, one, two, three)的情況。考慮到hanoi(1)的情況已經(jīng)分析過了，可知這時(shí)實(shí)際上將產(chǎn)生三個(gè)動(dòng)作，分別是： one =》two one =》three two =》three 很顯然，這實(shí)際上相當(dāng)于將one柱上的兩個(gè)盤直接搬到three柱上。 再看hanoi(3, one, two, three)的情況。分析 hanoi(2, one , three, two) one =》three hanoi(2, two, one, three) 即：先將one柱上的兩個(gè)盤搬到two柱上，再將one柱上的一個(gè)盤搬到three柱上，最后再將two柱上的兩個(gè)盤搬到three柱上。這不就等于將one柱上的三個(gè)盤直接搬到three柱上嗎？ 運(yùn)用歸納法可知，對(duì)任意n， hanoi(n-1, one , three, two) one =》three hanoi(n-1, two, one, three) 就是先將one柱上的n-1個(gè)盤搬到two柱上，再將one柱上的一個(gè)盤搬到three柱上，最后再將two柱上的n-1個(gè)盤搬到three柱上。這就是我們所需要的結(jié)果！ 回答者：wuchenghua121 - 經(jīng)理 四級(jí) 12-5 11:51 漢諾塔 漢諾塔（又稱河內(nèi)塔）問題是印度的一個(gè)古老的傳說。開天辟地的神勃拉瑪在一個(gè)廟里留下了三根金剛石的棒，第一根上面套著64個(gè)圓的金片，最大的一個(gè)在底下，其余一個(gè)比一個(gè)小，依次疊上去，廟里的眾僧不倦地把它們一個(gè)個(gè)地從這根棒搬到另一根棒上，規(guī)定可利用中間的一根棒作為幫助，但每次只能搬一個(gè)，而且大的不能放在小的上面。解答結(jié)果請(qǐng)自己運(yùn)行計(jì)算，程序見尾部。面對(duì)龐大的數(shù)字(移動(dòng)圓片的次數(shù))18446744073709551615，看來，眾僧們耗盡畢生精力也不可能完成金片的移動(dòng)。 后來，這個(gè)傳說就演變?yōu)闈h諾塔游戲: 1.有三根桿子A,B,C。A桿上有若干碟子 2.每次移動(dòng)一塊碟子,小的只能疊在大的上面 3.把所有碟子從A桿全部移到C桿上 經(jīng)過研究發(fā)現(xiàn)，漢諾塔的破解很簡(jiǎn)單，就是按照移動(dòng)規(guī)則向一個(gè)方向移動(dòng)金片： 如3階漢諾塔的移動(dòng)：A→C,A→B,C→B,A→C,B→A,B→C,A→C 此外，漢諾塔問題也是程序設(shè)計(jì)中的經(jīng)典遞歸問題。 補(bǔ)充：漢諾塔的算法實(shí)現(xiàn)（c++） #include