|
Csdn上的一个问题
程序运行：
输入n,输出其和等于n的所有不增的正整数和式。例如，n=4,程序将输出：
4=4；
4=3+1
4=2+2
4=2+1+1
4=1+1+1+1
但如果用递归方法
算法：
递归函数设置两个参数：参数i是本次递归调用要分解的数，参数k是本次递归调用将分
解出第k个和数。
1） 对要分解的数i，可分解出来的数j共有i种可能选择，它们分别是：i,i-1,...,2,1。 但是为了保证分解出来的和数依次构成不增的正整数数列，则要求从i分解出来的和数j不能超过a[k-1]。为了保证上述要求对第一步(k=1)分解也成立，程序可以在a[0]中预置n，即第一个和数最大为n。
2） 在分解过程中，当分解出来的数j=i时，说明已完成一个完整的和式分解，应该将和式输出；当分解出来的数j<i时，说明还有i-j需要分解，并且分解出第k+1个以及之后的和数。
 #include<stdio.h>
#undef N
#define N 5
  void rd(int i,int *b, int k) ...{
 int j = 0;
int t = 0;
for(j=i;j>=1;j--)
  if(j<=b[k-1])...{
b[k]=j;
if(j==i)
...{
printf("%d=%d",N, b[1]);
for(t=2;t<=k;t++)
printf("+%d", b[t]);
printf(" ");
 }
else
rd(i-j, b, k+1); //继续分解的数是i-j,分解出第k+1个和数
}
 }
int main(int argc, char* argv[])
...{
int b[N+1];
b[0]=N;
rd(N, b, 1);
return 0;
}
|
