题目链接:
http://poj.org/problem?id=1664
题目描述:
有n个苹果,m个盒子,盒子和苹果都没有顺序,盒子可以为空,问:有多少种放置方式?
解题思路:
当前有n个苹果,m个盒子。
(1):假设当前最少的盒子放置一个苹果,则给m个盒子分别放一个苹果,剩下n-m个苹果。
(2):假设当前最少的盒子不放苹果,则剩m-1个box,n个苹果。
代码:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
using namespace std; int f (int n, int m); int main ()
{
int t, n, m;
scanf ("%d", &t);
while (t --)
{
scanf ("%d %d", &n, &m);
printf ("%d\n", f(n, m));
}
return ;
} int f (int n, int m)
{
if (n < )//没有苹果了,违法
return ;
if (n == || m == )//一个盒子,无论有几个苹果,就只有一种放置方法,没有苹果一样;
return ;//若有一个苹果就需要讨论累加到哪一个剩余的盒子里,盒子没有顺序,但是盒子里苹果数目不同
return f (n-m, m) + f (n, m-);
}