算法学习01------汉诺塔Hanoi算法

mac2022-06-30  18

    汉诺塔算法思想与把大象装进冰箱的思想相似。假设有三个柱子A,B,C。要把A柱子上的n个盘子移到C柱子上,始终要求大的盘子在下,小的盘子在上。可以先把A柱子上的n-1个盘子当做整体,先移到辅助柱子B上,接着把A上最大的盘子移到C柱子上,最后把B柱子的盘子移到C柱子上,总共三步骤。

步骤如下:

    1、将A柱子上的n-1个盘子看作是整体,将它移到B柱子上(相当于打开冰箱的门);

    2、将A柱子上最大的也就是最底端的盘子移到C柱子上(相当于把大象装进冰箱); 

    3、将B柱子上的盘子移到C柱子上(相当于关闭冰箱门)

 

步骤虽少,但如何打开冰箱门呢?

A移动到B,需要借助第三个柱子C,才能移动到B,B柱子就作为一个辅助柱子;同样B移动到C也要借助A,A此时就为辅助柱子。

通过递归的思想,可以很好地解决打开冰箱的问题,每一次递归都要走这三个步骤,打开、放大象、关冰箱。

代码实现如下:

#include <iostream>int main(void){    void Hanoi(int n,char A,char B,char C);    int n;    char A='A',B='B',C='C';    std::cout<<"Please input the number of plates :";    std::cin>>n;    std::cout<<"the actions of move are :"<<std::endl;    Hanoi(n,'A','B','C');    return 0;}void Hanoi(int n,char A,char B,char C){    void move(char x,char y);    if(n==1)move(A,C);    else{        Hanoi(n-1,A,C,B);        move(A,C);        Hanoi(n-1,B,A,C);    }}void move(char x,char y){    std::cout<<x<<"--->"<<y<<std::endl;}

运行结果(运行系统:Windows、编译软件:GCC、代码语言:C++)如下:

 

 

 

最新回复(0)