当前位置:首页 > 题库 > 正文内容

7-9 数的划分 (10 分)

Luz3个月前 (03-20)题库290
7-9 数的划分 (10 分)

将整数n分成k份,且每份不能为空,任意两个解不能相同(不考虑顺序)。

例如:n=7,k=3,下面三种分法被认为是相同的。

{1,1,5};{1,5,1};{5,1,1};

问有多少种不同的分法。 输出一个整数,即不同的分法。

输入格式:

两个整数n,k(6<n≤200,2≤k≤6),中间用单个空格隔开。

输出格式:

一个整数,即不同的分法。

输入样例:

8 2

输出样例:

4
作者
严华云
单位
湖州师范学院
代码长度限制
16 KB
时间限制
400 ms
内存限制
64 MB
#include<iostream>
using namespace std;
int n,k,p[10000],sum=0,ans=0;
void dfs(int pre,int num,int cnt)
{
    if(cnt==1) 
    {
        ans++;
        //for(int i=0;i<k-1;i++){
        //	cout<<p[i]<<' '; 
		//}
		//cout<<num<<endl;
        return;
    }
    for(int i=pre;i<=num/cnt;i++){
		p[k-cnt]=i;
    	dfs(i,num-i,cnt-1); 
	}  
}
int main()
{
    cin>>n>>k;
    dfs(1,n,k);
   cout<<ans;
    return 0;
}


分享给朋友:

发表评论

访客

◎欢迎参与讨论,请在这里发表您的看法和观点。