• <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>

            The Fourth Dimension Space

            枯葉北風寒,忽然年以殘,念往昔,語默心酸。二十光陰無一物,韶光賤,寐難安; 不畏形影單,道途阻且慢,哪曲折,如渡飛湍。斬浪劈波酬壯志,同把酒,共言歡! -如夢令

            POJ 1095 卡特蘭數(shù)+dfs

            感覺和上次codeforce的第四題有點像,雖然沒做出來,呵呵。
            看來枚舉左右子樹這一招還是蠻常用的。其實我本來想練下卡特蘭數(shù)的,結(jié)果變成練DFS了。
            注意遞歸求解左右孩子時的那兩個參數(shù),一定要先加上1,否則就不對了。

            #include<stdio.h>
            long long a[20];  
            long long b[20]; 
            //定理:n個結(jié)點能形成的二叉樹總數(shù)為 卡特蘭數(shù) C(2n,n)/(n+1) 或者由遞推公式Ci+1=2*(2*i+1)/(i+2)*Ci 
            //設計figure(n),n代表這棵樹整體的偏移量
            //分別算出其左右子樹各自的偏移量,遞歸求解即可
            //由于先遞歸左兒子,輸出順序與題意相符
            void figure(int n) 
            {       
                
            int t,i,j;  
                
            if(n==1){printf("X");return;}     
                j
            =0;
                
            while(trueif(b[++j]>=n) break;         
                n
            =n-b[j-1];//j代表有幾個結(jié)點,n此時代表在這些結(jié)點下的序號    
                for(i=0;i<j;i++)   
                
            {          
                    t
            =a[i]*a[j-1-i];    
                    
            if(t>=n)  break;           
                    
            else n=n-t;   
                }
                 
                
            if(i!=0)    //i是此時左子樹掛的節(jié)點數(shù)
                {        
                    printf(
            "(");  
                    figure(b[i
            -1]+1+(n-1)/a[j-1-i]);//初始的時刻,只需要增加1,左子樹的偏移量就增加1,而之后的部分,需要右子樹變換a[j-i-1]次,左子樹的偏移量才增加1  
                    printf(")");
                }
                
                printf(
            "X");  
                
            if(i!=j-1)    
                
            {        
                    printf(
            "(");  
                    figure(b[j
            -2-i]+1+(n-1)%a[j-1-i]);   
                    printf(
            ")");   
                }
               
            }
                    
            int main()  
            {      
                
            int n;   
                
            int i,j;     
                a[
            0]=1;     
                a[
            1]=1;       
                b[
            1]=1;     
                b[
            0]=0;     
                
            for(i=2;i<20;i++
                
            {        
                    a[i]
            =2*(2*(i-1)+1)*a[i-1]/(i+1) ;//卡特蘭數(shù)遞推公式
                    b[i]=b[i-1]+a[i];   
                }
                
                
            while(scanf("%d",&n)&&n)   
                
            {      
                    solve(n);   
                    printf(
            "\n");   
                }
                   
                
            return 0;  
            }
              

            posted on 2010-04-13 17:33 abilitytao 閱讀(2143) 評論(5)  編輯 收藏 引用

            評論

            # re: POJ 1095 卡特蘭數(shù)+dfs 2010-04-13 19:37 abilitytao

            srand(time(NULL))
            是以當前到1970年的時間間隔的秒數(shù)為種子,time(NULL),指不需要保存一個時間對象
            通常情況下可以Time tTime;然后time(&tTime)來將這個時間獲取到。

            而rand()是以剛才生成的種子為基礎來產(chǎn)生一個隨機數(shù),每調(diào)用一次產(chǎn)生一個數(shù),貌似如果期間沒有再次調(diào)用srand來生成種子,rand()是接著前面的序列來產(chǎn)生下一個數(shù)。(個人想法)
            因為:
            srand(time(NULL));
            int x = rand();
            int y = rand();
            x和y的值不一樣。而:
            srand(time(NULL));
            int x = rand();
            srand(time(NULL));
            int y = rand();
            則是相同,因為后一種使用了同一個種子(運行期間時間很短,返回的秒數(shù)相同)  回復  更多評論   

            # re: POJ 1095 卡特蘭數(shù)+dfs[未登錄] 2010-04-16 09:49 yoyo

            I can understand a[i] stores catalan number when there are i nodes.
            but what is b[] used for?

            Thanks,
            yoyo  回復  更多評論   

            # re: POJ 1095 卡特蘭數(shù)+dfs[未登錄] 2010-04-16 10:59 abilitytao

            @yoyo
            b[i]=a[1]+a[2]+...a[i];  回復  更多評論   

            # re: POJ 1095 卡特蘭數(shù)+dfs[未登錄] 2010-04-16 11:19 yoyo

            @abilitytao
            :-) I can know it from code, while no idea what's the purpose of b[i] = a[1]+...a[i]

            Thanks for quick replying.

            yoyo  回復  更多評論   

            # re: POJ 1095 卡特蘭數(shù)+dfs 2010-04-16 17:50 abilitytao

            @yoyo
            the intention is to find the node number of the the tree that you want.
            you are not chinese? or you can understand it through my notes by Chinese.  回復  更多評論   

            久久久精品人妻一区二区三区蜜桃| 91久久精品电影| 久久天天躁狠狠躁夜夜躁2014| 亚洲欧洲中文日韩久久AV乱码| 久久狠狠爱亚洲综合影院| 久久av无码专区亚洲av桃花岛| 久久久久久免费一区二区三区| 一本色道久久综合狠狠躁篇 | 久久久久久av无码免费看大片| 欧美日韩中文字幕久久久不卡| 久久久久久精品免费看SSS| 久久综合久久综合久久综合| 欧美久久久久久| 亚洲国产精品久久| 久久久久久精品久久久久| 国产福利电影一区二区三区久久久久成人精品综合 | 99久久国产亚洲综合精品| 成人综合伊人五月婷久久| 中文字幕无码久久久| 99久久免费只有精品国产| 久久久久无码精品国产不卡| 伊人久久大香线蕉成人| 久久久久无码专区亚洲av| 久久er国产精品免费观看2| av色综合久久天堂av色综合在| 久久久久无码精品| 国产综合成人久久大片91| 欧美久久综合性欧美| 国产精品视频久久久| 人妻无码αv中文字幕久久| 久久人做人爽一区二区三区| 久久久久婷婷| 久久久久久久亚洲精品| 久久青青草原亚洲av无码| 国产成人精品久久亚洲高清不卡| 国产亚洲婷婷香蕉久久精品| 国产亚洲欧美精品久久久| 久久国产色AV免费观看| 国产午夜精品久久久久免费视| 久久综合久久自在自线精品自| 久久人人爽爽爽人久久久|