[算法题]汉诺塔问题


问题描述 三个柱子,起初有若干个按大小关系顺序安放的盘子,需要全部移动到另外一个柱子上。移动规则:在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。 移动次数: f(n)=2n -1

解法思路

使用递归算法进行处理。

汉诺塔的算法大概有3个步骤:

(1)把a上的n-1个盘通过c移动到b。

(2)把a上的最下面的盘移到c。

(3)因为n-1个盘全在b上了,所以把b当做a重复以上步骤就好了。

在网上找到一个3阶的汉诺塔递归过程示意图,参考一下。

代码实现

代码

#include<stdio.h>

intstep=0;
voidhanoi(intn,charstart,charassist,charend){
 if(n>=1){
hanoi(n-1,start,end,assist);
printf("move%dfrom%c-->%c
",n,start,end);
step++;
hanoi(n-1,assist,start,end);
}
}

intmain(){
 intn;
scanf("%d",&n);
hanoi(n,'A','B','C');
printf("Totallymove%dsteps
",step);
 return 0;
}

运行结果

Pleaseinputthedisknum:
3
move1fromA-->C
move2fromA-->B
move1fromC-->B
move3fromA-->C
move1fromB-->A
move2fromB-->C
move1fromA-->C
Totallymove7steps
优质内容筛选与推荐>>
1、FPGA作为从机与STM32进行SPI协议通信---Verilog实现
2、git初使用
3、实验
4、从取球问题到含重复的组合问题模板
5、ZOJ3554 A Miser Boss(dp)


长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

    阅读
    好看
    已推荐到看一看
    你的朋友可以在“发现”-“看一看”看到你认为好看的文章。
    已取消,“好看”想法已同步删除
    已推荐到看一看 和朋友分享想法
    最多200字,当前共 发送

    已发送

    朋友将在看一看看到

    确定
    分享你的想法...
    取消

    分享想法到看一看

    确定
    最多200字,当前共

    发送中

    网络异常,请稍后重试

    微信扫一扫
    关注该公众号