一、問題引入

小明在數(shù)學(xué)課上遇到一道奧數(shù)題是這樣的，【】3*6528=3【】*8256，在兩個【】內(nèi)填入相同的數(shù)字使得等式成立。

不用分析了，直接show代碼：

for(int i=1;i<=9;i++)if((i*10+3)*6528==(30+i)*8256)printf("%d",i); //答案為4

?

這就是最簡單的枚舉算法。

枚舉算法的基本思想是：有序地去嘗試每一種可能。

?

二、問題拓展

現(xiàn)在小明又遇到一個稍微復(fù)雜一點的奧數(shù)題，【】【】【】+【】【】【】=【】【】【】，將數(shù)字1~9分別填入9個【】中，每個數(shù)字智能使用一次使得等式成立。

分析：根據(jù)枚舉思想我們只需要枚舉每一位上所有可能的數(shù)就好了。

int a,b,c,d,e,f,g,h,i,total=0;for(a=1;a<=9;a++) //第1個數(shù)的百位for(b=1;b<=9;b++) //第1個數(shù)的十位for(c=1;c<=9;c++) //第1個數(shù)的個位for(d=1;d<=9;d++) //第2個數(shù)的百位for(e=1;e<=9;e++) //第2個數(shù)的十位for(f=1;f<=9;f++) //第2個數(shù)的個位for(g=1;g<=9;g++) //第3個數(shù)的百位for(h=1;h<=9;h++) //第3個數(shù)的十位for(i=1;i<=9;i++) //第3個數(shù)的個位 { //接下來要判斷每一位上的數(shù)互不相等 if(a!=b && a!=c && a!=d && a!=e && a!=f && a!=g && a!=h && a!=i&& b!=c && b!=d && b!=e && b!=f && b!=g && b!=h && b!=i&& c!=d && c!=e && c!=f && c!=g && c!=h && c!=i&& d!=e && d!=f && d!=g && d!=h && d!=i&& e!=f && e!=g && e!=h && e!=i&& f!=g && f!=h && f!=i&& g!=h && g!=i&& h!=i&& a*100+b*10+c+d*100+e*10+f==g*100+h*10+i){total++;printf("%d%d%d+%d%d%d=%d%d%d\n",a,b,c,d,e,f,g,h,i);}}printf("total=%d",total/2); //這是關(guān)鍵return 0;

?

注意：因為173+286=459與286+173=459是同一種組合，因此我們在輸出的時候需要將total的值除以2.

?

三、代碼優(yōu)化

但是上述代碼中的if判斷條件似乎太長了，我這輩子估計都很難看到如此冗雜的判斷條件了...

所以我們用一個book數(shù)組來解決互不相等的問題：

int a[10],i,total=0,book[10],sum; //這里用a[1]-a[9]來代替剛才的a~ifor(a[1]=1;a[1]<=9;a[1]++)for(a[2];a[2]<=9;a[2]++)for(a[3];a[3]<=9;a[3]++)for(a[4];a[4]<=9;a[4]++)for(a[5];a[5]<=9;a[5]++)for(a[6];a[6]<=9;a[6]++)for(a[7];a[7]<=9;a[7]++)for(a[8];a[8]<=9;a[8]++)for(a[9];a[9]<=9;a[9]++){for(i=1;i<=9;i++) //初始化數(shù)組book[i]=0;for(i=1;i<=9;i++) //如果某個數(shù)出現(xiàn)過就標(biāo)記一下book[a[i]]=1;sum=0;for(i=1;i<=9;i++)sum+=book[i]; //統(tǒng)計供出現(xiàn)了多少個不同的數(shù) if(sum==9&&a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9]){total++;printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);} }printf("total=%d",total/2);return 0;

上面這段代碼中，為了方便標(biāo)記哪些數(shù)出現(xiàn)過，我將循環(huán)變量a、b、c、d、e、f、g、h、i用一個一維數(shù)組a代替，用book數(shù)組來標(biāo)記1~9每個數(shù)是否出現(xiàn)過，默認(rèn)為0，出現(xiàn)過的就設(shè)為1。然后我們只需要判斷book數(shù)組中有多少個1就可以了。如果恰好有9個1則表示，1~9每個數(shù)都有且只出現(xiàn)過一次。

?

四、篇外：dfs求解

#include<stdio.h> int a[10],book[10],total=0; void dfs(int step) //step表示現(xiàn)在站在第幾個盒子面前 {int i;if(step==10){if(a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]==a[7]*100+a[8]*10+a[9]){/*如果滿足要求，可行解+1，并打印這個解*/ total++;printf("%d%d%d+%d%d%d=%d%d%d\n",a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9]);}return; //返回之前的一步（最近調(diào)用的地方） }/*站在第step個盒子面前，按照1、2、3...n的順序一一嘗試*/for(i=1;i<=9;i++){if(book[i]==0){a[step]=i;book[i]=1;dfs(step+1);book[i]=0;}} return; } int main() {dfs(1);printf("total=%d",total/2);return 0; } 奧數(shù)算式求解-dfs

?

總結(jié)

以上是生活随笔為你收集整理的坑爹的奥数——枚举的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。