C語言實(shí)例 九位累進(jìn)可除數(shù)

求九位累進(jìn)可除數(shù)。所謂九位累進(jìn)可除數(shù)就是這樣一個數(shù)：這個數(shù)用到1到9這九個數(shù)字組成，每個數(shù)字剛好只出現(xiàn)一次。這九個位數(shù)的前兩位能被2整除，前三位能被3整除......前N位能被N整除，整個九位數(shù)能被9整除。

*問題分析與算法設(shè)計(jì)

問題本身可以簡化為一個窮舉問題：只要窮舉每位數(shù)字的各種可能取值，按照題目的要求對窮舉的結(jié)果進(jìn)行判斷就一定可以得到正確的結(jié)果。

問題中給出了“累進(jìn)可除”這一條件，就使得我們可以在窮舉法中加入條件判斷。在窮舉的過程中，當(dāng)確定部分位的值后，馬上就判斷產(chǎn)生的該部分是否符合“累進(jìn)可除”條件，若符合，則繼續(xù)窮舉下一位數(shù)字;否則剛剛產(chǎn)生的那一位數(shù)字就是錯誤的。這樣將條件判斷引入到窮舉法之中，可以盡可能早的發(fā)現(xiàn)矛盾，盡早地放棄不必要窮舉的值，從而提高程序的執(zhí)行效率。

為了達(dá)到早期發(fā)現(xiàn)矛盾的目的，不能采用多重循環(huán)的方法實(shí)行窮舉，那樣編出的程序質(zhì)量較差。程序中使用的算法不再是窮舉法，而是回朔法。

*程序說明與注釋

#include

#define NUM 9

int a[NUM+1];

int main()

{

int i,k,flag,not_finish=1;

long sum;

i=1;

/*i:正在處理的數(shù)組元素，表示前i-1個元素已經(jīng)滿足要求，正處理的是第i個元素*/

a[1]=1; /*為元素a[1]設(shè)置初值*/

while(not_finish) /*not_finish=1:處理沒有結(jié)束*/

{

while(not_finish&&i<=NUM)

{

for(flag=1,k=1;flag&&k

if(a[k]==a[i])flag=0; /*判斷第i個元素是否與前i-1個元素重復(fù)*/

for(sum=0,k=1;flag&&k<=i;k++)

{

sum=10*sum+a[k];

if(sum%k)flag=0; /*判斷前k位組成的整數(shù)是否能被k整除*/

}

if(!flag) /*flag=0:表示第i位不滿足要求，需要重新設(shè)置*/

{

if(a[i]==a[i-1]) /*若a[i]的值已經(jīng)經(jīng)過一圈追上a[i-1]*/

{

i--; /*i值減1，退回處理前一個元素*/

if(i>1&&a[i]==NUM)

a[i]=1; /*當(dāng)?shù)趇位的值達(dá)到NUM時，第i位的值取1*/

else if(i==1&&a[i]==NUM) /*當(dāng)?shù)?位的值達(dá)到NUM時結(jié)束*/

not_finish=0; /*置程序結(jié)束標(biāo)記*/

else a[i]++; /*第i位的值取下一個,加1*/

}

else if(a[i]==NUM) a[i]=1;

else a[i]++;

}

else /*第i位已經(jīng)滿足要求，處理第i+1位*/

if(++i<=NUM) /*i+1處理下一元素，當(dāng)i沒有處理完畢時*/

if(a[i-1]==NUM) a[i]=1; /*若i-1的值已為NUM，則a[i]的值為1*/

else a[i]=a[i-1]+1; /*否則，a[i]的初值為a[i-1]值的"下一個"值*/

}

if(not_finish)

{

printf("\nThe progressire divisiable number is:");

for(k=1;k<=NUM;k++) /*輸出計(jì)算結(jié)果*/

printf("%d",a[k]);

if(a[NUM-1]

else a[NUM-1]=1;

not_finish=0;

printf("\n");

}

}

}

*運(yùn)行結(jié)果

The progressire divisible number is: 381654729

*思考題

求N位累進(jìn)可除數(shù)。用1到9這九個數(shù)字組成一個N(3<=N<=9)位數(shù)，位數(shù)字的組成不限，使得該N位數(shù)的前兩位能被2整除，前3位能被3整除，......，前N位能被N整除。求滿足條件的N位數(shù)。

深圳北大青鳥