FZU 1064教授のテスト(カトラン数、再帰)

Problem 1064教授のテストAccept:149 Submit:364 Time Limit:1000 mSec Memory Limit:32768 KB
Problem Description
年に一度の大学院生の面接がまた近づいている.福州大学コンピュータ学部は、学生のツリー構造に対する認識をテストし、プログラミング能力を検証するために、面接の内容を、学生たちにノードの個数がm以上のすべての二叉木を番号順に印刷するようにプログラミングするように要求した.ツリー番号のルールは、ノードが1つしかないツリー番号が1です.以下の条件の1つを満たす場合、定義二叉木aの番号はbより大きい:1.aのノード数はbより多い.2.aのノード数がbと等しく、aの左サブツリー番号がbの左サブツリーより大きい場合.3.aのノード数と左サブツリー番号はbと等しく、aの右サブツリー番号はbの右サブツリーより大きい.ツリーのノードは大文字Xで表されます.たとえば、次のようになります.
もちろんmが大きい場合、答えの間違いを検証する仕事も重いので、教授はその中のいくつかの番号の二叉木を抽出するつもりです.彼はあなたにnと番号の二叉木の標準的な答えを生み出すプログラムを作成してもらいたいと思っています.Input
入力データは、複数のデータのグループから構成されます.各セットのデータは、n(1≦n≦10^8)の値を表す整数のみである.入力データはn=0で終了し、このデータは処理しない.Output
各グループのデータについて、1行だけ出力します.つまり、あなたが求めた標準的な答えです.二叉木の出力形式は、(左サブツリー){左サブツリーが空であれば省略}X{ルート}(右サブツリー){右サブツリーが空であれば省略}ここで{...}の内容は説明であり、出力する必要はない.例えば、上図において5番のツリーをX(((X)Xと表すことができる.6番の木は(X)X(X)と表示されます.Sample Input
20 0 Sample Output
((X)X(X))X
カトラン数の応用.再帰で直接出力する.このツリーランキングに基づいて、左サブツリーのノード数とランキング、および右サブツリーのノード数とランキングを決定します.カトラン数のアプリまとめについては、このブログを参考にhttp://blog.csdn.net/dacc123/article/details/50922138

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
long long int a[20];
long long int n;
int tag;
void fun(int num,int n)
{
      if(n==0) return;
      if(n==1) {if(tag==1)cout<<"X";
      else cout<<"(X)";return;}
      int num2=0;
      int i;
      for( i=0;i<20;i++)
      {
          num2+=a[i]*a[n-i-1];
          if(num2>=num)
              break;
      }
      num2-=a[i]*a[n-i-1];
      num-=num2;num--;
      if(n!=tag)
         cout<<"(";
      fun(num/a[n-i-1]+1,i);

         cout<<"X";
      fun(num%a[n-i-1]+1,n-i-1);
       if(n!=tag)
          cout<<")";



}
int main()
{
    a[0]=1;
    for(int i=1;i<20;i++)
        a[i]=(a[i-1]*(4*i-2)/(i+1));
    while(scanf("%lld",&n)!=EOF)
    {
        if(n==0)
            break;

        int i;
        int num3=0;
        for( i=1;i<20;i++)
        {
            num3+=a[i];
            if(num3>=n)
                break;
        }
        num3-=a[i];
        int num2=n-num3;
        tag=i;
        fun(num2,i);
        cout<<endl;



    }
}