• <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)  編輯 收藏 引用 所屬分類: 數論
            婷婷国产天堂久久综合五月| 久久91精品国产91久| 久久国产精品-久久精品| 国产成人久久激情91| 91久久精品无码一区二区毛片| 国产精品女同一区二区久久| 亚洲va久久久久| 狠狠狠色丁香婷婷综合久久俺| 精品乱码久久久久久夜夜嗨| 综合人妻久久一区二区精品| 色综合色天天久久婷婷基地| 久久久久久国产精品美女| 久久最近最新中文字幕大全| 亚洲熟妇无码另类久久久| 久久精品国产欧美日韩| 天天爽天天狠久久久综合麻豆| 国产视频久久| 久久精品国产91久久麻豆自制 | yy6080久久| 国产99久久九九精品无码| 久久精品国产亚洲77777| 国产一区二区久久久| 久久99国产一区二区三区| 久久精品www人人爽人人| 国产精品久久久久久久久软件| 国产亚洲精久久久久久无码AV| 国产精品久久精品| www.久久热| 精品久久久久中文字幕日本| 天堂久久天堂AV色综合| 人妻无码中文久久久久专区| 久久人人爽人人爽人人av东京热 | 亚洲AV无码久久| 精品多毛少妇人妻AV免费久久 | 99精品久久精品| 97久久国产亚洲精品超碰热| 久久99精品久久只有精品| 久久发布国产伦子伦精品| 久久99国产精品久久99果冻传媒| 国产精品久久久久国产A级| 69国产成人综合久久精品|