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

    
            

            




            







												


        



			
			


			
            
				
					
	
            
		
            
			ACM PKU 1664 放蘋果 類似整數(shù)劃分問題的遞歸
		
            
		
            http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=1664 

            

            放蘋果 
            Time Limit:1000MS  Memory Limit:10000K
            Total Submit:6074 Accepted:3764 
            Description
            把M個(gè)同樣的蘋果放在N個(gè)同樣的盤子里，允許有的盤子空著不放，問共有多少種不同的分法？（用K表示）5，1，1和1，5，1 是同一種分法。
            Input
            第一行是測(cè)試數(shù)據(jù)的數(shù)目t（0 <= t <= 20）。以下每行均包含二個(gè)整數(shù)M和N，以空格分開。1<=M，N<=10。
            Output
            對(duì)輸入的每組數(shù)據(jù)M和N，用一行輸出相應(yīng)的K。
            Sample Input
            17 3

            Sample Output
            8

            Source
            lwx@POJ




            看到這道題立即想到了遞歸的經(jīng)典案例：整數(shù)劃分問題。 

            將正整數(shù)n表示成一系列正整數(shù)之和：n=n1+n2+…+nk， 
            其中n1≥n2≥…≥nk≥1，k≥1。 
            正整數(shù)n的這種表示稱為正整數(shù)n的劃分。求正整數(shù)n的不 
            同劃分個(gè)數(shù)。 
            例如正整數(shù)6有如下11種不同的劃分： 
            6； 
            5+1； 
            4+2，4+1+1； 
            3+3，3+2+1，3+1+1+1； 
            2+2+2，2+2+1+1，2+1+1+1+1； 
            1+1+1+1+1+1。 

              將最大加數(shù)x不大于m的劃分個(gè)數(shù)記作q(n,m) 
            有 
                                   1                                      n=1 || m=1 
            q(n,m)  =  {       q(n,n)                                n<m 
                                   1+q(n,n-1)                         n=m 
                                   q(n,m-1)+q(n-m,m)            n>m>1 

            重點(diǎn)在n>m>1的情況。 
            呵呵，當(dāng)時(shí)我還花了好些功夫才理解到哦，真是精妙。有了這一點(diǎn)經(jīng)驗(yàn)，放蘋果的問題就容易了，我們也有遞歸式 
            將在m個(gè)盤中放n個(gè)蘋果記作fun(m,n)，且不能有空盤。（題目中的可以有空盤 不方便遞歸，我們循環(huán)累加） 
            對(duì)于fun(m,n) 
                                  1                                 n=1||m=n   
            resulut   =       0                                 n<m 
                                 ∑ fun(n-m,i)                   n>=m   , i=1..n 

            當(dāng)n>=m時(shí)，是不是方法和整數(shù)劃分問題的n>m>1時(shí)很像呢？呵呵 


            于是我們得到代碼 
            

             1#include "stdio.h" 
             2int fun(int m,int n) 
             3{ 
             4int i,result; 
             5if(n==1||m==n) return 1; 
             6  else if(n<m) return 0; 
             7  else 
             8  { 
             9   result=0; 
            10   for(i=1;i<=n;i++) 
            11    result+=fun(n-m,i); 
            12   return result; 
            13  }             
            14}             
            15void main() 
            16{ 
            17int T,m,n,k,i; 
            18int result=0; 
            19scanf("%d",&T); 
            20while(T--) 
            21{ 
            22  scanf("%d %d",&m,&n); 
            23  for(i=1;i<=n;i++) 
            24  result=result+fun(m,i); 
            25  printf("%d\n",result); 
            26}             
            27}             
            28
            

            

		
            
			posted on 2007-09-14 02:05 流牛ζ木馬 閱讀(2753) 評(píng)論(9)  編輯 收藏 引用  
		
            
	
            
	
	


	


            
	    
    


            

            評(píng)論
            
	
	
			
            
				# re: ACM PKU 1664 放蘋果 類似整數(shù)劃分問題的遞歸
					
						2007-11-20 20:57
					
				ban
			
            
			
            
				e....你把m和n的 含義都交換了。。。害我想了半天  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: ACM PKU 1664 放蘋果 類似整數(shù)劃分問題的遞歸
					
						2007-11-27 11:40
					
				maliang
			
            
			
            
				盤子可以為空，那m==n的時(shí)候可以return 1 嗎？
            maleungxp@gmail.com  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: ACM PKU 1664 放蘋果 類似整數(shù)劃分問題的遞歸
					
						2008-05-04 03:12
					
				haha
			
            
			
            
				

            #include <stdio.h>

            int main ()

            {

            	int i,j,k,n,ii,t,kk,z;

            	int a[100][100];

            	scanf("%d",&t);

            

            	for (ii=1; ii <=t; ii++)

            	{

            		scanf("%d%d", &n,&kk);

            		z=0;

            		for (k=1; k<kk+1; k++)

            		{

            		for (i=0 ; i <n-k+1; i++)

            		 for (j=0; j <k+1; j++)

            			a[i][j]=0;

            		

                             for (i=0; i <=n-k; i++) 

            		  a[i][1]=1;

                     

            		  for (i=0; i <=n-k;i++)

            			for (j=2; j<=k; j++)

            		  if (i>=j) a[i][j]=a[i-j][j]+a[i][j-1] ; 

            			else a[i][j]=a[i][j-1];

            

            			z=z+a[n-k][k];

            		}

            				printf("%d\n",z);

            	}

                return 0;

            }

              回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: ACM PKU 1664 放蘋果 類似整數(shù)劃分問題的遞歸
					
						2008-05-06 11:24
					
				traveler
			
            
			
            
				謝謝啦，我終于也明白了。。。  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: ACM PKU 1664 放蘋果 類似整數(shù)劃分問題的遞歸
					
						2008-06-18 20:37
					
				Gill
			
            
			
            
				非遞歸算法

            n<kk時(shí)出錯(cuò)

            

            @haha

              回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: ACM PKU 1664 放蘋果 類似整數(shù)劃分問題的遞歸[未登錄]
					
						2008-08-23 21:46
					
				李
			
            
			
            
				厲害呀，這都能聯(lián)想到整數(shù)劃分  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: ACM PKU 1664 放蘋果 類似整數(shù)劃分問題的遞歸
					
						2009-04-17 09:54
					
				dream
			
            
			
            
				錯(cuò)的  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: ACM PKU 1664 放蘋果 類似整數(shù)劃分問題的遞歸
					
						2011-02-28 19:33
					
				stufever
			
            
			
            
				到底是m=1還是m=0遞歸結(jié)束都有道理，看你怎么理解了，我這里有解題報(bào)告http://stufever.com/?p=80  回復(fù)  更多評(píng)論
				  
			
            
		
			
            
				# re: ACM PKU 1664 放蘋果 類似整數(shù)劃分問題的遞歸
					
						2013-10-27 16:23
					
				unkown
			
            
			
            
				"呵呵，當(dāng)時(shí)我還花了好些功夫才理解到哦，真是精妙"  精妙在哪里? 最關(guān)鍵的地方樓主一筆帶過啦~~    回復(fù)  更多評(píng)論
				  
			
            
		

            




            



            


            

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

            


            

            		
		
            
	
            	

            



            

				
				

			
            
			
            
				
					
            
	
            
		
            <2007年9月>
            
	
            日一二三四五六
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            30123456
            

            

					

            導(dǎo)航
            

					

            統(tǒng)計(jì)
            
	
					

            公告
            
	MY Email/MSN :mars1021@163.com
QQ : 27402040
流牛ζ木馬 
 



            






            

            



					

            常用鏈接
            


            留言簿(6)
            


		
            隨筆檔案
            
		
				
			
	
		
            相冊(cè)
            
		
				
			
	



            搜索
            



            最新隨筆
            

            


            


            最新評(píng)論
	
            

            
	
			
		

            


            閱讀排行榜
            



            評(píng)論排行榜
            


				
			
            
			
			
			
			
			 

	

            






            

            


            



                
    







            
	   
	



狠狠色婷婷久久综合频道日韩
|
亚洲精品无码久久久|
国产农村妇女毛片精品久久|
亚洲人成电影网站久久|
亚洲αv久久久噜噜噜噜噜|
.精品久久久麻豆国产精品|
婷婷久久综合九色综合绿巨人|
人妻少妇久久中文字幕一区二区
|
国产精品久久99|
国产精品99久久久精品无码|
精品亚洲综合久久中文字幕|
久久亚洲日韩看片无码|
丰满少妇人妻久久久久久|
久久久久久国产精品美女
|
手机看片久久高清国产日韩|
久久综合久久久|
亚洲国产欧美国产综合久久|
久久久国产精华液|
国产精品成人无码久久久久久|
久久天天躁狠狠躁夜夜躁2O2O|
综合久久精品色|
久久人人爽人人爽人人片AV东京热
|
人妻精品久久久久中文字幕69
|
婷婷伊人久久大香线蕉AV|
中文字幕久久亚洲一区|
久久精品国产亚洲精品|
伊人色综合久久天天|
久久91精品国产91久久小草|
久久精品aⅴ无码中文字字幕重口
久久精品a亚洲国产v高清不卡
|
午夜天堂av天堂久久久|
久久久久久久波多野结衣高潮|
久久久噜噜噜久久|
久久久久久一区国产精品|
久久WWW免费人成—看片|
国产精品九九久久免费视频|
99久久精品免费看国产免费|
亚洲国产成人久久精品影视|
国产精品无码久久久久|
国内精品久久久久久麻豆|
欧美大战日韩91综合一区婷婷久久青草|
久久激情亚洲精品无码?V|