[算法题] 汉诺塔问题

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

解法思路

使用递归算法进行处理。

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

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

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

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

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

代码实现

代码

#include <stdio.h>

int step = 0;
void hanoi(int n, char start, char assist, char end){
 if(n>=1){
        hanoi(n-1, start, end, assist);
        printf("move %d from %c --> %c \n", n, start, end);
        step++;
        hanoi(n-1, assist, start, end);
    }
}

int main(){
 int n;
    scanf("%d", &n);
    hanoi(n, 'A', 'B', 'C');
    printf("Totally move %d steps\n", step);
 return 0;
}

运行结果

Please input the disk num:
3
move 1 from A --> C
move 2 from A --> B
move 1 from C --> B
move 3 from A --> C
move 1 from B --> A
move 2 from B --> C
move 1 from A --> C
Totally move 7 steps

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

一文教你如何用神经网络识别验证码!

AI 研习社按:本文作者 Slyne_D,原载于作者个人博客,雷锋网 AI 研习社已获授权。文中相关链接详见文末“阅读原文”。 这是去年博主心血来潮实现的一个小...

2733
来自专栏应用案例

关于机器学习,这可能是目前最全面最无痛的入门路径和资源!

之前搞机器学习的那帮人都喜欢用Python,所以Python慢慢就积攒了很多优秀的机器学习库,所谓的库,你就理解为别人封装好的一些具有某些功能的模块,我们可以通...

2397
来自专栏人工智能LeadAI

TensorFlow从0到1 | 第十二章:TensorFlow构建3层NN玩转MNIST

上一篇 11 74行Python实现手写体数字识别展示了74行Python代码完成MNIST手写体数字识别,识别率轻松达到95%。这算不上一个好成绩,不过我并不...

34813
来自专栏大数据风控

R中时间序列分析-趋势预测ARIMA

时间序列预测(time series forecasting) ARIMA模型(Autoregressive Integrated Moving Average...

21910
来自专栏机器学习之旅

python开发:特征工程代码模版(一)

作为一个算法工程师,我们接的业务需求不会比数据分析挖掘工程师少,作为一个爱偷懒的人,总机械重复的完成一样的预处理工作,我是不能忍的,所以在最近几天,我正在完善一...

712
来自专栏LET

精度,Precision

1837
来自专栏刘明的小酒馆

图片相似检测:三行代码实现

检查两个图片的相似度,一个简单而快速的算法:感知哈希算法(Perceptual Hash),通过某种提取特征的方式为每个图片计算一个指纹(哈希),这样对比两个图...

2415
来自专栏WOLFRAM

用Wolfram语言绘制一笔画环形迷宫

2084
来自专栏Python攻城狮

Python数据科学(六)- 资料清理(Ⅰ)1.Pandas1.资料筛选2.侦测遗失值3.补齐遗失值

成功爬取到我们所需要的数据以后,接下来应该做的是对资料进行清理和转换, 很多人遇到这种情况最自然地反应就是“写个脚本”,当然这也算是一个很好的解决方法,但是,p...

983
来自专栏marsggbo

汉诺塔问题算法介绍

其实算法非常简单,当盘子的个数为n时,移动的次数应等于2^n – 1(有兴趣的可以自己证明试试看)。后来一位美国学者发现一种出人意料的简单方法,只要轮流进行两步...

1769

扫码关注云+社区