POJ-1664-放苹果

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

一步步递归就行了，但要注意好递归出口和判断的条件。 还有为了避免重复，我们让下一个盘子放的苹果数要小于等于上一个盘子。

#include <stdio.h> #include <iostream> using namespace std; int count; void fun(int m,int n,int max)//m是当前盘子放的苹果数，n是当前还有几个盘子，max是下一个盘子放的最大的苹果数。 { if(m==0&&n==0) //递归出口 有当盘子数和苹果数都为零时才算一种方法 { count++; return ; } else if(m<0||n<0) return ; for(int i=max;i>=0;i--)//i表示下个盘子放的最大苹果数 不能从1开始 因为每递归一次max都会不相等。 { fun(m-i,n-1,i); //为了避免重复，我们让下一个盘子放的苹果数要小于等于上一个盘子。 //一共有m-i个苹果准备放， 还剩n-1个盘子 ， 下个盘子放的最大数是i 并且i只与上个盘子的的苹果数有关 } } int main() { int t; scanf("%d",&t); while(t--) { int m,n; scanf("%d%d",&m,&n); count=0; fun(m,n,m); //一共有7个苹果准备放，当前有3个盘子，第一个盘子最多放7个苹果。 printf("%d\n",count); } return 0; }