-
漢諾塔
鎖定
- 中文名
- 漢諾塔
- 外文名
- Tower of Hanoi
- 別 名
- 河內塔
- 發明人
- 愛德華·盧卡斯
- 來 源
- 印度古老傳説
漢諾塔背景介紹
漢諾塔由來
法國數學家愛德華·盧卡斯曾編寫過一個印度的古老傳説:在世界中心貝拿勒斯(在印度北部)的聖廟裏,一塊黃銅板上插着三根寶石針。印度教的主神梵天在創造世界的時候,在其中一根針上從下到上地穿好了由大到小的64片金片,這就是所謂的漢諾塔。不論白天黑夜,總有一個僧侶在按照下面的法則移動這些金片:一次只移動一片,不管在哪根針上,小片必須在大片上面。僧侶們預言,當所有的金片都從梵天穿好的那根針上移到另外一根針上時,世界就將在一聲霹靂中消滅,而梵塔、廟宇和眾生也都將同歸於盡。
不管這個傳説的可信度有多大,如果考慮一下把64片金片,由一根針上移到另一根針上,並且始終保持上小下大的順序。這需要多少次移動呢?這裏需要遞歸的方法。假設有n片,移動次數是f(n).顯然f(1)=1,f(2)=3,f(3)=7,且f(k+1)=2*f(k)+1。此後不難證明f(n)=2^n-1。n=64時,
假如每秒鐘一次,共需多長時間呢?一個平年365天有31536000秒,閏年366天有31622400秒,平均每年31557600秒,計算一下:
18446744073709551615秒
計算的python程序:
def f(n): if n==0: return 0 else: return 2*f(n-1)+1 x=int(input("請輸入片的個數:")) print("需要移動",f(x),"次")
請輸入片的個數:64
需要移動 18446744073709551615 次
這表明移完這些金片需要5845.42億年以上,而地球存在不過45億年,太陽系的預期壽命據説也就是數百億年。真的過了5845.42億年,不説太陽系和銀河系,至少地球上的一切生命,連同梵塔、廟宇等,都早已經灰飛煙滅。
漢諾塔印度傳説
和漢諾塔故事相似的,還有另外一個印度傳説
[1]
:舍罕王打算獎賞國際象棋的發明人──宰相西薩·班·達依爾。國王問他想要什麼,他對國王説:“陛下,請您在這張棋盤的第1個小格裏賞給我一粒麥子,在第2個小格里給2粒,第3個小格給4粒,以後每一小格都比前一小格加一倍。請您把這樣擺滿棋盤上所有64格的麥粒,都賞給您的僕人吧!”國王覺得這個要求太容易滿足了,就命令給他這些麥粒。當人們把一袋一袋的麥子搬來開始計數時,國王才發現:就是把全印度甚至全世界的麥粒全拿來,也滿足不了那位宰相的要求。
那麼,宰相要求得到的麥粒到底有多少呢?總數為
1+2+2^2 + … +2^63=2^64-1
等於移完漢諾塔所需的步驟數。我們已經知道這個數字有多麼大了。人們估計,全世界兩千年也難以生產這麼多麥子!
漢諾塔相關預言
有預言説,這件事完成時宇宙會在一瞬間閃電式毀滅。也有人相信婆羅門還在一刻不停地搬動着圓盤。
漢諾塔所需時間
漢諾塔宇宙壽命
如果移動一個圓盤需要1秒鐘的話,等到64個圓盤全部重新落在一起,宇宙被毀滅是什麼時候呢?
因此讓我們邏輯性的思考一下吧。
3個的時候能夠移動最大的3盤時如圖1所示。
到此為止用了7次。
接下來如右圖,在上面再放上3個圓盤時還要用7次(把3個圓盤重新放在一起需要的次數)。
因此,4個的時候是
“3個圓盤重新摞在一起的次數”+1次+“3個圓盤重新摞在一起需要的次數”
=2x“3個圓盤重新摞在一起的次數”+1次
=15次。
那麼,n個的時候是
2x“(n-1)個圓盤重新摞在一起的次數”+1次。
由於1 個的時候是1次,結果n個的時候為(2的n次方減1)次。
1個圓盤的時候 2的1次方減1
2個圓盤的時候 2的2次方減1
3個圓盤的時候 2的3次方減1
4個圓盤的時候 2的4次方減1
5個圓盤的時候 2的5次方減1
........
n個圓盤的時候 2的n次方減1
也就是説,n=64的時候是(2的64次方減1)次。
因此,如果移動一個圓盤需要1秒的話,宇宙的壽命=2的64次方減1(秒)
2的64次方減1到底有多大呢?動動計算器,答案是一個二十位的數字約是1.84467440*10^19
用一年=60秒x60分x24小時x365天來算的話,大約有5800億年吧。
太陽及其行星形成於50億年前,其壽命約為100億年。
漢諾塔問題在數學界有很高的研究價值,而且還在被一些數學家們所研究。
也是我們所喜歡玩的一種益智遊戲,它可以幫助開發智力,激發我們的思維。
漢諾塔經典題目
有三根相鄰的柱子,標號為A,B,C,A柱子上從下到上按金字塔狀疊放着n個不同大小的圓盤,要把所有盤子一個一個移動到柱子B上,並且每次移動同一根柱子上都不能出現大盤子在小盤子上方,請問至少需要多少次移動,設移動次數為H(n)。
[2]
首先我們肯定是把上面n-1個盤子移動
到柱子C上,然後把最大的一塊放在B上,最後把C上的所有盤子移動到B上,由此我們得出表達式:
H⑴ = 1
H(n) = 2*H(n-1)+1 (n>1)
那麼我們很快就能得到H(n)的一般式:
H(n) = 2^n - 1 (n>0)
並且這種方法的確是最少次數的,證明非常簡單,可以嘗試從2個盤子的移動開始證,你可以試試。
進一步加深問題(解法原創*_*):
假如現在每種大小的盤子都有兩個,並且是相鄰的,設盤子個數為2n,問:⑴假如不考慮相同大小盤子的上下要多少次移動,設移動次數為J(n);⑵只要保證到最後B上的相同大小盤子順序與A上時相同,需要多少次移動,設移動次數為K(n)。
⑴中的移動相當於是把前一個問題中的每個盤子多移動一次,也就是:
J(n) = 2*H(n) = 2*(2^n - 1)= 2^(n+1)-2
在分析⑵之前
,我們來説明一個現象,假如A柱子上有兩個大小相同的盤子,上面一個是黑色的,下面一個是白色的,我們把兩個盤子移動到B上,需要兩次,盤子順序將變成黑的在下,白的在上,然後再把B上的盤子移動到C上,需要兩次,盤子順序將與A上時相同,由此我們歸納出當相鄰兩個盤子都移動偶數次時,盤子順序將不變,否則上下顛倒。
現在回到最開始的問題,n個盤子移動,上方的n-1個盤子總移動次數為2*H(n-1),所以上方n-1個盤子的移動次數必定為偶數次,最後一個盤子移動次數為1次。
討論問題⑵,
綜上兩點,可以得出,要把A上2n個盤子移動到B上,首先可以得出上方的2n-2個盤子必定移動偶數次,所以順序不變,移動次數為:
J(n-1) = 2^n-2
然後再移動倒數第二個盤子,移動次數為2*J(n-1)+1 = 2^(n+1)-3,
最後移動最底下一個盤子,所以總的移動次數為:
K(n) = 2*(2*J(n-1)+1)+1 = 2*(2^(n+1)-3)+1 = 2^(n+2)-5
開天闢地的神勃拉瑪在一個廟裏留下了三根金剛石的棒,第一根上面套着64個圓的金片,最大的一個在底下,其餘一個比一個小,依次疊上去,廟裏的眾僧不倦地把它們一個個地從這根棒搬到另一根棒上,規定可利用中間的一根棒作為幫助,但每次只能搬一個,而且大的不能放在小的上面。計算結果非常恐怖(移動圓片的次數)大約是1.84467440*10^19,眾僧們即便是耗盡畢生精力也不可能完成金片的移動了。
漢諾塔算法介紹
其實算法非常簡單,當盤子的個數為n時,移動的次數應等於2^n – 1(有興趣的可以自己證明試試看)。後來一位美國學者發現一種出人意料的簡單方法,只要輪流進行兩步操作就可以了。首先把三根柱子按順序排成品字型,把所有的圓盤按從大到小的順序放在柱子A上,根據圓盤的數量確定柱子的排放順序:若n為偶數,按順時針方向依次擺放 A B C;
若n為奇數,按順時針方向依次擺放 A C B。
⑴按順時針方向把圓盤1從現在的柱子移動到下一根柱子,即當n為偶數時,若圓盤1在柱子A,則把它移動到B;若圓盤1在柱子B,則把它移動到C;若圓盤1在柱子C,則把它移動到A。
⑵接着,把另外兩根柱子上可以移動的圓盤移動到新的柱子上。即把非空柱子上的圓盤移動到空柱子上,當兩根柱子都非空時,移動較小的圓盤。這一步沒有明確規定移動哪個圓盤,你可能以為會有多種可能性,其實不然,可實施的行動是唯一的。
⑶反覆進行⑴⑵操作,最後就能按規定完成漢諾塔的移動。
所以結果非常簡單,就是按照移動規則向一個方向移動金片:
如3階漢諾塔的移動:A→C,A→B,C→B,A→C,B→A,B→C,A→C
漢諾塔程序實現
漢諾塔Python
def hanoi(n, a, b, c): if n == 1: print(a, '-->', c) else: hanoi(n - 1, a, c, b) print(a, '-->', c) hanoi(n - 1, b, a, c) # 調用 hanoi(5, 'A', 'B', 'C')
漢諾塔C語言
#include <stdio.h> #include <windows.h> void Hanoi(int n, char a,char b,char c); void Move(int n, char a, char b); int count; int main() { int n=8; printf("漢諾塔的層數:\n"); scanf(" %d",&n); Hanoi(n, 'A', 'B', 'C'); Sleep(20000); return 0; } void Hanoi(int n, char a, char b, char c) { if (n == 1) { Move(n, a, c); } else { Hanoi(n - 1, a, c, b); Move(n, a, c); Hanoi(n - 1, b, a, c); } } void Move(int n, char a, char b) { count++; printf("第%d次移動 Move %d: Move from %c to %c !\n",count,n,a,b); }
漢諾塔C++
#include <iostream> using namespace std; void hanoi(int num, char a, char b, char c, int* all); void move(char x, char y, int* all); int main(void) { int number, all = 0; cout << "請輸入移盤數:"; cin >> number; hanoi(number, 'A', 'B', 'C', &all); cout << "共需" << all << "步。\n"; return 0; } void hanoi(int num, char a, char b, char c, int* all) { if (num == 1) { move(a, c, all); } else { hanoi(num - 1, a, c, b, all); move(a, c, all); hanoi(num - 1, b, a, c, all); } } void move(char x, char y, int* all) { cout << x << "-->" << y << "\n"; *all += 1; }
漢諾塔含非遞歸
document.write("遞歸:</br>"); mov(3,"A","B","C"); document.write("非遞歸:</br>"); mov_stack(3,"A","B","C"); function mov(i,A,B,C){ if(i==1){ document.write(A + "->" + C + "</br>" ); } else{ mov(i-1,A,C,B); document.write(A + "->" + C + "</br>" ); mov(i-1,B,A,C); } } function mov_stack(n,A,B,C){ var stack = []; var len = parseInt(Math.pow(2,n)); for(let key = 0;key < len;key++){ var obj = {}; stack.push(obj); } var index = 0; //分配堆棧空間 stack[index].i = n; stack[index].A = A; stack[index].B = B; stack[index].C = C; //堆棧初始化 index++; //push while(index!=0){ if(stack[index - 1].i > 1){ stack[index].i = stack[index - 1].i - 1; stack[index].A = stack[index - 1].A; stack[index].B = stack[index - 1].C; stack[index].C = stack[index - 1].B; index++; //if(i>1) push } else{ document.write(stack[index - 1].A + "->" + stack[index - 1].C + "</br>"); //if(i == 1) show index--; //pop if(index==0){ break; } if(stack[index - 1].i == stack[index - 2].i)//是否為第二個 { while(index>1 && stack[index - 1].i == stack[index - 2].i)//pop { index -= 2; } if(index==0){ break; } } document.write(stack[index - 1].A + "->" + stack[index - 1].C + "</br>"); stack[index].i = stack[index - 1].i; stack[index].A = stack[index - 1].B; stack[index].B = stack[index - 1].C; stack[index].C = stack[index - 1].A; index++; /* push 因為 A B C B A C 所以 A C B B C A */ } } }
漢諾塔遞歸
#include <iostream> using namespace std; template<int n> void hanoi(char a, char b, char c){ hanoi<n - 1>(a, c, b); printf("%c -> %c\n", a, c); hanoi<n - 1>(b, a, c); } template<> void hanoi<1>(char a, char b, char c){ printf("%c -> %c\n", a, c); } //////////////////////////////////////////////// template<int n, char a, char b, char c> class hanoi1{ public: static int hanoi(){ hanoi1<n-1, a, c, b>::hanoi(); printf("%c -> %c\n", a, c); hanoi1<n-1, b, a, c>::hanoi(); } }; template<char a, char b, char c> class hanoi1<1, a, b ,c>{ public: static int hanoi(){ printf("%c -> %c\n", a, c); } }; int main(){ #define N 4 cout<<"類模板偏特化:"; hanoi1<N,'A','B','C'>::hanoi(); cout<<endl; cout<<"函數模板全特化:"; hanoi<3>('A','B','C'); exit(0); }
漢諾塔C#
using System; class HANOI { private static int time = 0; public static void Main(string[] args) { Hanoi(3, "x", "y", "z"); Console.WriteLine(time + " Times"); Console.ReadKey(); } public static void Hanoi(int n, string x, string y, string z) { if (n == 1) { Console.WriteLine(x + "--->" + z); time++; return; } Hanoi(n - 1, x, z, y); Hanoi(1, x, y, z); Hanoi(n - 1, y, x, z); } }
漢諾塔Java
public class Hanoi { /** * * @param n 盤子的數目 * @param origin 源座 * @param assist 輔助座 * @param destination 目的座 */ public void hanoi(int n, char origin, char assist, char destination) { if (n == 1) { move(origin, destination); } else { hanoi(n - 1, origin, destination, assist); move(origin, destination); hanoi(n - 1, assist, origin, destination); } } // Print the route of the movement private void move(char origin, char destination) { System.out.println("Direction:" + origin + "--->" + destination); } public static void main(String[] args) { Hanoi hanoi = new Hanoi(); hanoi.hanoi(3, 'A', 'B', 'C'); } }
漢諾塔php
漢諾塔主要是有三個塔座X,Y,Z,要求將三個大小不同,依小到大編號為1,2.....n的圓盤從X移動到塔座Z上,要求
(1):每次只能移動一個圓盤
(2):圓盤可以插到X,Y,Z中任一塔座上
(3):任何時候不能將一個較大的圓盤壓在較小的圓盤之上
主要是運用了遞歸的思想,這裏使用php做個簡單的實現......
<?php function hanoi($n,$x,$y,$z){ if($n==1){ move($x,1,$z); }else{ hanoi($n-1,$x,$z,$y); move($x,$n,$z); hanoi($n-1,$y,$x,$z); } } function move($x,$n,$z){ echo'movedisk'.$n.'from'.$x.'to'.$z.'<br>'; } hanoi(10,'x','y','z'); ?>
漢諾塔pascal
var m:integer; procedure move(getone,putone:char); begin writeln(getone,'->',putone) end; procedure hanoi(n:integer;one,two,three:char); begin if n=1 then move(one,three) else begin hanoi(n-1,one,three,two); move(one,three); hanoi(n-1,two,one,three) end end; begin readln(m); write('the step to moving disks:'); writeln; hanoi(m,'A','B','C') end.
漢諾塔Lua
function hanoi(num, a,b,c) if (num == 1) then print(a .."-->"..c) else hanoi(num-1, a,c,b) print(a .."-->"..c) hanoi(num-1, b,a,c) end end hanoi(3,'A','B','C')
漢諾塔易語言
子程序 漢諾塔盤子運動
.參數 盤子數,整數型
.參數 柱子甲,文本型
.參數 柱子乙,文本型
.參數 柱子丙,文本型
.如果 (盤子數 = 1)
' 如果只有一個盤,則直接將它從柱子一移動到柱子三
移動 (1,柱子甲,柱子丙)
.否則
' 把1 ~ n - 1個盤從柱子一移動到柱子二,用柱子三作為中轉
漢諾塔盤子運動 (盤子數 - 1,柱子甲,柱子丙,柱子乙)
' 把第n個盤從柱子一移動到柱子三
移動 (盤子數,柱子甲,柱子丙)
' 把1 ~ n - 1個盤從柱子二移動到柱子三,用柱子一作為中轉
漢諾塔盤子運動 (盤子數 - 1,柱子乙,柱子甲,柱子丙)
.如果結束
.子程序 移動
.參數 盤子號,整數型
.參數 甲柱子,文本型
.參數 乙柱子,文本型
路徑 = 路徑 + “步驟” + 到文本 (步驟) + “:” + “把” + 到文本 (盤子號) + “號圓盤從柱子 ” + 甲柱子 + “ 移動到” + 乙柱子 + “上 ” + #換行符
步驟 = 步驟 + 1
.子程序 _計算圖形按鈕_被單擊
.局部變量 盤子總數,整數型
.局部變量 現在柱子,文本型
.局部變量 中間柱子,文本型
.局部變量 目標柱子,文本型
' 把盤子編輯框.內容傳給現在柱子
現在柱子 = 盤子編輯框.內容
' 把中間編輯框.內容傳給中間柱子
中間柱子 = 中間編輯框.內容
' 把目標編輯框.內容傳給目標柱子
目標柱子 = 目標編輯框.內容
.如果真 (到數值 (現在柱子) ≤ 0 或 到數值 (中間柱子) ≤ 0 或 到數值 (目標柱子) ≤ 0 或 到數值 (個數編輯框.內容) ≤ 0 或 到數值 (個數編輯框.內容) > 10)
信息框 (“柱子或圓盤數量只能是大於0小於10的數字!”,#錯誤圖標,“出現錯誤了:”)
返回
.如果真結束
盤子總數 = 到數值 (個數編輯框.內容)
結果編輯框.內容 = “”
路徑 = “”
' 首次調用漢諾塔盤子運動程序
漢諾塔盤子運動 (盤子總數,現在柱子,中間柱子,目標柱子)
結果編輯框.內容 = 路徑
步驟 = 1
漢諾塔世界紀錄
2020年8月3日,中國西安的夏焱以33.039秒的成績成功打破6層漢諾塔吉尼斯世界紀錄。
[5-7]
來自中國的蔣振雄於2021年5月9日在廈門市舉辦的世界紀錄認證官方挑戰中成功完成5層漢諾塔,用時17.012秒。經世界紀錄認證(WRCA)官方審核,蔣振雄成功創造“最快時間完成5層漢諾塔”世界紀錄。
[11]
來自中國的陳明澤於2021年5月9日在廈門市舉辦的世界紀錄認證官方挑戰中成功完成7層漢諾塔,用時1分14.933秒。經世界紀錄認證(WRCA)官方審核,陳明澤成功創造“最快時間完成7層漢諾塔”世界紀錄。
[12]
任婕在2022年11月3日成功完成五層漢諾塔(單手),用時14.94秒。
[15]
- 參考資料
-
- 1. 棋盤麥粒問題 .百度百科[引用日期2015-01-26]
- 2. 漢諾塔問題 .百度百科[引用日期2020-02-15]
- 3. 譚浩強.C++程序設計(第三版)題解與上機指導:清華大學出版社,2015:40-43
- 4. 譚浩強.C程序設計(第五版):清華大學出版社,2017:185-189
- 5. 慕了慕了!小夥新年收到吉尼斯世界紀錄認證 .新浪網 作者 新華網[引用日期2022-01-25]
- 6. 西安#小夥新年收到吉尼斯世界紀錄認證# .新浪網 作者華商網[引用日期2022-01-25]
- 7. 漢諾塔玩出極致 西安小夥創吉尼斯世界紀錄 - 陝西網絡廣播電視台 .陝西網絡廣播電視台[引用日期2022-01-25]
- 8. Fastest time to solve a 6 level Tower of Hanoi | 吉尼斯世界紀錄 .吉尼斯世界紀錄官網[引用日期2022-03-16]
- 9. Fastest time to solve a 6 level Tower of Hanoi | 吉尼斯世界紀錄 .吉尼斯世界紀錄官網[引用日期2022-03-18]
- 10. Fastest time to solve a 6 level Tower of Hanoi blindfolded | 吉尼斯世界紀錄 .吉尼斯世界紀錄官網[引用日期2022-03-18]
- 11. 最快時間完成5層漢諾塔-WRCA官方|世界紀錄認證||世界影響力評審委員會|世界紀錄申報|世界紀錄認證申報|世界影響力評審|世界影響力申報 .世界紀錄官方[引用日期2022-03-20]
- 12. 最快時間完成7層漢諾塔-WRCA官方|世界紀錄認證||世界影響力評審委員會|世界紀錄申報|世界紀錄認證申報|世界影響力評審|世界影響力申報 .吉尼斯世界紀錄官網[引用日期2022-03-20]
- 13. 《請吃飯的姐姐》黃貫中朱茵隔空秀恩愛,20年前情侶歌之迷被揭開 藍天下-浙江衞視官網 .藍天下-浙江衞視官網 .藍天下浙江衞視官方網站[引用日期2022-07-25]
- 14. 《請吃飯的姐姐》第2021-08-27期請吃飯的姐姐之蔡少芬扳手腕笑倒宋雨琦 朱茵黃貫中高級秀恩愛-綜藝節目-完整版視頻在線觀看-愛奇藝 .浙江衞視《請吃飯的姐姐》第2021-08-27期 第18分46秒最右邊的圖片是雙人復原魔方紀錄證書 下方正中央的是漢諾塔紀錄證書 18分50秒是漢諾塔紀錄詳情[引用日期2022-07-25]
- 15. SSZ國際聯賽 國際排名 魔方比賽 腦力運動 魔方段位認證 口才 美術 書法 繞口令 .SSZ國際聯賽官網[引用日期2022-12-04]
- 16. 11.141秒單手移完5層漢諾塔 廈門10歲男孩刷新世界紀錄 .光明網[引用日期2022-12-09]
- 17. 廈門10歲男孩刷新世界紀錄 .廈門網[引用日期2022-12-09]
- 18. SSZ國際聯賽 國際排名 魔方比賽 腦力運動 魔方段位認證 口才 美術 書法 繞口令 .SSZ國際聯賽[引用日期2023-02-16]
- 19. 廈門8歲男孩打破世界紀錄 4.305秒單手完成4層漢諾塔 .台海網.2023-03-09[引用日期2023-03-09]
- 收起