暴力放苹果

浏览数：13 / 时间：2015年06月11日

放苹果

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 27339		Accepted: 17355

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

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <stdlib.h>
 4 #include <math.h>
 5 #include <string.h>
 6 using namespace std;
 7 typedef long long ll;
 8 int n,m,cou,a[100];
 9 void dfs(int k,int nn,int mm)///解法1
10 {
11     //printf("%d--",cou);
12     if(mm>m) return ;
13     if(nn==0)
14     {
15         if(mm<=m)
16         {
17             cou++;
18         }
19         return;
20     }
21     for(int i=k; i<=nn; i++)///第i个数不小于第i-1个数，这样不会造成重复。
22     {///如果是从1一直到nn，那么就会生成所有的排列情况，会有重复。
23         dfs(i,nn-i,mm+1);
24     }
25 }
26 int f(int nn,int mm)///解法2
27 {///整数划分
28     ///所谓n关于m的划分，就是n分成任意个非负数部分，但是每一个部分都不超过m
29     ///两种情况: 1 至少存在一个m，相当与n-m后再进行m的划分。
30     ///          2  不存在m，也就是n关于转化成m-1的划分。
31     if(nn<0) return 0;
32     if(nn==1||mm==1) return 1;
33     return f(nn-mm,mm)+f(nn,mm-1);
34 }
35 int main()
36 {
37     int t;
38     scanf("%d",&t);
39     while(t--)
40     {
41         scanf("%d%d",&n,&m);
42         /*{cou=0;
43         dfs(1,n,0);
44         printf("%d\n",cou);}*/
45             printf("%d\n",f(n,m));
46     }
47     return 0;
48 }