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简单递归
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <sstream> #include <cstdio> #include <vector> #include <string> #include <cmath> #include <stack> #include <queue> #include <map> #include <set> #define MAX 0x3f3f3f3f #define fori(a,b) for(int i=a;i<=b;i++) #define forj(a,b) for(int j=a;j<=b;j++) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const double PI = acos(-1); const int M=1e2+10; const int mod=1e9+7; map<ll,ll> ma; int flag[11]={0}; void sortt(int n) { int i; if(n==1) return ; if(flag[n-1]!=1) { sortt(n-1); flag[n-1]=1; cout<<n-1<<" "<<"UP"<<endl; } for(i=n-2;i>=0;i--) { if(flag[i]!=0) { sortt(i); flag[i]=0; cout<<i<<" "<<"DOWN"<<endl; } } return ; } int main() { int n,i; cin>>n; for(i=1;i<=n;i++) flag[i]=1; for(i=n;i>=1;i--) { sortt(i); flag[i]=0; cout<<i<<" "<<"DOWN"<<endl; } return 0; }
