游客 Signup | Login
中文 | En

1201 - C语言8.4

通过次数

0

提交次数

0

Time Limit : 1 秒 Memory Limit : 32 MB

用递归的方法输出Hanoi（汉诺）塔问题的解决步骤。汉诺塔问题描述如下：

古代有一个梵塔，塔内有3个座A、B、C。初始时A座上有n个盘子，盘子大小不等，大的在下，小的在上。有一个老和尚想把这n个盘子从A座移动到C座，但是每次只允许移动一个盘子，而且在移动过程中在3个座上需要始终保持大盘在下，小盘在上，在移动过程中可以使用B座。
要求使用递归的方法模拟并输出移动的步骤。

Input

一个正整数n，保证n不超过5。

Output

解决n个盘子的汉诺塔问题的步骤。

每一步一行，在这一行中输出将盘子从一个座移动至另一个的过程。例如移动A座顶部的盘子至C座，则输出A->C。
请注意行尾输出换行。

Examples

Input Format

3

Output Format

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

Solution C

#include<stdio.h>
void hanoi(int n,char x,char y,char z);
void move(char a,char b);

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

void hanoi(int n,char x,char y,char z)
{
	if(n==1)
		move(x,z);
	else
	{
		hanoi(n-1,x,z,y);
		move(x,z);
		hanoi(n-1,y,x,z);
	}
}

void move(char a,char b)
{
	printf("%c->%c\n",a,b);
}

Solution C++

#include <stdio.h>
void move(char x, char y) {
	printf("%c->%c\n", x, y);
}
void hanoi(int n, char a, char b, char c) {
	if (n == 1) {
		move(a, c);
	} else {
		hanoi(n - 1, a, c, b);
		move(a, c);
		hanoi(n - 1, b, a, c);
	}
}
int main() {
	int n;
	scanf("%d", &n);
	hanoi(n, 'A', 'B', 'C');
	return 0;
}
请先登陆