• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 7,comments - 3,trackbacks - 0
            We can number binary trees using the following scheme:

            The empty tree is numbered 0.
            The single-node tree is numbered 1.
            All binary trees having m nodes have numbers less than all those having m+1 nodes.
            Any binary tree having m nodes with left and right subtrees L and R is numbered n such that all trees having m nodes numbered > n have either

              Left subtrees numbered higher than L, or
              A left subtree = L and a right subtree numbered higher than R.

            The first 10 binary trees and tree number 20 in this sequence are shown below:

            Your job for this problem is to output a binary tree when given its order number.

            Input

            Input consists of multiple problem instances. Each instance consists of a single integer n, where 1 <= n <= 500,000,000. A value of n = 0 terminates input. (Note that this means you will never have to output the empty tree.)

            Output

            For each problem instance, you should output one line containing the tree corresponding to the order number for that instance. To print out the tree, use the following scheme:

            A tree with no children should be output as X.
            A tree with left and right subtrees L and R should be output as (L')X(R'), where L' and R' are the representations of L and R.
              If L is empty, just output X(R').
              If R is empty, just output (L')X.

            Sample Input

            1 
            20
            31117532
            0

            Sample Output

            X 
            ((X)X(X))X
            (X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)


            思路:
            a數組表示節點數為j所能表示最大的數。
            則第j個節點所能表示的數a[j]符合卡特蘭數:
            a[j] = a[0] * a[j - 1] + a[1] * a[j - 2] + ...... + a[j - 1] * a[0];
            表示:有j個節點 = 左邊0個節點的個數 * 右邊j - 1個節點的個數 + ...... + 左邊j - 1個節點的個數 * 右邊0個節點的個數。

            之后根據讀入的n,判斷出節點數,在再判斷出左右的節點數和左右所代表的數。
            然后調用遞歸。

            #include <cstdio>
            #include 
            <cstring>
            using namespace std;

            int a[25], b[25];

            void solve(int n)
            {
                
            int t, i, j;
                
            if (n == 0return;
                
            if (n == 1)
                {
                    printf(
            "X");
                    
            return;
                }
                
            for (j = 1;; ++j)
                {
                    
            if (b[j] >= n)
                        
            break;
                }
                n 
            = n - b[j - 1];
                
            for (i = 0; i < j; ++i)
                {
                    t 
            = a[i] * a[j - 1 - i];
                    
            if (n > t)
                    {
                        n 
            = n - t;
                    }
                    
            else
                        
            break;
                }
                
            if (i != 0)
                {
                    printf(
            "(");
                    solve(b[i 
            - 1+ 1 + (n - 1)/ a[j - 1 - i]);
                    printf(
            ")");
                }
                printf(
            "X");
                
            if (i != j - 1)
                {
                    printf(
            "(");
                    solve(b[j 
            - 2 - i] + 1 + (n - 1% a[j - 1 - i]);
                    printf(
            ")");
                }
            }

            int main()
            {
                
            int n;
                
            int i, j;
                b[
            0= 0;
                a[
            0= b[1= a[1= 1;
                
            for (i = 2; i < 20++i)
                {
                    a[i] 
            = 0;
                    
            for (j = 0; j < i; ++j)
                    {
                        a[i] 
            += a[j] * a[i - j - 1];
                    }
                    b[i] 
            = b[i - 1+ a[i];
                }
                
            while (scanf("%d"&n) && n)
                {
                    solve(n);
                    printf(
            "\n");
                }
                
            return 0;
            }
            posted on 2011-10-25 20:55 LLawliet 閱讀(423) 評論(0)  編輯 收藏 引用 所屬分類: 數論
            久久妇女高潮几次MBA| 久久久一本精品99久久精品66| 久久99精品国产麻豆宅宅| 一本大道久久东京热无码AV| 亚洲乱码中文字幕久久孕妇黑人| 久久99国产精品尤物| 欧美伊人久久大香线蕉综合69| 蜜桃麻豆WWW久久囤产精品| 久久w5ww成w人免费| 伊人久久精品线影院| 久久精品国产亚洲av麻豆图片| 亚洲精品国精品久久99热一| 国产69精品久久久久99| 国产精品久久99| 久久精品人人槡人妻人人玩AV | 伊人情人综合成人久久网小说| 2021久久国自产拍精品| 久久久久婷婷| 国产精品久久久久乳精品爆| 国产精品久久久久蜜芽| 久久久久久极精品久久久| 久久亚洲精品国产精品| 久久精品亚洲精品国产色婷 | 久久99精品国产麻豆宅宅| 99久久久久| 伊人色综合久久| 99久久精品毛片免费播放| 无码人妻少妇久久中文字幕蜜桃 | 欧美伊人久久大香线蕉综合 | 久久中文字幕人妻熟av女| 久久黄色视频| 久久强奷乱码老熟女网站| 欧美日韩精品久久久久 | 国产精品九九九久久九九| 久久综合给合久久狠狠狠97色69 | 丰满少妇人妻久久久久久4| 成人国内精品久久久久影院| 久久精品国产久精国产一老狼| 亚洲精品tv久久久久久久久久| 久久久亚洲精品蜜桃臀| 亚洲精品NV久久久久久久久久|