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

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

            




            
	
					
	
            
		
            
			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 
            //設(shè)計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 閱讀(2144) 評論(5)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    


            

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

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

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

            

            而rand()是以剛才生成的種子為基礎(chǔ)來產(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ù)相同）  回復(fù)  更多評論
				  
			
            
		
			
            
				# 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  回復(fù)  更多評論
				  
			
            
		
			
            
				# re: POJ 1095 卡特蘭數(shù)+dfs[未登錄]
					
						2010-04-16 10:59
					
				abilitytao
			
            
			
            
				@yoyo

            b[i]=a[1]+a[2]+...a[i];  回復(fù)  更多評論
				  
			
            
		
			
            
				# 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  回復(fù)  更多評論
				  
			
            
		
			
            
				# 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.  回復(fù)  更多評論
				  
			
            
		

            




            



            


            

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

            


            

            		
		
            
	
            	

            



            

				

            


    
    







            
	   
	



久久亚洲sm情趣捆绑调教|
精品久久久久久成人AV|
久久综合久久伊人|
要久久爱在线免费观看|
波多野结衣久久一区二区|
亚洲AV日韩精品久久久久|
秋霞久久国产精品电影院|
国产成人香蕉久久久久|
中文字幕精品久久|
久久精品国产福利国产秒|
日韩中文久久|
久久精品九九亚洲精品天堂|
亚洲国产成人久久综合野外|
97久久久久人妻精品专区|
久久精品国产亚洲5555|
久久人人爽人人爽人人AV东京热
|
亚洲午夜久久久|
国产精品久久久亚洲|
一本色道久久综合狠狠躁篇|
国产精品9999久久久久|
亚洲精品无码久久久|
女人香蕉久久**毛片精品|
天天躁日日躁狠狠久久|
久久综合精品国产一区二区三区|
久久66热人妻偷产精品9|
久久国产欧美日韩精品免费|
国产精品99久久不卡|
国产成人精品白浆久久69|
久久成人国产精品免费软件|
久久精品成人免费观看97|
人妻无码αv中文字幕久久琪琪布
人妻无码久久一区二区三区免费
人妻无码中文久久久久专区
|
久久久久久九九99精品|
国产精品久久久久久久久软件|
91久久精品国产成人久久|
72种姿势欧美久久久久大黄蕉|
日韩精品久久久肉伦网站
|
久久久久久久久无码精品亚洲日韩|
91精品国产高清久久久久久国产嫩草|
久久久久女人精品毛片|
亚洲va久久久噜噜噜久久狠狠|
亚洲女久久久噜噜噜熟女|