Hanoi(汉诺塔)问题

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

其实n-1层A->B和n-1层B->C这两步只是出发地、借助点和目的地不一样，但是方法和所需步数就是一样的。
也就是其实都可以分解为
如同当两个盘子时那样:

先把第1层盘子从A->B、
再把第2层盘子从A->C、
再把原来从A->B的那1层盘子从B->C

图片说明

#include <stdio.h>

static int i=0;    

void hanoi(int n, char chufadi, char jiezhudian, char mudidi)     
{                                                //假设一开始针对n层盘子chufadi为A,jiezhudian为B(jiezhudian像跳台或者辅助器一样),mudidi为C 
    void move(char chufadi, char mudidi);        // ^
    if(n<=0)                //防止n为0的情况      // |
    return ;                                     // |
                                                 // |
    if(n==1)                                     // |
    move( chufadi, mudidi);                      // |
    else{                                        // |
                                                 // |
    hanoi(n-1, chufadi, mudidi, jiezhudian);    // 这时候针对n-1层盘子,chufadi还是原来的chufadi(A)，但是jiezhudian由原来的jiezhudian(B)变为了原来的mudidi(C) 
    move( chufadi, mudidi);                        //这时候需要将第n层盘子就从原来的chufadi(A)移到mudidi(C) 
    hanoi(n-1, jiezhudian, chufadi, mudidi);    //这时候针对n-1层已经移到B的盘子其实移动的方法和第15行几乎一样 

    }
}

void move(char chufadi, char mudidi)
{
    printf("%d:%c-->%c\n",i+1,chufadi,mudidi);
    i++;
}

int main(int argc,char const *argv[])
{
    int n;
    printf("选择在A上的盘子个数:\n");
    scanf("%d",&n);
    printf("\n");
    hanoi(n,'A','B','C');
    printf("需要移动盘子的总次数:%d",i);
    return 0;
}

include <stdio.h>

static int i=1; //记录移动所需的次数

void hanoi(int n,char one,char two,char three) /这里抽象的很，需要理解为将n个盘子从one座移到three座(借助two座)的过程【其中one、two、three只是个形式位置】
----后面的hanoi(n-1,one,three,two)其实看成开头的定义hanoi(int n,char one,char two,char three)的形式样子
也就是one(实际位置如A)借助three(实际位置如C)移动到two(实际位置如B).下面的(3)其实和上面介绍的方法一样
one、two、three只是个形式位置，但A、B、C才是实际位置/
{
void move(char x,char y);
if(n==1)
move(one,three); //递归的关键点，跟two没什么关系，主要为one→three
else
{
hanoi(n-1,one,three,two); //(1).将A座上的n-1个盘(借助C)座先移动到B座上【这是针对总的情况】
move(one,three); //(2).把A座剩下的一个盘直接移到C座上【这是针对总的情况】
hanoi(n-1,two,one,three); //(3).将n-1个盘从B座(借助A)座移动到C座上【这是针对总的情况】
}
}
//其实(1)和(3)的移动方法一样，只是座的名字不同了( 总的情况移动方法和(1)、(3)也是类似的)
void move(char x,char y)
{
printf("%d:%c-->%c\n",i,x,y); //主力输出点!
i++;
}

int main()
{
int n;
printf("input the number of diskes:");
scanf("%d",&n); //输入盘子个数
printf("The step to move %d diskes:\n",n);
hanoi(n,'A','B','C');
printf("The total number of times is %d",i-1);
return 0;
}