• <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ù)的，結果變成練DFS了。
            注意遞歸求解左右孩子時的那兩個參數(shù)，一定要先加上1，否則就不對了。
            

            #include<stdio.h>
            long long a[20];  
            long long b[20]; 
            //定理：n個結點能形成的二叉樹總數(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(true) if(b[++j]>=n) break;         
                n            =n-b[j-1];//j代表有幾個結點，n此時代表在這些結點下的序號    
                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 閱讀(2142) 評論(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.  回復  更多評論
				  
			
            
		

            




            






            

				

            


    
    







            
	   
	



久久综合九色综合欧美狠狠|
国产成人无码精品久久久性色|
国产午夜精品理论片久久影视|
A狠狠久久蜜臀婷色中文网|
国产成人综合久久精品尤物|
国内精品久久久久影院网站
|
久久久久久国产a免费观看不卡|
亚州日韩精品专区久久久|
性做久久久久久久|
精品国产91久久久久久久a|
久久精品国产亚洲AV久|
国产精品久久久久一区二区三区
|
国产999精品久久久久久|
久久亚洲天堂|
94久久国产乱子伦精品免费|
国产成人精品综合久久久|
国産精品久久久久久久|
国产亚洲精久久久久久无码|
伊人久久精品影院|
精品久久久久久无码人妻蜜桃
|
亚洲天堂久久久|
国产精品青草久久久久福利99|
少妇久久久久久被弄高潮|
久久无码人妻精品一区二区三区|
俺来也俺去啦久久综合网|
久久99热这里只有精品66|
99久久这里只有精品|
无码人妻久久一区二区三区免费丨
|
99久久99这里只有免费费精品|
久久精品国产99国产精品亚洲|
久久无码精品一区二区三区|
精品久久久久久无码免费|
93精91精品国产综合久久香蕉|
99热成人精品热久久669|
久久人妻少妇嫩草AV无码专区|
久久亚洲国产最新网站|
一级女性全黄久久生活片免费|
日本加勒比久久精品|
亚洲国产日韩综合久久精品|
亚洲精品视频久久久|
国内高清久久久久久|