2.1 蠻力法

2.1.1 蠻力法的設(shè)計思想

蠻力法（bruteforcemethod，也稱窮舉法）通常采用一定的策略依次處理待求解問題的所有數(shù)據(jù)，從而找出問題的解，是一種簡單直接地解決問題的方法。例如，對于給定的整數(shù)a和非負(fù)整數(shù)n，計算an的值，最直接的想法就是把1和a相乘n次。

蠻力法常常直接基于問題的描述，所以是最容易應(yīng)用的方法。但是，用蠻力法設(shè)計的算法其時間性能往往也是最低的。因此，蠻力法通常用來解決非常基本的問題。在本書中，有關(guān)線性表的基本操作、順序查找算法、模式匹配BF算法、起泡排序、簡單選擇排序等算法都是蠻力法的應(yīng)用實(shí)例。

2.1.2 算法設(shè)計實(shí)例——數(shù)字謎

【問題】 求解如圖2-1所示數(shù)字謎。

圖2-1 數(shù)字謎

【想法】 將A、B、C依次試探每一個可能解，約束條件是滿足等式關(guān)系（ABB）×B=ACBC。

【算法】 注意到，A的窮舉范圍是1～9，B的窮舉范圍是2～9（因為乘法結(jié)果有進(jìn)位，則B至少是2），C的窮舉范圍是0～9，算法用偽代碼描述如下：

【程序】 可以在主函數(shù)中直接實(shí)現(xiàn)數(shù)字謎算法，程序如下：

            #include＜stdio.h＞                            //使用庫函數(shù)printf
            intmain（）
            {
              intA，B，C，temp1，temp2，flag=0；
              for（A=1；A＜=9；A++）                      //將A從1到9依次試探

                  for（B=2；B＜=9；B++）                  //將B從2到9依次試探
                    for（C=0；C＜=9；C++）                //將C從0到9依次試探
                    {
                      temp1=A*100+B*10+B；                //計算ABB的值
                      temp2=A*1000+C*100+B*10+C；         //計算ACBC的值
                      if（temp1*B==temp2）                //如果ABB*B等于ACBC
                      {
                        printf（＂A=%d，B=%d，C=%d\n＂，A，B，C）；    //輸出結(jié)果
                        printf（＂%d×%d=%d\n＂，temp1，B，temp2）；
                        flag=1；
                      }                                   //結(jié)束if語句
                    }                                     //結(jié)束內(nèi)層for循環(huán)
                  if（flag==0）printf（＂無解\n＂）；     //窮舉過程中沒有滿足約束條件的解
                  return0；                               //將0返回操作系統(tǒng)，表明程序正常結(jié)束
              }