有个算法问题想请教大家,题目是这样子:
比如对于4来说,所有和为4的情况:
4 =4
3+1 =4
2+1+1 =4
2+2 =4
1+1+1+1 =4
那么要得到所有和等于n的所有情况,怎么写这个算法?


谢谢!

用递归应该可以做出来

递归。

觉得简单，就是写不对

#include <stdio.h>

int q(int n,int m) //将N分解成由1到M中的数的和
{
if(n<1||m<1)
return 0;
if(n==1||m==1)
return 1;
if(n<m)
return(q(n,n));
if(n==m)
return(q(n,m-1))+1;
return q(n,m-1)+q(n-m,m);
}

main()
{int n;
scanf("%d",&n);
printf("%d",q(n,n));
}

#define N 40
int a[N],r[N];
void main()
{int i,k,n;
printf("请输入 n:");
scanf("%d",&n);
a[0]=r[0]=n;
k=1;
while(1)
{if(r[k-1]==0)
{printf("%d=%d",a[0],a[1]);
for(i=2;i<k;i++)
printf("+%d",a[i]);
printf("\n");
while(k>1&&a[k-1]==1)
k--;
if(k==1) break;
a[k-1]--;
r[k-1]++;
}
else
{a[k]=r[k-1]<a[k-1]? r[k-1]:a[k-1];
r[k]=r[k-1]-a[k];
k++;
}
}
}

    楼上用的是回溯法吧

感谢PcrazyC和yigedaizi的热心帮忙，两人的程序都可以运行。我昨天晚上回去也看了，后来发现一个新的想法也可以实现，用动态规划的思想，就是从一开始，一直往大的方向扩展，最终也可以实现。多谢大家帮忙

yigedaizi，你的程序有点不明白，能不能给点说明？

定义一个数组r[]，用于存储当前还未分解的余数。在求
一个解的第K步时，a[k]为第K个和数，r[k]为相应的余数。当找到一个分解后（此步r[k]等
于0），输出解，并作回溯处理，从当前K退回到第一个不为1的和数，将其减1，并将其余数
加1，准备去找另一个解，否则，生成下一步的分解和数与余数.