• <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 閱讀(2145) 評論(5)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    


            

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

            是以當前到1970年的時間間隔的秒數(shù)為種子，time(NULL),指不需要保存一個時間對象

            通常情況下可以Time tTime;然后time(&tTime)來將這個時間獲取到。

            

            而rand()是以剛才生成的種子為基礎來產生一個隨機數(shù)，每調用一次產生一個數(shù)，貌似如果期間沒有再次調用srand來生成種子，rand()是接著前面的序列來產生下一個數(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.  回復  更多評論
				  
			
            
		

            




            






            

				

            


    
    







            
	   
	



久久精品国产亚洲77777|
思思久久好好热精品国产|
久久99精品综合国产首页|
色综合久久综合网观看|
亚洲国产精品无码久久久久久曰|
无码人妻少妇久久中文字幕蜜桃
|
色悠久久久久久久综合网|
久久久国产打桩机|
国产AV影片久久久久久
|
色天使久久综合网天天|
99久久精品免费|
国产亚洲精久久久久久无码77777|
国产精品久久久久无码av|
亚洲七七久久精品中文国产
|
久久九九兔免费精品6|
九九久久精品国产|
欧美一区二区精品久久|
久久天天躁狠狠躁夜夜avapp|
性高朝久久久久久久久久|
四虎国产精品免费久久5151
|
久久天天躁狠狠躁夜夜2020|
国产精品久久精品|
精品国产乱码久久久久久1区2区
|
久久精品国产秦先生|
久久久无码一区二区三区
|
久久久久综合网久久|
久久综合给合久久狠狠狠97色69
|
午夜精品久久影院蜜桃|
亚洲一区二区三区日本久久九|
精品无码久久久久国产|
香蕉久久av一区二区三区|
亚洲午夜久久久久妓女影院|
伊人久久久AV老熟妇色|
久久精品国产99国产精品亚洲
|
色综合久久最新中文字幕|
一本伊大人香蕉久久网手机|
国产精品99久久精品爆乳|
久久夜色精品国产www|
亚洲午夜久久久|
久久中文骚妇内射|
狠狠色丁香久久综合五月|