ACM PKU 1664 放苹果 类似整数划分问题的递归

http://acm.pku.edu.cn/JudgeOnline/bbs?problem_id=1664 

放苹果 
Time Limit:1000MS  Memory Limit:10000K
Total Submit:6074 Accepted:3764 
Description
把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
Input
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
Output
对输入的每组数据M和N，用一行输出相应的K。
Sample Input
17 3

Sample Output
8

Source
lwx@POJ




看到这道题立即想到了递归的经典案例：整数划分问题。 

将正整数n表示成一系列正整数之和：n=n1+n2+…+nk， 
其中n1≥n2≥…≥nk≥1，k≥1。 
正整数n的这种表示称为正整数n的划分。求正整数n的不 
同划分个数。 
例如正整数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。 

  将最大加数x不大于m的划分个数记作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 

重点在n>m>1的情况。 
呵呵，当时我还花了好些功夫才理解到哦，真是精妙。有了这一点经验，放苹果的问题就容易了，我们也有递归式 
将在m个盘中放n个苹果记作fun(m,n)，且不能有空盘。（题目中的可以有空盘 不方便递归，我们循环累加） 
对于fun(m,n) 
                      1                                 n=1||m=n   
resulut   =       0                                 n<m 
                     ∑ fun(n-m,i)                   n>=m   , i=1..n 

当n>=m时，是不是方法和整数划分问题的n>m>1时很像呢？呵呵 


于是我们得到代码 
 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 流牛ζ木马 阅读(2722) 评论(9)  编辑 收藏 引用

评论

# re: ACM PKU 1664 放苹果 类似整数划分问题的递归 2007-11-20 20:57 ban

e....你把m和n的 含义都交换了。。。害我想了半天  回复  更多评论   

# re: ACM PKU 1664 放苹果 类似整数划分问题的递归 2007-11-27 11:40 maliang

盘子可以为空，那m==n的时候可以return 1 吗？
maleungxp@gmail.com  回复  更多评论   

# re: ACM PKU 1664 放苹果 类似整数划分问题的递归 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;
}
  回复  更多评论   

# re: ACM PKU 1664 放苹果 类似整数划分问题的递归 2008-05-06 11:24 traveler

谢谢啦，我终于也明白了。。。  回复  更多评论   

# re: ACM PKU 1664 放苹果 类似整数划分问题的递归 2008-06-18 20:37 Gill

非递归算法
n<kk时出错

@haha
  回复  更多评论   

# re: ACM PKU 1664 放苹果 类似整数划分问题的递归[未登录] 2008-08-23 21:46 李

厉害呀，这都能联想到整数划分  回复  更多评论   

# re: ACM PKU 1664 放苹果 类似整数划分问题的递归 2009-04-17 09:54 dream

错的  回复  更多评论   

# re: ACM PKU 1664 放苹果 类似整数划分问题的递归 2011-02-28 19:33 stufever

到底是m=1还是m=0递归结束都有道理，看你怎么理解了，我这里有解题报告http://stufever.com/?p=80  回复  更多评论   

# re: ACM PKU 1664 放苹果 类似整数划分问题的递归 2013-10-27 16:23 unkown

"呵呵，当时我还花了好些功夫才理解到哦，真是精妙" 精妙在哪里? 最关键的地方楼主一笔带过啦~~   回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2011年8月>
日一二三四五六
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

导航

统计

公告

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

常用链接

留言簿(6)

随笔档案

相册

搜索

最新随笔

最新评论

阅读排行榜

评论排行榜