九连环
Time Limit: 1000 ms Memory Limit: 65536 KiB
Submit Statistic
Problem Description
不知道大家有没有玩过一个叫做 九连环 的玩具，如下图所示。
如果你不了解九连环，那玄黄就带你领略九连环的奥妙： 九连环是我国传统的民间智力玩具，玩具上面有九个连环套在杆上，目标就是通过一定的方式将九个连环从杆上全部取下来。 玩法是这样的： 1、对每个环，有2种操作：把这个环放到杆上或把这个环从杆上取下 2、你可以随意的对第1个环进行操作 3、如果你想对第i个环(i>1)进行操作，你必须将第i-1个环放在杆上，且必须把前i-2个环从杆上取下
Input
输入一个整数n ( 0<n<10 )，代表杆上面的连环个数。
Output
输出把所有连环取下来的最少操作步骤，每一步占一行，输出一个整数i和操作”UP”或者”DOWN”，代表将第i个环放到杆上或从杆上取下来，整数和操作用空格分开。详情见示例输出。
Sample Input
4
Sample Output
2 DOWN
1 DOWN
4 DOWN
1 UP
2 UP
1 DOWN
3 DOWN
1 UP
2 DOWN
1 DOWN
Hint
Source
玄黄
代码如下：
//9 连环问题
#include<stdio.h>
#include<stdlib.h>
void down(int n) ;
void up(int n) ;
void down(int n )
{ if(n>2)
down(n-2) ;//要把第n个环都拿掉，首先要把前n-2个环拿掉（开始都在棒上，所以第n-1个环肯定在棒上）
printf("%d DOWN\n",n) ;
if(n>2)
up(n-2) ;//为了第n-1个环可以从棒上拿下要保证n-2个环在棒上
if(n>1)
down(n-1) ;//开始对滴n-1个环进行操作
}
void up(int n)//往上面拿环同上分析
{
if(n>1)
up(n-1) ;
if(n>2)
down(n-2) ;
printf("%d UP\n",n) ;
if(n>2)
up(n-2) ;
}
int main()
{
int n ;
scanf("%d",&n) ;
down(n) ;//把n环全部都拿掉
return 0 ;
}
/***************************************************
****************************************************/
