• 炮兵問題的優化，設立邏輯數組

蠻力法設計思想

有策略地窮舉 + 驗證

• 制定窮舉策略
• 避免重復

簡單來說，就是列舉問題所有可能的解，然后去看看是否滿足題目要求，是一種逆向解題方式。（我也不知道答案是什么，但是我知道答案肯定在這些范圍里面，我一個個試就完了。）

所以我們應該做的是

• 知道可能的答案都有哪些
• 使用方法將其一一列舉
• 將每個解依次與條件比照

蠻力法使用范圍

• 所有解空間：例如a,b,c取值范圍都是 0~9，問abc組成的三位數的所有情況
• 所有路徑：遍歷圖、遍歷樹

蠻力法的格式

蠻力法由循環和選擇語句構成

• 使用循環，窮舉所有情況
• 使用選擇，判斷當前情況是否成立
  • 若成立，則得到問題的解
  • 若不成立，則繼續循環

循環 + 分支

for(){for(){// 獲取X所有可能的情況if(X滿足條件){printf("X");}}
}

蠻力法思想：窮舉所有情況，找到符合條件的。

這也意味著，得能夠窮舉，因此問題規模不能太大。

示例1：求完全數

思想：窮舉所有數字，將符合條件的找出來。

關鍵點：求數字的所有因子。
對于數x，因子y，需要x % y = 0，此處y也需要嘗試1 ~ x-1的所有數。

判斷因子和是否等于x。

因此程序為

// 求完全數
#include <iostream>
using namespace std;int main() {for (int i = 2; i <= 1000; i++) {int sum = 0;for (int j = 1; j <= i - 1; j++) {if (i % j == 0) { // 若是因子sum += j;}}if (sum == i) {cout << "完全數：" << i << endl;}}return 0;
}

這里還有點bug，是數學知識不完備，因子在1 ~ m/2的范圍，因子不可能比原數字的一半還要大（除了它本身），我們循環地太多了。內循環應該是j <= i/2。

結果為：

我們需要非常清晰地體會到構建程序框架的思維過程。

int main() {// 窮舉所有情況for (int i = 2; i <= 1000; i++) {// 求因子之和// 比較因子與該數是否相等}return 0;
}

然后，我們再實現其細節。

充分體會：窮舉情況，再依次判斷的計算過程。

示例2：求水仙花數

在數字100~999中，求水仙花數，例如：1³ + 5³+ 3³ = 153。

同樣地，窮舉 + 驗證。

關鍵點：求一個三位數的每一位的數。

先建立思維框架

// 窮舉100~999的所有數字
for(){// 求三位數的每一位數，將其立方和相加// 判斷數字與其立方和是否相等}

代碼為：

// 求水仙花數
#include <iostream>
using namespace std;int main() {for (int i = 100; i <= 999; i++) {int sum = 0;int temp = i;while (temp){int x = temp % 10;sum += (x*x*x);temp /= 10;}if (i == sum) {cout << "水仙花數：" << i << endl;}}return 0;
}

答案為：

再強調一遍

• 循環 + 選擇
• 先構建思維框架，再填充細節

示例3：象棋算式

我們先將問題的輸入找到：也就是5個變量，且滿足

• 每個變量范圍是0~9
• 5個變量各不相同

然后窮舉所有的可能性，看是否能夠滿足表達式，這是恐怖的5層循環，但是問題規模還在可接受范圍內。

我們試試看。

• 兵：a
• 炮：b
• 馬：c
• 卒：d
• 車：e

#include <iostream>
using namespace std;int main() {int a, b, c, d, e;for (a = 0; a <= 9; a++) {for (b = 0; b <= 9; b++) {for (c = 0; c <= 9; c++) {for (d = 0; d <= 9; d++) {for (e = 0; e <= 9; e++) {// 若5個數都不同，再看是否滿足表達式if (!(a == b || a == c || a == d || a == e|| b == c || b == d || b == e|| c == d || c == e|| d == e)) {int add1 = a * 1000 + b * 100 + c * 10 + d;int add2 = a * 1000 + b * 100 + e * 10 + d;int sum = e * 10000 + d * 1000 + c * 100 + a * 10 + d;if (sum == add1 + add2) {cout << "兵 = " << a << " 炮 = " << b << " 馬 = " << c << " 卒 = " << d << " 車 = " << e << endl;}}}}}}}return 0;
}

結果是

不過顯然，太低效率了，如果有n的話，這個算法的時間復雜度是O(n⁵)，這幾乎是不可接受的，太暴力了，問題規模顯得有點大，是10⁵了。

所以，我們雖然遵循了 循環 + 選擇，但是，窮舉地過于直接，看看有沒有其他辦法呢？

思想：即便是窮舉，也要“聰明地”窮舉

同樣是窮舉，也有不同的方法，最粗暴的就是循環，一層循環不行就嵌套多重循環……好蠢但是很簡單好想。

我們來看看，同樣是窮舉，不同做法的差異。

示例

對于一個含有6個元素的一維數組，該數組每個數只能是0或1，將所有情況窮舉出來。
例如(0,0,0,0,0,0)、(0,1,0,1,1,0)

最愚蠢的做法，直接6重循環。

#include <iostream>
using namespace std;int main() {int a, b, c, d, e, f;int number[6];for (a = 0; a <= 1; a++) {for (b = 0; b <= 1; b++) {for (c = 0; c <= 1; c++) {for (d = 0; d <= 1; d++) {for (e = 0; e <= 1; e++) {for (f = 0; f <= 1; f++) {number[0] = a;number[1] = b;number[2] = c;number[3] = d;number[4] = e;number[5] = f;for (int i = 0; i < 6; i++) {cout << number[i] << "  ";}cout << endl;}}}}}}return 0;
}

結果：
這的確可以完成任務，但是這樣的算法真的很糟糕，不是嗎？

我們來看看優化后的窮舉的方法：

我們將其與二進制結合，因為對于這樣的0、1序列，與二進制有直接聯系，我們直接將十進制是0~63，轉換為二進制，存入數組中，就可以了，這樣大大降低了時間復雜度！

#include <iostream>
using namespace std;int main() {int number[6];for (int i = 0; i <= 63; i++) {// 轉換為二進制，除二求余再倒置int temp = i;for (int j = 5; j >= 0; j--) {number[j] = temp % 2;temp /= 2;}// 輸出結果for (int k = 0; k < 6; k++) {cout << number[k] << "  ";}cout << endl;}return 0;
}

窮舉加驗證，循環加選擇，蠻力解難題

窮舉有方法，驗證有策略，循環盡量淺，選擇看題目

我們之前談過，窮舉法，需要能夠窮舉，數據規模不太大，現在，我們在此基礎上進行了優化，同樣能夠窮舉的，窮舉方式的選擇也很重要。

對于循環，我們希望盡可能減少嵌套層數。

當然了，簡單的屬于通用普適技法，稍難的就需要動用你的觀察力，但是這些東西你熟悉了，也就變成了簡單的了。

接下來我們嘗試優化示例3。

示例3優化

我們只關注，如何進行窮舉，并且盡可能減小窮舉規模空間，關注一個條件：5個數各不相同。

這樣一來，我們的問題規模就由10⁵ = 10,000 變成了 10 x 9 x 8 x 7 x 6 = 30,240 ，變成了原來的30%左右。

可以用多重循環來列舉出它們各種不同的取值情況，逐一地判斷它們是否滿足上述等式；為了避免同一數字被重復使用，可設立邏輯數組x，x[i]（0≤i≤9）值為1時表示數i沒有被使用，為0時表示數i已被使用。

int main() {int x[10];int a, b, c, d, e, i, m, n, s;for (i = 0; i <= 9; i++) x[i] = 1;   /*x數組置初值*/for (a = 1; a <= 9; a++){x[a] = 0; /*表示不能再讓其他變量取與a相同的值*/for (b = 0; b <= 9; b++)if (x[b])  /*如果b取的當前值未被其他的變量重復*/{x[b] = 0; /*表示不能再讓其他變量取與b相同的值*/for (c = 0; c <= 9; c++)if (x[c])   /*如果c取的當前值未被其他的變量重復*/{x[c] = 0;  /*表示不能再讓其他變量取與c相同的值*/for (d = 0; d <= 9; d++)if (x[d])    /*如果d取的當前值未被其他的變量重復*/{x[d] = 0;   /*表示不能再讓其他變量取與d相同的值*/for (e = 0; e <= 9; e++)if (x[e]){m = a * 1000 + b * 100 + c * 10 + d;n = a * 1000 + b * 100 + e * 10 + d;s = e * 10000 + d * 1000 + c * 100 + a * 10 + d;if (m + n == s)printf("兵:%d 炮:%d 馬:%d 卒:%d車:%d\n",a, b, c, d, e);}x[d] = 1;  /*本次循環未找到解,讓d取其他值*/}x[c] = 1;  /*本次循環未找到解,讓c取其他值*/}x[b] = 1;     /*本次循環未找到解,讓b取其他值*/}x[a] = 1;  /*本次循環未找到解,讓a取其他值*/}return 0;
}

重要的收獲：窮舉有方法，不能上來題都不看就開始舉，有條件地窮舉，減少解空間，對于本題，5個數不同，可以當作題目條件來驗證，也可以當成窮舉的約束條件。

同樣的條件，不同的看法，就會產生不同的解決方案。

還記得離散數學中的附加條件證明法嗎，將結論中的前提當條件用，再推出最終結論，極大簡化了運算。

百元買百雞問題

已知公雞5元一只，母雞3元一只，小雞1元三只，用100元買100只雞，問公雞、母雞、小雞各多少只？

1. 知道解空間
   • 公雞：x 0~20
   • 母雞：y 0~33
   • 小雞：z 0~100
2. 如何列舉
   • 最簡單思路：三重循環
3. 如何驗證
   1. x + y + z = 100
   2. 5x + 3y + z/3 = 100
   3. z % 3 == 0
   4. 這樣看來，可以將z變量去掉了，解空間也減少了100倍，三重循環也變成了二重循環。也就是我們將驗證條件當成解空間的約束條件，減少了解空間的規模，這與我們上面的示例3優化是一個思路。

注意：小雞是1元3只，需要注意 z/3 時，int會去掉小數點，需要驗證z是3的倍數。

#include <iostream>
using namespace std;int main() {int x, y, z;for (x = 0; x <= 20; x++) {for (y = 0; y <= 33; y++) {if ((100 - x - y) % 3 == 0) {if ((5 * x + 3 * y + (100 - x - y) / 3) == 100) {cout << "公雞：" << x << endl;cout << "母雞：" << y << endl;cout << "小雞：" << 100 - x - y << endl;cout << "**********" << endl;}}}}return 0;
}

示例

求所有的三位數,它除以11所得的余數等于它的三個數字的平方和.

分析：

1. 解空間：三位數x，100~999
2. 如何枚舉：循環
3. 如何驗證（約束條件）：x % 11 == 三個數字平方和
4. 約束條件可否去限制解空間? 否

#include <iostream>
using namespace std;
// 求所有的三位數,它除以11所得的余數等于它的三個數字的平方和.
int main() {for (int i = 100; i <= 999; i++) {// 求三個數平方和int sum = 0;int temp = i;while (temp){int x = temp % 10;sum += (x * x);temp /= 10;}// 驗證if (sum == i % 11) {cout << "數字：" << i << endl;}}return 0;
}

結果：

對問題進行建模

我們進一步分析上一題

求所有的三位數,它除以11所得的余數等于它的三個數字的平方和.

假設3位數A的三個數是x，y，z。

1. 0 <= A % 11 <= 10
2. x² + y² + z² <= 10，x*100 + y*10 + z = A
3. 1 <= x <= 3， 0 <= y <= 3，0 <= z <= 3，且都是整數

這樣一來，經過簡單的人工處理，解空間減少了很多，然后再進行 窮舉 + 驗證 就可以了，顯然比之前的更加高效，因為進行了人工分析。

int x, y, z;
for (x = 1; x <= 3; x++) {for (y = 0; y <= 3; y++) {for (z = 0; z <= 3; z++) {int num = x * 100 + y * 10 + z;if ((x*x + y * y + z * z) == num % 11) {cout << "數字：" << num << endl;}}}
}

這里強調的其實也是，將驗證條件進一步分析，將其轉換為解空間的約束條件，以降低解空間規模。

窮舉 + 驗證：窮舉范圍、窮舉方式、驗證條件、約束條件

我們再回顧之前的例子，充分體會窮舉法的分析思路。

窮舉依賴的技術是遍歷，也就是解空間的每個解，都要找一遍，注意盡量避免充分。

示例1

• 解空間：2~1000
• 驗證條件：各因子之和等于本身
• 約束條件：沒有可以轉化的驗證條件
• 窮舉方式：解空間 + 約束條件–>循環

示例2

在數字100~999中，求水仙花數，例如：1³ + 5³+ 3³ = 153。

• 解空間：100~999
• 驗證條件：水仙花數
• 約束條件：無
• 窮舉方式：解空間+約束條件–>循環

示例3

• 解空間：5個變量，每個變量范圍0~9
• 驗證條件：滿足題目表達式
• 約束條件：5個變量各不相同
• 窮舉方式：解空間+約束方式–>減小解空間–>5重循環，如果有值重復，則跳出

示例4

對于一個含有6個元素的一維數組，該數組每個數只能是0或1，將所有情況窮舉出來。
例如(0,0,0,0,0,0)、(0,1,0,1,1,0)

注意：本題本身就是求解空間

• 解空間：6個數，每個數是0或1，求全部的0、1序列
• 驗證條件：情況不重復
• 約束條件：無
• 窮舉方式：解空間+約束條件–>6重循環

問題建模 & 轉化：類二進制數

很明顯這題的0、1序列，與二進制數類似，可以轉換問題，改為求0~63十進制的二進制，間接解題。

屬于特殊解法，需要驚人的洞察力。

示例5

已知公雞5元一只，母雞3元一只，小雞1元三只，用100元買100只雞，問公雞、母雞、小雞各多少只？

• 原始解空間：3個變量，x∈[0,20]，y∈[0,33]，z∈[0,100]
• 驗證條件
  • x + y + z = 100（看做約束條件）
  • 5x + 3y + z/3 = 100
  • z / 3為整數（z % 3 = 0）
• 約束條件：將驗證條件中第一條，轉換為約束條件，也就是z = 100 - x -y這與就去掉了一個變量，這個變量范圍最大，能夠充分減少解空間。
• 約束后解空間：2個變量，x∈[0,20]，y∈[0,33]
• 窮舉方式：雙重循環

注意：誰是驗證條件，誰是約束條件，是跟你的看法有關的。

示例6

求所有的三位數,它除以11所得的余數等于它的三個數字的平方和.

• 原始解空間：數字A，三個位是x，y，z，A范圍100~999
• 驗證條件
  • A % 11 = x² + y² + z²
• 約束條件：由驗證條件進一步分析得出，需要有經驗和洞察力
  • A % 11 ∈[0,10]
  • x∈[1,3]，y∈[0,3]，z∈[0,3]
• 約束后解空間：x∈[1,3]，y∈[0,3]，z∈[0,3]
• 窮舉方式：三重循環

備注：驗證方式需要具體問題具體分析。

充分體會不同算法的組合，因為一道題目，可能背后涉及到多個不同的算法的組合。