• <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)寒，忽然年以殘，念往昔，語(yǔ)默心酸。二十光陰無(wú)一物，韶光賤，寐難安； 不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！  -如夢(mèng)令
            

            




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

            #include<stdio.h>
            long long a[20];  
            long long b[20]; 
            //定理：n個(gè)結(jié)點(diǎn)能形成的二叉樹(shù)總數(shù)為 卡特蘭數(shù) C(2n,n)/(n+1) 或者由遞推公式Ci+1=2*(2*i+1)/(i+2)*Ci 
            //設(shè)計(jì)figure(n)，n代表這棵樹(shù)整體的偏移量
            //分別算出其左右子樹(shù)各自的偏移量，遞歸求解即可
            //由于先遞歸左兒子，輸出順序與題意相符
            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代表有幾個(gè)結(jié)點(diǎn)，n此時(shí)代表在這些結(jié)點(diǎn)下的序號(hào)    
                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是此時(shí)左子樹(shù)掛的節(jié)點(diǎn)數(shù)
                {        
                    printf(            "(");  
                    figure(b[i            -1]+1+(n-1)/a[j-1-i]);//初始的時(shí)刻，只需要增加1，左子樹(shù)的偏移量就增加1，而之后的部分，需要右子樹(shù)變換a[j-i-1]次，左子樹(shù)的偏移量才增加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) 評(píng)論(5)  編輯 收藏 引用  
		
            
	
            
	
	





            
	    
    


            

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

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

            通常情況下可以Time tTime;然后time(&tTime)來(lái)將這個(gè)時(shí)間獲取到。

            

            而rand()是以剛才生成的種子為基礎(chǔ)來(lái)產(chǎn)生一個(gè)隨機(jī)數(shù)，每調(diào)用一次產(chǎn)生一個(gè)數(shù)，貌似如果期間沒(méi)有再次調(diào)用srand來(lái)生成種子，rand()是接著前面的序列來(lái)產(chǎn)生下一個(gè)數(shù)。（個(gè)人想法）

            因?yàn)椋?
            srand(time(NULL))；

            int x = rand();

            int y = rand();

            x和y的值不一樣。而：

            srand(time(NULL));

            int x = rand();

            srand(time(NULL));

            int y = rand();

            則是相同，因?yàn)楹笠环N使用了同一個(gè)種子（運(yùn)行期間時(shí)間很短，返回的秒數(shù)相同）  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: POJ 1095 卡特蘭數(shù)+dfs[未登錄](méi)
					
						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ù)  更多評(píng)論
				  
			
            
		
			
            
				# re: POJ 1095 卡特蘭數(shù)+dfs[未登錄](méi)
					
						2010-04-16 10:59
					
				abilitytao
			
            
			
            
				@yoyo

            b[i]=a[1]+a[2]+...a[i];  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: POJ 1095 卡特蘭數(shù)+dfs[未登錄](méi)
					
						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ù)  更多評(píng)論
				  
			
            
		
			
            
				# 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ù)  更多評(píng)論
				  
			
            
		

            




            



            


            

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

            


            

            		
		
            
	
            	

            



            

				

            


    
    







            
	   
	



香港aa三级久久三级老师2021国产三级精品三级在
|
国产免费福利体检区久久|
久久精品成人免费观看97|
久久中文字幕人妻熟av女|
久久99国产精品久久99|
久久精品成人|
精品久久久久久亚洲精品|
亚洲成av人片不卡无码久久|
无码久久精品国产亚洲Av影片
|
国内精品久久久人妻中文字幕|
91精品婷婷国产综合久久|
久久天天躁狠狠躁夜夜不卡|
国产高潮国产高潮久久久|
要久久爱在线免费观看|
国产亚洲精品自在久久|
综合久久精品色|
国产精品美女久久久网AV|
久久精品国产亚洲77777|
亚洲精品久久久www|
精品久久久久久无码国产|
国产精品一区二区久久国产|
久久精品国产色蜜蜜麻豆|
亚洲AⅤ优女AV综合久久久|
色综合久久天天综合|
狠狠色婷婷久久一区二区三区|
四虎国产精品成人免费久久|
欧美亚洲日本久久精品|
久久久国产精华液|
国产女人aaa级久久久级|
久久久九九有精品国产|
国产精品一久久香蕉国产线看
|
国产福利电影一区二区三区，免费久久久久久久精
|
天天久久狠狠色综合|
99久久er这里只有精品18|
久久久久成人精品无码中文字幕|
久久精品国产AV一区二区三区|
一本色道久久综合|
久久免费看黄a级毛片|
7777久久久国产精品消防器材|
久久久亚洲裙底偷窥综合|
亚洲AV日韩精品久久久久久久|