c语言之汉诺塔的实现

思路

汉诺塔问题就是有三个盘子，让我们把其中一个盘子上的东西全移到另一个盘子上，注意的是中途必须满足大东西必须在小东西下面。

这里，我们有A B C三个盘子，假如A上有一个珠子，那我们直接把这一个移到C上就可以；如果有两个珠子，那我们先把上面的珠子移到B上，再把大珠子移到C上，最后把B盘子上的移到C上即A->B A->C B->C。如果有三个，即A->C A->B C->B A->C B->A B->C A->C；通过思考，我们都是把除最大的的其余的放在B上，然后把最大的移到C上。

同时，如果我们要移n个珠子，我们要移动2^n-1次。

代码

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
void move(char pos1, char pos2)
{
	printf(" %c->%c ", pos1, pos2);
}
/*
n是珠子的个数
pos1是起始位置
pos2是中转位置
pos3是目的位置
*/
void Hanoi(int n, char pos1, char pos2, char pos3)
{
	if (n == 1)
	{
		move(pos1, pos3);
	}
	else
	{
		Hanoi(n - 1, pos1, pos3,pos2);
		move(pos1, pos3);
		Hanoi(n - 1, pos2, pos1, pos3);
	}
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	Hanoi(n, 'A', 'B', 'C');
	return 0;
}

运行结果