C/C++ 編程中最常用的算法 - 窮舉搜索

cpp_learners 2022-01-07 22:34:49 阅读数:335

c++ 中最 最常 常用 算法

算法中,最常用的應該就是窮舉搜索算法了吧,也許你已經使用過了,只是自己不知到而已!


講述一道題目,你就會知道什麼是窮舉算法了!

我國古代數學家張丘建在《算經》一書中曾提出過著名的“百錢買百雞”問題,該問題敘述如下:
雞翁一,值錢五;雞母一,值錢三;雞雛三,值錢一;百錢買百雞,則翁、母、雛各幾何?
上題的意思是公雞一只五塊錢,母雞一只三塊錢,小雞三只一塊錢,現在要用一百塊錢買一百只雞,問公雞、母雞、小雞各多少只?

題目已經給出了,看著題目,你能想到的最簡單的解决辦法是什麼?
是不是將全部結果都判斷一次,然後超出符合條件的就可以了!

所以代碼如下:

int main(void) {

int fChook = 0; // 公雞數量
int mChook = 0; // 母雞數量
int litleChook = 0; // 小雞數量
int count1 = 0; // 統計循環次數
for (fChook = 0; fChook <= 20; fChook++) {

for (mChook = 0; mChook <= 33; mChook++) {

for (litleChook = 3; litleChook <= 99; litleChook += 3) {

count1++;
if ((fChook * 5 + mChook * 3 + litleChook / 3) == 100 && (fChook + mChook + litleChook) == 100) {

cout << "公雞:" << fChook << ",母雞:" << mChook << ",小雞:" << litleChook << endl;
}
}
}
}
//cout << "未優化循環次數:" << count1 << endl;
return 0;
}

為什麼第一個for循環判斷條件是小於等於20?
因為一只公雞5元錢,5乘以20就剛好等於100元了,所以公雞的數量不能超過20只。

為什麼第二個for循環判斷條件是小於等於33?
因為一只母雞3元錢,3乘以33等於99元,所以母雞的數量不能超過33只。

為什麼第三個for循環判斷條件是小於等於99?
小雞三只1元錢,99除以3等於33元,且99只小雞已經是頂峰了,因為不能單獨買一只小雞。

運行截圖:
在這裏插入圖片描述
可以看到,不管怎麼算都是正確的!

上面的代碼,就是窮舉搜索算法!

窮舉法(枚舉法)的基本思想是:

  1. 列舉出所有可能的情况,逐個判斷有哪些是符合問題所要求的條件,從而得到問題的全部解答。
  2. 它利用計算機運算速度快、精確度高的特點,對要解决問題的所有可能情况,一個不漏地進行檢查,從中找出符合要求的答案。

用窮舉算法解决問題,通常可以從兩個方面進行分析:
(1)問題所涉及的情况:問題所涉及的情况有哪些,情况的種數必須可以確定。把它描述出來。應用窮舉時對問題所涉及的有限種情形必須一一列舉,既不能重複,也不能遺漏。重複列舉直接引發增解,影響解的准確性;而列舉的遺漏可能導致問題解的遺漏。
(2)答案需要滿足的條件:分析出來的這些情况,需要滿足什麼條件,才成為問題的答案,把這些條件描述出來。

那他這樣到底循環判定了多少次呢?還是上面那一套代碼,將注釋那行代碼解開注釋,再一次運行:
在這裏插入圖片描述
天呐!運行了兩萬多次,要不是我點的CUP還可以,這不得卡死?
不行,這代碼絕對不行,我們來看看還有沒有可以優化的地方!

這當然有!

就是當公雞達到一定數量時,母雞就無需判斷那麼多次了;當母雞達到一定數量時,小雞就無需判斷那麼多次了!
接著這個思路,我們來寫優化代碼。

優化後的代碼如下:

int main(void) {

int fChook = 0; // 公雞數量
int mChook = 0; // 母雞數量
int litleChook = 0; // 小雞數量
int count1 = 0;
int count2 = 0;
for (fChook = 0; fChook <= 20; fChook++) {

for (mChook = 0; mChook <= 33; mChook++) {

for (litleChook = 3; litleChook <= 99; litleChook += 3) {

count1++;
if ((fChook * 5 + mChook * 3 + litleChook / 3) == 100 && (fChook + mChook + litleChook) == 100) {

cout << "公雞:" << fChook << ",母雞:" << mChook << ",小雞:" << litleChook << endl;
}
}
}
}
cout << endl << "-----------------華麗的分割線------------------" << endl << endl;
/* 通過錢的總數控制 */
for (fChook = 0; fChook <= 20; fChook++) {

for (mChook = 0; mChook <= (100 - fChook * 5) / 3; mChook++) {

for (litleChook = 3; litleChook <= (100 - (fChook * 5 + mChook * 3)) * 3; litleChook += 3) {

count2++;
if ((fChook * 5 + mChook * 3 + litleChook / 3) == 100 && (fChook + mChook + litleChook) == 100) {

cout << "公雞:" << fChook << ",母雞:" << mChook << ",小雞:" << litleChook << endl;
}
}
}
}
cout << endl << "未優化循環次數:" << count1 << ",優化後循環次數:" << count2 << endl;
return 0;
}

代碼中,我是通過錢來控制剩下兩個for循環的判斷條件的。
第二個for循環,(100 - fChook * 5) / 3,先拿一百塊錢减去當前公雞數量所花費的錢,剩下的錢再除以一只母雞的價格,那麼就可以得到母雞最多可以買多少只了。
第三個for循環也是一樣的思路,一百元减去當前公雞數量所花費的錢和母雞數量所花費的錢,剩下來的錢,再乘以三(小雞一只三元),就可以得到小雞還可以再買多少只了!

在這裏插入圖片描述
看到沒有,優化後循環次數是一萬兩千多次,這效率瞬間提昇了一半,這不得起飛?

當然,因該也還有其它的優化思路,這就得大家發動腦筋思考啦!

所以,大家懂了吧,即使是遍曆全部結果,也還是有優化的空間的,這窮舉算法也是不錯的!(用最簡單的辦法,找出所需要的結果)


學會了這個用法,我們來做一道簡單的練習題。

有 20 枚硬幣,可能包括 4 種類型:1 元、5 角、1 角和 5 分。
已知 20 枚硬幣的總價值為 10 元,求各種硬幣的數量。

例如:4、11、5、0 就是一種方案。而 8、2、10、 0 是另一個可能的方案,顯然方案並不是唯一的,請編寫程序求出類似這樣的不同的方案一共有多少種?
(1)編程思路。
直接對四種類型的硬幣的個數進行窮舉。其中,1 元最多 10 枚、5 角最多 20 枚、1 角最多 20 枚、5 分最多 20 枚。

開始寫代碼吧
如果以元為單比特,則 5 角、1 角、5 分會化成浮點型數據,容易計算出錯。可以將 1元、5 角、1 角、5 分變成 100 分、50 分、10 分和 5 分,從而全部采用整型數據處理!

做法和思路跟上面類似,我就直接將代碼列舉出來了!

#include <iostream>
#include <string>
using namespace std;
int main(void) {

int a100 = 0; // 1元的硬幣數量
int a50 = 0; // 5角的硬幣數量
int a10 = 0; // 1角的硬幣數量
int a5 = 0; // 5分的硬幣數量
int count = 0; // 記錄可行的方案總數
int count1 = 0;
int count3 = 0;
for (a100 = 0; a100 <= 10; a100++) {

for (a50 = 0; a50 <= 20; a50++) {

for (a10 = 0; a10 <= 20; a10++) {

for (a5 = 0; a5 <= 20; a5++) {

count1++;
if ((a100 * 100 + a50 * 50 + a10 * 10 + a5 * 5) == 1000 && (a100 + a50 + a10 + a5) == 20) {

cout << "1元硬幣:" << a100 << "枚, 5角硬幣:" << a50 << "枚, 1角硬幣:" << a10 << "枚, 5分硬幣:" << a5 << "枚!" << endl;
count++;
}
}// a5 end.
}// a10 end.
}// a50 end.
}// a100 end.
cout << "一共有:" << count << "種組合!" << endl;
count = 0;
cout << endl << "-----------------華麗的分割線------------------" << endl << endl;
/* 通過硬幣數量控制 */
for (a100 = 0; a100 <= 10; a100++) {

for (a50 = 0; a50 <= (20 - a100); a50++) {

for (a10 = 0; a10 <= (20 - a100 - a50); a10++) {

for (a5 = 0; a5 <= (20 - a100 - a50 - a10); a5++) {

count3++;
if ((a100 * 100 + a50 * 50 + a10 * 10 + a5 * 5) == 1000 && (a100 + a50 + a10 + a5) == 20) {

cout << "1元硬幣:" << a100 << "枚, 5角硬幣:" << a50 << "枚, 1角硬幣:" << a10 << "枚, 5分硬幣:" << a5 << "枚!" << endl;
count++;
}
}// a5 end.
}// a10 end.
}// a50 end.
}// a100 end.
cout << "一共有:" << count << "種組合!" << endl;
cout << endl << "未優化循環次數:" << count1 << ",優化後循環次數:" << count3 << endl;
return 0;
}

在這裏插入圖片描述


總結

其實這個窮舉搜索算法大家都會使用,重點是理解它的思路和過程;知道怎麼去優化就可以的了!

版权声明:本文为[cpp_learners]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201072234486283.html