整数划分（二）

时间限制：

1000 ms  |  内存限制：

65535 KB

难度：

3

 

描述

把一个正整数m分成n个正整数的和，有多少种分法？

例：把5分成3个正正数的和，有两种分法：

1 1 3

1 2 2

 

输入

第一行是一个整数T表示共有T组测试数据(T<=50)

每组测试数据都是两个正整数m,n，其中(1<=n<=m<=100),分别表示要拆分的正数和拆分的正整数的个数。

输出

输出拆分的方法的数目。

样例输入

25 25 3

样例输出

22

1 #include 
         
           2 #include 
          
            3  4 using namespace std; 5  6 int fun(int m, int n)  //等同于把 m 个苹果放在 n 个盘子里，每个盘子不空 7 { 8     if(m < n) 9         return 0;10     if(m == n || n == 1)11         return 1;12     else13         return fun(m-n, n) + fun(m-1, n-1);//分成两种情况：1.至少有一个盘子中放了一个苹果；  2.每个盘子中苹果个数都大于1个14 }15 16 int main()17 {18     int T, n, m;19     scanf("%d", &T);20     while(T--)21     {22         scanf("%d%d", &m, &n);23         printf("%d\n", fun(m, n));24     }25     return 0;26 }27 28 29 //本题更快的方法就是先打表30  31 #include
           
            32 int main()33 {34     int a,b,n,m,k;35     int ok[105][105]={
       0};36     ok[1][1]=1;37     for(a=2;a<=100;a++)38     {39         for(b=1;b<=a;b++)40             ok[a][b]=ok[a-b][b]+ok[a-1][b-1];41     }42     scanf("%d",&k);43     while(k--)44     {45         scanf("%d%d",&n,&m);46         printf("%d\n",ok[n][m]);47     }48 }