• <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 閱讀(420) 評論(0)  編輯 收藏 引用 所屬分類: 數論
            国产亚州精品女人久久久久久| 亚洲国产日韩欧美综合久久| 亚洲AV日韩AV永久无码久久| 亚洲va久久久噜噜噜久久天堂| 久久久亚洲欧洲日产国码aⅴ | 亚洲日本va午夜中文字幕久久| 亚洲一级Av无码毛片久久精品| 亚洲熟妇无码另类久久久| 97久久超碰国产精品2021| 久久精品成人| 午夜精品久久久久久毛片| 久久精品国产72国产精福利| 伊人久久综合精品无码AV专区| 久久天堂电影网| 久久99久久99精品免视看动漫| 久久精品国产亚洲综合色| 久久综合亚洲色HEZYO社区| 99国产精品久久| 亚洲国产另类久久久精品小说| 精品免费久久久久国产一区| 婷婷综合久久中文字幕蜜桃三电影| 久久久精品人妻无码专区不卡 | 久久久无码精品亚洲日韩按摩 | 青青热久久国产久精品| 久久精品国产精品亚洲毛片| 久久综合日本熟妇| 精品久久久久久国产免费了| 久久91亚洲人成电影网站| 亚洲va久久久噜噜噜久久| 狠狠色丁香久久婷婷综合_中 | 久久夜色撩人精品国产| 精品久久久久久无码中文野结衣| 久久精品亚洲日本波多野结衣 | 久久久无码精品亚洲日韩京东传媒| 国产亚州精品女人久久久久久 | 国产精品久久久久久搜索| 久久综合香蕉国产蜜臀AV| 日本人妻丰满熟妇久久久久久| 99久久这里只精品国产免费| 久久99国产精品久久99小说| 久久久久久久精品妇女99|