• <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數(shù)組表示節(jié)點(diǎn)數(shù)為j所能表示最大的數(shù)。
            則第j個(gè)節(jié)點(diǎn)所能表示的數(shù)a[j]符合卡特蘭數(shù):
            a[j] = a[0] * a[j - 1] + a[1] * a[j - 2] + ...... + a[j - 1] * a[0];
            表示:有j個(gè)節(jié)點(diǎn) = 左邊0個(gè)節(jié)點(diǎn)的個(gè)數(shù) * 右邊j - 1個(gè)節(jié)點(diǎn)的個(gè)數(shù) + ...... + 左邊j - 1個(gè)節(jié)點(diǎn)的個(gè)數(shù) * 右邊0個(gè)節(jié)點(diǎn)的個(gè)數(shù)。

            之后根據(jù)讀入的n,判斷出節(jié)點(diǎn)數(shù),在再判斷出左右的節(jié)點(diǎn)數(shù)和左右所代表的數(shù)。
            然后調(diào)用遞歸。

            #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) 評(píng)論(0)  編輯 收藏 引用 所屬分類(lèi): 數(shù)論

            只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
            網(wǎng)站導(dǎo)航: 博客園   IT新聞   BlogJava   博問(wèn)   Chat2DB   管理


            日本久久中文字幕| 国产999精品久久久久久| 久久精品国产乱子伦| 久久人做人爽一区二区三区| 99精品久久久久久久婷婷| 久久久久久亚洲AV无码专区| 国内精品久久久久| 久久夜色撩人精品国产小说| 思思久久精品在热线热| 97精品久久天干天天天按摩| 激情综合色综合久久综合| 久久www免费人成看片| 国产一区二区三区久久| 精品水蜜桃久久久久久久| 亚洲色大成网站www久久九| 国产三级精品久久| 亚洲AV乱码久久精品蜜桃| 国产 亚洲 欧美 另类 久久 | 国产精品美女久久久免费| 久久精品这里只有精99品| 色99久久久久高潮综合影院| 精品久久久久久无码中文字幕一区| yellow中文字幕久久网| 国产亚洲精品久久久久秋霞| 欧美精品一本久久男人的天堂| 区久久AAA片69亚洲| 久久精品国产99国产精偷| 亚洲精品无码久久一线| 久久久久久A亚洲欧洲AV冫| 一本大道加勒比久久综合| 精品久久久久久无码中文字幕一区| 久久久WWW成人免费精品| 九九精品99久久久香蕉| 日产精品99久久久久久| 伊人久久国产免费观看视频| 久久人人爽人爽人人爽av| 国产精品99久久久久久www| 91精品国产色综久久| 久久综合九色综合久99| 国产精品18久久久久久vr| 丁香狠狠色婷婷久久综合|