7-37 整数分解为若干项之和
程序员文章站
2022-06-07 16:53:42
...
7-37 整数分解为若干项之和
题目描述：
将一个正整数N分解成几个正整数相加，可以有多种分解方法，例如7=6+1，7=5+2，7=5+1+1，…。编程求出正整数N的所有整数分解式子。
输入格式：
每个输入包含一个测试用例，即正整数N (0<N≤30)。
输出格式：
按递增顺序输出N的所有整数分解式子。递增顺序是指：对于两个分解序列N ={n1,n2,⋯}和N2={m1,m2,⋯}，若存在i使得n1=m1,⋯,ni=mi，但是ni+1 <mi+1,则N1序列必定在N2 序列之前输出。每个式子由小到大相加，式子间用分号隔开，且每输出4个式子后换行。
输入与输出样例：
思路分析：
该题目要求将一个整数的分解因子的组合，全部输出出来，该题可以用DFS深搜算法去解决，通过递归和回溯来解决，例如，输入7，从b=1开始累加a1,a2,a3,a4⋯an.，当b=7，就输出该组合，当b>7时候,就回溯到上一个节点开始累加，当小于时候，继续累加，废话不多说，直接上代码。
错误示范代码：
#include<stdio.h>
int b[30],c=0,d=0,m=0;
void lemon(int a)//这里应该使变量a 为全局变量，让主函数和分函数一起使用
{
if(c==a)
{
printf("%d=",a);
for(int h=0;h<d;h++)
{
if(h!=d-1)
printf("%d+",b[h]);
else
printf("%d",b[h]);
}
m++;
if(m%4==0)
printf("\n");
else if(m%4!=0 && d!=0)
printf(";");
return;
}
if(c>a)
return;
if(c<a)
{
for(int e=1;e<=a;e++)//这里如果e=1，会导致后面分解出现问题，当7=1+1+1+1+3时候，应该以这样输出，但是 如果e=1
//它会以7=1+1+1+1+2+1输出，因为递归时。导致e=1，满足c==a，输出分解因子。
{
b[d++]=e;
c+=e;
lemon(a);
c-=e;
d--;
}
}
}
int main()
{
int a;//应为全局变量才行
scanf("%d",&a);
lemon(a);
}
运行过程：
原因分析：
该代码，第一次我错误将a当作局部变量传递给函数以及分解因子首位固定为1，而应该将a变成全局变量以及e的值随着分解因子的值所变化。
正确代码：
#include<stdio.h>
int b[30],c=0,d=-1,m=0,a;//全局变量方便函数与主函数操作
void lemon(int x)
{
if(c==a)//当分解因子的值等于输入的值时，说明已经分解完成。输出数组中的值。
{
printf("%d=",a);
for(int h=0;h<=d;h++)
{
if(h!=d)
printf("%d+",b[h]);
else
printf("%d",b[h]);
}
m++;
if(m%4==0)
printf("\n");
else if(m%4!=0 && d!=0)
printf(";");
return;
}
if(c>a)//当值大于a时，回溯到上一个节点，
return;
if(c<a)//当值小于a时候，说明还未完全分解，继续将整数分解。
{
for(int e=x;e<=a;e++)//这里会有一个小错误，如果让e=1，后面将会出现值错误。
{
b[++d]=e;//将每一个 分解因子，存入数组中，
c+=e;//记录分解因子的和。
lemon(e);
c-=e;//回溯上一个节点后，减去该e的值
d--;//改变数组的下标
}
}
}
int main()
{
scanf("%d",&a);
lemon(1);
}