您当前的位置： 首页 > 学无止境 > 心得笔记 网站首页心得笔记

036第七章 函数05 c语言完成经典的汉诺塔问题

发布时间：2021-05-01 11:39:51编辑：雪饮阅读（）

 汉诺塔问题是一个比较经典的问题，就是有3个塔，A、B、C，那么A塔上有64个环。每希望达成从A塔移动到C塔上，每次只能移动一个环，而这必须在C塔上以大环在下面，小环在上面进行摆放，可以借用B塔。而对于A塔原本的64个环也都是从最底下向塔顶环的大小逐渐变小进行摆放的。

那么这里环的个数64，其实不重要，重要的是移动环的过程。
汉诺算法分析
算分法析：
第一次移动，要把A柱子上的前n-1个移动到B柱子上；（图1）
第二次移动，直接把A柱子上的最后一个移动到C柱子上；（图2）
第三次移动，把B柱子上的n-1个柱子通过柱子A移动到柱子C上。（图3）

那么具体实现如：
#include <stdio.h>
#include <string.h>
/*
 算法思路：1将 n-1个盘子先放到B座位上
          2.将A座上地剩下的一个盘移动到C盘上
          3、将n-1个盘从B座移动到C座上
*/
//函数声明
void move(char x, char y);
void hannuo(int n,char one ,char two,char three)
{
       //递归截止条件(当只A上面只有一个盘的时候，则直接移动到c塔)
       if(n==1){
        move(one, three);
       }
        else
       {
        /*
        将 n-1个盘子先放到B座位上
        由于每次都是move one=>three,所以移动到b塔，就相当于把传参的最后一个参数设置为当前的two，而上次的two参数位置本次则传递为three
        */
        hannuo(n-1,one ,three,two);
        //将A座上地剩下的一个盘移动到C盘上
        move(one,three);
        /*
        将n-1个盘从B座移动到C座上
        参数传递与上面将n-1移动到b塔类似同理
        */
        hannuo(n-1,two,one,three);
        
       }
}
void move(char x,char y)
{
 static int k=1;
 printf("\n %c--->%c,本次移动数字:%d",x,y,k);
 k++;
}
 
int main()
{
 int n;
 printf("input your number");
 scanf("%d",&n);
 hannuo(n,'A','B','C');
 return 0;
}