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

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