算法-数学排列组合问题

Question

输入
每组输入是两个整数n和k。(1 <= n <= 100, 1 <= k <= n)

输出
第一行： 将n划分成若干正整数之和的划分数。
第二行： 将n划分成k个正整数之和的划分数。
第三行： 将n划分成最大数不超过k的划分数。
第四行： 将n划分成若干奇正整数之和的划分数。
第五行： 将n划分成若干不同整数之和的划分数。

Answer 1

#include<iostream.h>
int Func_a(int n,int max) // 将n划分成最大数不超过max的划分数。
{
int counter=0;
int i;

if(max<=1)
{
return 1;
}
else
{
for(i=1;i<=max;i++)
{
counter+=Func_a(n-i,(i<n-i)?i:(n-i));
}

return counter;
}
}

int Func_b(int n,int k,int max) //将n划分成k个不大于max的正整数之和的划分数。
{
int counter=0;
int min,i;

min=(int)((n+k-1)/k);
if(k==1||k==n)
{
return 1;
}
else
{
min=n-(int)(n/k)*(k-1);
for(i=min;(i<=n-k+1&&i<=max);i++)
{

counter+=Func_b(n-i,k-1,i);
}

return counter;
}
}

int Func_c(int n,int max) //将n划分成若干奇正整数之和的划分数。
{
int counter=0;
int i;

if(max<=1)
{
return 1;
}
else
{
for(i=1;2*i<=max+1;i++)
{
counter+=Func_c(n-2*i+1,(i<n-2*i+1)?i:(n-2*i+1));
}
return counter;
}
}

int Func_d(int n,int max) // 将n划分成若干不同整数之和的划分数。
{
int counter=0;
int i;

if(max*(max-1)/2<n)
{
return 0;
}else{
if(max*(max-1)/2==n||n==0)
{
return 1;
}else{
for(i=1;i<max;i++)
{
counter+=Func_d(n-i,i);
}
return counter;
}
}
}

void main()
{
int n,k;
cout<<"输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)n";
cin>>n>>k;
cout<<Func_a(n,n)<<endl;//第一行： 将n划分成若干正整数之和的划分数。

cout<<Func_b(n,k,n-k+1)<<endl;//第二行： 将n划分成k个正整数之和的划分数。

cout<<Func_a(n,k)<<endl;//第三行： 将n划分成最大数不超过k的划分数。

cout<<Func_c(n,n)<<endl;//第四行： 将n划分成若干奇正整数之和的划分数。

cout<<Func_d(n,n)<<endl;//第五行： 将n划分成若干不同整数之和的划分数。

cout<<endl;//第六行： 打印一个空行。

}

评论人: KnightZLJ 发布时间: 2009-11-5 0:32:28
#include<iostream.h>
int Func_a(int n,int max) // 将n划分成最大数不超过max的划分数。
{
int counter=0;
int i;

if(max<=1)
{
return 1;
}
else
{
for(i=1;i<=max;i++)
{
counter+=Func_a(n-i,(i<n-i)?i:(n-i));
}

return counter;
}
}

int Func_b(int n,int k,int max) //将n划分成k个不大于max的正整数之和的划分数。
{
int counter=0;
int min,i;

min=(int)((n+k-1)/k);
if(k==1||k==n)
{
return 1;
}
else
{
min=n-(int)(n/k)*(k-1);
for(i=min;(i<=n-k+1&&i<=max);i++)
{

counter+=Func_b(n-i,k-1,i);
}

return counter;
}
}

int Func_c(int n,int max) //将n划分成若干奇正整数之和的划分数。
{
int counter=0;
int i;

if(max<=1)
{
return 1;
}
else
{
for(i=1;2*i<=max+1;i++)
{
counter+=Func_c(n-2*i+1,(i<n-2*i+1)?i:(n-2*i+1));
}
return counter;
}
}

int Func_d(int n,int max) // 将n划分成若干不同整数之和的划分数。
{
int counter=0;
int i;

if(max*(max-1)/2<n)
{
return 0;
}else{
if(max*(max-1)/2==n||n==0)
{
return 1;
}else{
for(i=1;i<max;i++)
{
counter+=Func_d(n-i,i);
}
return counter;
}
}
}

void main()
{
int n,k;
cout<<"输入是两个整数n和k。(1 <= n <= 50, 1 <= k <= n)n";
cin>>n>>k;
cout<<Func_a(n,n)<<endl;//第一行： 将n划分成若干正整数之和的划分数。

cout<<Func_b(n,k,n-k+1)<<endl;//第二行： 将n划分成k个正整数之和的划分数。

cout<<Func_a(n,k)<<endl;//第三行： 将n划分成最大数不超过k的划分数。

cout<<Func_c(n,n)<<endl;//第四行： 将n划分成若干奇正整数之和的划分数。

cout<<Func_d(n,n)<<endl;//第五行： 将n划分成若干不同整数之和的划分数。

}