「分苹果」分苹果算法

分苹果

题目内容：

把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？M, N为自然数。说明：如有7个苹果，2个盘子，则(5, 1, 1)和(1, 5, 1)和(1, 1, 5)都是同一种分法。

输入描述

第一行一个整数表示数据的组数（多组数据），对于每组数据第一行是苹果个数M (1 ≤ m ≤ 100) ，第二行是盘子个数N(1 ≤ n ≤ 100)。

输出描述

每组数据输出一行,放苹果的方法个数。

输入样例

1 
3 
2

输出样例

/*
思路1： 
122 212 221是同种方法,则取代表 221
123 .321 是同种方法,则取代表 321
能当“代表”的组合的特点是,前面的不小于后面的.
这是一个限制条件.
想来想去用递归最好.
比如10个放入3个篮子,变成：
第一个放10,再把0个放入剩余2个篮子
第一个放9,再把1个放入剩余2个篮子
第一个放8,再把2个放入剩余2个篮子
第一个放7,再把3个放入剩余2个篮子
.
总之,M个苹果,N个篮子,
第一个放a个,a的范围是从M减小到0,
而再将(M-a)个苹果放入N-1个篮子.
但是放的时候要一定满足“前面的不小于后面的”.

思路2：
f(m, n)表示将m个苹果放入n个盘子 
f(10,3) = f(10, 2) + f(7, 3) 
10个苹果放入3个盘子 = 10个苹果放入2个盘子（有空盘子，有一个盘子不放）
+ 7个苹果放入3个盘子（没有空盘子，每一个盘子里面先各放一个苹果，就只剩下7个苹果）

然后递归 ，下面算法按思路2解 
*/ 

#include<stdio.h>  
int fun(int m,int n){   
    if(m==0||n==1)    
        return 1;     
    if(n>m)  
        return fun(m,m);  //如果前面的小于后面的，则一定会有空盘子，则等于m个苹果放入m个盘子 
    else  
        return fun(m,n-1)+fun(m-n,n);  //有空盘子的情况 +　没有空盘子的情况 
}  
int main(){  
    int t,m,n;  
    scanf("%d",&t);  
    while(t--){     
        scanf("%d%d",&m,&n);  
        printf("%d\n",fun(m,n));  
    }  
    return 0;  
}

分苹果算法

分苹果

相关阅读

栏目导航

推荐阅读

热门阅读