题解Ⅲ级（）

 

时间限制: 1000 ms  空间限制: 262144 KB

题目描述 

  汉诺塔由编号为1到n大小不同的圆盘和三根柱子a,b,c组成，编号越小盘子越小。开始时，这n个圆盘由大到小依次套在a柱上，如图1.6.3所示。要求把a柱上n个圆盘按下述规则移到c柱上：
  ①一次只能移一个圆盘，它必须位于某个柱子的顶部；
  ②圆盘只能在三个柱子上存放；
  ③任何时刻不允许大盘压小盘。
  将这n个盘子用最少移动次数从a柱移动到c柱上，输出每一步的移动方法。

  

输入

  只有一行，一个整数n(1<=n<=20),表示盘子的数量。

输出

  输出若干行，每一行的格式是“步数.Move 盘子编号 from 源柱 to 目标柱”。

样例输入

3
样例输出

1.Move 1 from a to c
2.Move 2 from a to b
3.Move 1 from c to b
4.Move 3 from a to c
5.Move 1 from b to a
6.Move 2 from b to c
7.Move 1 from a to c
数据范围限制

  1<=n<=20

问题分析

  这是一个经典的问题，可以用递归程序解决。

程序说明

  测试数据有毒，看似正确的程序，没有得100分。87.5分居然算通过！！！

  参见参考链接。

要点详解

将共用功能用封装到函数中是一种好的做法。

参考链接：I00014 汉若塔问题的C++程序

得87.5分的C语言程序：

[cpp] view plain copy

#include <stdio.h>  

  

int step;  

  

void hanoi(int depth, char from, char to, char alternate)  

{  

    if(depth == 0)  

        return;  

  

    hanoi(depth-1, from, alternate, to);  

    printf("%d.Move %d from %c to %c\n", step++, depth, from, to);  

    hanoi(depth-1, alternate, to, from);  

}  

  

int main(void)  

{  

    int n;  

  

    scanf("%d", &n);  

  

    step = 1;  

    hanoi(n, 'a', 'c', 'b');  

  

    return 0;  

}