C趣味編程百例(32)滿足特異條件的數(shù)列

97.滿足特異條件的數(shù)列
     輸入m和n(20>=m>=n>0)求出滿足以下方程的正整數(shù)數(shù)列 i1,i2,...,in，使得：i1+i1+...+in=m，且i1>=i2...>=in。例如：
     當(dāng)n=4, m=8時(shí)，將得到如下5 個(gè)數(shù)列：
     5 1 1 1 4 2 1 1 3 3 1 1 3 2 2 1 2 2 2 2
    *問題分析與算法設(shè)計(jì)
     可將原題抽象為：將M分解為N個(gè)整數(shù)，且N個(gè)整數(shù)的和為M，i1>=i2>=...>=in。分解整數(shù)的方法很低多，由于題目中有"i1>=i2>=.....>=in，提示我們可先確定最右邊in元素的值為1，然后按照條件使前一個(gè)元素的值一定大于等于當(dāng)前元素的值，不斷地向前推就可以解決問題。下面的程序允許用戶選定M和N，輸出滿足條件的所有數(shù)列。
    *程序與程序注釋
    #include
    #define NUM 10 /*允許分解的元素?cái)?shù)量*/
    int i[NUM]; /*記錄分解出的數(shù)值的數(shù)組*/
    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; /*當(dāng)前從后向前k個(gè)元素的和*/
     k=n; /*從后向前正在處理的元素下標(biāo)*/
     i[n]=1; /*將最后一個(gè)元素的值置為1作為初始值*/
     printf("There are following possible series:\n");
     while(1)
     {
     if(sum+i[k]     if(k<=1) /*若正要處理的是第一個(gè)元素*/
     {i[1]=total-sum;flag=1;} /*則計(jì)算第一個(gè)元素的并置標(biāo)記*/
     else{
     sum+=i[k--];
     i[k]=i[k+1]; /*置第k位的值后k-1*/
     continue; /*繼續(xù)向前處理其它元素*/
     }
     else if(sum+i[k]>total||k!=1) /*若和已超過total或不是第一個(gè)元素*/
     { sum-=i[++k]; flag=0;} /*k向后回退一個(gè)元素*/
     else flag=1; /*sum+i[k]=total&&k=1 則設(shè)置flag標(biāo)記*/
     if(flag)
     {
     printf("[%d]:",++count);
     for(flag=1;flag<=n;++flag)
     printf("%d",i[flag]);
     printf("\n");
     }
     if(++k>n) /*k向后回退一個(gè)元素后判斷是否已退出最后一個(gè)元素*/
     break;
     sum-=i[k];
     i[k]++; /*試驗(yàn)下一個(gè)分解*/
     }
    }
    *運(yùn)行結(jié)果
     Please enter requried terms(<=10):4
     their sum:8