大學(xué)計(jì)算機(jī)基礎(chǔ)-基于計(jì)算思維（Windows 10+Office 2016）（第2版）課件 10.2.2復(fù)雜蠻力法

大學(xué)計(jì)算機(jī)基礎(chǔ)——基于計(jì)算思維（Windows10+Office2016）第10章算法思維與運(yùn)用10.2.2復(fù)雜蠻力法10.2蠻力算法問題2復(fù)雜蠻力算法劉老師帶了41名同學(xué)去公園劃船，共租了10條船。每條大船坐6人，每條小船坐4人，問大船、小船各租幾條則剛好坐下所有人？1.問題分析對(duì)于此問題，我們可以馬上列出一個(gè)二元一次方程組：

small+big=104×small+6×big=42用消元法可以很快解出該方程組問題2復(fù)雜蠻力算法但怎么讓計(jì)算機(jī)來解這個(gè)方程組呢？用蠻力法試試。①確定窮舉對(duì)象小船small

大船big②確定窮舉范圍0~100~10③確定約束條件small+big=104×small+6×big=42④窮舉可能的解從（0，0）開始，然后依次判斷（0，1）、（0，2）、（0，3）…（0，10），（1，0）、（1，1）…(10，10)是否同時(shí)滿足兩個(gè)約束條件問題2復(fù)雜蠻力算法2．算法實(shí)現(xiàn)①用循環(huán)結(jié)構(gòu)內(nèi)再嵌套循環(huán)結(jié)構(gòu)來實(shí)現(xiàn)。此問題中，用small作為外循環(huán)還是用big作為外循環(huán)，都不影響結(jié)果。假設(shè)用small作外循環(huán)，big作內(nèi)循環(huán)：small+big=104×small+6×big=42當(dāng)small=0時(shí)，big分別從0取到10，判斷每種組合是否滿足兩個(gè)約束條件；然后再取small=1，big又從0取到10，再判斷；最后small=10時(shí)，big又從0取到10，再判斷，這樣就能窮舉所有可能的解。問題2復(fù)雜蠻力算法2．算法實(shí)現(xiàn)操作實(shí)現(xiàn)時(shí)，則應(yīng)先搭好完整的外層循環(huán)結(jié)構(gòu)（small從0到10），然后在其內(nèi)的循環(huán)體內(nèi)再搭建內(nèi)層循環(huán)（big從0到10），如圖所示。問題2復(fù)雜蠻力算法2．算法實(shí)現(xiàn)②在內(nèi)層循環(huán)體內(nèi)（big層內(nèi)）再判斷是否同時(shí)滿足2個(gè)約束條件，是則輸出small和big的值，否則不輸出，如圖所示。問題2復(fù)雜蠻力算法3．運(yùn)行結(jié)果問題2復(fù)雜蠻力算法4．算法優(yōu)化本例中為了提高該算法的時(shí)間效率，可以減少窮舉對(duì)象和縮小窮舉范圍。因?yàn)榇笮〈豢倲?shù)是固定的，所以只要以big為窮舉對(duì)象，根據(jù)方程1的約束條件就可得small=10-big；small=10-bigsmall+big=10問題2復(fù)雜蠻力算法4．算法優(yōu)化再根據(jù)方程2可將big的窮舉范圍縮小為從0到7，這樣用一個(gè)單循環(huán)（big從0到7）就可實(shí)現(xiàn)了。4×small+6×big=42Big≤7問題2復(fù)雜蠻力算法4．算法優(yōu)化循環(huán)體內(nèi)首先由big計(jì)算出small，即small=10-big，然后只要判斷是否滿足另一個(gè)約束條件：4×small+6×big=42即可。問題2復(fù)雜蠻力算法4．算法優(yōu)化這樣就只要對(duì)big窮舉8次，明