poj1741，POJ 1095 Trees Made to Order

2023-11-09 阅读 26 评论 0

摘要：閑來無事，跑到POJ上找找水題，好久不寫C的代碼，感覺生疏了。 View Code 1 #include<stdio.h> 2 #include<string.h> 3 #define MAXN 19 4 int num[MAXN]; 5 6 void OutputBinaryTree(int n, int k, bool s) { 7 if (n == 0) return;

閑來無事，跑到POJ上找找水題，好久不寫C的代碼，感覺生疏了。

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define MAXN 19
 4 int num[MAXN];
 5 
 6 void OutputBinaryTree(int n, int k, bool s) {
 7     if (n == 0) return;
 8     int i, j, sum;
 9     for (i = sum = 0, j=num[n-1]; sum + j < k; sum += j, ++i, j = num[i] * num[n-1-i]) {}
10     k -= sum;
11     if(s) printf("(");
12     OutputBinaryTree(i, (k + num[n-1-i] - 1) / num[n-1-i], true);
13     printf("X");
14     j =  k % num[n-1-i];
15     OutputBinaryTree(n-1-i, j == 0 ? num[n-1-i] : j, true);
16     if(s) printf(")");
17 }
18 
19 int main(){
20     int i, j, k;
21     memset(num, 0, sizeof(int) * MAXN);
22     num[0] = num[1] = 1;
23     for (i = 2; i < MAXN; i++) 
24     for (j = 0; j < i; j++)
25         num[i] += num[j] * num[i-1-j];
26 
27     while(scanf("%d", &k) && k) {
28     for (i = 1; k > num[i]; k -= num[i], ++i){}
29     OutputBinaryTree(i, k, false);
30     printf("\n");
31     }
32     return 0;
33 }