[poj]1644放苹果

 
    把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。
 
解题思路:

设f(m,n)为把m个苹果放到n个盘子中的方法数,m>=0,n>=0.

若m和n中任何一个等于0,那么f(m,n) = 1,注意不是等于0,因为相当于就那么一种结果,就是不往盘子里面放(没有苹果),或者,连盘子都没有。
若n=1,显然对于任意的m>=0 有f(m,1) = 1
若m=1,显然对于任意的n>=0 有f(1,n) = 1
接下来讨论m>1 && n>1的情况:
若 m < n 则 f(m,n) = f(m,m)。即空哪几个盘子都是一样的

若 m>=n 则 大体有两种放法:

第1种情况:至少有一个盘子为空,即什么也不放,这部分的方法数为f(m,n-1);

第2种情况:全部盘子都有苹果,那么先从m个苹果中抽取出n个出来,各个盘子分一个,考虑剩下的m-n个苹果放到n个盘子里的放法,这样就成功把f(m,n)降到了f(m-n,n)。
所以,m>=n时,有f(m,n) = f(m,n-1) + f(m-n,n);
 
AC代码:
#include<stdio.h>
int f(int x,int y)
{
    if(y ==1||x==0) return 1;
    if(x<y) return f(x,x);
    return f(x,y-1)+f(x-y,y);//至少一个盘子为空或者每个盘子都放了苹果
}

int main()
{
    int t,m,n,i;
    scanf("%d",&t);
    for(i=0;i<t;i++)
       {
        scanf("%d%d",&m,&n);
        printf("%d\n",f(m,n));
    }
       return 0;
}

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。