信息學(xué)奧賽課課通(C++)第9單元-電子課件

1、第 9 單元 基本算法作者：林厚從信息學(xué)奧賽課課通(C+)第 1 課 進(jìn)制轉(zhuǎn)換學(xué)習(xí)目標(biāo)1. 理解二進(jìn)制計(jì)數(shù)原理。2. 掌握不同進(jìn)制數(shù)之間的轉(zhuǎn)換原理和實(shí)現(xiàn)方法。3. 學(xué)會使用進(jìn)制轉(zhuǎn)換的原理解決一些實(shí)際問題。進(jìn)制實(shí)際生活中，人們使用十進(jìn)制計(jì)數(shù)。但是，任何信息在計(jì)算機(jī)中都是采用二進(jìn)制編碼表示的，有時還會用到十六進(jìn)制。十進(jìn)制計(jì)數(shù)原理采用“0” “9”十個符號，運(yùn)算規(guī)則為“逢十進(jìn)一”，基數(shù)是十。二進(jìn)制計(jì)數(shù)原理采用“0” 和“1”兩個符號，運(yùn)算規(guī)則是“逢二進(jìn)一”，基數(shù)是二。進(jìn)制 顯然，十進(jìn)制中的數(shù)“10”和二進(jìn)制中的“10”、十六進(jìn)制中的“10”是不一樣的。為了區(qū)分，我們分別表示成（10）10、（10）2

2、、（10）16。有時也會在一個數(shù)的后面加上英文字母D、B、H來分別表示該數(shù)是十進(jìn)制數(shù)、二進(jìn)制數(shù)或者十六進(jìn)制數(shù)，如96D、110B、2B3FH等。1. 進(jìn)制轉(zhuǎn)換的基本原理不同進(jìn)制數(shù)之間轉(zhuǎn)換的基本原理就是依據(jù)其“運(yùn)算規(guī)則”和“權(quán)”的含義進(jìn)行乘除運(yùn)算。(1) 二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)一個二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)的方法是將其表示成“按權(quán)展開式”，再按十進(jìn)制運(yùn)算規(guī)則求和。這種方法可以擴(kuò)展到任意 n 進(jìn)制。進(jìn)制(2) 二進(jìn)制數(shù)與十六進(jìn)制數(shù)之間的相互轉(zhuǎn)換二進(jìn)制數(shù)轉(zhuǎn)換成十六進(jìn)制數(shù)的方法是以小數(shù)點(diǎn)為準(zhǔn)，往前、往后“四位一段”分別轉(zhuǎn)換成十六進(jìn)制數(shù)再求和，不滿四位要補(bǔ)齊。(3) 十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制十進(jìn)制數(shù)轉(zhuǎn)換成二進(jìn)制

3、要將整數(shù)和小數(shù)分開轉(zhuǎn)換，最后再求和。整數(shù)的轉(zhuǎn)換方法是：不斷除以 2 求余數(shù)，最后反序輸出；小數(shù)的轉(zhuǎn)換方法是：不斷乘以 2，將每次得到的整數(shù)部分依次輸出，并且每次都將整數(shù)部分恢復(fù)為 0。2. 進(jìn)制轉(zhuǎn)換的應(yīng)用舉例例 1、進(jìn)制轉(zhuǎn)換【問題描述】將任意一個 n 進(jìn)制整數(shù) x 轉(zhuǎn)換成十進(jìn)制。【輸入格式】第 1 行 1 個正整數(shù) n，1n10；第 2 行 1 個整數(shù) x。【輸出格式】一行一個數(shù)，表示轉(zhuǎn)換得到的十進(jìn)制數(shù)，保證答案不超過 2147483647。【輸入樣例】2100110【輸出樣例】38【問題分析】讀入 n 和 x，根據(jù) n 和 x 的位數(shù)，分別求出 x 的每一位對應(yīng)的“權(quán)值”，然后窮舉每一位，將

4、它乘以該位對應(yīng)的權(quán)值，累加便可得到結(jié)果。 更高效、更簡潔的算法是采用“秦九韶公式”。對于樣例輸入，可以這樣計(jì)算：(1*2)0)*2+0)*2+1)*2+1)*2+0=38 具體實(shí)現(xiàn)采用“迭代法”，用一個變量不斷乘以n，再加上下一位xi。/p9-1-1#includeusing namespace std;int main() freopen(” change.in ” , ” r ” ,stdin); freopen( ” change.out ” , ” w ” ,stdout); int n,ans = 0,i = 0; char s32; scanf( ” %dn ” ,&n); whi

5、le(si = getchar() != n) ans = ans * n + (si - 48); i+; printf( ” %dn ” ,ans); return 0;例2、汽車牌照【問題描述】小 Y 最近發(fā)現(xiàn)街上的汽車越來越多了，作為汽車的重要標(biāo)志汽車牌照也是越來越不夠用了，已經(jīng)從以前的十進(jìn)制發(fā)展到三十六進(jìn)制了，以前的一個汽車牌照“蘇 D88888”，現(xiàn)在的牌照“蘇 D0YY11”。小 Y 突發(fā)其想，想知道他看到的大量汽車牌照中最近的兩個汽車牌照相差多少？【輸入格式】若干行(不超過 500000 行)，每行為一個汽車牌照。每個汽車牌照為一個 7 位的字符串，格式為 SD，其中一個 表示

6、一個 09 或AZ，所涉及的字母均為大寫。【輸出格式】一行一個數(shù)，表示最接近的兩個汽車牌照之間的差值，要求為十進(jìn)制數(shù)。【輸入樣例】SD12345SD88888SD22222SD99999【輸出樣例】1678245例3、數(shù)列【問題描述】給定一個正整數(shù) k，把所有 k 的方冪及所有有限個互不相等的 k 的方冪之和構(gòu)成一個遞增的序列。例如，當(dāng) k=3 時，這個序列是：1，3，4，9，10，12，13，請求出這個序列的第 n 項(xiàng)的值(用十進(jìn)制數(shù)表示)?！据斎敫袷健恳恍袃蓚€正整數(shù) k 和 n，之間用一個空格隔開，且 3k15，10n1000?！据敵龈袷健恳恍幸粋€正整數(shù)?！据斎霕永? 100【輸出樣例】

7、981實(shí)踐鞏固第 2 課 高精度運(yùn)算學(xué)習(xí)目標(biāo)1. 體會高精度運(yùn)算的應(yīng)用場合。2. 熟練掌握高精度加法和乘法運(yùn)算。高精度運(yùn)算在編程進(jìn)行數(shù)值運(yùn)算時，有時會遇到運(yùn)算的精度要求特別高，遠(yuǎn)遠(yuǎn)超過各種數(shù)據(jù)類型的精度范圍；有時數(shù)據(jù)又特別大，遠(yuǎn)遠(yuǎn)超過各種數(shù)據(jù)類型的極限值。這種情況下，就需要進(jìn)行“高精度運(yùn)算”。高精度運(yùn)算首先要處理好數(shù)據(jù)的接收和存儲問題，其次要處理好運(yùn)算過程中的“進(jìn)位”和“借位”問題。例1、高精度加法【問題描述】輸入兩個 1000 位以內(nèi)的正整數(shù)，輸出它們的和?！据斎霕永?23456789987654321【輸出樣例】1111111110【問題分析】用字符串的方式讀入兩個高精度數(shù)，轉(zhuǎn)存到兩個整

8、型數(shù)組 a 和 b 中，如圖 9.2-1 所示，模擬加法的過程，從低位(第 0 位)開始對應(yīng)位 ai 和 bi 相加，同時處理進(jìn)位，結(jié)果存儲到另一個數(shù)組 c 中。最后，從高位到低位輸出 ci。參考程序見教材329頁。例2、高精度乘法【問題描述】輸入兩個 100 位以內(nèi)的正整數(shù)，輸出它們的乘積?！据斎霕永?23456789987654321【輸出樣例】121932631112635269【問題分析】 如圖 9.2-2 所示，模擬“豎式”乘法的過程，用一個數(shù)的每一位 ai (從低位開始)逐位與另一個數(shù)的每一位 bj 相乘，結(jié)果存儲到 ci+j 位，同時處理好進(jìn)位。參考程序見教材330頁。例3、n

9、! 的精確值【問題描述】輸入 n，輸出 n! 的精確值，n!=123n，1n2 時，存在遞推關(guān)系：f (n) = f(n-1) + f(n-2)。 在遞推問題模型中，每個數(shù)據(jù)項(xiàng)都與它前面的若干個數(shù)據(jù)項(xiàng)（或后面的若干個數(shù)據(jù)項(xiàng)）存在一定的關(guān)聯(lián)，這種關(guān)聯(lián)一般是通過一個“遞推關(guān)系式”來描述的。求解問題時，需要從初始的一個或若干數(shù)據(jù)項(xiàng)出發(fā)，通過遞推關(guān)系式逐步推進(jìn)，從而推導(dǎo)計(jì)算出最終結(jié)果。這種求解問題的方法叫“遞推法”。其中，初始的若干數(shù)據(jù)項(xiàng)稱為“遞推邊界”。遞推解決遞推問題有三個重點(diǎn)：建立正確的遞推關(guān)系式；分析遞推關(guān)系式的性質(zhì)；根據(jù)遞推關(guān)系式編程求解。遞推法分為“順推”和“倒推”兩類模型。所謂順推，就是

10、從問題的邊界條件(初始狀態(tài))出發(fā)，通過遞推關(guān)系式依次從前往后遞推出問題的解；所謂倒推，就是在不知道問題的邊界條件(初始狀態(tài))下，從問題的最終解(目標(biāo)狀態(tài)或某個中間狀態(tài))出發(fā)，反過來推導(dǎo)問題的初始狀態(tài)。例1、鋪瓷磚【問題描述】用紅色的 11 和黑色的 22 兩種規(guī)格的瓷磚不重疊地鋪滿 n3 的路面，求出有多少種不同的鋪設(shè)方案。【輸入格式】一行一個整數(shù) n，0n1000?！据敵龈袷健恳恍幸粋€整數(shù)，為鋪設(shè)方案的數(shù)量模12345的結(jié)果?！据斎霕永?【輸出樣例】3【問題分析】用 f(n) 表示 n3 的路面有多少種不同的鋪設(shè)方案。把路面看成 n 行 3 列，則問題可以分成兩種情況考慮，一種是最后一行用

11、 3 塊 11 的瓷磚鋪設(shè)；另一種是最后兩行用 1 塊 22 和 2 塊 11 的瓷磚鋪設(shè)(最后兩行就有兩種鋪法)，第一種鋪法就轉(zhuǎn)換為 f(i-1) 的問題了，第二種鋪法就轉(zhuǎn)換成 f(i-2) 的問題了。根據(jù)加法原理，得到的遞推關(guān)系式為 f(i) = f(i-1) +f(i-2)2，邊界為 f(0)=1，f(1)=1。 參考程序見教材350-351頁。例2、彩帶【問題描述】 一中 90 周年校慶，小林準(zhǔn)備用一些白色、藍(lán)色和紅色的彩帶來裝飾學(xué)校超市的櫥窗，他希望滿足以下兩個條件：(1) 相同顏色的彩帶不能放在相鄰的位置；(2) 一條藍(lán)色的彩帶必須放在一條白色的彩帶和一條紅色的彩帶中間。 現(xiàn)在，他

12、想知道滿足要求的放置彩帶的方案數(shù)有多少種。例如，如圖 9.4-1 所示為櫥窗寬度n=3 的所有放置方案，共 4 種?！据斎敫袷健恳恍幸粋€整數(shù) n，表示櫥窗寬度(或者說彩帶數(shù)目)。【輸出格式】一行一個整數(shù)，表示裝飾櫥窗的彩帶放置方案數(shù)?！緲永斎搿?【樣例輸出】4【數(shù)據(jù)規(guī)?！繉?30% 的數(shù)據(jù)滿足：1n15。對 100% 的數(shù)據(jù)滿足：1n45?！締栴}分析】 用 f (i) 表示寬度為 i 的櫥窗(或 i 條彩帶)的合法放置方案數(shù)，則 f(1) =2，f(2) =2，f(3) =4，f(4) =6，f(5) =10，不難發(fā)現(xiàn)，答案就是初始值不一樣的斐波那契數(shù)列，所以，用遞推法就可以很方便地求出 f

13、 (n)。 參考程序見教材352頁。例3、城市路徑【問題描述】 地圖上有 n 個城市，一只奶牛要從 1 號城市開始依次經(jīng)過這些城市，最終到達(dá) n 號城市。但是這只奶牛覺得這樣太無聊了，所以它決定跳過其中的一個城市(但是不能跳過 1 號和 n 號城市)，使得它從 1 號城市開始，到達(dá) n 號城市所經(jīng)過的總距離最小。假設(shè)每一個城市 i 都有一個坐標(biāo)(x i ，y i )，從 (x 1 ，y 1 ) 的城市 1 到 (x 2 ，y 2 ) 的城市 2 之間的距離為 | x 1 -x 2 | + | y 1 -y 2 | ?！据斎敫袷健康?1 行 1 個正整數(shù) n，表示城市個數(shù)。接下來的 n 行，每行

14、 2 個數(shù) x i 和 y i ，表示城市 i 的坐標(biāo)。【輸出格式】一行一個數(shù)，使得它從1號城市開始，跳過某一個城市，到達(dá)n號城市所經(jīng)過的最小總距離。【輸入樣例】40 08 311 -110 0【輸出樣例】14【樣例說明】跳過 2 號城市。【數(shù)據(jù)規(guī)?！繉τ?40% 的數(shù)據(jù)滿足：n1000。對于 100% 的數(shù)據(jù)滿足：3n100000，-1000 x i ，y i 1000?！締栴}分析】設(shè)f (i)為從城市1依次跳到城市i的距離之和，設(shè)g(i)為從城市i依次跳到城市n的距離之和，則問題的答案為 minf (i-1)+g(i+1)+disi-1,i+1。其中，dis i-1,i+1表示城市 i-1

15、 到城市 i+1的曼哈頓距離，f (i)和 g(i)都可以用遞推來預(yù)處理求出：f(i)= f(i-1)+ disi-1,i，g(i) =g(i+1) +disI,i+1。也可以設(shè) f (i)表示從城市 1 依次跳到城市 n，且跳過城市 i 的距離之和，sum 表示表示從城市 1 依次跳到城市 n 的距離之和，則 f (i)=minsumdisI,i-1-disi+1.i+disi-1,i+1。 參考程序見教材353頁。例4、穿越沙漠【問題描述】一輛卡車欲穿過 1000 千米的沙漠，卡車耗油為 1 升 / 千米，卡車總載油能力為 500 升。顯然，卡車裝一次油是過不了沙漠的。因此，司機(jī)必須設(shè)法在

16、沿途建立幾個貯油點(diǎn)，使卡車能順利穿越沙漠。試問：司機(jī)如何建立這些貯油點(diǎn)？每一貯油點(diǎn)應(yīng)存多少油，才能使卡車以消耗最少汽油的代價(jià)通過沙漠？結(jié)果保留小數(shù)點(diǎn)后兩位。編程計(jì)算及打印建立的貯油點(diǎn)序號，各貯油點(diǎn)距沙漠邊沿出發(fā)的距離以及存油量，格式如下：No. Distance(km) Oil (litre)1 . .2 . .3 . .【問題分析】因?yàn)閺钠鹗键c(diǎn)出發(fā)無法確定第 1 個貯油點(diǎn)的位置及貯油量，所以順推行不通。下面換個思路倒推試試看。先從終點(diǎn)出發(fā)倒推最后一個貯油點(diǎn)的位置及貯油量，然后再把最后一個貯油點(diǎn)作為終點(diǎn)，倒推倒數(shù)第 2 個貯油點(diǎn)的位置及貯油量，設(shè) dis(i)表示第 i 個貯油點(diǎn)至終點(diǎn)(i=0

17、)的距離，oil (i)表示第 i 個貯油點(diǎn)的貯油量。從終點(diǎn)向起始點(diǎn)倒推，逐一求出每個貯油點(diǎn)的位置及存油量，如圖 9.4-2 所示。從貯油點(diǎn) i 向貯油點(diǎn) i+1 倒推的策略是，卡車在點(diǎn) i 和點(diǎn) i+1 間往返若干次。卡車每次返回i+1 處時正好耗盡 500 升汽油，而每次從 i+1 處出發(fā)時又必須裝滿 500 升汽油。兩點(diǎn)之間的距離必須滿足在耗油最少的條件下使 i 點(diǎn)貯存 i500 升汽油的要求(0in-1)，根據(jù)貪心思想，第一個貯油點(diǎn) i=1 應(yīng)距終點(diǎn) i=0 處 500 千米且在該處貯藏 500 升汽油，這樣才能保證卡車能由 i=1 處到達(dá)終點(diǎn) i=0 處，這就是說，dis(1)=50

18、0，oil(1)=500。而為了在 i=1 處貯藏 500升汽油，卡車至少從 i=2 處開兩趟滿載油的車至 i=1 處，所以 i=2 處至少存貯 2500 升汽油，即 oil(2) =5002=1000，另外再加上從 i=1 返回至 i=2 處的一趟空載，合計(jì)往返 3 次，往返路程的耗油量按最省要求只能為500升，即d 1，2 = 500/3，所以dis (2)=dis (1)+d 1，2 =dis (1)+500/3。同理，為了在i=2處貯存1000升汽油，卡車至少從i=3處開3趟滿載油的車至i=2處。所以，i=3 處至少存貯 3500 升汽油，即 oil(3)=5003=1500，加上 i

19、=2 至 i=3 處的 2 趟返程空車，合計(jì) 5 次，路途耗油量也應(yīng)該是 500 升，即 d 2，3 =500/5，所以 dis(3)=dis(2)+d 2，3 =dis(2)+500/5。依次類推，為了在 i=k 處貯藏 k500 升汽油，卡車至少從 i=k+1 處開 k 趟滿載車至 i=k 處，即oil(k+1)=(k+1)500=oil (k)+500，加上從 i=k 返回 i=k+1 的 k-1 趟返程空車，合計(jì) 2*k-1 次，總耗油量按最省要求為 500 升，即 d k， k+1 = 500/ (2k-1)，所以 dis(k+1) = dis(k)+d k，k+1 = dis(k)

20、+500/(2k-1)。最后一個貯油點(diǎn)的位置如圖 9.4-4 所示。最后，i=n至起始點(diǎn)的距離為1000-dis (n)，oil (n)=500n。為了在i=n處取得n500升汽油，卡車至少從始點(diǎn)開n+1次滿載車至i=n，加上從i=n返回起始點(diǎn)的n趟返程空車，合計(jì)2n+1次，總耗油量應(yīng)正好為(1000-dis(n)(2n+1)，即起始點(diǎn)藏油為 oil (n)+(1000-dis(n)(2n+1)。 參考程序見教材355頁。例5、偶數(shù)個3【問題描述】編程求出所有的 n 位數(shù)中，有多少個數(shù)中有偶數(shù)個數(shù)字 3?！据斎敫袷健恳恍幸粋€正整數(shù) n，0n1的宮殿，將其分解成4個k/2大小的宮殿，先看一下公主

21、站的位置是屬于哪一塊，因?yàn)楦鶕?jù)公主所在的位置，我們可以確定中間位置所放的毯子類型，再遞歸處理公主所站的那一塊，直到出現(xiàn)邊界條件k=1的情況，然后在公主邊上鋪上一塊合適的地毯，遞歸結(jié)束。參考程序見教材368-370頁。 3. 分治與遞歸的應(yīng)用舉例分治與遞歸的思想簡單易懂，但是如果采用直接遞歸來實(shí)現(xiàn)，存在著大量“冗余”計(jì)算，效率比較低。一般可以采用以下幾種思路進(jìn)行優(yōu)化，一是將遞歸公式轉(zhuǎn)化成遞推算法實(shí)現(xiàn)；二是采用所謂的“記憶化”方法，設(shè)置一個數(shù)組 f 記錄每一項(xiàng)的值，第一次計(jì)算出第 i 項(xiàng)的值 f （i），就同時存儲到數(shù)組 fi中，避免以后再次遞歸調(diào)用 f （i），從而減少冗余計(jì)算；三是定義一個手工

22、棧保存和恢復(fù)遞歸過程中的現(xiàn)場信息，模擬遞歸調(diào)用，其缺點(diǎn)是減低了程序的可讀性。例6、平面分割【問題描述】平面上有 n 條封閉曲線，其中任何兩條封閉曲線恰好相交于兩點(diǎn)，且任何三條封閉曲線不相交于同一點(diǎn)，計(jì)算這些封閉曲線把平面分割成的區(qū)域個數(shù)?！据斎霕永?【輸出樣例】8【問題分析】設(shè) f (n)為 n 條封閉曲線把平面分割成的區(qū)域個數(shù)。如圖 9.5-4 所示，f(1)=2，f(2)=4，f(3)=8，F(xiàn)(4)=14，f(5)數(shù)起來比較困難，但是也能數(shù)得出 f(5)=22。找規(guī)律發(fā)現(xiàn)，f (2)-f(1)=2，f(3)-f(2)=4，f(4) f(3)=6，f(5)-f(4)=8猜想結(jié)論：f(n)-

23、f(n-1)= 2(n-1)，即遞歸公式為 f(n)=f(n-1)+2(n-1)，邊界條件為 f(1) =2?？梢院唵巫C明以上猜想：當(dāng)平面上已有 n-1 條封閉曲線將平面分割成 f （n-1）個區(qū)域后，第n 條封閉曲線每與曲線相交一次，就會增加 2 個區(qū)域，因?yàn)槠矫嫔弦延辛?n-1 條封閉曲線，且第n 條曲線與已有的每一條封閉曲線恰好相交于兩點(diǎn)，且不會與任何兩條曲線交于同一點(diǎn)，故平面上一共增加 2（n-1）個區(qū)域，加上已有的 f （n-1）個區(qū)域，一共有 f （n-1）+2（n-1）個區(qū)域。如果不滿足于以上遞推算法，可以進(jìn)一步推出其“通項(xiàng)公式”：f （n）= f （n-1）+2（n-1）f （

24、n-1）= f （n-2）+2（n-2）f （n-2）= f （n-3）+2（n-3）f （2）= f （1）+2把以上 n-1 個等式的左邊和右邊分別累加，再約去相同項(xiàng)，得到：f （n）= f （1）+ 2 （1+2+3+（n-1） = n2 -n+2。參考程序見教材371頁。例7、斐波那契數(shù)列【問題描述】輸入 n，1n1000，輸出斐波那契數(shù)列第 n 項(xiàng)模 9997 的值?！据斎霕永?0【輸出樣例】55【問題分析】直接遞歸求解存在著大量的冗余計(jì)算，利用數(shù)學(xué)知識可以計(jì)算出時間復(fù)雜度為 O(1+sqrt(5) /2)n)，顯然超時嚴(yán)重。因此，可以采用“記憶化”的方法進(jìn)行算法優(yōu)化。/p9-5-

25、7#includeusing namespace std;int n,a1001;int f(int x)if(x = 1 | x = 2) return 1;if(ax != -1) return ax;else return ax =(f(x-1) + f(x-2) % 9997);int main()freopen( “ fib.in “ , “ r “ ,stdin);freopen( “ fib.out “ , “ w “ ,stdout);cin n;for (int i = 1; i = n; i+) ai = -1;cout f(n) B，一般情況下有 A+BB+A。但是，當(dāng)

26、A=B+C 時，按字符串的大小定義有 AB，此時有可能出現(xiàn) A+BB+A 的情況。如 A= 121 ，B= 12 ，則 A+B= 12112 ，B+A= 12121 ，所以A+BB。按這一定義將所有的數(shù)字字符串從大到小排序后連接起來所得到的數(shù)字字符串即是問題的解。排序時先將所有字符串中的最大值選出來存在數(shù)組的第一個元素中，再從第二至最后一個元素中最大的字符串選出來存在數(shù)組的第二個元素中，直到從最后兩個元素中選出最大的字符串存在數(shù)組的倒數(shù)第二個元素中為止。需要說明的是，按本題定義的字符串的大小定義是有序的，即如果 A+BB+A，B+CC+B，則一定有 A+CC+A。證明方法如下：引理：記 nA

27、為 n 個字符串 A 按字符串加法運(yùn)算規(guī)則相加之和，則由 A+BB+A 可推導(dǎo)出nA+mBmB+nA，其中 m，n 為任意的自然數(shù)。用反證法可證明反過來也成立。設(shè) la 為字符串 A 的長度，lb 為字符串 B 的長度，lc 為字符串 C 的長度，再設(shè) n=lb*lc，m=la*lc，k=la*lb，則 nA，mB，kC 三 個 字 符 串 等 長，根 據(jù) 引 理 有：nA+mBmB+nA，mB+kCkC+mB，從而得到 nAmBkC，所以 nA+kCkC+nA，A+CC+A。要使 n 個字符串拼接起來后得到一個最大的字符串和式，則一定要將按上述定義最大的字符串放在第一個，否則必可通過將最大的

28、字符串與它左側(cè)的字符串交換得到更大的字符串和式。參考程序見教材386頁。（2） 構(gòu)造法根據(jù)描述的算法，用貪心的策略依次構(gòu)造出一個解，可證明一定是合法的解。即用貪心法找可行解。例5、取火柴游戲【問題描述】輸入 k 及 k 個整數(shù) n 1 ，n 2 ，n k ，表示有 k 堆火柴棒，第 i 堆火柴棒的根數(shù)為 n i 。接著便是和計(jì)算機(jī)對弈游戲，取火柴的規(guī)則如下：每次可以從一堆中取走若干根火柴，也可以將一堆全部取走，但不允許跨堆取，也不允許不取。誰取走最后一根火柴算誰勝利。例如，k=2，n 1 =n 2 =2，A 代表你，P 代表計(jì)算機(jī)，若決定 A 先?。篈： （2，2）（1，2） / 從一堆中取一

29、根P： （1，2）（1，1） / 從另一堆中取一根A： （1，1）（1，0）P： （1，0）（0，0） /P 勝利如果決定 A 后?。篜： （2，2）（2，0）A： （2，0）（0，0） /A 勝利又如 k=3，n 1 =1，n 2 =2，n 3 =3，A 決定后?。篜： （1，2，3）（0，2，3）A： （0，2，3）（0，2，2）A 已將游戲歸結(jié)為（2，2）的情況，不管 P 如何取 A 都必勝?！据斎霕永?3 6 9【輸出樣例】4 3 / 表示第 1 次從第 3 堆取 4 個出來必勝3 6 5 / 第 1 次取后的狀態(tài)【輸入樣例】415 22 19 10【輸出樣例】lose / 先取必?cái)?/p>

30、【問題分析】具體分析和程序見教材388-389頁。（3） 調(diào)整法用貪心的策略，依次構(gòu)造出一個解 S1。假設(shè)最優(yōu)解 S2 不同于 S1，找出不同之處，在不破壞最優(yōu)性的前提下，逐步調(diào)整 S2，最終使其變?yōu)?S1，從而 S1 也是最優(yōu)解。例6、排隊(duì)接水【問題描述】有 n 個人在一個水龍頭前排隊(duì)接水，假如每個人接水的時間為 Ti ，請編程找出一種這 n 個人排隊(duì)的順序，使得 n 個人的平均等待時間最小?！据斎敫袷健康?1 行為一個整數(shù) n；第 2 行分別表示每人的接水時間 T1 ，T2 ，Tn ，每兩個數(shù)據(jù)之間有 1 個空格。【輸出格式】第 1 行為一種排隊(duì)順序，即 1n 的一種排列，每兩個數(shù)據(jù)之間有

31、 1 個空格。第 2 行為這種排列方案下的平均等待時間（輸出結(jié)果精確到小數(shù)點(diǎn)后兩位）?！据斎霕永?056 12 1 99 1000 234 33 55 99 812【輸出樣例】3 2 7 8 1 4 9 6 10 5291.90【問題分析】具體分析和程序見教材390-391頁。3. 貪心的應(yīng)用舉例例7、餐巾具體見教材391-395頁。例8、大神排隊(duì)具體見教材395-396頁。例9、最大的子序列和具體見教材396-398頁。實(shí)踐鞏固第 7 課 窮舉學(xué)習(xí)目標(biāo)1. 熟練應(yīng)用窮舉算法解決一些實(shí)際問題。2. 掌握窮舉算法的常用優(yōu)化方法。3. 體會二進(jìn)制窮舉思想及其應(yīng)用。 窮舉計(jì)算機(jī)的特點(diǎn)之一就是運(yùn)算速

32、度快，善于重復(fù)做一件事。“窮舉”正是基于這一特點(diǎn)的最古老的算法。它一般是在一時找不出解決問題的更好途徑，即從數(shù)學(xué)上找不到求解的公式或規(guī)則時，根據(jù)問題中的“約束條件”，將解的所有可能情況一一列舉出來，然后再逐個驗(yàn)證是否符合整個問題的求解要求，從而求得問題的可行解或者最優(yōu)解。1. 窮舉算法的應(yīng)用舉例例1、樓層編號【問題描述】小林在 NOIP 比賽期間住在“新世界”酒店。和其他酒店不一樣的是，這個酒店每天都有一個高能的數(shù)字 t，這個數(shù)字在樓層中是不會出現(xiàn)的，以 t=3 為例，則 3、13、31、33 等樓層是不存在的，樓層編號為 1，2，4，5，所以實(shí)際上的 4 樓才是 3 樓。已知小林預(yù)訂了編號為

33、 m 層的房間，并且當(dāng)天高能數(shù)字是 t，現(xiàn)在他想知道房間所在的真實(shí)樓層是多少?！据斎敫袷健恳恍袃蓚€整數(shù) m 和 t，1m100000，0t9，保證 m 對 t 合法?！据敵龈袷健恳恍幸粋€整數(shù)，表示真實(shí)樓層。【輸入樣例】14 3【輸出樣例】12【問題分析】 根據(jù)題意，只要從 1m 窮舉樓層編號，將所有含高能數(shù)字 t 的樓層計(jì)數(shù)存儲在 ans 中，最后的答案就是 m-ans。 參考程序見教材405頁。例2、火柴棒等式【問題描述】給出 n 根火柴棒，可以拼出多少個形如“A+B=C”的等式？等式中的 A、B、C 是用火柴棒拼出的整數(shù)（若該數(shù)非零，則最高位不能是 0）。用火柴棒拼數(shù)字 09 的拼法如圖

34、9.7-1 所示。需要注意以下幾點(diǎn)：（1） 加號與等號各自需要兩根火柴棒。（2） 如果 A B，則 A+B=C 與 B+A=C 視為不同的等式（A、B、C 均大于或等于 0）。（3） n 根火柴棒必須全部用上（n24）?！据斎霕永?4【輸出樣例】2【樣例說明】兩個等式分別為：0+1=1 和 1+0=1?！締栴}分析】首先，預(yù)處理每個數(shù)字（09）需要用幾根火柴棒，存儲在數(shù)組 f 中。然后，窮舉 a 和 b，算出它們的和 c，再判斷下列約束條件是否成立：f （a）+ f （b）+ f （c）= n-4?，F(xiàn)在的問題是：a 和 b 的范圍有多大？可以發(fā)現(xiàn)盡量用數(shù)字 1 拼成的數(shù)比較大，分析可知最多不會

35、超過 1111。程序?qū)崿F(xiàn)時，分別用三個循環(huán)語句預(yù)處理好所有兩位數(shù)、三位數(shù)、四位數(shù)構(gòu)成所需要的火柴棒數(shù)量。 參考程序見教材406頁。例3、比例簡化【問題描述】在社交媒體上，經(jīng)常會看到針對某一個觀點(diǎn)同意與否的民意調(diào)查以及結(jié)果。例如，對某觀點(diǎn)表示支持的有 1498 人，反對的有 902 人，那么其比例可以簡單地記為1498902。因該比例的數(shù)值太大，難以一眼看出它們的關(guān)系。若把比例記為 53，雖然與真實(shí)結(jié)果有一定的誤差，但依然能夠較為準(zhǔn)確地反映調(diào)查結(jié)果，同時也顯得比較直觀。現(xiàn)給出支持人數(shù) A 和反對人數(shù) B，以及一個上限 L，請將 A 比 B 化簡為 A 比 B，要求在 A和 B 均不大于 L，且

36、A 和 B 互質(zhì)（兩個整數(shù)的最大公約數(shù)為 1）的前提下，A/B A/B 且 A/B-A/B 的值盡可能小。【輸入格式】一行三個整數(shù) A，B，L，每兩個整數(shù)之間用一個空格隔開，分別表示支持人數(shù)、反對人數(shù)以及上限。【輸出格式】一行兩個整數(shù) A 和 B，中間用一個空格隔開，表示化簡后的比例。【輸入樣例】1498 902 10【輸出樣例】5 3【數(shù)據(jù)規(guī)?！繉τ?100% 的數(shù)據(jù)滿足：1A10 6 ，1B10 6 ，1L100，A/BL?！締栴}分析】首先，答案為一個分?jǐn)?shù)，而且分子，分母都小于或等于 L。所以，可以直接窮舉分子 i （對應(yīng)題目中的 A）和分母 j （對應(yīng)題目中的 B）。結(jié)合題目的具體要求分

37、析：（1） i，jL，這個可以作為窮舉的范圍。（2） i/jA/B，且 i/j-A/B 的值盡量小。前者只要轉(zhuǎn)換成 i*Bj*A，后者可以“打擂臺”實(shí)現(xiàn)。假設(shè)用K1/K2表示最后的答案，初值設(shè)置為1000000/1，min=abs （k1*B-k2*A）。如果abs （i/j-A/B） abs（K1/K2-A/B），即如果 abs（i*B-j*A） abs（k1*B-k2*A），則更新 K1、K2 和 min。（3） 答案的分子、分母要互質(zhì)，這個只要從小到大窮舉 i、從大到小窮舉 j，第一個符合條件的答案肯定就是最簡分?jǐn)?shù)。假設(shè) L=10，如果先窮舉到 1/5 得到一個答案，后面的 2/10 是

38、不會更新答案的。 參考程序見教材407-408頁。例4、奶牛碑文【問題描述】小偉暑假期間到大草原旅游，在一塊石頭上發(fā)現(xiàn)了一些有趣的碑文。碑文似乎是一個神秘古老的語言，只包括三個大寫字母 C、O 和 W。盡管小偉看不懂，但是令他高興的是，C、O、W的順序形式構(gòu)成了一句他最喜歡的奶牛單詞“COW”?，F(xiàn)在，他想知道有多少次 COW 出現(xiàn)在文本中。如果 COW 內(nèi)穿插了其他字符，只要 COW 字符出現(xiàn)在正確的順序，小偉也不介意。甚至，他也不介意出現(xiàn)不同的 COW 共享一些字母。例如，CWOW 出現(xiàn)了 1 次 COW，CCOW 算出現(xiàn)了2 次 COW，CCOOWW 算出現(xiàn)了 8 次 COW?！据斎敫袷健?/p>

39、第 1 行為 1 個整數(shù) N。第 2 行為 N 個字符的字符串，每個字符是一個 C、O 或 W?！据敵龈袷健枯敵?COW 作為輸入字符串的字串出現(xiàn)的次數(shù)（不一定是連續(xù)的）。提示：答案會很大，建議用 64 位整數(shù)（long long）?！据斎霕永?COOWWW【輸出樣例】6【數(shù)據(jù)規(guī)?！繉τ?50% 的數(shù)據(jù)滿足：N60。對于 100% 的數(shù)據(jù)滿足：N105 ?！締栴}分析】因?yàn)橹挥?3 個字母，所以可以窮舉字符串中的每一個“O”，假設(shè)位置 i，然后分別計(jì)算其左邊“C” 的個數(shù) li 和右邊“W” 的個數(shù) ri，再利用乘法原理進(jìn)行計(jì)數(shù) li*ri，每次把答案累加到 ans 中。 參考程序見教材409

40、頁。2. 窮舉算法的優(yōu)化窮舉算法的特點(diǎn)是算法設(shè)計(jì)、實(shí)現(xiàn)都相對簡單，但時間復(fù)雜度和空間復(fù)雜度往往較大。因此，用窮舉算法解決問題時，往往需要盡量優(yōu)化算法，從而減少窮舉的次數(shù)，提高窮舉的效率。窮舉算法優(yōu)化的思路主要有結(jié)合約束條件，通過數(shù)學(xué)推導(dǎo)，減少窮舉的范圍和數(shù)量；通過預(yù)處理（如部分和、是否素?cái)?shù)等），以空間換時間，避免在窮舉過程中重復(fù)計(jì)算或判斷等。例5、三角形個數(shù)【問題描述】輸入一根木棒的長度 n，1n10000，將該木棒分成三段，每段的長度為正整數(shù)，輸出由該三段小木棒組成的不一樣的三角形個數(shù)。【輸入樣例】10【輸出樣例】2【樣例說明】兩個能組成的三角形邊長分別為 2、4、4 和 3、3、4?！締栴}

41、分析】窮舉三角形三條邊長（假設(shè)為 a、b、c）的可能值，判斷能否構(gòu)成一個三角形，若能則計(jì)數(shù)，最后輸出計(jì)數(shù)器的值。為了保證組成的三角形不重復(fù)，只要在窮舉時設(shè)定 1abcn-2。優(yōu)化思想很簡單但很重要，“能算不舉”，窮舉兩條邊，根據(jù)木棒長度直接計(jì)算出第三條邊長。 參考程序見教材410頁。例6、阿姆斯特朗數(shù)【問題描述】編程找出所有的三位數(shù)到七位數(shù)中的阿姆斯特朗數(shù)。阿姆斯特朗數(shù)也叫水仙花數(shù)，它的定義如下：若一個 n 位自然數(shù)的各位數(shù)字的 n 次方之和等于它本身，則稱這個自然數(shù)為阿姆斯特朗數(shù)。例如，153（153=111+333 +555）是一個三位的阿姆斯特朗數(shù)，8208 則是一個四位的阿姆斯特朗數(shù)。

42、【問題分析】由于阿姆斯特朗數(shù)是沒有規(guī)律的，只能采用窮舉法一一驗(yàn)證 1009999999 內(nèi)的所有數(shù)是否是阿姆斯特朗數(shù)，若是，則打印之。但是，如果對任意一個數(shù) K，都去求它的各位的若干次方，再求和判斷是否等于K，效率比較差。注意到，每個位只可能是09，而且只會算到37次方。所以，為了使得程序盡快運(yùn)行出正確結(jié)果，采用“以空間換時間”的策略，使用一個數(shù)組 p 預(yù)處理出所有數(shù)字的各次冪之值，pi,j表示 i 的 j 次方。另外，為了避免每次都對一個數(shù)進(jìn)行逐位分解操作，直接用數(shù)組 a8存儲一個數(shù)的每一位，窮舉 1009999999。 參考程序見教材411頁。例7、金幣【問題描述】國王將金幣作為工資，發(fā)放

43、給忠誠的騎士。第一天，騎士收到一枚金幣；之后兩天（第二天和第三天）里，每天收到兩枚金幣；之后三天（第四、五、六天）里，每天收到三枚金幣；之后四天（第七、八、九、十天）里，每天收到四枚金幣這種工資發(fā)放模式會一直這樣延續(xù)下去。當(dāng)連續(xù) n天每天收到 n 枚金幣后，騎士會在之后的連續(xù) n+1 天里，每天收到 n+1 枚金幣（n 為正整數(shù)）。請編程確定從第一天開始的給定天數(shù)內(nèi)，騎士一共獲得了多少金幣。【輸入格式】輸入包含至少一行，但不多于 1000 行。除最后一行外，輸入的每行是一組輸入數(shù)據(jù)，包含一個正整數(shù) n，表示天數(shù)。輸入的最后一行為 0，表示輸入結(jié)束?！据敵龈袷健繉γ總€數(shù)據(jù)輸出一行一個整數(shù)，表示該

44、數(shù)據(jù)對應(yīng)總金幣數(shù)。【輸入樣例】106711151610010000100021220【輸出樣例】301418355561945942820298209198【數(shù)據(jù)規(guī)?！繉τ?60% 的數(shù)據(jù)滿足：n103 ；對于 80% 的數(shù)據(jù)滿足：n106 ；對于 100% 的數(shù)據(jù)滿足：n1012 ?！締栴}分析】每次窮舉每天獲得的金幣數(shù)，或者將答案保存在數(shù)組中直接輸出，可以獲得部分分。下面利用數(shù)學(xué)推導(dǎo)進(jìn)行優(yōu)化。因?yàn)椋? 2 +2 2 +3 2 +k 2 = k （k+1）（2k+1）/ 6，假設(shè)前 n 個數(shù)為 1，2，2，3，3，3，k，k，k，k，如何求 k 呢？根據(jù) 1+2+3+k = n，即 k 2 +

45、k-2n = 0，把 k 看成未知數(shù)，解方程可求出 k =（-1 + sqrt （1+8n）/ 2 = sqrt （2n+0.25）- 0.5，另一個負(fù)數(shù)解不合法舍去。 參考程序見教材413頁。3. 二進(jìn)制窮舉思想對于二進(jìn)制數(shù) 00000，00001，00010，11111，它們是嚴(yán)格遞增有序的，如何生成類似的二進(jìn)制數(shù)字序列，就是“二進(jìn)制窮舉”思想，其應(yīng)用非常廣泛?！岸M(jìn)制窮舉”的實(shí)現(xiàn)代碼如下:3. 二進(jìn)制窮舉思想#includeusing namespace std;int main()int n;int b100;scanf( “ %d ” ,&n);for(int i = 0; i =

46、n; i+) bi = 0;while(b0 = 0)for(int i = 1; i = n; i+) printf( “ %d ” ,bi);printf( “ n ” );int j = n;while(bj = 1) j-;bj+;for(int i = j + 1; i 0) & (x7 0) & (x3 0) & (x3 3)x7 = x7 + x3 - 3; x3 = 3;elsex3 = x7 + x3; x7 = 0;4） 7 斤的瓶子往 10 斤的瓶子里倒，規(guī)則為：if(x7 0)x10 = x10 + x7; x7 = 0;5） 3 斤的瓶子往 7 斤的瓶子里倒，規(guī)則為：

47、if(x3 0) & (x7 7)x3 = x3 + x7 - 7; x7 = 7;elsex7 = x3 + x7; x3 = 0;6） 3 斤的瓶子往 10 斤的瓶子里倒，規(guī)則為：if(x3 0)x10 = x10 + x3; x3 = 0; 控制策略規(guī)定了操作的順序，即在什么條件下用什么規(guī)則進(jìn)行操作，什么條件下停止運(yùn)行，它規(guī)定了問題求解的搜索策略和路線。控制策略一般分為不可撤回方式和可撤回方式（回溯法）兩類。另外，如果狀態(tài)的總數(shù)不太大時，可采用全部枚舉（寬度優(yōu)先搜索）的辦法得到最優(yōu)解。對于狀態(tài)比較大時，可采用深度優(yōu)先搜索，有時還要設(shè)計(jì)“啟發(fā)式”搜索或者進(jìn)行必要的“剪枝”優(yōu)化。對于狀態(tài)非常

48、大時，可采用一些貪心思想，先得到一個較優(yōu)解，以此作為“剪枝”或“分支定界”的依據(jù)，來盡快取得最優(yōu)解。 搜索問題一般有兩種情況：一種是給出初始結(jié)點(diǎn)，要求尋找符合約束條件的目標(biāo)結(jié)點(diǎn)；另一種是給出初始結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)，要求找到從初始結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的一條路徑。對于解的要求也不盡相同，有的問題要求出一個可行解，有的則要求出最優(yōu)解，還有的問題要找出全部解，有時還要按照一定的順序輸出。 搜索問題中的數(shù)據(jù)結(jié)構(gòu)一般要求表達(dá)要合理，有助于計(jì)算機(jī)的處理；信息要完整，能反應(yīng)出狀態(tài)的本質(zhì)和狀態(tài)之間的關(guān)系；還要節(jié)省存儲空間，盡可能地提高搜索的速度。比如分油問題本來用一個三元組（x10,x7,x3）即可，但是為了輸出方便，我

49、們增加一個d,用來表示該結(jié)點(diǎn)的父結(jié)點(diǎn)（由誰拓展而來），即變成一個四元組（x10,x7,x3,d）。另外，還會用到隊(duì)列來實(shí)現(xiàn)控制策略。當(dāng)然，不能忘記狀態(tài)變化過程中的重復(fù)性檢查，比如哈希表，因?yàn)榇蠖鄶?shù)情況下，出現(xiàn)重復(fù)狀態(tài)是毫無意義的，會造成死循環(huán)和空間的浪費(fèi)。3. 寬度優(yōu)先搜索的基本思想寬度優(yōu)先搜索（Breadth First Search，BFS），簡稱寬搜，又稱廣度優(yōu)先搜索。它是從初始結(jié)點(diǎn)開始，應(yīng)用產(chǎn)生式規(guī)則和控制策略生成第一層結(jié)點(diǎn)，同時檢查目標(biāo)結(jié)點(diǎn)是否在這些生成的結(jié)點(diǎn)中。若沒有，再用產(chǎn)生式規(guī)則將所有第一層結(jié)點(diǎn)逐一拓展，得到第二層結(jié)點(diǎn)，并逐一檢查第二層結(jié)點(diǎn)是否包含目標(biāo)結(jié)點(diǎn)。若沒有，再用產(chǎn)生式規(guī)

50、則拓展第二層結(jié)點(diǎn)。如此依次拓展，檢查下去，直至發(fā)現(xiàn)目標(biāo)結(jié)點(diǎn)為止。如果拓展完所有結(jié)點(diǎn)，都沒有發(fā)現(xiàn)目標(biāo)結(jié)點(diǎn)，則問題無解。對于以上“無向圖”，從頂點(diǎn) V0 開始進(jìn)行寬度優(yōu)先搜索，得到的一個序列為 V0，V1，V2，V3，V4，V6，V5。寬度優(yōu)先搜索是一種“盲目”搜索，所有結(jié)點(diǎn)的拓展都遵循“先進(jìn)先出”的原則，所以采用“隊(duì)列”來存儲這些狀態(tài)。寬度優(yōu)先搜索的算法框架如下：void BFS while (front rear)p = false;對于例1的分油問題，隊(duì)列的每個元素均為一個四元組（x10，x7，x3，d），寬度優(yōu)先搜索的狀態(tài)變化如下：參考程序見教材433-435頁。4. 寬度優(yōu)先搜索應(yīng)用舉例

51、例2、瓷磚【問題描述】在一個 wh 的矩形廣場上，每一塊 11 的地面都鋪設(shè)了紅色或黑色的瓷磚。小林同學(xué)站在某一塊黑色的瓷磚上，他可以從此處出發(fā)，移動到上、下、左、右四個相鄰的且是黑色的瓷磚上?，F(xiàn)在，他想知道，通過重復(fù)上述移動所能經(jīng)過的黑色瓷磚數(shù)?！据斎敫袷健康?1 行為 h、w，2w、h50，之間由一個空格隔開；以下為一個 w 行 h 列的二維字符矩陣，每個字符為“.”“#”“”，分別表示該位置為黑色的瓷磚、紅色的瓷磚、小林的初始位置?！据敵龈袷健枯敵鲆恍幸粋€整數(shù)，表示小林從初始位置出發(fā)經(jīng)過的黑色瓷磚數(shù)。【輸入樣例】11 9. # . . . . . . . . . # . # # # #

52、# # # . # . # . . . . . # . # . # . # # # . # . # . # . . # . # . # . # # # # # . # . # . . . . . . . # . # # # # # # # # # . . . . . . . . . . .【輸出樣例】59【問題分析】讀入字符數(shù)組，找到小林的初始位置“”，并把坐標(biāo)入隊(duì)，作為隊(duì)頭元素。寬度優(yōu)先搜索，檢查隊(duì)頭元素的上、下、左、右四個位置是否是黑色瓷磚“.”，是則入隊(duì)，不斷取出隊(duì)頭元素進(jìn)行四個方向的拓展，直到隊(duì)列為空。為了避免一個位置被多次重復(fù)走到，定義一個布爾型數(shù)組 ai,j用來判重，位置（i，j）

53、為黑色瓷磚設(shè)置為 true，紅色的或者走過的瓷磚設(shè)置為 false。最后，隊(duì)列的尾指針即為答案。本題是搜索的一個重要應(yīng)用，所謂的求“聯(lián)通塊”問題。參考程序見教材436-437頁。例3、最大黑區(qū)域【問題描述】二值圖像是由黑和白兩種像素組成的矩形點(diǎn)陣，圖像識別的一個操作是求出圖像中最大黑區(qū)域的面積。請?jiān)O(shè)計(jì)一個程序完成二值圖像的這個操作。黑區(qū)域由黑像素組成，一個黑區(qū)域中的每像素至少與該區(qū)域中的另一像素相鄰，規(guī)定一個像素僅與其上、下、左、右的像素相鄰。兩個不同的黑區(qū)域沒有相鄰的像素。一個黑區(qū)域的面積是其所包含的像素?cái)?shù)?！据斎敫袷健康?1 行含兩個整數(shù) n 和 m，1n、m100，分別表示二值圖像的行數(shù)

54、與列數(shù)。后面n行，每行含m個整數(shù)0或1，其中第i行表示圖像的第i行的m個像素，0表示白像素，1 表示黑像素。每行中的兩個數(shù)之間用一個空格分隔?！据敵龈袷健枯敵鲆恍幸粋€數(shù)，表示相應(yīng)的圖像中最大黑區(qū)域的面積?！据斎霕永? 60 1 1 0 0 11 1 0 1 0 10 1 0 0 1 00 0 0 1 1 11 0 1 1 1 0【輸出樣例】7【問題分析】如果先找到一個黑點(diǎn)，那么問題就和例 2 一樣了。所以，本題只要從左上角開始，利用一個兩重循環(huán)窮舉找到一個黑點(diǎn)（ai，j=1），然后做一遍寬搜，并且記下此黑色區(qū)域（聯(lián)通塊）的大小，再通過打擂臺記錄最大值作為答案 ans。如果題目要求的是有幾個黑

55、區(qū)域，則只要每次寬搜時“計(jì)數(shù)器”加一。參考程序見教材438-439頁。例4、飛越原野【問題描述】在一片廣闊的土地上有一個鳥人，他需要從這里穿過原野回到基地。這片原野上有平地（P）、有湖泊（L）。因?yàn)轼B人可以飛，所以有的時候，他可以飛越湖泊?，F(xiàn)在，鳥人需要用最快的時間回到基地。假設(shè)原野是一個 mn 的矩陣，有兩種地形，用 P 和 L 表示。鳥人只能停留在平地上。他目前處在（1，1）這個位置，而目的地是（m，n）。他可以向上、下、左、右四個方向移動，或者飛行。每移動一格需要 1 個單位時間。而飛行無論飛多遠(yuǎn)，都只需要 1 個單位時間。飛行的途中不可以改變方向。也就是說，飛行也只能是上、下、左、右四

56、個方向，并且一次飛行最終必須降落在平地上。當(dāng)然，受到能量的限制，鳥人不能無限制地飛行，他總共最多可以飛行的距離為 D?！据斎敫袷健康?1 行是 3 個整數(shù) m、n 和 D，3 個數(shù)都不超過 100。下面是一個 mn 的字符矩陣，表示原野?！据敵龈袷健枯敵鲆恍幸粋€整數(shù)表示最短時間。如果無法到達(dá)，輸出“impossible”。【輸入樣例】4 4 2PLLPPPLPPPPPPLLP【輸出樣例】5【問題分析】具體分析及參考程序見教材440-441頁。例5、關(guān)系網(wǎng)絡(luò)【問題描述】有 n 個人，編號為 1n。其中有一些人相互認(rèn)識，現(xiàn)在 x 想要認(rèn)識 y，可以通過他所認(rèn)識的人來認(rèn)識更多的人（如果 a 認(rèn)識 b

57、、b 認(rèn)識 c，那么 a 可以通過 b 來認(rèn)識 c），求出 x 最少需要通過多少人才能認(rèn)識 y?！据斎敫袷健康?1 行 3 個正整數(shù) n、x、y，其中：n100，1x、yn。接下來是一個 nn 的鄰接矩陣，ai,j=1 表示 i 認(rèn)識 j，ai,j=0 表示 i 不認(rèn)識 j。保證 i=j 時，ai,j=0，并且 ai,j =aj,i，一行中的兩個數(shù)之間有一個空格?！据敵龈袷健枯敵鲆恍幸粋€數(shù)，表示 x 認(rèn)識 y 最少需要通過的人數(shù)?！据斎霕永? 1 50 1 0 0 01 0 1 1 00 1 0 1 00 1 1 0 10 0 0 1 0【輸出樣例】2【問題分析】本題是寬度優(yōu)先搜索的一個重要

58、應(yīng)用“求最優(yōu)值問題”。先設(shè)答案 ans=0。把 x 加入隊(duì)列并設(shè)置為隊(duì)頭元素，從隊(duì)頭開始進(jìn)行寬搜，窮舉鄰接矩陣的第 x 行，看 x 認(rèn)識誰（判斷 ax,j=1），認(rèn)識的人（j）全部依次入隊(duì)，并且 ans+，如果出現(xiàn)了 y，則輸出 ans，結(jié)束搜索，否則，取出隊(duì)頭元素繼續(xù)寬搜。參考程序見教材442-443頁。實(shí)踐鞏固第 10 課 深度優(yōu)先搜索學(xué)習(xí)目標(biāo)1. 掌握深度優(yōu)先搜索的基本思想和算法框架。2. 熟練應(yīng)用深度優(yōu)先搜索求解一些實(shí)際問題。3. 初步了解深度優(yōu)先搜索中的剪枝優(yōu)化。深度優(yōu)先搜索深度優(yōu)先搜索是將當(dāng)前狀態(tài)按照一定的規(guī)則順序，先拓展一步得到一個新狀態(tài)，再對這個新狀態(tài)遞歸拓展下去。如果無法拓展

59、，則退回一步到上一個狀態(tài)，再按照原先設(shè)定的規(guī)則順序重新尋找一個狀態(tài)拓展。如此搜索，直至找到目標(biāo)狀態(tài)，或者遍歷完所有狀態(tài)。所以，深度優(yōu)先搜索也是一種“盲目”搜索。深度優(yōu)先搜索對于圖9.10-1所示的一個“無向圖”，從頂點(diǎn)V0開始進(jìn)行深度優(yōu)先搜索，得到的一個序列為：V0，V1，V2，V6，V5，V3，V4。 1. 深度優(yōu)先搜索的算法框架深度優(yōu)先搜索（Depth First Search，DFS），簡稱深搜，其狀態(tài)“退回一步”的順序符合“后進(jìn)先出”的特點(diǎn)，所以采用“?！贝鎯顟B(tài)。深搜適用于要求所有解方案的題目。深搜可以采用直接遞歸的方法實(shí)現(xiàn)，其算法框架如下：1. 深度優(yōu)先搜索的算法框架void df

60、s(int dep, 參數(shù)表 );自定義參數(shù) ;if( 當(dāng)前是目標(biāo)狀態(tài) )輸出解或者作計(jì)數(shù)、評價(jià)處理 ;elsefor(i = 1; i m，n 的拆分和 m 的拆分本質(zhì)上是一樣的，可以把 n 的拆分看成先拆出一個數(shù) i （1in），然后再對剩下的 n-i 遞歸拆分。設(shè) rest 表示拆分后的余數(shù)，s 數(shù)組用來存儲拆分的方案。顯然，當(dāng) rest=0 的時候，就應(yīng)該輸出當(dāng)前的一種拆分方案。題目規(guī)定 S 1 S 2 S k 。顯然，S k+1 的范圍應(yīng)該從 S k 到 rest。參考程序見教材456頁。例5、背包問題問題描述】小明就要去春游了。媽媽給他買了很多好吃的。小明想把這些吃的都放進(jìn)他的書包