C趣味编程百例(32)满足特异条件的数列

文章作者 100test 发表时间 2007:03:10 17:34:35
来源 100Test.Com百考试题网

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
#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] 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