97.满足特异条件的数列 输入m和n(20>=m>=n>0)求出满足以下方程的正整数数列 i1,i2,...,in，使得：i1+i1+...+in=m，且i1>=i2...>=in。例如： 当n=4, m=8时，将得到如下5 个数列： 5 1 1 1 4 2 1 1 3 3 1 1 3 2 2 1 2 2 2 2 *问题分析与算法设计 可将原题抽象为：将M分解为N个整数，且N个整数的和为M，i1>=i2>=...>=in。分解整数的方法很低多，由于题目中有"i1>=i2>=.....>=in，提示我们可先确定最右边in元素的值为1，然后按照条件使前一个元素的值一定大于等于当前元素的值，不断地向前推就可以解决问题。下面的程序允许用户选定M和N，输出满足条件的所有数列。 *程序与程序注释 #include<stdio.h> #define NUM 10 /*允许分解的最大元素数量*/ int i[NUM]; /*记录分解出的数值的数组*/ void main() { int sum,n,total,k,flag,count=0; printf("Please enter requried terms(<=10):"); scanf("%d",&n); printf(" their sum:"); scanf("%d",&total); sum=0; /*当前从后向前k个元素的和*/ k=n; /*从后向前正在处理的元素下标*/ i[n]=1; /*将最后一个元素的值置为1作为初始值*/ printf("There are following possible series:\n"); while(1) { if(sum+i[k]<total) /*若后k位的和小于指定的total*/ if(k<=1) /*若正要处理的是第一个元素*/ {i[1]=total-sum;flag=1;} /*则计算第一个元素的并置标记*/ else{ sum+=i[k--]; i[k]=i[k+1]; /*置第k位的值后k-1*/ continue; /*继续向前处理其它元素*/ } else if(sum+i[k]>total||k!=1) /*若和已超过total或不是第一个元素*/ { sum-=i[++k]; flag=0;} /*k向后回退一个元素*/ else flag=1; /*sum+i[k]=total&&k=1 则设置flag标记*/ if(flag) { printf("[%d]:",++count); for(flag=1;flag<=n;++flag) printf("%d",i[flag]); printf("\n"); } if(++k>n) /*k向后回退一个元素后判断是否已退出最后一个元素*/ break; sum-=i[k]; i[k]++; /*试验下一个分解*/ } } *运行结果 Please enter requried terms(<=10):4 their sum:8 There are following possible series: [1]: 5111 [2]: 4211 [3]: 3311 [4]: 3221 [5]: 2222

评论