3145 汉诺塔游戏

3145 汉诺塔游戏

 时间限制: 1 s

 空间限制: 32000 KB

 题目等级 : 白银 Silver

 查看运行结果

题目描述 Description

汉诺塔问题(又称为河内塔问题),是一个大家熟知的问题。在A,B,C三根柱子上,有n个不同大小的圆盘(假设半径分别为1-n吧),一开始他们都叠在我A上(如图所示),你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。

游戏中的每一步规则如下:

1. 每一步只允许移动一个盘子(从一根柱子最上方到另一个柱子的最上方)

2. 移动的过程中,你必须保证大的盘子不能在小的盘子上方(小的可以放在大的上面,最大盘子下面不能有任何其他大小的盘子)

如对于n=3的情况,一个合法的移动序列式:

1 from A to C

2 from A to B

1 from C to B

3 from A to C

1 from B to A

2 from B to C

1 from A to C

给出一个数n,求出最少步数的移动序列

输入描述 Input Description

一个整数n

输出描述 Output Description

第一行一个整数k,代表是最少的移动步数。

接下来k行,每行一句话,N from X to Y,表示把N号盘从X柱移动到Y柱。X,Y属于{A,B,C}

样例输入 Sample Input

3

样例输出 Sample Output

7

1 from A to C

2 from A to B

1 from C to B

3 from A to C

1 from B to A

2 from B to C

1 from A to C

数据范围及提示 Data Size & Hint

n<=10

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 using namespace std;
 5 int tot=0;
 6 void ha1(int n,char a,char c,char b)
 7 {
 8     if(n==0)return;
 9     ha1(n-1,a,b,c);
10     tot++;
11     ha1(n-1,b,c,a);
12 }
13 void ha2(int n,char a,char c,char b)
14 {
15     if(n==0)return;
16     ha2(n-1,a,b,c);
17     tot++;
18     cout<<n<<" from"<<" "<<(char)(a-32)<<" "<<"to"<<" "<<(char)(c-32)<<" "<<endl;
19     ha2(n-1,b,c,a);
20 }
21 int main()
22 {
23     int n;
24     cin>>n;
25     ha1(n,'a','c','b');
26     cout<<tot<<endl;
27     tot=0;
28     ha2(n,'a','c','b');
29     return 0;
30 }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P2966 [USACO09DEC]牛收费路径Cow Toll Paths

    题目描述 Like everyone else, FJ is always thinking up ways to increase his revenue. ...

    attack
  • 1269 匈牙利游戏 2012年CCC加拿大高中生信息学奥赛

    1269 匈牙利游戏 2012年CCC加拿大高中生信息学奥赛 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond...

    attack
  • 25:求特殊自然数

    25:求特殊自然数 总时间限制: 1000ms 内存限制: 65536kB描述 一个十进制自然数,它的七进制与九进制表示都是三位数,且七进制与九进制的三位数码...

    attack
  • js中判断由字符串from和to代表的两个日期的先后关系

    源哥
  • 腾讯产品经理现身说法:to b的产品经理和to c产品经理区别

    用户1756920
  • 「R」数据可视化21: Edge Bunding图

    本文作者蒋刘一琦,自嘲是一个有艺术追求的生信狗,毕业于浙江大学生物信息学专业,目前在复旦大学就读研究生,研究方向为宏基因组。

    王诗翔呀
  • 超详细,Windows系统搭建Flink官方练习环境

    如何快速的投入到Flink的学习当中,很多人在搭建环境过程中浪费了太多的时间。一套一劳永逸的本机Flink开发环境可以让我们快速的投入到Flink的学习中去,将...

    实时计算
  • 快速学习-ERC20 代币合约

    cwl_java
  • 以太坊·代币开发详解

    本文节选自《Netkiller Blockchain 手札》

    netkiller old
  • How to Maintain a Website and Web Server?

    How-to-Maintain-a-Website-and-Web-Server-.png

    用户4822892

扫码关注云+社区

领取腾讯云代金券