放苹果
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 24985 | Accepted: 15908 |
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
1 7 3
Sample Output
8
Source
我写的代码自己写了几个测试数据集，都没有问题的。放到POJ上，死活跑不过：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
|
#include<stdio.h>int f(int m, int n)
{ int
i,result;
result=0;
if(n<=0)
return
0;
if((0==m) || (1==m) || (1==n))
return
1;
for( i=m ; i>=m/2
&& i>0
; i-- )
{
if( (m-i) > i )
{
if( (n-1) > 1)
{
result=result+f(m-i,n-1)-1;
}
break;
}
else
{
result=result+f(m-i,n-1);
}
}
return
result;
}int main(void)
{ int
t,m,n;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&m,&n);
if(n<=0)
{
printf("\n1");
}
else
{
printf("\n%d",f(m,n));
}
}
return
0;
} |
贴一个正确版本：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
#include <stdio.h>#include <stdlib.h> int f(int, int);
int main()
{ int
t, m, n, sum;
scanf("%d", &t);
while
(t--)
{
scanf("%d%d", &m, &n);
sum = f(m, n);
printf("%d\n", sum);
}
system("pause");
return
0;
} /* m为剩余苹果数，n为剩余盘子数 */int f(int m, int n)
{ /* 有些盘子不放苹果，已包含在f(m, n - 1)中，返回0*/
if
(m < 0) return
0;
/* 刚好每个盘子放1个，只有一种情况 */
if
(m == 0) return
1;
/* 只有1个盘子可以放，也只有全部放入这一种情况 */
if
(n == 1) return
1;
/* n个盘子内至少都放1个 + 只放入n-1个盘子中 */
return
f(m - n, n) + f(m, n - 1);
} |