[算法题] 汉诺塔问题

问题描述 三个柱子,起初有若干个按大小关系顺序安放的盘子,需要全部移动到另外一个柱子上。移动规则:在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。 移动次数: 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 条评论
登录 后参与评论

相关文章

来自专栏量子位

PyTorch 0.2发布:更多NumPy特性,高阶梯度、分布式训练等

李林 编译整理 量子位 报道 | 公众号 QbitAI Facebook的机器学习框架(之一)PyTorch今天发布了新版本:0.2.0。 这一版本引入了Num...

34515
来自专栏CreateAMind

Curiosity-driven Exploration 好奇心代码阅读

992
来自专栏mwangblog

用遗传算法求函数最大值三:主程序和结果

573
来自专栏AI研习社

问答 | 有没有什么办法让GPU显存不会溢出?

501
来自专栏漫漫深度学习路

pytorch: 常见bug与debug

本博文用来记录自己的 pytorch 踩坑过程,虽然 pytorch 命令式编程,声称容易 debug,可是 代码给出的错误提示可是令人相当头疼,所以在本文中记...

3358
来自专栏xingoo, 一个梦想做发明家的程序员

河内之塔

题目说明:   创世纪时,Benares有一座波罗教塔,是由三只钻石棒所支撑,开始时神在第一根棒子上放置了64个由上至下 依小到大的排列的金盘,并命令僧侣将所有...

1699
来自专栏生信宝典

R语言学习 - 火山图

火山图 火山图用于展示基因表达差异的分布,横轴为Log2 Fold Change,越偏离中心差异倍数越大;纵轴为(-1)*Log10 P_adjust,值越大差...

2487
来自专栏简书专栏

基于Keras+CNN的MNIST数据集手写数字分类

Keras官方github链接:https://github.com/keras-team/keras 官方的口号是Keras: Deep Learning ...

792
来自专栏人工智能

TensorFlow 到底有几种模型格式?

用过 TensorFlow 时间较长的同学可能都发现了 TensorFlow 支持多种模型格式,但这些格式都有什么区别?怎样互相转换?今天我们来一一探索。 1....

9819
来自专栏贾志刚-OpenCV学堂

手撕OpenCV源码之filter2D(一)

在上篇的GaussianBlur中提到,gaussianBlur使用的是filter2D的实现,因此上篇仅仅描述了高斯滤波器的生成细节,并没有针对滤波的计算细节...

841

扫码关注云+社区