題目要求:
    求一個9位數(shù),該數(shù)的每一位均是1-9之間的數(shù),但是每位上的數(shù)字各不相同.最后使得這個9位數(shù)從高位開始,前一位能被1整除,前兩位能被2整除,前三位能被3整除,前四位能被4整除……一直到整個9位數(shù)能被9整除.

算法設計:
    對于這類題,相信大多數(shù)人一拿到手就想到窮舉所有的可能性(如果你不這樣想,那你就是例外了:)呵呵).剛開始偶也想到了用9重for循環(huán)來窮舉,后來想用遞歸能否實現(xiàn)呢?好,我們來結合程序說明,這樣比較清晰些哈.我們用一個數(shù)組a來存儲所有可能用到的數(shù)字,其中a[0]不用,后面的就依次為1-9對應數(shù)組a[1]到a[9].而后用另外一個數(shù)組b來存儲已經(jīng)被使用了的數(shù)字,如我們使用了數(shù)字3(數(shù)組a中的a[3],那我們就使b[3]=a[3],同時要從a中剔除3這個數(shù)以表示這個數(shù)字已經(jīng)被使用了,所以就置a[3]=0.程序中還有一個深度變量depth,表示當前的深度,如剛開始的時候為1,此時depth=1,如果result=12,則depth=2,這樣設置是為了便于用result對depth整除運算,免得又增加一個變量.最后到第9層深度的時候,即已經(jīng)窮舉到第9個數(shù)了,如果有結果則輸出.
    好了,大致過程說了.我們就用實例來說明程序的過程.首先depth=1,窮舉a中的每一個數(shù),所以result=1,由于result能被1整除,所以滿足條件.此時1已經(jīng)被使用了,所以要在b中保存這個數(shù),并從a中剔除它,所以有b=a;a=0;然后進入下一個數(shù)字的猜測,即depth=2,由于a[1]=0了,所以此時窮舉的數(shù)就是從2開始了,使得result=12,此時result也能被2整除,所以就進入第三個數(shù)的猜測.如果我們在這里改一下,使a[2]=3,則result=13就不能被2整除了,所以就要返回到上一次函數(shù)調(diào)用的位置,即getnum(depth+1);此時注意,我們已經(jīng)從第2層深度返回到第一層深度了.然后執(zhí)行后面的語句a=b;使剛才被剔除的數(shù)又重新回到a中來(因為這個數(shù)在第2個位置不合適,但是它又必須到其他的位置,所以要重新加入到a中來,以便其他位的窮舉).呵呵,不曉得說清楚沒,大家有興趣的話,可以在紙上畫一畫.好了,我把程序貼出來,大家看看吧:)

源程序(編譯通過)

#include < stdio.h >

int a[]={0,1,2,3,4,5,6,7,8,9}; //所有可能的數(shù)字
int b[10] ={0};           //用于臨時存放已經(jīng)被用了的數(shù)字
long result=0;           //最后的結果

void getnum(int depth)    //遞歸函數(shù)求解最后的結果,depth為深度,從1開始計算
{
 int i;
 if(depth==10)return;
 for(i=1;i < 10;i++)
    if(a !=0){           //窮舉每一個在數(shù)組a中的可能的數(shù)
        result=result*10+a;
        if(result%depth==0){    //看這個求得的數(shù)是否滿足整除的條件,如果是則將
             b=a;          //該數(shù)字放入已經(jīng)使用數(shù)字的數(shù)組b中,同時使a中對?
             a=0;               //應位的數(shù)為0,表使用了,并從該數(shù)組中剔除.
             getnum(depth+1);
             a=b;          //恢復被剔除的數(shù),窮舉下一個可能的數(shù)
             if(depth==9)printf("%ld \n",result);
           }
        result/=10;               //同時使結果恢復到上一個狀態(tài)
       }
}

void main()
{
 getnum(1);   //從深度為1開始窮舉,即只有1位數(shù)的情況
 getch();
}

    最后的結果就是381654729