• <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(true) if(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.  回復  更多評論
				  
			
            
		

            




            






            

				

            


    
    







            
	   
	



热99re久久国超精品首页|
久久久久亚洲av无码专区导航|
欧美牲交A欧牲交aⅴ久久
|
久久久久亚洲av成人无码电影|
久久精品国产精品国产精品污|
国产精品九九久久免费视频
|
欧美一区二区精品久久|
久久亚洲精品视频|
久久精品中文字幕一区|
人人狠狠综合久久亚洲婷婷|
伊人久久大香线蕉AV一区二区|
色欲久久久天天天综合网精品
|
欧美日韩中文字幕久久久不卡
|
大伊人青草狠狠久久|
欧美精品福利视频一区二区三区久久久精品
|
最新久久免费视频|
www.久久热.com|
久久精品亚洲AV久久久无码|
精品999久久久久久中文字幕|
久久人人青草97香蕉|
国产69精品久久久久99|
久久亚洲私人国产精品vA|
久久无码一区二区三区少妇|
精品乱码久久久久久久|
亚洲中文字幕无码久久综合网
|
国产亚洲精久久久久久无码|
久久婷婷国产剧情内射白浆
|
欧美性大战久久久久久|
国产精品一久久香蕉产线看|
久久亚洲AV成人出白浆无码国产|
久久国内免费视频|
无码任你躁久久久久久久|
久久久久国产精品三级网|
女人香蕉久久**毛片精品|
狠狠色丁香婷综合久久|
久久亚洲国产午夜精品理论片|
久久香蕉一级毛片|
日本精品久久久久中文字幕|
亚洲欧美日韩精品久久|
久久精品国产亚洲AV不卡|
亚洲成av人片不卡无码久久|