汉诺塔问题-创新互联

• • 汉诺塔问题简介
  • 解题思路
  • 题目及题解

汉诺塔(又称河内塔)问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里
留下了三根金刚石的棒，第一根上面套着64个圆的金片，大的一个在底下，其余一个
比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规
定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。解答
结果请自己运行计算，程序见尾部。面对庞大的数字(移动圆片的次数)15，看来，众僧们
耗尽毕生精力也不可能完成金片的移动。
后来，这个传说就演变为汉诺塔游戏:
1.有三根杆子A,B,C。A杆上有若干碟子
2.每次移动一块碟子,小的只能叠在大的上面
3.把所有碟子从A杆全部移到C杆上

1.如果只有一个金片，则把该金片从源移动到目标棒，结束。
2.如果有n个金片，则把前n-1个金片移动到中转的棒，然后把自己移动到目标棒，最后再把前n-1个移动到目标棒。

题目描述

汉诺塔问题(又称为河内塔问题)，是一个大家熟知的问题。在A，B，C三根柱子上，有n个不同大小的圆盘(假设半径分别为1~n吧)一开始他们都鲁在A上，你的目标是在最少的合法移动步数内将所有盘子从A塔移动到C塔。游戏中的每一步规则如下1每一步只允许移动一个盘子(从一根柱子最上方到另一个柱子的最上方)2.移动的过程中，你必须保证大的盘子不能在小的盘子上方(小的可以放在大的上面，大盘子下面不能有任何其他大小的盘子)给出一个数n，求出最少步数的移动序列

输入

输入盘子数N

输出

输出步数M，接下的M行，按以下格式输出 i 盘子编号，a为柱编号，b为柱编号

输入样例

3

输出样例
7
1 form A to C
2 form A to B
1 form C to B
3 form A to C
1 form B to A
2 form B to C
1 form A to C

题解

#define _CRT_SECURE_NO_WARNINGS 1
#include#includevoid Hanoi(int n, char pos1, char pos2, char pos3);
void move(char pos1,char pos2);
int main()
{int n;
	scanf("%d", &n);
	printf("%.0lf\n", pow(2, n) - 1);
	Hanoi(n, 'A', 'B', 'C');
	return 0;
}
//pos1 起始位置
// pos2 中转位置
// pos3 目的位置
void move(int n,char pos1,char pos2)
{printf("%d form %c to %c\n",n,pos1,pos2 );
}
void Hanoi(int n,char pos1,char pos2,char pos3)
{int count = 0;

	if (n == 1)
	{		move(1,pos1, pos3);//递归结束条件，直接从起始位置至目的位置
	}
	else
	{Hanoi(n - 1, pos1, pos3, pos2);
		move(n,pos1, pos3);
		Hanoi(n - 1, pos2, pos1, pos3);
	}

}

输出截图

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧