A-A+

整数划分(二)

2012年10月22日 acm未分类 暂无评论 阅读 22 次

整数划分(二)

时间限制: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

递归算法不太会使,但是能马马虎虎写个大概,算法参考:NYOJ七月
[cpp]
#include<iostream>
using namespace std;
int sum;
int p(int n,int k)
{
if(n<k) return 0;
else if(k==1)return 1;
else if(k==n)return 1;
else sum=p(n-1,k-1)+p(n-k,k);
return sum;
}
int main()
{
int n,k,t;
cin >>t ;
while (t--)
{
sum=0;
cin>>n>>k;
cout<<p(n,k)<<endl;
}
return 0;
}
[/cpp]

标签:

给我留言

Copyright © C/C++程序员之家 保留所有权利.   Theme  Ality 浙ICP备15011757号-3

用户登录