华师一附中OI组

标题: 教授的测试（二叉树计数） [打印本页]
作者: admin    时间: 2020-1-29 10:52
标题: 教授的测试（二叉树计数）
一年一度的研究生面试又快要来临了。为了测试学生对树结构的认识，同时也检验他们的编程能力，福州大学计算机系把面试的一项内容定为：要求学生们编程按编号顺序打印出节点个数不少于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{根}(右子树){若右子树为空则省略}
其中{…}中的内容是说明，不必输出。例如，在上图中编号为5的树可表示为X((X)X)；编号为6的树表示为(X)X(X)。
Sample Input
20
0

Sample Output
((X)X(X))X


作者: admin    时间: 2020-1-29 11:05
来一组测试数据
输入
2727
45678
80270
12163
82596
53868849
66951445
95227629
98046525
1154205
0
输出
X((X((X)X))X(((X(X))X)X))
(X(X))X(X((X(X((X(X(X)))X)))X))
((((X(X))X((X)X))X((X(X))X))X)X
(X)X(X((((X((X)X))X)X(X))X))
X(X(X(X(X(X((X((X)X((X)X)))X))))))
X(X(((((X((X)X))X(X))X(X))X)X((X((X(X))X))X(X))))
X(((((X)X)X((X)X(X(X))))X)X(X(X((X)X((X(X))X)))))
(X(X))X(((X)X((X((X)X))X(X(X))))X(((X)X(X))X(X)))
((X)X)X((((X)X(X))X(X((X((X(X))X))X)))X((X)X(X)))
X(X(((X((X)X(X(((X)X)X))))X)X((X)X(X))))
作者: admin    时间: 2020-1-31 11:23
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int catalan[18] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790};
  4. int n;
  5. int nodes(int x)
  6. {
  7.         int sum = 0;
  8.         for (int i=1; i<=17; i++)
  9.         {
  10.                 sum += catalan[i];
  11.                 if (sum>x) return i;
  12.         }
  13.         return 18;
  14. }

  16. void dfs(int node,int x)
  17. {
  18.         if (node==0) return ;
  19.         if (node==1)
  20.         {
  21.                 cout<<"X";
  22.                 return ;
  23.         }
  24.         int temp_no = x;
  25.         int left = 0,right = node - 1;
  26.         while (1)
  27.         {
  28.                 int temp;
  29.                 if ((temp = catalan[left]*catalan[right])>=temp_no)
  30.                         break;
  31.                 temp_no -= temp;
  32.                 left ++;
  33.                 right --;
  34.         }
  35.         if (left>0)
  36.         {
  37.                 cout<<"(";
  38.                 dfs(left,(temp_no - 1)/catalan[right] + 1);
  39.                 cout<<")";
  40.         }
  41.         cout<<"X";
  42.         if (right>0)
  43.         {
  44.                 cout<<"(";
  45.                 dfs(right,(temp_no - 1)%catalan[right] + 1);
  46.                 cout<<")";
  47.         }
  48. }

  50. int main()
  51. {
  52.         cin>>n;
  53.         int node = nodes(n);
  54.         int temp = n;
  55.         for (int i=1; i<node; i++)
  56.                 temp -= catalan[i];
  57.         dfs(node,temp);
  58.         return 0;
  59. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2