2023學(xué)年完整公開課版第9單元電子

第9單元基本算法林厚從信息學(xué)奧賽課課通C第1課進制轉(zhuǎn)換學(xué)習(xí)目標1理解二進制計數(shù)原理。2掌握不同進制數(shù)之間的轉(zhuǎn)換原理和實現(xiàn)方法。3學(xué)會使用進制轉(zhuǎn)換的原理解決一些實際問題。進制實際生活中，人們使用十進制計數(shù)。但是，任何信息在計算機中都是采用二進制編碼表示的，有時還會用到十六進制。十進制計數(shù)原理采用“0”~“9”十個符號，運算規(guī)則為“逢十進一”，基數(shù)是十。二進制計數(shù)原理采用“0”和“1”兩個符號，運算規(guī)則是“逢二進一”，基數(shù)是二。進制顯然，十進制中的數(shù)“10”和二進制中的“10”、十六進制中的“10”是不一樣的。為了區(qū)分，我們分別表示成（10）10、（10）2、（10）16。有時也會在一個數(shù)的后面加上英文字母D、B、H來分別表示該數(shù)是十進制數(shù)、二進制數(shù)或者十六進制數(shù)，如96D、110B、2B3FH等。1進制轉(zhuǎn)換的基本原理不同進制數(shù)之間轉(zhuǎn)換的基本原理就是依據(jù)其“運算規(guī)則”和“權(quán)”的含義進行乘除運算。1二進制數(shù)轉(zhuǎn)換成十進制數(shù)一個二進制數(shù)轉(zhuǎn)換成十進制數(shù)的方法是將其表示成“按權(quán)展開式”，再按十進制運算規(guī)則求和。這種方法可以擴展到任意n進制。進制2二進制數(shù)與十六進制數(shù)之間的相互轉(zhuǎn)換二進制數(shù)轉(zhuǎn)換成十六進制數(shù)的方法是以小數(shù)點為準，往前、往后“四位一段”分別轉(zhuǎn)換成十六進制數(shù)再求和，不滿四位要補齊。3十進制數(shù)轉(zhuǎn)換成二進制十進制數(shù)轉(zhuǎn)換成二進制要將整數(shù)和小數(shù)分開轉(zhuǎn)換，最后再求和。整數(shù)的轉(zhuǎn)換方法是：不斷除以2求余數(shù)，最后反序輸出；小數(shù)的轉(zhuǎn)換方法是：不斷乘以2，將每次得到的整數(shù)部分依次輸出，并且每次都將整數(shù)部分恢復(fù)為0。2進制轉(zhuǎn)換的應(yīng)用舉例例1、進制轉(zhuǎn)換【問題描述】將任意一個n進制整數(shù)轉(zhuǎn)換成十進制?！据斎敫袷健康?行1個正整數(shù)n，1<n<10；第2行1個整數(shù)?！据敵龈袷健恳恍幸粋€數(shù)，表示轉(zhuǎn)換得到的十進制數(shù)，保證答案不超過2147483647。【輸入樣例】2100110【輸出樣例】38【問題分析】讀入n和，根據(jù)n和的位數(shù)，分別求出的每一位對應(yīng)的“權(quán)值”，然后窮舉每一位，將它乘以該位對應(yīng)的權(quán)值，累加便可得到結(jié)果。更高效、更簡潔的算法是采用“秦九韶公式”。對于樣例輸入，可以這樣計算：1*2＋0*20*21*21*20=38具體實現(xiàn)采用“迭代法”，用一個變量不斷乘以n，再加上下一位。//esain{freopen””,”r”,stdin;freopen””,”w”,stdout;intn,ans=0,i=0;chars;scanf”%d\n”,n;whiles=getchar!='\n'{ans=ans*ns-48;i;}printf”%d\n”,ans;return0;}例2、汽車牌照【問題描述】小Y最近發(fā)現(xiàn)街上的汽車越來越多了，作為汽車的重要標志——汽車牌照也是越來越不夠用了，已經(jīng)從以前的十進制發(fā)展到三十六進制了，以前的一個汽車牌照“蘇D88888”，現(xiàn)在的牌照“蘇D0YY11”。小Y突發(fā)其想，想知道他看到的大量汽車牌照中最近的兩個汽車牌照相差多少？【輸入格式】若干行不超過500000行，每行為一個汽車牌照。每個汽車牌照為一個7位的字符串，格式為SD×××××，其中一個×表示一個0~9或A~，所涉及的字母均為大寫。【輸出格式】一行一個數(shù)，表示最接近的兩個汽車牌照之間的差值，要求為十進制數(shù)?！据斎霕永縎D12345SD88888SD22222SD99999【輸出樣例】1678245例3、數(shù)列【問題描述】給定一個正整數(shù)，把所有的方冪及所有有限個互不相等的的方冪之和構(gòu)成一個遞增的序列。例如，當=3時，這個序列是：1，3，4，9，10，12，13，…請求出這個序列的第n項的值用十進制數(shù)表示?！据斎敫袷健恳恍袃蓚€正整數(shù)和n，之間用一個空格隔開，且3≤≤15，10≤n≤1000?！据敵龈袷健恳恍幸粋€正整數(shù)?！据斎霕永?100【輸出樣例】981實踐鞏固第2課高精度運算學(xué)習(xí)目標1體會高精度運算的應(yīng)用場合。2熟練掌握高精度加法和乘法運算。高精度運算在編程進行數(shù)值運算時，有時會遇到運算的精度要求特別高，遠遠超過各種數(shù)據(jù)類型的精度范圍；有時數(shù)據(jù)又特別大，遠遠超過各種數(shù)據(jù)類型的極限值。這種情況下，就需要進行“高精度運算”。高精度運算首先要處理好數(shù)據(jù)的接收和存儲問題，其次要處理好運算過程中的“進位”和“借位”問題。例1、高精度加法【問題描述】輸入兩個1000位以內(nèi)的正整數(shù)，輸出它們的和?！据斎霕永?23456789987654321【輸出樣例】1111111110【問題分析】用字符串的方式讀入兩個高精度數(shù)，轉(zhuǎn)存到兩個整型數(shù)組a和b中，如圖92-1所示，模擬加法的過程，從低位第0位開始對應(yīng)位a相加，同時處理進位，結(jié)果存儲到另一個數(shù)組c中。最后，從高位到低位輸出c。參考程序見教材329頁。例2、高精度乘法【問題描述】輸入兩個100位以內(nèi)的正整數(shù)，輸出它們的乘積。【輸入樣例】123456789987654321【輸出樣例】【問題分析】如圖92-2所示，模擬“豎式”乘法的過程，用一個數(shù)的每一位a相乘，結(jié)果存儲到c位，同時處理好進位。參考程序見教材330頁。例3、n!的精確值【問題描述】輸入n，輸出n!的精確值，n!=1×2×3×…×n，1<n<1000?！据斎霕永?00【輸出樣例】【問題分析】假設(shè)已經(jīng)計算好n-1!，那么，對于求n!，就是用一個整數(shù)去乘以一個高精度數(shù)。只要用n乘以n-1!的每一位從低位開始，同時不斷處理進位。參考程序見教材331頁。例4、n/m的精確值【問題描述】輸入n和m，輸出n除以m的精確值。假設(shè)n和m在int范圍以內(nèi)，結(jié)果精確到小數(shù)點后100位。【輸入樣例】355113【輸出樣例】【問題分析】如圖92-3所示，模擬數(shù)學(xué)中的“短除法”。由數(shù)學(xué)知識可知，除法運算中被除數(shù)、除數(shù)和商、余數(shù)的關(guān)系為：新的被除數(shù)=10×余數(shù)商=被除數(shù)／除數(shù)余數(shù)=被除數(shù)%除數(shù)參考程序見教材332頁。實踐鞏固第3課模擬學(xué)習(xí)目標1熟練應(yīng)用模擬法解決一些實際問題。2體驗?zāi)M法的審題分析和細節(jié)測試。模擬在信息學(xué)奧賽中，有一類問題是模擬一個游戲的對弈過程，或者模擬一項任務(wù)的操作過程，進行統(tǒng)計計分、判斷輸贏等。這些問題很難建立數(shù)學(xué)模型用特定算法解決，一般只能采用“模擬”法。用模擬法解題必須關(guān)注以下幾個問題：審題要仔細，游戲規(guī)則不能錯；分析要全面，各種特例不能漏；編程要細心，測試運行要到位。例1、蚱蜢【問題描述】有一天，一只蚱蜢像往常一樣在草地上愉快地跳躍，它發(fā)現(xiàn)了一條寫滿了英文字母的紙帶。蚱蜢只能在元音字母A、E、I、O、U、Y間跳躍，一次跳躍所需的能力是兩個位置的差。紙帶所需的能力值為蚱蜢從紙帶開頭的前一個位置根據(jù)規(guī)則跳到紙帶結(jié)尾的后一個位置的過程中能力的最大值。蚱蜢想知道跳躍紙帶所需的能力值最小是多少。如圖93-1所示的紙帶所需的能力值最小是4。【輸入格式】一行一個字符串，字符串長不超過100。【輸出格式】一行一個整數(shù)，代表最小能力值?！据斎霕永縈LBVWSQFDCVBNHTJLLBVWSQFDCVBNHTJLPMNFVC【輸出樣例】85【問題分析】從頭到尾枚舉紙帶的每一個字母，按照規(guī)則模擬蚱蜢在元音字母之間跳躍的過程，打擂臺記錄能力值。參考程序見教材336頁。例2、遭遇戰(zhàn)【問題描述】小林和小華在一個n×n的矩形方格里玩游戲，矩形左上角為0，0，右下角為n-1，n-1。兩人同時進入地圖的隨機位置，并以相同速度進行走位。為了隱蔽性，兩人都不會再走自己走過的格子。如果兩人向某一方向前進，那么他們會跑到不能跑為止，當不能跑的時候，小林會向右轉(zhuǎn)，小華則會向左轉(zhuǎn)，如果不能跑，則不再動?，F(xiàn)在已知兩人進入地圖的初始位置和方向，請算出兩人遭遇的位置?！据斎敫袷健康?行1個正整數(shù)t，表示測試數(shù)據(jù)組數(shù)，1≤t≤10。接下來的t組數(shù)據(jù)，每組數(shù)據(jù)的第1行包含1個整數(shù)n，1≤n≤1000。第2行包含3個整數(shù)、y和d，表示小林的初始位置和一開始跑的方向。其中，d=0表示東；d=1表示南；d=2表示西；d=3表示北。第3行與第2行格式相同，但描述的是小華。【輸出格式】輸出t行，若會遭遇，則包含兩個整數(shù)，表示他們第一次相遇格子的坐標，否則輸出“-1”?！据斎霕永?20000124010320【輸出樣例】-113【問題分析】設(shè)置兩個布爾型數(shù)組，分別記錄模擬每個人走過的格子。如果兩人沒有相遇并且還可以跑，就讓他們按照規(guī)則一直跑下去。參考程序見教材337-338頁。例3、乒乓球【問題描述】國際乒聯(lián)立志推行一系列改革，以推動乒乓球運動在全球的普及。其中11分制改革引起了很大的爭議，有一部分球員因為無法適應(yīng)新規(guī)則只能選擇退役。華華就是其中一位，他退役之后走上了乒乓球研究工作，意圖弄明白11分制和21分制對選手的不同影響。在開展研究之前，他首先需要對自己多年比賽的統(tǒng)計數(shù)據(jù)進行一些分析，所以需要一些幫忙。華華通過以下方式進行分析，首先將比賽每個球的勝負列成一張表，然后分別計算在11分制和21分制下，雙方的比賽結(jié)果截至記錄末尾。比如，現(xiàn)在有這么一份記錄，其中W表示華華獲得一分，L表示華華對手獲得一分：WWWWWWWWWWWWWWWWWWWWWWLW。在11分制下，此時比賽的結(jié)果是華華第一局11比0獲勝，第二局11比0獲勝，正在進行第三局，當前比分1比1。而在21分制下，此時比賽結(jié)果是華華第一局21比0獲勝，正在進行第二局，比分2比1。如果一局比賽剛開始，則此時比分為0比0。本題就是要對于一系列比賽信息的輸入WL形式，輸出正確的結(jié)果?！据斎敫袷健枯斎胛募舾尚凶址啃兄炼?0個字母，字符串由大寫的W、L和E組成。其中E表示比賽信息結(jié)束，程序應(yīng)該忽略E之后的所有內(nèi)容。【輸出格式】輸出由兩部分組成，每部分有若干行，每一行對應(yīng)一局比賽的比分按比賽信息輸入順序。其中第一部分是11分制下的結(jié)果，第二部分是21分制下的結(jié)果，兩部分之間由一個空行分隔。【輸入樣例】WWWWWWWWWWWWWWWWWWWWWWLWE【輸出樣例】11∶011∶01∶121∶02∶1【問題分析】讀入字符串，分別按照11分制和21分制下的規(guī)則模擬比賽進行計分輸出。參考程序見教材339-340頁。例4、保齡球【問題描述】打保齡球是用一個滾球去打擊十個站立的柱，將柱擊倒。一局分十輪，每輪可滾球一次或多次，以擊倒的柱數(shù)為依據(jù)計分。一局得分為十輪得分之和，而每輪的得分不僅與本輪滾球情況有關(guān)，還可能與后續(xù)一兩輪的滾球情況有關(guān)。即某輪某次滾球擊倒的柱數(shù)不僅要計入本輪得分，還可能會計入前一兩輪得分。具體的滾球擊柱規(guī)則和計分方法如下：1若某一輪的第一次滾球就擊倒全部十個柱，則本輪不再滾球若是第十輪則還需另加兩次滾球，不妨稱其為第十一輪和第十二輪，并不是所有的情況都需要滾第十一輪和第十二輪球。該輪得分為本次擊倒柱數(shù)10與以后兩次滾球所擊倒柱數(shù)之和。2若某一輪的第一次滾球未擊倒十個柱，則可對剩下未倒的柱再滾球一次。如果這兩次滾球擊倒全部十個柱，則本輪不再滾球若是第十輪則還需另加一次滾球，該輪得分為這兩次共擊倒柱數(shù)10與以后一次滾球所擊倒柱數(shù)之和。3若某一輪兩次滾球未擊倒全部十個柱，則本輪不再繼續(xù)滾球，該輪得分為這兩次滾球擊倒的柱數(shù)之和?？傊?，若某一輪中一次滾球或兩次滾球擊倒十個柱，則本輪得分是本輪首次滾球開始的連續(xù)三次滾球擊倒柱數(shù)之和其中有一次或兩次不是本輪滾球。若一輪內(nèi)二次滾球擊倒柱數(shù)不足十個，則本輪得分即為這兩次擊倒柱數(shù)之和。下面以實例說明如下：輪123456789101112擊球情況///729/818//9//8/各輪得分302719918920202020累計總分30577685103112132152172192現(xiàn)在請編寫一個保齡球計分程序，用來計算并輸出最后的總得分?！据斎敫袷健枯斎胍恍?，為前若干輪滾球的情況，每輪滾球用一到兩個字符表示，每一個字符表示一次擊球，字符“/”表示擊倒當前球道上的全部的柱，否則用一個數(shù)字字符表示本次滾球擊倒的當前球道上的柱的數(shù)目，兩輪滾球之間用一個空格隔開?！据敵龈袷健枯敵鲆恍幸粋€整數(shù)，代表最后的得分?！据斎霕永?】///729/818//9//8/【輸出樣例1】192【輸入樣例2】9090/9/81///72//0【輸出樣例2】170【輸入樣例3】///729/818//9/15【輸出樣例3】169【問題分析】本題的難點在于每一次、每一輪滾球的分數(shù)不能立刻算出，可能依賴于后面1~2輪，所以需要多次積分。參考程序見教材341-342頁。實踐鞏固第4課遞推學(xué)習(xí)目標1理解遞推關(guān)系和遞推法。2體會遞推法解題的三個重點和兩類模型。3熟練應(yīng)用遞推法解決一些實際問題。遞推“遞推”是計算機解題的一種常用方法。利用“遞推法”解題首先要分析歸納出“遞推關(guān)系”。如經(jīng)典的斐波那契數(shù)列問題，用fi表示第i項的值，則f1=0，f2=1，在n>2時，存在遞推關(guān)系：fn=fn-1fn-2。在遞推問題模型中，每個數(shù)據(jù)項都與它前面的若干個數(shù)據(jù)項（或后面的若干個數(shù)據(jù)項）存在一定的關(guān)聯(lián)，這種關(guān)聯(lián)一般是通過一個“遞推關(guān)系式”來描述的。求解問題時，需要從初始的一個或若干數(shù)據(jù)項出發(fā)，通過遞推關(guān)系式逐步推進，從而推導(dǎo)計算出最終結(jié)果。這種求解問題的方法叫“遞推法”。其中，初始的若干數(shù)據(jù)項稱為“遞推邊界”。遞推解決遞推問題有三個重點：建立正確的遞推關(guān)系式；分析遞推關(guān)系式的性質(zhì)；根據(jù)遞推關(guān)系式編程求解。遞推法分為“順推”和“倒推”兩類模型。所謂順推，就是從問題的邊界條件初始狀態(tài)出發(fā)，通過遞推關(guān)系式依次從前往后遞推出問題的解；所謂倒推，就是在不知道問題的邊界條件初始狀態(tài)下，從問題的最終解目標狀態(tài)或某個中間狀態(tài)出發(fā)，反過來推導(dǎo)問題的初始狀態(tài)。例1、鋪瓷磚【問題描述】用紅色的1×1和黑色的2×2兩種規(guī)格的瓷磚不重疊地鋪滿n×3的路面，求出有多少種不同的鋪設(shè)方案?！据斎敫袷健恳恍幸粋€整數(shù)n，0<n<1000?！据敵龈袷健恳恍幸粋€整數(shù)，為鋪設(shè)方案的數(shù)量模12345的結(jié)果?！据斎霕永?【輸出樣例】3【問題分析】用fn表示n×3的路面有多少種不同的鋪設(shè)方案。把路面看成n行3列，則問題可以分成兩種情況考慮，一種是最后一行用3塊1×1的瓷磚鋪設(shè)；另一種是最后兩行用1塊2×2和2塊1×1的瓷磚鋪設(shè)最后兩行就有兩種鋪法，第一種鋪法就轉(zhuǎn)換為fi-1的問題了，第二種鋪法就轉(zhuǎn)換成fi-2的問題了。根據(jù)加法原理，得到的遞推關(guān)系式為fi=fi-1fi-2×2，邊界為f0=1，f1=1。參考程序見教材350-351頁。例2、彩帶【問題描述】一中90周年校慶，小林準備用一些白色、藍色和紅色的彩帶來裝飾學(xué)校超市的櫥窗，他希望滿足以下兩個條件：1相同顏色的彩帶不能放在相鄰的位置；2一條藍色的彩帶必須放在一條白色的彩帶和一條紅色的彩帶中間。現(xiàn)在，他想知道滿足要求的放置彩帶的方案數(shù)有多少種。例如，如圖94-1所示為櫥窗寬度n=3的所有放置方案，共4種?！据斎敫袷健恳恍幸粋€整數(shù)n，表示櫥窗寬度或者說彩帶數(shù)目?！据敵龈袷健恳恍幸粋€整數(shù)，表示裝飾櫥窗的彩帶放置方案數(shù)?！緲永斎搿?【樣例輸出】4【數(shù)據(jù)規(guī)模】對30%的數(shù)據(jù)滿足：1≤n≤15。對100%的數(shù)據(jù)滿足：1≤n≤45?！締栴}分析】用fi表示寬度為i的櫥窗或i條彩帶的合法放置方案數(shù)，則f1=2，f2=2，f3=4，f4=6，f5=10，……不難發(fā)現(xiàn)，答案就是初始值不一樣的斐波那契數(shù)列，所以，用遞推法就可以很方便地求出fn。參考程序見教材352頁。例3、城市路徑【問題描述】地圖上有n個城市，一只奶牛要從1號城市開始依次經(jīng)過這些城市，最終到達n號城市。但是這只奶牛覺得這樣太無聊了，所以它決定跳過其中的一個城市但是不能跳過1號和n號城市，使得它從1號城市開始，到達n號城市所經(jīng)過的總距離最小。假設(shè)每一個城市i都有一個坐標i，yi，從1，y1的城市1到2，y2的城市2之間的距離為|1-2||y1-y2|?！据斎敫袷健康?行1個正整數(shù)n，表示城市個數(shù)。接下來的n行，每行2個數(shù)i和yi，表示城市i的坐標?！据敵龈袷健恳恍幸粋€數(shù)，使得它從1號城市開始，跳過某一個城市，到達n號城市所經(jīng)過的最小總距離?！据斎霕永?008311-1100【輸出樣例】14【樣例說明】跳過2號城市?！緮?shù)據(jù)規(guī)模】對于40%的數(shù)據(jù)滿足：n≤1000。對于100%的數(shù)據(jù)滿足：3≤n≤100000，-1000≤i，yi≤1000。【問題分析】設(shè)fi為從城市1依次跳到城市i的距離之和，設(shè)gi為從城市i依次跳到城市n的距離之和，則問題的答案為min{fi-1gi1dis表示城市i-1到城市i1的曼哈頓距離，fi和gi都可以用遞推來預(yù)處理求出：fi=fi-1dis。也可以設(shè)fi表示從城市1依次跳到城市n，且跳過城市i的距離之和，sum表示表示從城市1依次跳到城市n的距離之和，則fi=min{sum–dis}。參考程序見教材353頁。例4、穿越沙漠【問題描述】一輛卡車欲穿過1000千米的沙漠，卡車耗油為1升/千米，卡車總載油能力為500升。顯然，卡車裝一次油是過不了沙漠的。因此，司機必須設(shè)法在沿途建立幾個貯油點，使卡車能順利穿越沙漠。試問：司機如何建立這些貯油點？每一貯油點應(yīng)存多少油，才能使卡車以消耗最少汽油的代價通過沙漠？結(jié)果保留小數(shù)點后兩位。編程計算及打印建立的貯油點序號，各貯油點距沙漠邊沿出發(fā)的距離以及存油量，格式如下：NoDistancemOillitre1××××××××××2××××××××××3××××××××××【問題分析】因為從起始點出發(fā)無法確定第1個貯油點的位置及貯油量，所以順推行不通。下面換個思路倒推試試看。先從終點出發(fā)倒推最后一個貯油點的位置及貯油量，然后再把最后一個貯油點作為終點，倒推倒數(shù)第2個貯油點的位置及貯油量，……設(shè)disi表示第i個貯油點至終點i=0的距離，oili表示第i個貯油點的貯油量。從終點向起始點倒推，逐一求出每個貯油點的位置及存油量，如圖94-2所示。從貯油點i向貯油點i1倒推的策略是，卡車在點i和點i1間往返若干次?？ㄜ嚸看畏祷豬1處時正好耗盡500升汽油，而每次從i1處出發(fā)時又必須裝滿500升汽油。兩點之間的距離必須滿足在耗油最少的條件下使i點貯存i×500升汽油的要求0≤i≤n-1，根據(jù)貪心思想，第一個貯油點i=1應(yīng)距終點i=0處500千米且在該處貯藏500升汽油，這樣才能保證卡車能由i=1處到達終點i=0處，這就是說，dis1=500，oil1=500。而為了在i=1處貯藏500升汽油，卡車至少從i=2處開兩趟滿載油的車至i=1處，所以i=2處至少存貯2×500升汽油，即oil2=500×2=1000，另外再加上從i=1返回至i=2處的一趟空載，合計往返3次，往返路程的耗油量按最省要求只能為500升，即d1，2=500/3，所以dis2=dis1d1，2=dis1500/3。同理，為了在i=2處貯存1000升汽油，卡車至少從i=3處開3趟滿載油的車至i=2處。所以，i=3處至少存貯3×500升汽油，即oil3=500×3=1500，加上i=2至i=3處的2趟返程空車，合計5次，路途耗油量也應(yīng)該是500升，即d2，3=500/5，所以dis3=dis2d2，3=dis2500/5。依次類推，為了在i=處貯藏×500升汽油，卡車至少從i=1處開趟滿載車至i=處，即oil1=1×500=oil500，加上從i=返回i=1的-1趟返程空車，合計2*-1次，總耗油量按最省要求為500升，即d，1=500/2×-1，所以dis1=disd，1=dis500/2×-1。最后一個貯油點的位置如圖94-4所示。最后，i=n至起始點的距離為1000-disn，oiln=500×n。為了在i=n處取得n×500升汽油，卡車至少從始點開n1次滿載車至i=n，加上從i=n返回起始點的n趟返程空車，合計2×n1次，總耗油量應(yīng)正好為1000-disn×2×n1，即起始點藏油為oiln1000-disn×2×n1。參考程序見教材355頁。例5、偶數(shù)個3【問題描述】編程求出所有的n位數(shù)中，有多少個數(shù)中有偶數(shù)個數(shù)字3?！据斎敫袷健恳恍幸粋€正整數(shù)n，0<n<1000。【輸出格式】一行一個正整數(shù)，表示n位數(shù)中有多少個數(shù)有偶數(shù)個3?！据斎霕永?【輸出樣例】73【問題分析】無論一個多位數(shù)中有幾個3，都可以分為奇數(shù)個和偶數(shù)包括0個兩組，在一個多位數(shù)末尾加上一個3，就會改變其奇偶性，加其他數(shù)字都不會改變它的奇偶性。所以，可以1~9這九個一位數(shù)為基礎(chǔ)，采用每次向末尾加一位的方法，逐步構(gòu)造并達到n位數(shù)，來討論它們的奇偶性。設(shè)ai存儲i位數(shù)中3為奇數(shù)的個數(shù)，bi存儲i位數(shù)中3為偶數(shù)的個數(shù)，則很容易推出遞推關(guān)系式：ai=ai-1×9bi-1，bi=bi-1×9ai-1，因為首位不為0，所以邊界條件為：a1=1，b1=8。程序?qū)崿F(xiàn)時，也可以用一個數(shù)組來優(yōu)化。參考程序見教材356頁。例6、新約瑟夫游戲【問題描述】一個皆大歡喜的新游戲：假設(shè)n個人站成一圈，從第1人開始交替的去掉游戲者，但只是暫時去掉（例如，首先去掉2），直到最后剩下唯一的幸存者為止。幸存者選出后，所有比幸存者號碼高的人每人將得到1塊錢，并且永久性地離開，其余剩下的人將重復(fù)以上過程，比幸存者號碼高的人每人將得到1塊錢后離開。一旦經(jīng)過這樣的過程后，人數(shù)不再減少，最后剩下的那些人將得到2塊錢。請計算一下組織者一共要付出多少錢？如圖94-5所示，第一輪有5人，幸存者是3，所以4、5得到1塊錢后離開，下一輪幸存者仍然是3，因此沒有人離開，所以每人得到2塊錢，總共要付出22×3=8塊錢?！据斎敫袷健恳恍幸粋€整數(shù)n，不超過32767?！据敵龈袷健恳恍幸粋€整數(shù)，不超過65535，表示總共要付出多少錢?！据斎霕永?0【輸出樣例】13【問題分析】“約瑟夫”問題有很多種變形，這是其中的一種。首先，每個人都會得到1塊錢，只有最后的那些幸存者多得到了1塊錢。所以，我們只要求出最后會幸存幾個人便行了。假設(shè)經(jīng)過m次出圈操作后還剩finalm個人，此時人數(shù)不再減少了，則問題的解應(yīng)該為：finalmn。如何求finalm呢？顯然，當?shù)趇次的finali=i時，人數(shù)就不會再減少了，此時的i即為m；否則，我們就需要對剩下的finali個人再進行報數(shù)出圈操作。設(shè)josei表示i個人的圈報數(shù)后的幸存者編號，設(shè)報到的人出去，則josei-1可以理解為第一輪第一次報數(shù)，出去后的狀態(tài)。如圖94-6所示左圖，出去后會從1繼續(xù)報數(shù)，此時圈中有i-1個人，從1開始報數(shù)，編號josei為：1，2，…i，1，2，…-1。我們可以人為地把這個圈逆時針轉(zhuǎn)個單位，即變成圖94-6所示右圖的狀態(tài)，此時報數(shù)的編號josei-1：1，2，…i-，i-1，i-2，…i-1。觀察以上兩個序列發(fā)現(xiàn)，除了加邊框的兩個數(shù)據(jù)外，其它所有數(shù)據(jù)都滿足下列規(guī)律：josei=josei-1modi。對這個式子稍做調(diào)整，變成如下公式就都滿足了：josei=josei-11modi1。至此，我們就找到了問題的遞推關(guān)系式，邊界條件也很明顯，就是jose1=1。然后，順推求出每個josei，直到某一次josei=i,則finali賦值為i，否則，finali賦值為finaljosei。參考程序見教材357-358頁。實踐鞏固第5課分治與遞歸學(xué)習(xí)目標1體會分治思想及二分法。2掌握分治與遞歸的關(guān)系及遞歸算法。3熟練應(yīng)用分治與遞歸思想解題，并掌握遞歸算法的常用優(yōu)化手段。1分治“分治”是一種常用的解題策略。它是將一個難以直接解決的大問題，分解成若干規(guī)模較小的、相互獨立的、相同或類似的子問題，分而治之，再合成得到問題的解。根據(jù)“平衡子問題”的思想，一般會把問題分解成兩個規(guī)模相等的子問題，也就是“二分法”，比如經(jīng)典的二分查找（折半查找）問題。例1、找偽幣【問題描述】給出16個一模一樣的硬幣，其中有1個是偽造的，并且那個偽造的硬幣比真的硬幣要輕一些，本題的任務(wù)是找出這個偽造的硬幣。為了完成這一任務(wù)，將提供一臺可用來比較兩組硬幣重量的儀器，利用這臺儀器，可以知道兩組硬幣孰輕孰重。例1、找偽幣【問題分析】方法1、窮舉法依次比較硬幣1與硬幣2、硬幣3和硬幣4、硬幣5和硬幣6……最多通過8次比較來判斷偽幣的存在并找出這個偽幣。方法2、二分法把16個硬幣的情況看成一個大問題。第一步，把這一大問題分成兩個小問題，隨機選擇8個硬幣作為第一組（A組），剩下的8個硬幣作為第二組（B組）。第二步，利用儀器判斷偽幣在A組還是在B組中，如果在A組中，則再把A組中的8個硬幣隨機分成2組，每組4個再去判斷……這樣，只要（必須）4次比較一定能找出偽幣。例1、找偽幣方法3、三分法把16個硬幣分成3組（A組5個、B組5個、C組6個），利用儀器比較A、B兩組，一次就可以判斷出偽幣在A、B、C哪一組中。假如在C組中，則再把C組中的6個分成3組（2個、2個、2個），再用儀器比較一次判斷出在哪一組。然后再比較1次就能判斷出2個硬幣中哪個是偽幣。這樣，只要2~3次比較便能找出偽幣。例1、找偽幣例2、循環(huán)比賽日程表【問題描述】設(shè)有n位選手的循環(huán)比賽，其中n=2m，m為正整數(shù)。要求每位選手要與其他n-1位選手都賽一次。每名選手每天比賽一次，循環(huán)賽共進行n-1天，要求每天沒有選手輪空。圖95-1是8位選手時（m=3）的循環(huán)比賽表，表中第一行為8位選手的編號，下面7行，依次是每位選手每天的對手?！締栴}分析】這是一個“對稱性”的數(shù)字方陣。把方陣一分為四來看，左上角的4×4方陣就是前4位選手的循環(huán)比賽表，而右上角的4×4方陣是后4位選手的循環(huán)比賽表，它們在本質(zhì)上是一樣的，不同的只是選手編號而已，將左上角中方陣的所有元素加上4就能得到右上角的方陣。下方的兩個方陣表示前4位選手和后4位選手進行交叉循環(huán)比賽的情況，同樣具有對稱性，將右上角方陣復(fù)制到左下角即得到1，2，3，4四位選手和5，6，7，8四位選手的循環(huán)比賽表，根據(jù)對稱性，右下角的方陣應(yīng)與左上角的方陣相同。這樣，8位選手的循環(huán)比賽表可以由四名選手的循環(huán)比賽表根據(jù)對稱性“生成”出來。同理，4位選手的循環(huán)比賽表可以由2位選手的循環(huán)比賽表根據(jù)對稱性生成出來。所以，本題的“分治”思想很明顯，即不斷地把一個規(guī)模為n的構(gòu)造問題分成4個規(guī)模為n/2的子問題，然后，從這些子問題的解構(gòu)造出整個問題的解。參考程序見教材364頁。例3、快速排序【問題描述】隨機產(chǎn)生n個int范圍內(nèi)的整數(shù)，從小到大排序后輸出，其中n≤10^6?！締栴}分析】插入排序、選擇排序、冒泡排序等排序算法的時間復(fù)雜度都是On2?？焖倥判蛩惴ㄊ腔谶f歸思想，采用樸素的“劃分”思想將數(shù)據(jù)分類，就像分牌的時候大牌分一堆，小牌分一堆，這樣大問題就轉(zhuǎn)化成了形式相同但是規(guī)模較小的子問題?？焖倥判蛑?，將所有的數(shù)劃分成左邊一堆與右邊一堆，左邊的數(shù)恒小于或等于某個數(shù)，右邊的數(shù)恒大于或等于這個數(shù)，這樣，的位置就固定了，再對左、右兩部分遞歸操作。經(jīng)過實踐檢驗，一般選取n個數(shù)中正中間的那個數(shù)作為，也可以隨機產(chǎn)生一個位置，以這個位置的數(shù)作為?？焖倥判虻臅r間復(fù)雜度為Onlog2n。參考程序見教材365頁。2遞歸以上分治思想在每一步的實現(xiàn)上都分為三個步驟。1）分解。將原問題分解為若干規(guī)模較小、相互獨立、與原問題形式相同或相似的子問題。2）解決。若子問題的規(guī)模已經(jīng)達到邊界或可以直接求值，則返回解；否則，通過遞歸調(diào)用求解各個子問題。3）合并。將各個子問題的解合并為原問題的解。分治法一般采用遞歸算法實現(xiàn)。遞歸算法主要應(yīng)用在三種場合。1）數(shù)據(jù)的定義形式是遞歸的，如求n的階乘、求m和n的最大公約數(shù)等。2）數(shù)據(jù)之間的邏輯關(guān)系是遞歸的，如樹、圖等的定義和操作。3）某些問題的解法就是不斷重復(fù)執(zhí)行一種操作，只是問題規(guī)模由大化小，直至某個基本操作就結(jié)束，如快速排序、十進制轉(zhuǎn)換成二進制、漢諾塔等問題。例4、取模運算【問題描述】定義“取?！边\算：對于正整數(shù)a和p，a%p表示a除以p的余數(shù)，又稱“?！边\算?，F(xiàn)在，輸入三個正整數(shù)b、p、，請編程計算b^p%的值?！据斎敫袷健恳恍腥齻€正整數(shù)，分別表示b、p、的值。其中，b、p、×≤2147483647?！据敵龈袷健恳恍幸粋€整數(shù)，表示b^p%的值?！据斎霕永?109【輸出樣例】7【問題分析】基于數(shù)據(jù)范圍，本題不可能采用暴力計算bp的值再去模。利用分治思想分析指數(shù)運算，可以得到以下遞歸公式：同時，對于模運算有一個重要結(jié)論：A*B%=A%*B%%。這樣，使用“快速冪”的遞歸思想，快速計算bp%的值，同時避免高精度運算。例如，要計算210%9，就先去計算25%9，而這又要先去計算21%9和24%9，而21%9=2。算法的時間復(fù)雜度為O（log2p）。參考程序見教材366-367頁。例5、地毯填補【問題描述】相傳在一個古老的阿拉伯國家有一座宮殿，宮殿里有個四四方方的格子迷宮。國王選駙馬的方法非常特殊，也非常簡單：公主就站在其中一個方格子上，只要誰能用地毯將除公主所站立的格子之外的所有地方蓋上，就可以娶到美麗漂亮的公主。毯子的形狀只有如圖95-2所示的4種，并且每一方格只能用一層地毯，格子迷宮的大小為2的正方形?！据斎敫袷健康?行1個正整數(shù)，1≤≤10；第2行2個整數(shù)和y，表示公主所在方格的坐標（為行坐標，y為列坐標），和y之間有一個空格?！据敵龈袷健枯敵鰧⒚詫m填補完整的方案。每一補（行）為yc，其中和y為毯子拐角的行坐標和列坐標，c為所使用毯子的形狀，具體標號如圖95-2所示，毯子形狀分別用1、2、3、4表示，、y、c之間用一個空格隔開。【輸入樣例】333【輸出樣例】551224114143412441273154183363481722514632812841771661583852881【問題分析】分析問題明顯有一種遞歸重復(fù)的感覺。首先，對最簡單的情況（即=1）進行分析，公主只會在4個方格中的一個：如果在左上角，則使用3號毯子補，毯子拐角坐標位于（2，2）；如果在左下角，則使用2號毯子補，毯子拐角坐標位于（1，2）；如果在右上角，則使用1號毯子補，毯子拐角坐標位于（2，1）；如果在右下角，則使用4號毯子補，毯子拐角坐標位于（1，1）。對于=2，如圖95-3所示。假設(shè)公主所在的位置在（1，4），用實心圓表示，那么，可以把1號毯子拐角放在（2，3）處，用“”表示，這樣就將（1，3）~（2，4）的2×2方格全部覆蓋了。再考慮如何把3個2×2的方格全部覆蓋。這樣，問題就歸結(jié)為=1的情況了，但是有一點不同的是：沒有“公主”了，每一個=1的小方格都會留下一個空白，即圖中的空心圓，而且正好3個，組合后正好又是一個地毯形狀。用分治法來求解本題：對于任意>1的宮殿，將其分解成4個/2大小的宮殿，先看一下公主站的位置是屬于哪一塊，因為根據(jù)公主所在的位置，我們可以確定中間位置所放的毯子類型，再遞歸處理公主所站的那一塊，直到出現(xiàn)邊界條件=1的情況，然后在公主邊上鋪上一塊合適的地毯，遞歸結(jié)束。參考程序見教材368-370頁。3分治與遞歸的應(yīng)用舉例分治與遞歸的思想簡單易懂，但是如果采用直接遞歸來實現(xiàn)，存在著大量“冗余”計算，效率比較低。一般可以采用以下幾種思路進行優(yōu)化，一是將遞歸公式轉(zhuǎn)化成遞推算法實現(xiàn)；二是采用所謂的“記憶化”方法，設(shè)置一個數(shù)組f記錄每一項的值，第一次計算出第i項的值f（i），就同時存儲到數(shù)組f［i］中，避免以后再次遞歸調(diào)用f（i），從而減少冗余計算；三是定義一個手工棧保存和恢復(fù)遞歸過程中的現(xiàn)場信息，模擬遞歸調(diào)用，其缺點是減低了程序的可讀性。例6、平面分割【問題描述】平面上有n條封閉曲線，其中任何兩條封閉曲線恰好相交于兩點，且任何三條封閉曲線不相交于同一點，計算這些封閉曲線把平面分割成的區(qū)域個數(shù)。【輸入樣例】3【輸出樣例】8【問題分析】設(shè)fn為n條封閉曲線把平面分割成的區(qū)域個數(shù)。如圖95-4所示，f1=2，f2=4，f3=8，F(xiàn)4=14，f5數(shù)起來比較困難，但是也能數(shù)得出f5=22。找規(guī)律發(fā)現(xiàn)，f2-f1=2，f3-f2=4，f4–f3=6，f5-f4=8……猜想結(jié)論：fn-fn-1=2n-1，即遞歸公式為fn=fn-12n-1，邊界條件為f1=2?？梢院唵巫C明以上猜想：當平面上已有n-1條封閉曲線將平面分割成f（n-1）個區(qū)域后，第n條封閉曲線每與曲線相交一次，就會增加2個區(qū)域，因為平面上已有了n-1條封閉曲線，且第n條曲線與已有的每一條封閉曲線恰好相交于兩點，且不會與任何兩條曲線交于同一點，故平面上一共增加2（n-1）個區(qū)域，加上已有的f（n-1）個區(qū)域，一共有f（n-1）2（n-1）個區(qū)域。如果不滿足于以上遞推算法，可以進一步推出其“通項公式”：f（n）=f（n-1）2（n-1）f（n-1）=f（n-2）2（n-2）f（n-2）=f（n-3）2（n-3）……f（2）=f（1）2把以上n-1個等式的左邊和右邊分別累加，再約去相同項，得到：f（n）=f（1）2×（123…（n-1））=n^2-n2。參考程序見教材371頁。例7、斐波那契數(shù)列【問題描述】輸入n，1≤n≤1000，輸出斐波那契數(shù)列第n項模9997的值?！据斎霕永?0【輸出樣例】55【問題分析】直接遞歸求解存在著大量的冗余計算，利用數(shù)學(xué)知識可以計算出時間復(fù)雜度為O1sqrt5/2^n，顯然超時嚴重。因此，可以采用“記憶化”的方法進行算法優(yōu)化。//esain{ freopen““,“r“,stdin; freopen““,“w“,stdout; cin>>n; forinti=1;i<=n;ia=-1; cout<<fn<<endl; return0;}例8、砍伐樹木【問題描述】小華被大林叫去砍樹，他需要砍倒m米長的木材?，F(xiàn)在，小華弄到了一個奇怪的伐木機。伐木機工作過程如下：小華設(shè)置一個高度參數(shù)h（米），伐木機升起一個巨大的鋸片到高度h，并鋸掉所有的樹比h高的部分（當然，樹木不高于h米的部分保持不變）。小華就得到樹木被鋸下的部分。例如，如果一行樹的高度分別為20、15、10和17米，小華把鋸片升到15米的高度，切割后樹木剩下的高度將是15、15、10和15米，而小華將從第1棵樹得到5米，從第4棵樹得到2米，共得到7米木材。小華非常關(guān)注生態(tài)保護，所以他不會砍掉過多的木材。這正是他為什么要盡可能高地設(shè)定伐木機鋸片的原因。幫助小華找到伐木機鋸片的最大的整數(shù)高度h，使得他能得到的木材至少為m米。換句話說，如果再升高1米，則他將得不到m米木材?！据斎敫袷健康?行2個整數(shù)n和m，n表示樹木的數(shù)量，m表示需要的木材總長度。第2行n個整數(shù)，表示每棵樹的高度，值均不超過109。保證所有木材長度之和大于m，因此必然有解。【輸出格式】一行一個整數(shù)，表示砍樹的最高高度?！据斎霕永?20442402646【輸出樣例】36【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)滿足：1≤n≤10，1≤m≤30。對于70%的數(shù)據(jù)滿足：1≤n≤103，1≤m≤104。對于100%的數(shù)據(jù)滿足：1≤n≤106，1≤m≤2×109?！締栴}分析】分析題意，如果砍樹的高度是一行樹中最高一棵的高度，則砍下的木材的長度為0。而如果砍樹的高度為0，即地面的高度，則將砍下所有的樹木，由題意可知，這個值一定大于m。那么，我們逐步升高砍樹的高度h，顯然，砍下的木材數(shù)量會反過來逐漸減少。變化的規(guī)律是：h在“單調(diào)”上升時，砍下的木材數(shù)量“單調(diào)”下降。這樣，當h上升到某個確定的高度時，砍下的木材數(shù)量將少于需要的值m，我們說，這個高度減一的位置就是所求。由于砍樹的高度和砍下的木材總量的變化都是單調(diào)的，可以用“二分答案”的方法去快速地確定這個最高的砍樹高度。二分區(qū)間的左端點low設(shè)為0，右端點high設(shè)為最高一棵樹的高度，區(qū)間中點mid=（lowhigh1）/2，然后以mid作為砍樹的高度，線性掃描n棵樹，計算出砍下的木材總量sum。如果sum大于或等于m，則將區(qū)間左端點更新為mid，因為還可以繼續(xù)嘗試一個更高的砍樹高度。如果sum小于m，則說明mid不符合要求，需要減小砍樹高度，于是把區(qū)間右端點更新為mid-1。當左右區(qū)間重合時，查找結(jié)束。由于每次保證了區(qū)間左端點都符合要求，因此返回low作為問題的答案。算法的時間復(fù)雜度為O（nlog2（ma（h））），空間復(fù)雜度為O（n）。參考程序見教材373-374頁。本題另一個想法是先對n棵樹從低到高排序。然后從高向低掃描，每當相鄰兩棵樹有高度差時，以低的那棵樹的高度作為砍樹高度。我們維護這個砍下的木材數(shù)量之和以及前一次砍樹高度這兩個值。每一次砍樹后新增的木材數(shù)量是前后兩次砍樹的高度差乘以當前這棵樹之后的樹木的棵數(shù)。這樣在不斷掃描的過程中，砍樹高度會逐漸降低，而砍下的木材總量會逐漸增加。一旦在某個高度時，砍下的木材總量超過m，則經(jīng)過數(shù)學(xué)計算可以知道應(yīng)該升高多少高度，使得對于這最后一次的砍樹高度，滿足“砍樹高度盡可能高”的要求。這個算法的時間復(fù)雜度為O（nlog2n），空間復(fù)雜度為O（n）。參考程序見教材374頁。實踐鞏固第6課貪心學(xué)習(xí)目標1體會貪心法的基本思想。2初步了解貪心法正確性的證明方法。3熟練應(yīng)用貪心法求解一些實際問題。貪心法實際生活中，經(jīng)常需要求一些問題的“可行解”和“最優(yōu)解”，這就是所謂的“最優(yōu)化”問題。一般來說，每個最優(yōu)化問題都包含一組“限制條件”和一個“目標函數(shù)”，符合限制條件的問題求解方案稱為可行解，使目標函數(shù)取得最佳值（最大或最小）的可行解稱為最優(yōu)解。求解最優(yōu)化問題的算法很多，例如窮舉、搜索、動態(tài)規(guī)劃等。貪心法也是求解這類問題的一種常用方法。1貪心法的基本思想貪心法是從問題的某個初始解出發(fā)，采用逐步構(gòu)造最優(yōu)解的方法，向給定的目標前進。在每一個局部階段，都做一個“看上去”最優(yōu)的決策，并期望通過每一次所做的局部最優(yōu)選擇產(chǎn)生出一個全局最優(yōu)解。做出貪心決策的依據(jù)稱為“貪心策略”。要注意的是，貪心策略一旦做出，就不可再更改。與遞推不同的是，貪心嚴格意義上說只是一種策略或方法，而不是算法。推進的每一步不是依據(jù)某一個固定的遞推式，而是做一個當時“看似最佳”的貪心選擇（操作），不斷將問題歸納為更小的相似子問題。所以，歸納、分析、選擇正確合適的貪心策略，是解決貪心問題的關(guān)鍵。例1、獨木舟【問題描述】旅行社計劃組織一個獨木舟旅行。租用的獨木舟都是一樣的，最多乘兩人，而且載重有一個限度?，F(xiàn)在要節(jié)約費用，所以要盡可能地租用最少的舟。本題的任務(wù)是讀入獨木舟的載重量，參加旅行的人數(shù)以及每個人的體重，計算出所需要的獨木舟數(shù)目?！据斎敫袷健康?行是w（80≤w≤200），表示每條獨木舟最大的載重量。第2行是正整數(shù)n（1≤n≤30000），表示參加旅行的人數(shù)。接下來的n行，每行是一個正整數(shù)ti（5≤ti≤w），表示每個人的重量?！据敵龈袷健枯敵鲆恍幸粋€數(shù)，表示最少的獨木舟數(shù)目。【輸入樣例】1009902020305060708090【輸出樣例】6【問題分析】先將n個人按照體重t從大到小排序。對于每個人j，j從1開始，如果前面已租的獨木舟無法承載他，那么就重新租一個。只要設(shè)置一個數(shù)組ship，下標i從0開始，ship表示第i個獨木舟還可以承載多重，初始值全部設(shè)置為w，此時i加1，ship；如果前面有多個獨木舟可以承載他（某個ship），那么選擇其中ship設(shè)置成0。最后，只要輸出i即可。參考程序見教材381-382頁。例2、刪數(shù)【問題描述】輸入一個高精度的正整數(shù)n（長度小于或等于240位），去掉其中任意s個數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的n和s，尋找一種方案，使得剩下的數(shù)字組成的新數(shù)最小?！据斎敫袷健枯斎雰尚?，第1行為1個正整數(shù)n，第2行為1個整數(shù)s?！据敵龈袷健枯敵鲆恍幸粋€數(shù)，表示最后剩下的最小數(shù)?！据斎霕永?785434【輸出樣例】13【問題分析】為了盡可能逼近目標，選取的貪心策略為：每一步總是選擇一個使剩下的數(shù)最小的數(shù)字刪去，即按高位到低位的順序搜索，若各位數(shù)字遞增，則刪除最后一個數(shù)字；否則，刪除第一個遞減區(qū)間的首字符，這樣刪一位便形成了一個新數(shù)字串。然后回到數(shù)字串首，按上述規(guī)則再刪下一個數(shù)字。重復(fù)以上過程s次為止，剩下的數(shù)字串便是問題的解。參考程序見教材383頁。2貪心法的正確性證明對于一個問題，如果想用貪心法求解，首先要想到基于某種“序”或者“規(guī)則”的貪心策略。其次還要能證明其正確性。要嚴格證明一個貪心算法的正確性是很困難的，目前最有效的一種方法叫“矩陣胚理論”，但是很復(fù)雜。信息學(xué)競賽中常用的貪心證明方法，一般有反證法、構(gòu)造法、調(diào)整法。其實，即使一個貪心算法是不完全正確的，也可以努力尋找一些調(diào)整方法，或制定多種貪心策略，通過調(diào)整優(yōu)化、比較擇優(yōu)來爭取得到最優(yōu)解，甚至也可以先得到一個“較優(yōu)”解，然后，在此基礎(chǔ)上進行搜索剪枝或分支定界。例3、石子合并【問題描述】在一個圓形操場的四周擺放了n堆石子（n≤100），現(xiàn)要將石子有次序地合并成一堆。規(guī)定每次只能選相鄰的兩堆合并成新的一堆，并將新的一堆的石子數(shù)記為該次合并的得分。編程，讀入堆數(shù)n及每堆石子數(shù)（≤20），選擇一種合并石子的方案，使得做n-1次合并，得分的總和最??；選擇一種合并石子的方案，使得做n-1次合并，得分的總和最大。例如，如圖96-1所示的4堆石子，每堆石子數(shù)（從最上面的一堆開始按順時針方向數(shù)）依次為4、5、9、4，則3次合并得分總和最小的方案如圖96-2所示，得分總和最大的方案如圖96-3所示。【輸入格式】第1行為石子堆數(shù)n，第2行為每堆石子數(shù)，每兩個數(shù)之間用一個空格分隔?！据敵龈袷健康?行為最小得分值，第2行為最大得分值?！据斎霕永?4594【輸出樣例】4354【問題分析】看到樣例，很容易會想出一個貪心策略——每次選相鄰和最?。ù螅┑膬啥咽雍喜ⅰ５?，如圖96-4就是一個反例。其實，本題由于限定只能是“相鄰”的兩堆石子合并，并不能套用經(jīng)典的“哈夫曼樹”算法。題目所給樣例數(shù)據(jù)實際上是一個“陷阱”，造成了應(yīng)用貪心法即可解決的假象。正確的做法是“破環(huán)為鏈”，再做動態(tài)規(guī)劃（略）。所以，當一個貪心算法不能確定其100%正確，使用之前就應(yīng)該嘗試證明它的不正確性。而要證明其不正確，一種最簡單的方法就是舉一個反例。（1）反證法用貪心的策略，依次構(gòu)造出一個解S1，假設(shè)最優(yōu)解S2不同于S1，可以證明是矛盾的，從而得出S1就是最優(yōu)解。例4、最大整數(shù)【問題描述】設(shè)有n（n≤20）個正整數(shù)（小于或等于2147483647），將它們連接成一排，組成一個最大的多位整數(shù)。例如n=3，3個整數(shù)為13、312和343，連接成的最大整數(shù)為34331213?！据斎敫袷健康?行1個整數(shù)n。第2行為n個正整數(shù)，每兩個數(shù)之間用一個空格隔開。【輸出格式】一行一個數(shù)，表示連接成的最大整數(shù)。【輸入樣例】47134246【輸出樣例】7424613【問題分析】首先，自然會想到大的字符串應(yīng)該排在前面，因為如果A與B是兩個由數(shù)字字符構(gòu)成的字符串，且A>B，一般情況下有AB>BA。但是，當A=BC時，按字符串的大小定義有A>B，此時有可能出現(xiàn)AB<BA的情況。如A=‘121’，B=‘12’，則AB=‘12112’，BA=‘12121’，所以AB<BA。為了解決這個問題，根據(jù)題意引進另一種字符串比較辦法，將AB與BA相比較，如果前者大于后者，則認為A>B。按這一定義將所有的數(shù)字字符串從大到小排序后連接起來所得到的數(shù)字字符串即是問題的解。排序時先將所有字符串中的最大值選出來存在數(shù)組的第一個元素中，再從第二至最后一個元素中最大的字符串選出來存在數(shù)組的第二個元素中，直到從最后兩個元素中選出最大的字符串存在數(shù)組的倒數(shù)第二個元素中為止。需要說明的是，按本題定義的字符串的大小定義是有序的，即如果AB≥BA，BC≥CB，則一定有AC≥CA。證明方法如下：引理：記nA為n個字符串A按字符串加法運算規(guī)則相加之和，則由AB≥BA可推導(dǎo)出nAmB≥mBnA，其中m，n為任意的自然數(shù)。用反證法可證明反過來也成立。設(shè)la為字符串A的長度，lb為字符串B的長度，lc為字符串C的長度，再設(shè)n=lb*lc，m=la*lc，=la*lb，則nA，mB，C三個字符串等長，根據(jù)引理有：nAmB≥mBnA，mBC≥CmB，從而得到nA≥mB≥C，所以nAC≥CnA，AC≥CA。要使n個字符串拼接起來后得到一個最大的字符串和式，則一定要將按上述定義最大的字符串放在第一個，否則必可通過將最大的字符串與它左側(cè)的字符串交換得到更大的字符串和式。參考程序見教材386頁。（2）構(gòu)造法根據(jù)描述的算法，用貪心的策略依次構(gòu)造出一個解，可證明一定是合法的解。即用貪心法找可行解。例5、取火柴游戲【問題描述】輸入及個整數(shù)n1，n2，…，n，表示有堆火柴棒，第i堆火柴棒的根數(shù)為ni。接著便是和計算機對弈游戲，取火柴的規(guī)則如下：每次可以從一堆中取走若干根火柴，也可以將一堆全部取走，但不允許跨堆取，也不允許不取。誰取走最后一根火柴算誰勝利。例如，=2，n1=n2=2，A代表你，P代表計算機，若決定A先取：A：（2，2）→（1，2）//從一堆中取一根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勝利又如=3，n1=1，n2=2，n3=3，A決定后?。篜：（1，2，3）→（0，2，3）A：（0，2，3）→（0，2，2）A已將游戲歸結(jié)為（2，2）的情況，不管P如何取A都必勝。【輸入樣例】3369【輸出樣例】43//表示第1次從第3堆取4個出來必勝365//第1次取后的狀態(tài)【輸入樣例】415221910【輸出樣例】lose//先取必敗【問題分析】具體分析和程序見教材388-389頁。（3）調(diào)整法用貪心的策略，依次構(gòu)造出一個解S1。假設(shè)最優(yōu)解S2不同于S1，找出不同之處，在不破壞最優(yōu)性的前提下，逐步調(diào)整S2，最終使其變?yōu)镾1，從而S1也是最優(yōu)解。例6、排隊接水【問題描述】有n個人在一個水龍頭前排隊接水，假如每個人接水的時間為Ti，請編程找出一種這n個人排隊的順序，使得n個人的平均等待時間最小。【輸入格式】第1行為一個整數(shù)n；第2行分別表示每人的接水時間T1，T2，…，Tn，每兩個數(shù)據(jù)之間有1個空格?！据敵龈袷健康?行為一種排隊順序，即1~n的一種排列，每兩個數(shù)據(jù)之間有1個空格。第2行為這種排列方案下的平均等待時間（輸出結(jié)果精確到小數(shù)點后兩位）?！据斎霕永?056121991000234335599812【輸出樣例】3278149610529190【問題分析】具體分析和程序見教材390-391頁。3貪心的應(yīng)用舉例例7、餐巾具體見教材391-395頁。例8、大神排隊具體見教材395-396頁。例9、最大的子序列和具體見教材396-398頁。實踐鞏固第7課窮舉學(xué)習(xí)目標1熟練應(yīng)用窮舉算法解決一些實際問題。2掌握窮舉算法的常用優(yōu)化方法。3體會二進制窮舉思想及其應(yīng)用。窮舉計算機的特點之一就是運算速度快，善于重復(fù)做一件事?！案F舉”正是基于這一特點的最古老的算法。它一般是在一時找不出解決問題的更好途徑，即從數(shù)學(xué)上找不到求解的公式或規(guī)則時，根據(jù)問題中的“約束條件”，將解的所有可能情況一一列舉出來，然后再逐個驗證是否符合整個問題的求解要求，從而求得問題的可行解或者最優(yōu)解。1窮舉算法的應(yīng)用舉例例1、樓層編號【問題描述】小林在NOI層的房間，并且當天高能數(shù)字是t，現(xiàn)在他想知道房間所在的真實樓層是多少?！据斎敫袷健恳恍袃蓚€整數(shù)m和t，1≤m≤100000，0≤t≤9，保證m對t合法?！据敵龈袷健恳恍幸粋€整數(shù)，表示真實樓層。【輸入樣例】143【輸出樣例】12【問題分析】根據(jù)題意，只要從1~m窮舉樓層編號，將所有含高能數(shù)字t的樓層計數(shù)存儲在ans中，最后的答案就是m-ans。參考程序見教材405頁。例2、火柴棒等式【問題描述】給出n根火柴棒，可以拼出多少個形如“AB=C”的等式？等式中的A、B、C是用火柴棒拼出的整數(shù)（若該數(shù)非零，則最高位不能是0）。用火柴棒拼數(shù)字0~9的拼法如圖97-1所示。需要注意以下幾點：（1）加號與等號各自需要兩根火柴棒。（2）如果A≠B，則AB=C與BA=C視為不同的等式（A、B、C均大于或等于0）。（3）n根火柴棒必須全部用上（n≤24）?！据斎霕永?4【輸出樣例】2【樣例說明】兩個等式分別為：01=1和10=1?！締栴}分析】首先，預(yù)處理每個數(shù)字（0~9）需要用幾根火柴棒，存儲在數(shù)組f中。然后，窮舉a和b，算出它們的和c，再判斷下列約束條件是否成立：f（a）f（b）f（c）=n-4?，F(xiàn)在的問題是：a和b的范圍有多大？可以發(fā)現(xiàn)盡量用數(shù)字1拼成的數(shù)比較大，分析可知最多不會超過1111。程序?qū)崿F(xiàn)時，分別用三個循環(huán)語句預(yù)處理好所有兩位數(shù)、三位數(shù)、四位數(shù)構(gòu)成所需要的火柴棒數(shù)量。參考程序見教材406頁。例3、比例簡化【問題描述】在社交媒體上，經(jīng)常會看到針對某一個觀點同意與否的民意調(diào)查以及結(jié)果。例如，對某觀點表示支持的有1498人，反對的有902人，那么其比例可以簡單地記為1498∶902。因該比例的數(shù)值太大，難以一眼看出它們的關(guān)系。若把比例記為5∶3，雖然與真實結(jié)果有一定的誤差，但依然能夠較為準確地反映調(diào)查結(jié)果，同時也顯得比較直觀?，F(xiàn)給出支持人數(shù)A和反對人數(shù)B，以及一個上限L，請將A比B化簡為A′比B′，要求在A′和B′均不大于L，且A′和B′互質(zhì)（兩個整數(shù)的最大公約數(shù)為1）的前提下，A′/B′≥A/B且A′/B′-A/B的值盡可能小?！据斎敫袷健恳恍腥齻€整數(shù)A，B，L，每兩個整數(shù)之間用一個空格隔開，分別表示支持人數(shù)、反對人數(shù)以及上限?！据敵龈袷健恳恍袃蓚€整數(shù)A′和B′，中間用一個空格隔開，表示化簡后的比例?！据斎霕永?49890210【輸出樣例】53【數(shù)據(jù)規(guī)模】對于100%的數(shù)據(jù)滿足：1≤A≤106，1≤B≤106，1≤L≤100，A/B≤L。【問題分析】首先，答案為一個分數(shù)，而且分子，分母都小于或等于L。所以，可以直接窮舉分子i（對應(yīng)題目中的A′）和分母j（對應(yīng)題目中的B′）。結(jié)合題目的具體要求分析：（1）i，j≤L，這個可以作為窮舉的范圍。（2）i/j≥A/B，且i/j-A/B的值盡量小。前者只要轉(zhuǎn)換成i*B≥j*A，后者可以“打擂臺”實現(xiàn)。假設(shè)用1/2表示最后的答案，初值設(shè)置為1000000/1，min=abs（1*B-2*A）。如果abs（i/j-A/B）<abs（1/2-A/B），即如果abs（i*B-j*A）<abs（1*B-2*A），則更新1、2和min。（3）答案的分子、分母要互質(zhì)，這個只要從小到大窮舉i、從大到小窮舉j，第一個符合條件的答案肯定就是最簡分數(shù)。假設(shè)L=10，如果先窮舉到1/5得到一個答案，后面的2/10是不會更新答案的。參考程序見教材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?！据斎敫袷健康?行為1個整數(shù)N。第2行為N個字符的字符串，每個字符是一個C、O或W?！据敵龈袷健枯敵鯟OW作為輸入字符串的字串出現(xiàn)的次數(shù)（不一定是連續(xù)的）。提示：答案會很大，建議用64位整數(shù)（longlong）?！据斎霕永?COOWWW【輸出樣例】6【數(shù)據(jù)規(guī)模】對于50%的數(shù)據(jù)滿足：N≤60。對于100%的數(shù)據(jù)滿足：N≤105?！締栴}分析】因為只有3個字母，所以可以窮舉字符串中的每一個“O”，假設(shè)位置i，然后分別計算其左邊“C”的個數(shù)l，再利用乘法原理進行計數(shù)l，每次把答案累加到ans中。參考程序見教材409頁。2窮舉算法的優(yōu)化窮舉算法的特點是算法設(shè)計、實現(xiàn)都相對簡單，但時間復(fù)雜度和空間復(fù)雜度往往較大。因此，用窮舉算法解決問題時，往往需要盡量優(yōu)化算法，從而減少窮舉的次數(shù)，提高窮舉的效率。窮舉算法優(yōu)化的思路主要有結(jié)合約束條件，通過數(shù)學(xué)推導(dǎo)，減少窮舉的范圍和數(shù)量；通過預(yù)處理（如部分和、是否素數(shù)等），以空間換時間，避免在窮舉過程中重復(fù)計算或判斷等。例5、三角形個數(shù)【問題描述】輸入一根木棒的長度n，1≤n≤10000，將該木棒分成三段，每段的長度為正整數(shù)，輸出由該三段小木棒組成的不一樣的三角形個數(shù)?！据斎霕永?0【輸出樣例】2【樣例說明】兩個能組成的三角形邊長分別為2、4、4和3、3、4?！締栴}分析】窮舉三角形三條邊長（假設(shè)為a、b、c）的可能值，判斷能否構(gòu)成一個三角形，若能則計數(shù)，最后輸出計數(shù)器的值。為了保證組成的三角形不重復(fù)，只要在窮舉時設(shè)定1≤a≤b≤c≤n-2。優(yōu)化思想很簡單但很重要，“能算不舉”，窮舉兩條邊，根據(jù)木棒長度直接計算出第三條邊長。參考程序見教材410頁。例6、阿姆斯特朗數(shù)【問題描述】編程找出所有的三位數(shù)到七位數(shù)中的阿姆斯特朗數(shù)。阿姆斯特朗數(shù)也叫水仙花數(shù)，它的定義如下：若一個n位自然數(shù)的各位數(shù)字的n次方之和等于它本身，則稱這個自然數(shù)為阿姆斯特朗數(shù)。例如，153（153=1×1×13×3×35×5×5）是一個三位的阿姆斯特朗數(shù)，8208則是一個四位的阿姆斯特朗數(shù)?！締栴}分析】由于阿姆斯特朗數(shù)是沒有規(guī)律的，只能采用窮舉法一一驗證100~9999999內(nèi)的所有數(shù)是否是阿姆斯特朗數(shù)，若是，則打印之。但是，如果對任意一個數(shù)，都去求它的各位的若干次方，再求和判斷是否等于，效率比較差。注意到，每個位只可能是0~9，而且只會算到3~7次方。所以，為了使得程序盡快運行出正確結(jié)果，采用“以空間換時間”的策略，使用一個數(shù)組p預(yù)處理出所有數(shù)字的各次冪之值，p表示i的j次方。另外，為了避免每次都對一個數(shù)進行逐位分解操作，直接用數(shù)組a存儲一個數(shù)的每一位，窮舉100~9999999。參考程序見教材411頁。例7、金幣【問題描述】國王將金幣作為工資，發(fā)放給忠誠的騎士。第一天，騎士收到一枚金幣；之后兩天（第二天和第三天）里，每天收到兩枚金幣；之后三天（第四、五、六天）里，每天收到三枚金幣；之后四天（第七、八、九、十天）里，每天收到四枚金幣……這種工資發(fā)放模式會一直這樣延續(xù)下去。當連續(xù)n天每天收到n枚金幣后，騎士會在之后的連續(xù)n1天里，每天收到n1枚金幣（n為正整數(shù)）。請編程確定從第一天開始的給定天數(shù)內(nèi)，騎士一共獲得了多少金幣?！据斎敫袷健枯斎氚辽僖恍校欢嘤?000行。除最后一行外，輸入的每行是一組輸入數(shù)據(jù)，包含一個正整數(shù)n，表示天數(shù)。輸入的最后一行為0，表示輸入結(jié)束?！据敵龈袷健繉γ總€數(shù)據(jù)輸出一行一個整數(shù)，表示該數(shù)據(jù)對應(yīng)總金幣數(shù)?！据斎霕永?06711151610010000100021220【輸出樣例】301418355561945942820298209198【數(shù)據(jù)規(guī)?！繉τ?0%的數(shù)據(jù)滿足：n≤103；對于80%的數(shù)據(jù)滿足：n≤106；對于100%的數(shù)據(jù)滿足：n≤1012?！締栴}分析】每次窮舉每天獲得的金幣數(shù)，或者將答案保存在數(shù)組中直接輸出，可以獲得部分分。下面利用數(shù)學(xué)推導(dǎo)進行優(yōu)化。因為：122232…2=×（1）×（21）/6，假設(shè)前n個數(shù)為1，2，2，3，3，3，…，，，，，如何求呢？根據(jù)123…=n，即2-2n=0，把看成未知數(shù)，解方程可求出=（-1sqrt（18n））/2=sqrt（2n025）-05，另一個負數(shù)解不合法舍去。參考程序見教材413頁。3二進制窮舉思想對于二進制數(shù)00000，00001，00010，…，11111，它們是嚴格遞增有序的，如何生成類似的二進制數(shù)字序列，就是“二進制窮舉”思想，其應(yīng)用非常廣泛?！岸M制窮舉”的實現(xiàn)代碼如下:3二進制窮舉思想include<cstdio>usingnamesain{ intn; intb; scanf“%d”,n; forinti=0;i<=n;ib==0{ forinti=1;i<=n;iprintf“%d”,b; printf“\n”; intj=n; whileb; forinti=j1;i<=n;ib=0; } return0;}例8、0-1背包問題【問題描述】有n件物品，每件物品有一個重量和一個價值，分別記為W1，W2，…，Wn和C1，C2，…，Cn。現(xiàn)在有一個背包，其容量為W，要從n件物品種任取若干件，要求：（1）重量之和小于或等于W。（2）價值之和最大?！据斎敫袷健康?行2個整數(shù)，表示n和W，1≤n≤20，1≤W≤106。第2行n個整數(shù)，表示每一個物品的重量，1≤Wi≤104。第3行n個整數(shù)，表示每一個物品的價值，1≤Ci≤108。【輸出格式】一行一個數(shù)，表示符合背包容量的最大價值。【輸入樣例】820079588611286215688314547972524862【輸出樣例】334【問題分析】背包問題有很多類型，本題是最簡單的一種模型“0-1背包”，即每件物品只有不取和取兩種情況，對應(yīng)著二進制中的0和1。0-1背包有多種解決算法，具體在第13課詳細講解。這里采用二進制窮舉思想，從000…00窮舉到111…11，即定義一個數(shù)組b，元素b=0或者1，表示第i件物品不取或者取，每次判斷背包能否裝的下，同時對于價值打擂臺取最大值。參考程序見教材414-415頁。例9、組合數(shù)的生成【問題描述】從1、2、3、4、5、6這6個數(shù)字中任取4個數(shù)的組合有1234、1235、1236、1245、1246、1256、1345、1346、1356、1456、2345、2346、2356、2456、3456，共15種。若把它們看成4位數(shù)，發(fā)現(xiàn)是遞增的。編程，輸入n和r，1≤r≤n≤20，按照以上順序，輸出從n個數(shù)字（1~n）中任取r個數(shù)的所有組合?！据斎霕永?2【輸出樣例】121323【問題分析】觀察第一個數(shù)到最后一個數(shù)的變化規(guī)律，可以看出最后一位先變化（加1），變到n就要“進位”到上一位；對于倒數(shù)第二位，變化到n-1就要產(chǎn)生“進位”……每次“進位”后，本位及以后的所有位都要重新置成一個遞增的序列。這個算法的思路就是二進制窮舉思想，不過不是固定的“n進制”。參考程序見教材415-416頁。實踐鞏固第8課算法評價學(xué)習(xí)目標1學(xué)會從時間復(fù)雜度、空間復(fù)雜度等方面評價一個算法。2體會一題多解，學(xué)會對不同解題算法進行對比分析。3能根據(jù)題目的時間、