汉诺塔问题（递归求解）

编辑：谯胜平      分类：程序与算法      标签：递归      发布时间：2019-09-03      浏览次数：709次

Problem Description

汉诺塔（又称河内塔）问题源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

抽象成模型就是说：

有三根相邻的柱子，标号分别为A、B、C，A柱子按金字塔状叠放着n个不同大小的圆盘，现在要把所有盘子一个一个移动到柱子C上，并且任何时候同一根柱子上都不能出现大盘子在小盘子上方，给出具体的移动方案。

image.png

Input

每个输入文件一组数据。
第一行为一个正整数N（N<=16），表示圆盘的个数。

Output

每行输出一次移动，格式为“X->Y”，表示从柱子X移动最上方的圆盘到柱子Y最上方。

Sample Input 1

1

Sample Output 1

A->C

Sample Input 2

2

Sample Output 2

A->B
A->C
B->C

Sample Input 3

3

Sample Output 3

A->C
A->B
C->B
A->C
B->A
B->C
A->C

1、分析

使用递归方法进行移动。

  • 当有一个盘子时，直接将其从A柱子移动到C柱子；

  • 当有n个盘子时，先将上边n-1个盘子从A移动到中转柱子B上，然后再将最后剩下的一个盘子从A移动到C，最后将B上的n-1个盘子移动到C上，如下图所示。


ubang_20180526183834681_20190903522813.png

2、代码

#include<stdio.h>

//移动函数，n是盘子个数，盘子是从a移动到c上，b是中转盘 
void move(int n, char a, char b, char c){
	if(n == 1){
		//只有一个盘子，直接将盘子从a移动到c即可 
		printf("%c -> %c\n", a, c);
	}else{
		//先将n - 1个盘子从a移动到中转盘b上
		move(n - 1, a, c, b);
		//将剩下的一个盘子从a移动到c上
		printf("%c -> %c\n", a, c); 
		//再将n - 1个盘子从b移动到c上
		move(n - 1, b, a, c); 
	} 
}

int main(){
	int n;
	scanf("%d", &n);
	move(n, 'A', 'B', 'C');
	return 0;
}

参考链接：https://blog.csdn.net/qq_37873310/article/details/80461767



看不清？换一个