FZU 1064 教授的測試

Description

一年一度的研究所學生面試又快要來臨了。為了測試學生對樹結構的認識，同時也檢驗他們的程式設計能力，福州大學計算機系把面試的一項内容定為：要求學生們程式設計按編号順序列印出節點個數不少于m的所有二叉樹。

二叉樹編号規則如下：

• 僅有一個節點的樹編号為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

對于每組資料，輸出僅一行，即你求出的标準答案。 

二叉樹的輸出格式為： 

(左子樹){若左子樹為空則省略}X{根}(右子樹){若右子樹為空則省略}

Sample Input

20

Sample Output

((X)X(X))X

問标号是n的二叉樹長什麼樣，直接遞歸來求解，找出是多少個點組成的。

#include<cstdio>
#include<cmath>
#include<map>
#include<iomanip>
#include<iostream>
#include<string>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e3+10;
int n,f[maxn],flag;

void get(int x,int y)
{
  if (!x) return;
  for (int i=0;i<x;i++)
  {
    if (y<=f[i]*f[x-i-1])
    {
      if (flag)
      {
        printf("(");
        get(i,(y-1)/f[x-i-1]+1);
        printf("X");
        get(x-i-1,(y-1)%f[x-i-1]+1);
        printf(")");
      }
      else 
      {
        flag=1;
        get(i,(y-1)/f[x-i-1]+1);
        printf("X");
        get(x-i-1,(y-1)%f[x-i-1]+1);
      }
      break;
    }
    else y-=f[i]*f[x-i-1];
  }
}

int main()
{
  f[0]=f[1]=1;
  for (int i=2;i<maxn;i++)
  {
    f[i]=(long long)f[i-1]*(4*i-2)/(i+1);
  }
  while (~scanf("%d",&n),n) 
  {
    flag=0;
    for (int i=1;i<maxn;i++)
    {
      if (n<=f[i]) {get(i,n); break;}
      else n-=f[i];
    }
    printf("\n");
  }
  return 0;
}