NYOJ176整数划分（二）

 

整数划分（二）

时间限制：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),分别表示要拆分的正数和拆分的正整数的个数。

输出

输出拆分的方法的数目。

样例输入

2
5 2
5 3

样例输出

2
2

#include <cstdio>
#include <iostream>

using namespace std;

int fun(int m, int n)  //等同于把 m 个苹果放在 n 个盘子里，每个盘子不空
{
    if(m < n)
        return 0;
    if(m == n || n == 1)
        return 1;
    else
        return fun(m-n, n) + fun(m-1, n-1);//分成两种情况：1.至少有一个盘子中放了一个苹果；  2.每个盘子中苹果个数都大于1个
}

int main()
{
    int T, n, m;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &m, &n);
        printf("%d\n", fun(m, n));
    }
    return 0;
}


//本题更快的方法就是先打表
 
#include<stdio.h>
int main()
{
    int a,b,n,m,k;
    int ok[105][105]={0};
    ok[1][1]=1;
    for(a=2;a<=100;a++)
    {
        for(b=1;b<=a;b++)
            ok[a][b]=ok[a-b][b]+ok[a-1][b-1];
    }
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d%d",&n,&m);
        printf("%d\n",ok[n][m]);
    }
}