放苹果
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
);
}
|
本文转自二郎三郎博客园博客,原文链接:http://www.cnblogs.com/haore147/p/3644737.html,如需转载请自行联系原作者