输出和为一个给定整数的所有组合 C/C++

/*
输出和为一个给定整数的所有组合
例如n=5
5=1+4;5=2+3(相加的数不能重复)
则输出
5 = 1+4
5 = 2+3
这里注意,不能考虑负数,否则将有无数种情况。
*/

#include <stdio.h>

/*
输入正整数M、N,将M分成N个正整数的和,并且N个正整数各不相同,在屏幕上打印出分法个数。例如:M=5,N=2,那么,结果应该为2(有两种分法:5 = 1 + 4或者5 = 2 + 3)。
*/
int nums[100];//假设N<100

void print(int n)//打印函数,可不必理会
{
for(int i = 0; i <= n; i++)
{
printf(“%d “, nums[i]);
}
printf(“n”);
}

int doit(int m, int n, int length = 0)
//递归算法
//length存放nums中元素个数,递归用,但调用时可不必理会
{
if(n == 2)//n==2的情况很容易解决
{
int max = m / 2;
for(int i = 1; i <= max; i++)
{
nums[length] = i;
nums[length + 1] = m – i;
print(length + 1);
}
}
else
{
int max = m / n;
for(int i = 1; i <= max; i++)//大于2的使用递归,直到N==2
{
nums[length] = i;
doit(m – i, n – 1, length + 1);
}
}

return 0;
}

int main()//测试用函数
{
doit(5, 3);
return 0;
}

About 智足者富

http://chenpeng.info

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性:

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>