C++| n阶汉诺塔问题(递归)

//the problem of Hanoi

#include <iostream>

using namespace std;

void Move(int n, char x, char y)

{

cout<<"make "<<n<<" move to "<<y<<" from "<<x<<endl;

}

void Hannoi(int n, char a, char b, char c)

{

    if(n == 1)

Move(1, a, c);

    else

    {

Hannoi(n-1, a, c, b);

Move(n, a, c);

Hannoi(n-1, b, a, c);

    }

}

int main(int argc, const char * argv[]) {

int num;

cout<<"input your the floor of Hanoi:";

cin>>num;

Hannoi(num, 'a', 'b', 'c');

cout<<"step finished."<<endl;

    return 0;

}

问题描述：

X, Y, Z 是三个塔座，开始时有 n 个盘子依其半径大小套在柱子 X 上，其中半径大的在下面。现要将X上的圆盘移到Z上，并仍按同样顺序叠置。

移动规则：

1：每次只能移动1个圆盘 2：任何时刻都不允许将半径大的圆盘压在半径小的圆盘之上

以上程序中所用到的知识点如下：

• 递归

#一个过程直接或间接地调用自己 #实现容易，效率较低

• n阶Hanoi问题算法：

procedure Hanoi(n, X, Y, Z) if(n = 1)  then move(X, Z) else Hanoi(n-1, X, Z, Y) move(X, Z) Hanoi(n-1, Y, X, Z) endif END Hanoi