汉诺塔问题的解法

问题描述

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置64个金盘(如下图)。游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

解法

• 递归

C++代码

#include <iostream>

using namespace std;

void solve(int,char,char,char );

int main()
{

    solve(4,'A','B','C');
    return 0;
}


void solve(int m,char a,char b,char c)
{
    static int n;
    if(m!=0)
    {
        solve(m-1,a,c,b);
        cout<<"第"<<++n<<"步："<<a<<"->"<<c<<endl;
        solve(m-1,b,a,c);
    }

}

Python代码

n=0
def slove(m,a,b,c):
    global n
    if m!=0:
        slove(m-1,a,c,b)
        n+=1
        print('第{N}步:{fr}->{to}'.format(N=n,fr=a,to=c))
        slove(m-1,b,a,c)

slove(4,'A','B','C')

运行结果：

第1步:A->B
第2步:A->C
第3步:B->C
第4步:A->B
第5步:C->A
第6步:C->B
第7步:A->B
第8步:A->C
第9步:B->C
第10步:B->A
第11步:C->A
第12步:B->C
第13步:A->B
第14步:A->C
第15步:B->C