POJ 1664 放苹果

放苹果
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);  
}

  

 

 

 

POJ 1664 放苹果,布布扣,bubuko.com

POJ 1664 放苹果

上一篇:Start activity with App Chooser or not ?


下一篇:Android系统分区理解及分区目录细解