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