複製鏈接
請複製以下鏈接發送給好友

漢諾塔

鎖定
漢諾塔(Tower of Hanoi),又稱河內塔,是一個源於印度古老傳説的益智玩具。大梵天創造世界的時候做了三根金剛石柱子,在一根柱子上從下往上按照大小順序摞着64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。並且規定,在小圓盤上不能放大圓盤,在三根柱子之間一次只能移動一個圓盤。
2020年8月3日,夏焱以33.039秒的成績成功打破6層漢諾塔吉尼斯世界紀錄 [5-7] 
2021年5月16日,陳諾以29.328秒的成績打破了6層漢諾塔吉尼斯世界紀錄 [8] 
中文名
漢諾塔
外文名
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個圓盤全部重新落在一起,宇宙被毀滅是什麼時候呢?
圖1 圖1
讓我們來考慮一下64個圓盤重新摞好需要移動多少次吧。1個的時候當然是1次,2個的時候是3次,3個的時候就用了7次......這實在是太累了。
因此讓我們邏輯性的思考一下吧。
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);
}

算法來源: [4] 

漢諾塔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;
}
算法來源: [3] 

漢諾塔含非遞歸

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

漢諾塔 漢諾塔
簡單的用php實現了漢諾塔問題的求解,使用遞歸調用,但是用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年2月8日,中國西安的夏焱打破了6層漢諾塔項目吉尼斯世界紀錄,用時31.81秒。 [13-14] 
2021年5月16日,中國龍巖的陳諾打破了6層漢諾塔吉尼斯世界紀錄,用時29.328秒。 [9] 
2021年5月16日,中國龍巖的陳諾打破了盲移6層漢諾塔吉尼斯世界紀錄,用時39.74秒。 [10] 
來自中國的蔣振雄於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] 
2022年12月7日,10歲的廈門市開禾小學四年級學生蔡松欽,打破了11.141秒的成績打破“最快時間完成5層漢諾塔(單手)”的世界紀錄。 [16-17] 
張玉芳在2023年2月10日成功完成四層漢諾塔(單手),用時6.352秒 。創“世界最快單手完成四層漢諾塔”世界紀錄。 [18] 
2023年3月,廈門市濱北小學郭弘奕同學以4.305秒單手完成4層漢諾塔的成績,刷新了馬來西亞少年保持的WRCA世界紀錄 [19] 
參考資料
展開全部 收起