[算法题] 汉诺塔问题

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

相关文章

来自专栏张善友的专栏

Mix 10 上的asp.net mvc 2的相关Session

Beyond File | New Company: From Cheesy Sample to Social Platform Scott Hansel...

2767
来自专栏张善友的专栏

Miguel de Icaza 细说 Mix 07大会上的Silverlight和DLR

Mono之父Miguel de Icaza 详细报道微软Mix 07大会上的Silverlight和DLR ,上面还谈到了Mono and Silverligh...

2997
来自专栏芋道源码1024

熔断器 Hystrix 源码解析 —— 断路器 HystrixCircuitBreaker

本文主要基于 Hystrix 1.5.X 版本 1. 概述 2. HystrixCircuitBreaker 3. HystrixCircuitBreaker....

5747
来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

3005
来自专栏Ceph对象存储方案

Luminous版本PG 分布调优

Luminous版本开始新增的balancer模块在PG分布优化方面效果非常明显,操作也非常简便,强烈推荐各位在集群上线之前进行这一操作,能够极大的提升整个集群...

3655
来自专栏一个爱瞎折腾的程序猿

sqlserver使用存储过程跟踪SQL

USE [master] GO /****** Object: StoredProcedure [dbo].[sp_perfworkload_trace_s...

2840
来自专栏落花落雨不落叶

canvas画简单电路图

83111
来自专栏陈仁松博客

ASP.NET Core 'Microsoft.Win32.Registry' 错误修复

今天在发布Asp.net Core应用到Azure的时候出现错误InvalidOperationException: Cannot find compilati...

5228
来自专栏飞扬的花生

jsencrypt参数前端加密c#解密

      写程序时一般是通过form表单或者ajax方式将参数提交到服务器进行验证,如何防止提交的请求不被抓包后串改,虽然无法说绝对安全却给非法提交提高了难度...

4219
来自专栏杨龙飞前端

scrollto 到指定位置

2934

扫码关注云+社区