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时很像呢？呵呵

于是我们得到代码

#include "stdio.h"
2

int fun(int m,int n)
3

{
4

int i,result;
5

if(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

}
15

void main()
16

{
17

int T,m,n,k,i;
18

int result=0;
19

scanf("%d",&T);
20

while(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 流牛ζ木马阅读(2719) 评论(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

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

刷新评论列表

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！



网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

2009年8月

日

一

二

三

四

五

六

统计

随笔 - 63
文章 - 0
评论 - 154
引用 - 0

公告

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

常用链接

留言簿(6)

随笔档案

相册

撒旦

搜索

阅读排行榜

评论排行榜