算法與復(fù)雜性AlgorithmsandComplexity劉杰南華大學(xué)計(jì)算機(jī)學(xué)院軟件工程系算法與復(fù)雜性AlgorithmsandComplexit課程簡介1．課程學(xué)時(shí)總學(xué)時(shí)：48學(xué)時(shí)（理論）2．課程主要內(nèi)容介紹算法的概念及算法分析的基礎(chǔ)知識(shí)；介紹一些經(jīng)典算法*蠻力法分治法貪心法動(dòng)態(tài)規(guī)劃回溯法分支限界法

NP完全問題

*算法賞析課程簡介3．考核方法－－考查

課堂表現(xiàn)、考勤、實(shí)驗(yàn)（占60％）期末考查（小組答辯，占40％）

4．本課程主要參考書[1]王曉東編著，計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)，電子工業(yè)出版社，2012[2]屈婉玲等，算法設(shè)計(jì)與分析，清華大學(xué)出版社，2011劉汝佳——“白皮書”、“黑寶書”……5．網(wǎng)上學(xué)習(xí)（百度&CSDN）3．考核方法－－考查作業(yè)提交算法設(shè)計(jì)實(shí)現(xiàn)類的作業(yè)網(wǎng)址：:9988/（南華OJ）登陸賬號(hào)：學(xué)號(hào)（如：20134330101）密碼：學(xué)號(hào)后面的6位數(shù)字（以上面賬號(hào)為例，則密碼為330101）注意：已注冊(cè)過的同學(xué)提交本課程作業(yè)請(qǐng)用新賬號(hào)和口令。課程PPT和參考資料、其他作業(yè)（報(bào)告）9:9988/sc8/（南華大學(xué)數(shù)字化教學(xué)中心）計(jì)算機(jī)：WSTD-6758

軟件2班：UFSM-0601軟件3班：KQEQ-5247

物聯(lián)網(wǎng)：PPKL-3080船本軟件：PWAH-5676

船本計(jì)算機(jī)：VPKW-5550作業(yè)提交算法設(shè)計(jì)實(shí)現(xiàn)類的作業(yè)課程PPT和參考資料、其他作業(yè)（從經(jīng)典的IBM面試題說起村子中有50個(gè)人，每人有一條狗。在這50條狗中有病狗（這種病不會(huì)傳染）。于是人們就要找出病狗。每個(gè)人可以觀察其他的49條狗，以判斷它們是否生病（如果有病一定能看出來），只是自己的狗不能看。觀察后得到的結(jié)果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要槍斃自己的狗（發(fā)現(xiàn)后必須在一天內(nèi)槍斃），而且每個(gè)人只有權(quán)利槍斃自己的狗，沒有權(quán)利打死其他人的狗。第一天大家全看完了，但槍沒有響，第二天仍沒有槍響。到了第三天傳來一陣槍聲，問村里共有幾條病狗，如何推算得出？從經(jīng)典的IBM面試題說起村子中有50個(gè)人，每人有一條狗。在這Brainstorm騰訊面試題：給你10分鐘時(shí)間，根據(jù)上排給出十個(gè)數(shù)，在其下排填出對(duì)應(yīng)的十個(gè)數(shù)，要求下排每個(gè)數(shù)都是先前上排那十個(gè)數(shù)在下排出現(xiàn)的次數(shù)。

上排的十個(gè)數(shù)如下：【0，1，2，3，4，5，6，7，8，9】阿里巴巴面試題：澳大利亞的父母喜歡女孩，如果生出來的第一個(gè)女孩，就不再生了，如果是男孩就繼續(xù)生，直到生到第一個(gè)女孩為止，問若干年后，男女的比例是多少？淘寶校園筆試題：N個(gè)雞蛋放到M個(gè)籃子中，籃子不能為空，要滿足：對(duì)任意不大于N的數(shù)量，能用若干個(gè)籃子中雞蛋的和表示。對(duì)輸入整數(shù)N和M，輸出所有可能的雞蛋的放法。百度移動(dòng)開發(fā)筆試題：三色球排序的問題，相同的球放到一起，讓你按順序輸出紅白藍(lán)三種顏色的球，可以用012來表示，要求只能掃描一次數(shù)組。

Brainstorm騰訊面試題：給你10分鐘時(shí)間，根據(jù)上排給為什么學(xué)習(xí)算法？為什么學(xué)習(xí)算法？關(guān)于用計(jì)算機(jī)解決問題計(jì)算機(jī)的能力每秒5000次每秒數(shù)千億次繼電器真空管晶體管集成電路大規(guī)模集成電路超大規(guī)模集成電路元器件“單兵作戰(zhàn)”計(jì)算機(jī)網(wǎng)絡(luò)單機(jī)的串行分布計(jì)算結(jié)構(gòu)算法運(yùn)算速度………………關(guān)于用計(jì)算機(jī)解決問題每秒5000次每秒數(shù)千億次繼電器真空管晶世界最快的超級(jí)計(jì)算機(jī)（2014）10.神秘計(jì)算機(jī)——這是美國政府運(yùn)營的一臺(tái)神秘的、基于無限帶寬技術(shù)的CrayCS-Storm機(jī)器，具體位置不詳。它是唯一新入選榜單者，也是最節(jié)能的超級(jí)計(jì)算機(jī)，每瓦特電可每秒進(jìn)行2386.42百萬次浮點(diǎn)運(yùn)算。最高速度：每秒3.57千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：7.28萬個(gè)

9.Vulcan（美國）Vulcan是躋身最新榜單的美國能源部四大超級(jí)計(jì)算機(jī)性能最弱的一臺(tái)，它目前應(yīng)用于能源部的高性能運(yùn)算創(chuàng)新中心。最高速度：每秒4.29千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：39.3216萬個(gè)8.JUQUEEN（德國）JUQUEEN是前十榜單的“常客”，2012年年中以來未曾落選過。它運(yùn)營于德國北萊茵-威斯特伐利亞的Jülich研究中心。相比歐洲上榜的另一臺(tái)超級(jí)計(jì)算機(jī)，它的性能較弱。最高速度：每秒5千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：45.8752萬個(gè)7.Stampede（美國）該來自德州大學(xué)的超級(jí)計(jì)算機(jī)是此榜單上的唯一一臺(tái)戴爾產(chǎn)品，它也是全球最強(qiáng)大的學(xué)術(shù)用超級(jí)計(jì)算機(jī)。最高速度：每秒5.17千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：46.2462萬個(gè)6.PizDaint（瑞士）PizDaint是歐洲性能最強(qiáng)大的一臺(tái)超級(jí)計(jì)算機(jī)，它運(yùn)營于位于盧加諾的瑞士國家計(jì)算中心，以該中心80英里以外的阿爾卑斯山命名。最高速度：每秒6.27千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：11.5984萬個(gè)5.Mira（美國）Mira是前十榜單的另一位?？?，效力于美國阿貢國家實(shí)驗(yàn)室。這是它第六次上榜，同時(shí)也是連續(xù)第四次位居第五位。最高速度：每秒8.59千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：78.6432萬個(gè)4.KComputer（日本）富士通KComputer登上前十榜單的次數(shù)比Mira還要多，達(dá)到10次。2011年6月首次上榜它便是全球最快速的超級(jí)計(jì)算機(jī)。跟Mira一樣，它也是連續(xù)4次入選。最高速度：每秒10.5千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：70.5024萬個(gè)3.Sequoia（美國）Sequoia在躋身前500強(qiáng)榜單的時(shí)間比富士通KComputer僅晚6個(gè)月，第二次上榜便榮登首位。它運(yùn)行于美國能源部位于加州的勞倫斯利弗莫爾國家實(shí)驗(yàn)室。最高速度：每秒17.2千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：157.2864萬個(gè)2.Titan（美國）該美國超級(jí)計(jì)算機(jī)也是能源部的機(jī)器，它運(yùn)行于位于田納西州的橡樹嶺國家實(shí)驗(yàn)室。在最近的4次評(píng)比中，它都位居第二位。最高速度：每秒17.6千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：56.064萬個(gè)1.天河二號(hào)（中國）運(yùn)行于位于廣州的超級(jí)計(jì)算中心。最高速度：每秒33.9千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)312萬個(gè)。世界最快的超級(jí)計(jì)算機(jī)（2014）10.神秘計(jì)算機(jī)——這是美

計(jì)算機(jī)什么都能做?天河二號(hào)：32000顆主CPU，48000個(gè)協(xié)處理器，300多萬個(gè)計(jì)算核心，峰值計(jì)算速度達(dá)到每秒5.49億億次，而持續(xù)計(jì)算時(shí)的速度每秒可達(dá)3.39億億次。假設(shè)每人每秒鐘進(jìn)行一次運(yùn)算，“天河二號(hào)”運(yùn)算一小時(shí)，相當(dāng)于13億人同時(shí)用計(jì)算器算上1000年。除了助力探月工程、載人航天等政府科研項(xiàng)目外，天河二號(hào)目前已經(jīng)逐漸應(yīng)用于民用領(lǐng)域，比如石油勘探、汽車飛機(jī)的設(shè)計(jì)制造、基因測(cè)序等。

天河二號(hào)能做什么？計(jì)算機(jī)什么都能做?天河二號(hào)：3200

比如拿最簡單例子，26個(gè)英文字母全排列，它的排列數(shù)為：

26！≈4×1026以每年365天計(jì)算，共有

365×24×3600＝3.1536×107秒以每秒能完成109個(gè)排列的超高速電子計(jì)算機(jī)來做這項(xiàng)工作，需要

4×1026/(3.1536×1016)≈1.2×1010年即使計(jì)算機(jī)運(yùn)行速度隨著技術(shù)的提高，恐怕也還是不可能實(shí)現(xiàn)的。因計(jì)算機(jī)的速度再提高也有它的極限。比如拿最簡單例子，26個(gè)英文字母全排列，它的排列數(shù)為：用計(jì)算機(jī)解決問題的關(guān)鍵——算法一個(gè)熟悉的公式（NicklausWirth）：

程序=算法十?dāng)?shù)據(jù)結(jié)構(gòu)用計(jì)算機(jī)解決問題的關(guān)鍵——算法算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)，更是程序的基石，只有具有良好的算法基礎(chǔ)才能成為訓(xùn)練有素的軟件人才。對(duì)于計(jì)算機(jī)專業(yè)的學(xué)生來說，學(xué)習(xí)算法的理由是非常充分的。因?yàn)槟惚仨氈纴碜圆煌?jì)算領(lǐng)域的重要算法，你也必須學(xué)會(huì)設(shè)計(jì)新的算法、確認(rèn)其正確性并分析其效率。1、學(xué)習(xí)算法的必要性算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)，更是程序的基石，只有具有良好的算法基2、研究算法的重要性2.1問題能解決嗎

假設(shè)某一負(fù)責(zé)人交給你一個(gè)很難的任務(wù)，幾天后詢問你問題解決了沒有?？赡軙?huì)發(fā)生如下圖這樣的情況：問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎？”答：“我找不到一個(gè)有效的算法來解決它，沒能完成任務(wù)。”2、研究算法的重要性問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎？”答：“我找不到一個(gè)有效的算法來解決它，因?yàn)檫@樣的算法是不存在的?！?不過，要證明一個(gè)問題不存在有效算法，往往跟尋找有效算法一樣難。)問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎？”問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎？”答：“我找不到一個(gè)有效的算法來解決它，但不是我不行，因?yàn)樗羞@些名人也都找不到解決它的有效算法。”如果是你的話，你愿意是哪種結(jié)果？問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎？”偉大的智者——DonaldE.Knuth（美）高德納《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》的作者；

謙遜的長者——EdsgerWybe（荷蘭）Dijkstra算法（最短路徑算法）發(fā)明者；

運(yùn)籌學(xué)大師——GeorgeDantzing（俄國）在運(yùn)籌學(xué)建樹極高，獲得了包括“馮諾伊曼理論獎(jiǎng)”在內(nèi)的諸多獎(jiǎng)項(xiàng)。；

推動(dòng)時(shí)代前進(jìn)的人——JamesCooley（美）FFT（快速傅利葉變換）算法發(fā)明者，該算法主要用語數(shù)字信號(hào)處理技術(shù)；

FORTRAN之父——JohnBackus（美）FORTRAN之父，又提出規(guī)范編程語言語法的Backus-NaurForm(BNF)；影響計(jì)算機(jī)算法世界的十位大師偉大的智者——DonaldE.Knuth（美）高德納《實(shí)踐探索先鋒——

JonBentley（美）《ProgrammingPearls》（中文名《編程珠璣》）作者，精于軟件工程；

Pascal之父——NicklausWirth（瑞士）PASCAL之父，提出了“算法+數(shù)據(jù)結(jié)構(gòu)=程序”，他是創(chuàng)辦Borland公司的Philiekahn的老師；

算法的講解者——RobortSedgewick（美）算法講解者；

計(jì)算機(jī)領(lǐng)域的爵士

——

TonyHoare（英）快速排序算法（QuickSort）發(fā)明者，１９９９年加入微軟創(chuàng)辦了劍橋研究院；

首席算法官——

UdiManber（美）Google副總裁，首席算法官。影響計(jì)算機(jī)算法世界的十位大師實(shí)踐探索先鋒——JonBentley（美）《Progra來自圣經(jīng)的十大算法No10:Huffmancoding（霍夫曼編碼）No9:BinarySearch（二分查找）No8:Miller-Rabin算法（基于概率的素?cái)?shù)測(cè)試算法）No7:DepthFirstSearch、BreadthFirstSearch（深度、廣

度優(yōu)先搜索）No6:Gentry'sFullyHomomorphicEncryptionScheme

（紳士完全同態(tài)加密機(jī)制）算法No5:Floyd-Warshallall-pairs最短路徑算法No4:Quicksort（快速排序）No3:BFPRT算法（第k大元素平均復(fù)雜度為O（N）的算法，

俗稱"中位數(shù)之中位數(shù)算法"）No2:Knuth-Morris-Pratt字符串匹配算法No1:Union-find（并查集）源自CSDN博客，博主v_JULY_v來自圣經(jīng)的十大算法No10:Huffmancoding（為什么要學(xué)算法？如果不學(xué)，你可能用一個(gè)很花錢（Time,Space）的Algorithm去解決問題Life-timeJob:永遠(yuǎn)知道解某一問題最佳的Algorithm是什么方法：對(duì)于自己的領(lǐng)域隨時(shí)要查paper，update最佳的algorithms或至少知道可以問誰。為什么要學(xué)算法？如果不學(xué)，你可能用一個(gè)很花錢（Time,S為什么要學(xué)算法？2.如果不學(xué)，你可能去對(duì)NP-Complete的問題去找efficient的解Life-timeJob:去知道哪些問題是NP-Complete的RealApplicationAveragePerformance好的找Approximating的解為什么要學(xué)算法？2.如果不學(xué)，你可能去對(duì)NP-Comple作為即將從事計(jì)算機(jī)專業(yè)的人士實(shí)踐上必須了解計(jì)算領(lǐng)域中不同問題的一系列標(biāo)準(zhǔn)算法。具備設(shè)計(jì)新算法和分析其效率的能力。理論上算法研究是計(jì)算機(jī)科學(xué)的基石。培養(yǎng)分析問題的能力！作為即將從事計(jì)算機(jī)專業(yè)的人士實(shí)踐上2.2問題解決的好嗎？

設(shè)計(jì)出解決問題的算法后，要知道算法的優(yōu)劣好壞，是好算法則不必對(duì)其懷疑而再浪費(fèi)時(shí)間進(jìn)行研究。不是好算法則應(yīng)再進(jìn)行研究改進(jìn)。而如何知道算法的優(yōu)劣好壞，需要學(xué)習(xí)分析算法的方法。要設(shè)計(jì)出好算法，需要學(xué)習(xí)算法設(shè)計(jì)的常用方法。2.2問題解決的好嗎？一些有趣的問題

(1)

巡回推銷員問題:設(shè)有n個(gè)城市，已知任意兩城市間之距離，現(xiàn)有一推銷員想從某一城市出發(fā)巡回經(jīng)過每一城市（且每城市只經(jīng)過一次），最后又回到出發(fā)點(diǎn)，問如何找一條最短路徑。一些有趣的問題設(shè)距離矩陣如下：試一試求出最短路徑。設(shè)距離矩陣如下：試一試求出最短路徑。（2)

皇后問題:這是高斯1850年提出的一個(gè)著名問題：國際象棋中的“皇后”在橫向、直向、和斜向都能走步和吃子，問在n×n格的棋盤上如何能擺上n個(gè)皇后而使她們都不能互相吃。當(dāng)n很大時(shí)，問題很難。對(duì)于n=8,現(xiàn)已知此問題共有92種解，但只有12種是獨(dú)立的，其余的都可以由這12種利用對(duì)稱性或旋轉(zhuǎn)而得到。設(shè)n=4，試一試。

（2)皇后問題:這是高斯1850年提出的一個(gè)著名問題：國

(3）設(shè)天平有一些25克的砝碼，一些10克的砝碼，一些5克的砝碼和一些1克的砝碼?，F(xiàn)要稱63克的物體，問至少需要用幾個(gè)砝碼。

(4）背包問題1：有一旅行者要從n種物品中選取不超過b公斤重的行李隨身攜帶，要求總價(jià)值最大。例：設(shè)背包的容量為50千克。物品1重10千克，價(jià)值60元；物品2重20千克，價(jià)值100元；物品3重30千克，價(jià)值120元。求總價(jià)值最大。（5）背包問題2：設(shè)有n=8個(gè)體積分別為54，45，43，29，23，21，14，1的物體和一個(gè)容積為C=110的背包，問選擇哪幾個(gè)物體裝入背包可以使其裝的最滿。(3）設(shè)天平有一些25克的砝碼，一些10克的砝碼，一些5克

（6）裝箱問題：設(shè)有體積分別為v1,v2,…,vn的n種物品u1,u2,…,un裝到容量為L的箱子里。不同的裝箱方案所需的箱子數(shù)目可能不同，問如何裝箱能裝完這n種物品且使用的箱子數(shù)目最少。

（7）平面圖的四色猜想問題：一個(gè)平面圖是否用四種顏色就可使相鄰的區(qū)域顏色都不相同？（6）裝箱問題：設(shè)有體積分別為v1,v2,…,vn的n種物數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法C4.5：機(jī)器學(xué)習(xí)算法中的一個(gè)分類決策樹算法，是決策樹核心算法ID3的改進(jìn)算法。k-means算法：是一個(gè)聚類算法，把n的對(duì)象根據(jù)他們的屬性分為k個(gè)分割(k<n)。SVM：一種監(jiān)督式學(xué)習(xí)的方法，廣泛應(yīng)用于統(tǒng)計(jì)分類以及回歸分析中。Apriori算法：一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。EM算法：在概率模型中尋找參數(shù)最大似然估計(jì)的算法。數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法C4.5：機(jī)器學(xué)習(xí)算法中的一個(gè)分類決數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法PageRank：根據(jù)網(wǎng)站的外部鏈接和內(nèi)部鏈接的數(shù)量和質(zhì)量，衡量網(wǎng)站的價(jià)值。AdaBoost：一種迭代算法，針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構(gòu)成一個(gè)更強(qiáng)的最終分類器(強(qiáng)分類器)。

KNN：K最近鄰分類算法，是最簡單的機(jī)器學(xué)習(xí)算法之一。如果一個(gè)樣本在特征空間中的k個(gè)最相似的樣本中的大多數(shù)屬于某一類別，則它也屬于這個(gè)類別。NaiveBayes:樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論，有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，以及穩(wěn)定的分類效率。CART:分類與回歸樹數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法PageRank：根據(jù)網(wǎng)站的外部鏈接第1部分算法和算法分析第1章算法問題求解基礎(chǔ)第1部分算法和算法分析第1章算法問題求解基礎(chǔ)1.1算法概述1.2問題求解方法

1.3算法設(shè)計(jì)與分析

1.4遞歸和歸納

1.1算法概述1.1算法概述1.1算法概述1.1.1什么是算法

算法（algorithm）一個(gè)算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列。此外，算法具有下列5個(gè)特征:1.1.1什么是算法算法（algorithm）輸入（input）：算法有零個(gè)或多個(gè)輸入量；輸出（output）：算法至少產(chǎn)生一個(gè)輸出量；確定性（definiteness）：算法的每一條指令都有確切的定義，沒有二義性；能行性（effectiveness）：算法的每一條指令必須足夠基本，它們可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)；有窮性（finiteness）：算法必須總能在執(zhí)行有限步之后終止。輸入（input）：算法有零個(gè)或多個(gè)輸入量；

歐幾里德算法(輾轉(zhuǎn)相除法)計(jì)算兩個(gè)整數(shù)m和n（0≤m＜n)的最大公約數(shù)，記為gcd(m,n)。歐幾里德算法(輾轉(zhuǎn)相除法)【程序1-1】

歐幾里德遞歸算法voidSwap（int&a，int&b）{intc=a；a=b；b=c；}intRGcd(intm,intn){if(m==0)returnn;returnRGcd(n%m,m);}intGcd(intm,intn){if(m>n)Swap(m,n);returnRGcd(m,n);}【程序1-1】歐幾里德遞歸算法【程序1-2】

歐幾里德迭代算法intGcd(intm,intn){ if(m==0)returnn;if(n==0)returnm; if(m>n)Swap(m,n); while(m>0){ intc=n%m;n=m;m=c; } returnn;}【程序1-2】歐幾里德迭代算法【程序1-3】Gcd的連續(xù)整數(shù)檢測(cè)算法intGcd(intm,intn){ if(m==0)returnn;if(n==0)returnm; intt=m>n?n:m; while(m%t||n%t)t--; returnt;}【程序1-3】Gcd的連續(xù)整數(shù)檢測(cè)算法中學(xué)的解題思路：（1）找到m的所有質(zhì)因數(shù)（2）找到n的所有質(zhì)因數(shù)（3）找到（1），（2）中的公因數(shù)（4）求公因數(shù)的積，該乘積為m、n的最大公約數(shù)中學(xué)的解題思路：1.2問題求解方法1.2問題求解方法1.2.1問題和問題求解問題求解（problemsolving）是尋找一種方法來實(shí)現(xiàn)目標(biāo)。問題求解過程（problemsolvingprocess）通過使用問題領(lǐng)域知識(shí)來理解和定義問題，選擇和使用適當(dāng)?shù)膯栴}求解策略、技術(shù)和工具，將一個(gè)問題描述轉(zhuǎn)換成問題解的過程。計(jì)算機(jī)求解問題的關(guān)鍵之一是尋找一種問題求解策略（problemsolvingstrategy），得到求解問題的算法，從而得到問題的解。

1.2.1問題和問題求解問題求解（problemsol1.2.2問題求解過程

理解問題（understandtheproblem）

設(shè)計(jì)方案（designaplan）

實(shí)現(xiàn)方案（carryouttheplan）

回顧復(fù)查（lookback）1.2.2問題求解過程理解問題（understand1.2.3系統(tǒng)生命周期

一個(gè)計(jì)算機(jī)程序的開發(fā)過程就是使用計(jì)算機(jī)求解問題的過程。軟件工程（softwareengineering）將軟件開發(fā)和維護(hù)過程分成若干階段，稱為系統(tǒng)生命周期（systemlifecycle）或軟件生命周期。1.2.3系統(tǒng)生命周期一個(gè)計(jì)算機(jī)程序的開發(fā)過程就是使用軟件生命周期劃分為:分析（analysis）設(shè)計(jì)（design）編碼（codingorprogramming）測(cè)試（testing）維護(hù)（maintenance）等5個(gè)階段。前4個(gè)階段屬于開發(fā)期，最后一個(gè)階段處于運(yùn)行期。軟件生命周期1.3算法設(shè)計(jì)與分析1.3算法設(shè)計(jì)與分析1.3.1算法問題求解過程

算法分類一個(gè)精確算法（exactalgorithm）總能保證求得問題的解。一個(gè)啟發(fā)式算法（heuristicalgorithm）通過使用某種規(guī)則、簡化或智能猜測(cè)來減少問題求解時(shí)間。證明正確性分析算法設(shè)計(jì)程序理解問題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法1.3.1算法問題求解過程算法分類證明正確性分析算法設(shè)

對(duì)于最優(yōu)化問題，一個(gè)算法如果致力于尋找近似解而不是最優(yōu)解，被稱為近似算法（approximationalgorithm）。如果在算法中需做出某些隨機(jī)選擇，則稱為隨機(jī)算法（randomizedalgorithm）。對(duì)于最優(yōu)化問題，一個(gè)算法如果致力于尋找近似解而不是最優(yōu)解，1.3.2如何設(shè)計(jì)算法

使用計(jì)算機(jī)的問題求解策略主要指算法設(shè)計(jì)策略（algorithmdesignstrategy）。掌握一些基本的算法設(shè)計(jì)策略，判斷問題是否符合某種策略處理的問題特性。1.3.2如何設(shè)計(jì)算法使用計(jì)算機(jī)的問題求解策略主要指算1.3.3如何表示算法

算法描述方法自然語言流程圖偽代碼程序設(shè)計(jì)語言教材使用C/C++語言描述算法1.3.3如何表示算法算法描述方法1.3.4如何確認(rèn)算法確認(rèn)一個(gè)算法是否正確的活動(dòng)稱為算法確認(rèn)（algorithmvalidation）。使用數(shù)學(xué)方法證明算法的正確性，稱為算法證明（algorithmproof）。程序測(cè)試（programtesting）是指對(duì)程序模塊或程序總體，輸入事先準(zhǔn)備好的樣本數(shù)據(jù)（稱為測(cè)試用例，testcase），檢查該程序的輸出，來發(fā)現(xiàn)程序存在的錯(cuò)誤及判定程序是否滿足其設(shè)計(jì)要求的一項(xiàng)積極活動(dòng)。

1.3.4如何確認(rèn)算法確認(rèn)一個(gè)算法是否正確的活動(dòng)稱為算法1.3.5如何分析算法算法分析（algorithmanalysis）活動(dòng)是指對(duì)算法的執(zhí)行時(shí)間和所需空間的估算。當(dāng)然在算法寫成程序后，便可使用樣本數(shù)據(jù)，實(shí)際測(cè)量一個(gè)程序所消耗的時(shí)間和空間，這稱為程序的性能測(cè)量（performancemeasurement）。1.3.5如何分析算法算法分析（algorithman*1.4遞歸和歸納*1.4遞歸和歸納1.4.1遞歸

遞歸定義遞歸（recursive）定義是一種直接或間接引用自身的定義方法。一個(gè)合法的遞歸定義包括兩部分：基礎(chǔ)情況（basecase）和遞歸部分。例1-1

斐波那契數(shù)列1.4.1遞歸遞歸定義例1-1

斐波那契數(shù)列例1-1斐波那契數(shù)列

遞歸算法當(dāng)一個(gè)算法采用遞歸方式定義時(shí)便成為遞歸算法。一個(gè)遞歸算法是指直接或間接調(diào)用自身的算法。

【程序1-4】

求FnlongFib(longn){ if(n<=1)returnn; elsereturnFib(n-2)+Fib(n-1);}遞歸算法

可以用所謂的遞歸樹（recursivetree）來描述程序1-4的函數(shù)Fib執(zhí)行時(shí)的調(diào)用關(guān)系。圖1-2計(jì)算Fib（4）的遞歸樹

N??？可以用所謂的遞歸樹（recursivetree）來描述程

遞歸數(shù)據(jù)結(jié)構(gòu)使用遞歸方式定義的數(shù)據(jù)結(jié)構(gòu)稱為遞歸數(shù)據(jù)結(jié)構(gòu)（recursivedatastructure）。遞歸數(shù)據(jù)結(jié)構(gòu)1.4.2遞歸算法示例

例1-2

逆序輸出正整數(shù)的各位數(shù)

【程序1-5】

voidPrintDigit(unsignedintn){ cout<<n%10; //輸出最后一位數(shù)dk if(n>=10)PrintDigit(n/10); //以逆序輸出前k-1位數(shù)}1.4.2遞歸算法示例例1-2逆序輸出正整數(shù)的各位例1-3漢諾塔問題（towerofHanoi）假定有三個(gè)塔座：X，Y，Z，在塔座X上有n個(gè)直徑大小各不相同，按圓盤大小從小到大編號(hào)為1，2，…，n的圓盤?，F(xiàn)要求將X塔座上n個(gè)圓盤移到塔座Y上，并仍按同樣順序疊排。圓盤移動(dòng)時(shí)必須遵循下列規(guī)則：（1）每次只能移動(dòng)一個(gè)圓盤；（2）圓盤可以加到塔座X，Y，Z中任意一個(gè)上；（3）任何時(shí)刻都不能將一個(gè)較大的圓盤放在較小的圓盤之上。例1-3漢諾塔問題（towerofHanoi）算法與復(fù)雜性-第1講-概述課件【程序1-6】

漢諾塔問題enumtower{A='X',B='Y',C='Z'};voidMove(intn,towerx,towery){//將第n個(gè)圓盤從塔座x移到塔座y的頂部

cout<<"Thedisk"<<n<<"ismovedfrom" <<char(x)<<"totopoftower"<<char(y)<<endl;}【程序1-6】漢諾塔問題voidHanoi(intn,towerx,towery,towerz){//將x上部的n個(gè)圓盤移到y(tǒng)上，順序不變。

if(n){ Hanoi(n-1,x,z,y); Move(n,x,y); Hanoi(n-1,z,y,x); }}voidHanoi(intn,towerx,to1.4.3歸納證明定理1-1對(duì)于n≥0，程序1-5是正確的。

證明：（歸納法證明）當(dāng)n是1位數(shù)時(shí)，程序顯然是正確的。假定函數(shù)PrintDigit對(duì)所有位數(shù)小于k（k＞1）的正整數(shù)都能正確運(yùn)行，當(dāng)n的位數(shù)為k位時(shí)，此時(shí)有n≥10，算法必定先執(zhí)行語句cout<<n%10;然后執(zhí)行語句if(n>10)PrintDigit(n/10);。1.4.3歸納證明定理1-1對(duì)于n≥0，程序1-5是由于n/10是n的前k-1位數(shù)字形成的數(shù)，歸納法假設(shè)函數(shù)調(diào)用PrintDigit(n/10)能夠?qū)⑺_地（并在有限步內(nèi)）按數(shù)字的逆序輸出，那么，現(xiàn)在先執(zhí)行語句輸出個(gè)位數(shù)字（n%10），然后由于按逆序輸出前k-1位數(shù)字的做法是能夠正確按逆序輸出全部k位數(shù)字的，所以程序1-5是正確的。由于n/10是n的前k-1位數(shù)字形成的數(shù)，歸納法假設(shè)函數(shù)算法與復(fù)雜性AlgorithmsandComplexity劉杰南華大學(xué)計(jì)算機(jī)學(xué)院軟件工程系算法與復(fù)雜性AlgorithmsandComplexit課程簡介1．課程學(xué)時(shí)總學(xué)時(shí)：48學(xué)時(shí)（理論）2．課程主要內(nèi)容介紹算法的概念及算法分析的基礎(chǔ)知識(shí)；介紹一些經(jīng)典算法*蠻力法分治法貪心法動(dòng)態(tài)規(guī)劃回溯法分支限界法

NP完全問題

*算法賞析課程簡介3．考核方法－－考查

課堂表現(xiàn)、考勤、實(shí)驗(yàn)（占60％）期末考查（小組答辯，占40％）

4．本課程主要參考書[1]王曉東編著，計(jì)算機(jī)算法設(shè)計(jì)與分析(第4版)，電子工業(yè)出版社，2012[2]屈婉玲等，算法設(shè)計(jì)與分析，清華大學(xué)出版社，2011劉汝佳——“白皮書”、“黑寶書”……5．網(wǎng)上學(xué)習(xí)（百度&CSDN）3．考核方法－－考查作業(yè)提交算法設(shè)計(jì)實(shí)現(xiàn)類的作業(yè)網(wǎng)址：:9988/（南華OJ）登陸賬號(hào)：學(xué)號(hào)（如：20134330101）密碼：學(xué)號(hào)后面的6位數(shù)字（以上面賬號(hào)為例，則密碼為330101）注意：已注冊(cè)過的同學(xué)提交本課程作業(yè)請(qǐng)用新賬號(hào)和口令。課程PPT和參考資料、其他作業(yè)（報(bào)告）9:9988/sc8/（南華大學(xué)數(shù)字化教學(xué)中心）計(jì)算機(jī)：WSTD-6758

軟件2班：UFSM-0601軟件3班：KQEQ-5247

物聯(lián)網(wǎng)：PPKL-3080船本軟件：PWAH-5676

船本計(jì)算機(jī)：VPKW-5550作業(yè)提交算法設(shè)計(jì)實(shí)現(xiàn)類的作業(yè)課程PPT和參考資料、其他作業(yè)（從經(jīng)典的IBM面試題說起村子中有50個(gè)人，每人有一條狗。在這50條狗中有病狗（這種病不會(huì)傳染）。于是人們就要找出病狗。每個(gè)人可以觀察其他的49條狗，以判斷它們是否生?。ㄈ绻胁∫欢芸闯鰜恚皇亲约旱墓凡荒芸?。觀察后得到的結(jié)果不得交流，也不能通知病狗的主人。主人一旦推算出自己家的是病狗就要槍斃自己的狗（發(fā)現(xiàn)后必須在一天內(nèi)槍斃），而且每個(gè)人只有權(quán)利槍斃自己的狗，沒有權(quán)利打死其他人的狗。第一天大家全看完了，但槍沒有響，第二天仍沒有槍響。到了第三天傳來一陣槍聲，問村里共有幾條病狗，如何推算得出？從經(jīng)典的IBM面試題說起村子中有50個(gè)人，每人有一條狗。在這Brainstorm騰訊面試題：給你10分鐘時(shí)間，根據(jù)上排給出十個(gè)數(shù)，在其下排填出對(duì)應(yīng)的十個(gè)數(shù)，要求下排每個(gè)數(shù)都是先前上排那十個(gè)數(shù)在下排出現(xiàn)的次數(shù)。

上排的十個(gè)數(shù)如下：【0，1，2，3，4，5，6，7，8，9】阿里巴巴面試題：澳大利亞的父母喜歡女孩，如果生出來的第一個(gè)女孩，就不再生了，如果是男孩就繼續(xù)生，直到生到第一個(gè)女孩為止，問若干年后，男女的比例是多少？淘寶校園筆試題：N個(gè)雞蛋放到M個(gè)籃子中，籃子不能為空，要滿足：對(duì)任意不大于N的數(shù)量，能用若干個(gè)籃子中雞蛋的和表示。對(duì)輸入整數(shù)N和M，輸出所有可能的雞蛋的放法。百度移動(dòng)開發(fā)筆試題：三色球排序的問題，相同的球放到一起，讓你按順序輸出紅白藍(lán)三種顏色的球，可以用012來表示，要求只能掃描一次數(shù)組。

Brainstorm騰訊面試題：給你10分鐘時(shí)間，根據(jù)上排給為什么學(xué)習(xí)算法？為什么學(xué)習(xí)算法？關(guān)于用計(jì)算機(jī)解決問題計(jì)算機(jī)的能力每秒5000次每秒數(shù)千億次繼電器真空管晶體管集成電路大規(guī)模集成電路超大規(guī)模集成電路元器件“單兵作戰(zhàn)”計(jì)算機(jī)網(wǎng)絡(luò)單機(jī)的串行分布計(jì)算結(jié)構(gòu)算法運(yùn)算速度………………關(guān)于用計(jì)算機(jī)解決問題每秒5000次每秒數(shù)千億次繼電器真空管晶世界最快的超級(jí)計(jì)算機(jī)（2014）10.神秘計(jì)算機(jī)——這是美國政府運(yùn)營的一臺(tái)神秘的、基于無限帶寬技術(shù)的CrayCS-Storm機(jī)器，具體位置不詳。它是唯一新入選榜單者，也是最節(jié)能的超級(jí)計(jì)算機(jī)，每瓦特電可每秒進(jìn)行2386.42百萬次浮點(diǎn)運(yùn)算。最高速度：每秒3.57千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：7.28萬個(gè)

9.Vulcan（美國）Vulcan是躋身最新榜單的美國能源部四大超級(jí)計(jì)算機(jī)性能最弱的一臺(tái)，它目前應(yīng)用于能源部的高性能運(yùn)算創(chuàng)新中心。最高速度：每秒4.29千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：39.3216萬個(gè)8.JUQUEEN（德國）JUQUEEN是前十榜單的“?？汀?，2012年年中以來未曾落選過。它運(yùn)營于德國北萊茵-威斯特伐利亞的Jülich研究中心。相比歐洲上榜的另一臺(tái)超級(jí)計(jì)算機(jī)，它的性能較弱。最高速度：每秒5千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：45.8752萬個(gè)7.Stampede（美國）該來自德州大學(xué)的超級(jí)計(jì)算機(jī)是此榜單上的唯一一臺(tái)戴爾產(chǎn)品，它也是全球最強(qiáng)大的學(xué)術(shù)用超級(jí)計(jì)算機(jī)。最高速度：每秒5.17千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：46.2462萬個(gè)6.PizDaint（瑞士）PizDaint是歐洲性能最強(qiáng)大的一臺(tái)超級(jí)計(jì)算機(jī)，它運(yùn)營于位于盧加諾的瑞士國家計(jì)算中心，以該中心80英里以外的阿爾卑斯山命名。最高速度：每秒6.27千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：11.5984萬個(gè)5.Mira（美國）Mira是前十榜單的另一位?？?，效力于美國阿貢國家實(shí)驗(yàn)室。這是它第六次上榜，同時(shí)也是連續(xù)第四次位居第五位。最高速度：每秒8.59千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：78.6432萬個(gè)4.KComputer（日本）富士通KComputer登上前十榜單的次數(shù)比Mira還要多，達(dá)到10次。2011年6月首次上榜它便是全球最快速的超級(jí)計(jì)算機(jī)。跟Mira一樣，它也是連續(xù)4次入選。最高速度：每秒10.5千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：70.5024萬個(gè)3.Sequoia（美國）Sequoia在躋身前500強(qiáng)榜單的時(shí)間比富士通KComputer僅晚6個(gè)月，第二次上榜便榮登首位。它運(yùn)行于美國能源部位于加州的勞倫斯利弗莫爾國家實(shí)驗(yàn)室。最高速度：每秒17.2千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：157.2864萬個(gè)2.Titan（美國）該美國超級(jí)計(jì)算機(jī)也是能源部的機(jī)器，它運(yùn)行于位于田納西州的橡樹嶺國家實(shí)驗(yàn)室。在最近的4次評(píng)比中，它都位居第二位。最高速度：每秒17.6千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)：56.064萬個(gè)1.天河二號(hào)（中國）運(yùn)行于位于廣州的超級(jí)計(jì)算中心。最高速度：每秒33.9千萬億次浮點(diǎn)運(yùn)算，總核心數(shù)312萬個(gè)。世界最快的超級(jí)計(jì)算機(jī)（2014）10.神秘計(jì)算機(jī)——這是美

計(jì)算機(jī)什么都能做?天河二號(hào)：32000顆主CPU，48000個(gè)協(xié)處理器，300多萬個(gè)計(jì)算核心，峰值計(jì)算速度達(dá)到每秒5.49億億次，而持續(xù)計(jì)算時(shí)的速度每秒可達(dá)3.39億億次。假設(shè)每人每秒鐘進(jìn)行一次運(yùn)算，“天河二號(hào)”運(yùn)算一小時(shí)，相當(dāng)于13億人同時(shí)用計(jì)算器算上1000年。除了助力探月工程、載人航天等政府科研項(xiàng)目外，天河二號(hào)目前已經(jīng)逐漸應(yīng)用于民用領(lǐng)域，比如石油勘探、汽車飛機(jī)的設(shè)計(jì)制造、基因測(cè)序等。

天河二號(hào)能做什么？計(jì)算機(jī)什么都能做?天河二號(hào)：3200

比如拿最簡單例子，26個(gè)英文字母全排列，它的排列數(shù)為：

26！≈4×1026以每年365天計(jì)算，共有

365×24×3600＝3.1536×107秒以每秒能完成109個(gè)排列的超高速電子計(jì)算機(jī)來做這項(xiàng)工作，需要

4×1026/(3.1536×1016)≈1.2×1010年即使計(jì)算機(jī)運(yùn)行速度隨著技術(shù)的提高，恐怕也還是不可能實(shí)現(xiàn)的。因計(jì)算機(jī)的速度再提高也有它的極限。比如拿最簡單例子，26個(gè)英文字母全排列，它的排列數(shù)為：用計(jì)算機(jī)解決問題的關(guān)鍵——算法一個(gè)熟悉的公式（NicklausWirth）：

程序=算法十?dāng)?shù)據(jù)結(jié)構(gòu)用計(jì)算機(jī)解決問題的關(guān)鍵——算法算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)，更是程序的基石，只有具有良好的算法基礎(chǔ)才能成為訓(xùn)練有素的軟件人才。對(duì)于計(jì)算機(jī)專業(yè)的學(xué)生來說，學(xué)習(xí)算法的理由是非常充分的。因?yàn)槟惚仨氈纴碜圆煌?jì)算領(lǐng)域的重要算法，你也必須學(xué)會(huì)設(shè)計(jì)新的算法、確認(rèn)其正確性并分析其效率。1、學(xué)習(xí)算法的必要性算法是計(jì)算機(jī)科學(xué)的基礎(chǔ)，更是程序的基石，只有具有良好的算法基2、研究算法的重要性2.1問題能解決嗎

假設(shè)某一負(fù)責(zé)人交給你一個(gè)很難的任務(wù)，幾天后詢問你問題解決了沒有?？赡軙?huì)發(fā)生如下圖這樣的情況：問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎？”答：“我找不到一個(gè)有效的算法來解決它，沒能完成任務(wù)?！?、研究算法的重要性問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎？”答：“我找不到一個(gè)有效的算法來解決它，因?yàn)檫@樣的算法是不存在的?！?不過，要證明一個(gè)問題不存在有效算法，往往跟尋找有效算法一樣難。)問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎？”問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎？”答：“我找不到一個(gè)有效的算法來解決它，但不是我不行，因?yàn)樗羞@些名人也都找不到解決它的有效算法?！比绻悄愕脑?，你愿意是哪種結(jié)果？問：“交給你的問題，解決方案設(shè)計(jì)出來了嗎？”偉大的智者——DonaldE.Knuth（美）高德納《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》的作者；

謙遜的長者——EdsgerWybe（荷蘭）Dijkstra算法（最短路徑算法）發(fā)明者；

運(yùn)籌學(xué)大師——GeorgeDantzing（俄國）在運(yùn)籌學(xué)建樹極高，獲得了包括“馮諾伊曼理論獎(jiǎng)”在內(nèi)的諸多獎(jiǎng)項(xiàng)。；

推動(dòng)時(shí)代前進(jìn)的人——JamesCooley（美）FFT（快速傅利葉變換）算法發(fā)明者，該算法主要用語數(shù)字信號(hào)處理技術(shù)；

FORTRAN之父——JohnBackus（美）FORTRAN之父，又提出規(guī)范編程語言語法的Backus-NaurForm(BNF)；影響計(jì)算機(jī)算法世界的十位大師偉大的智者——DonaldE.Knuth（美）高德納《實(shí)踐探索先鋒——

JonBentley（美）《ProgrammingPearls》（中文名《編程珠璣》）作者，精于軟件工程；

Pascal之父——NicklausWirth（瑞士）PASCAL之父，提出了“算法+數(shù)據(jù)結(jié)構(gòu)=程序”，他是創(chuàng)辦Borland公司的Philiekahn的老師；

算法的講解者——RobortSedgewick（美）算法講解者；

計(jì)算機(jī)領(lǐng)域的爵士

——

TonyHoare（英）快速排序算法（QuickSort）發(fā)明者，１９９９年加入微軟創(chuàng)辦了劍橋研究院；

首席算法官——

UdiManber（美）Google副總裁，首席算法官。影響計(jì)算機(jī)算法世界的十位大師實(shí)踐探索先鋒——JonBentley（美）《Progra來自圣經(jīng)的十大算法No10:Huffmancoding（霍夫曼編碼）No9:BinarySearch（二分查找）No8:Miller-Rabin算法（基于概率的素?cái)?shù)測(cè)試算法）No7:DepthFirstSearch、BreadthFirstSearch（深度、廣

度優(yōu)先搜索）No6:Gentry'sFullyHomomorphicEncryptionScheme

（紳士完全同態(tài)加密機(jī)制）算法No5:Floyd-Warshallall-pairs最短路徑算法No4:Quicksort（快速排序）No3:BFPRT算法（第k大元素平均復(fù)雜度為O（N）的算法，

俗稱"中位數(shù)之中位數(shù)算法"）No2:Knuth-Morris-Pratt字符串匹配算法No1:Union-find（并查集）源自CSDN博客，博主v_JULY_v來自圣經(jīng)的十大算法No10:Huffmancoding（為什么要學(xué)算法？如果不學(xué)，你可能用一個(gè)很花錢（Time,Space）的Algorithm去解決問題Life-timeJob:永遠(yuǎn)知道解某一問題最佳的Algorithm是什么方法：對(duì)于自己的領(lǐng)域隨時(shí)要查paper，update最佳的algorithms或至少知道可以問誰。為什么要學(xué)算法？如果不學(xué)，你可能用一個(gè)很花錢（Time,S為什么要學(xué)算法？2.如果不學(xué)，你可能去對(duì)NP-Complete的問題去找efficient的解Life-timeJob:去知道哪些問題是NP-Complete的RealApplicationAveragePerformance好的找Approximating的解為什么要學(xué)算法？2.如果不學(xué)，你可能去對(duì)NP-Comple作為即將從事計(jì)算機(jī)專業(yè)的人士實(shí)踐上必須了解計(jì)算領(lǐng)域中不同問題的一系列標(biāo)準(zhǔn)算法。具備設(shè)計(jì)新算法和分析其效率的能力。理論上算法研究是計(jì)算機(jī)科學(xué)的基石。培養(yǎng)分析問題的能力！作為即將從事計(jì)算機(jī)專業(yè)的人士實(shí)踐上2.2問題解決的好嗎？

設(shè)計(jì)出解決問題的算法后，要知道算法的優(yōu)劣好壞，是好算法則不必對(duì)其懷疑而再浪費(fèi)時(shí)間進(jìn)行研究。不是好算法則應(yīng)再進(jìn)行研究改進(jìn)。而如何知道算法的優(yōu)劣好壞，需要學(xué)習(xí)分析算法的方法。要設(shè)計(jì)出好算法，需要學(xué)習(xí)算法設(shè)計(jì)的常用方法。2.2問題解決的好嗎？一些有趣的問題

(1)

巡回推銷員問題:設(shè)有n個(gè)城市，已知任意兩城市間之距離，現(xiàn)有一推銷員想從某一城市出發(fā)巡回經(jīng)過每一城市（且每城市只經(jīng)過一次），最后又回到出發(fā)點(diǎn)，問如何找一條最短路徑。一些有趣的問題設(shè)距離矩陣如下：試一試求出最短路徑。設(shè)距離矩陣如下：試一試求出最短路徑。（2)

皇后問題:這是高斯1850年提出的一個(gè)著名問題：國際象棋中的“皇后”在橫向、直向、和斜向都能走步和吃子，問在n×n格的棋盤上如何能擺上n個(gè)皇后而使她們都不能互相吃。當(dāng)n很大時(shí)，問題很難。對(duì)于n=8,現(xiàn)已知此問題共有92種解，但只有12種是獨(dú)立的，其余的都可以由這12種利用對(duì)稱性或旋轉(zhuǎn)而得到。設(shè)n=4，試一試。

（2)皇后問題:這是高斯1850年提出的一個(gè)著名問題：國

(3）設(shè)天平有一些25克的砝碼，一些10克的砝碼，一些5克的砝碼和一些1克的砝碼?，F(xiàn)要稱63克的物體，問至少需要用幾個(gè)砝碼。

(4）背包問題1：有一旅行者要從n種物品中選取不超過b公斤重的行李隨身攜帶，要求總價(jià)值最大。例：設(shè)背包的容量為50千克。物品1重10千克，價(jià)值60元；物品2重20千克，價(jià)值100元；物品3重30千克，價(jià)值120元。求總價(jià)值最大。（5）背包問題2：設(shè)有n=8個(gè)體積分別為54，45，43，29，23，21，14，1的物體和一個(gè)容積為C=110的背包，問選擇哪幾個(gè)物體裝入背包可以使其裝的最滿。(3）設(shè)天平有一些25克的砝碼，一些10克的砝碼，一些5克

（6）裝箱問題：設(shè)有體積分別為v1,v2,…,vn的n種物品u1,u2,…,un裝到容量為L的箱子里。不同的裝箱方案所需的箱子數(shù)目可能不同，問如何裝箱能裝完這n種物品且使用的箱子數(shù)目最少。

（7）平面圖的四色猜想問題：一個(gè)平面圖是否用四種顏色就可使相鄰的區(qū)域顏色都不相同？（6）裝箱問題：設(shè)有體積分別為v1,v2,…,vn的n種物數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法C4.5：機(jī)器學(xué)習(xí)算法中的一個(gè)分類決策樹算法，是決策樹核心算法ID3的改進(jìn)算法。k-means算法：是一個(gè)聚類算法，把n的對(duì)象根據(jù)他們的屬性分為k個(gè)分割(k<n)。SVM：一種監(jiān)督式學(xué)習(xí)的方法，廣泛應(yīng)用于統(tǒng)計(jì)分類以及回歸分析中。Apriori算法：一種最有影響的挖掘布爾關(guān)聯(lián)規(guī)則頻繁項(xiàng)集的算法。EM算法：在概率模型中尋找參數(shù)最大似然估計(jì)的算法。數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法C4.5：機(jī)器學(xué)習(xí)算法中的一個(gè)分類決數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法PageRank：根據(jù)網(wǎng)站的外部鏈接和內(nèi)部鏈接的數(shù)量和質(zhì)量，衡量網(wǎng)站的價(jià)值。AdaBoost：一種迭代算法，針對(duì)同一個(gè)訓(xùn)練集訓(xùn)練不同的分類器(弱分類器)，然后把這些弱分類器集合起來，構(gòu)成一個(gè)更強(qiáng)的最終分類器(強(qiáng)分類器)。

KNN：K最近鄰分類算法，是最簡單的機(jī)器學(xué)習(xí)算法之一。如果一個(gè)樣本在特征空間中的k個(gè)最相似的樣本中的大多數(shù)屬于某一類別，則它也屬于這個(gè)類別。NaiveBayes:樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論，有著堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，以及穩(wěn)定的分類效率。CART:分類與回歸樹數(shù)據(jù)挖掘領(lǐng)域十大經(jīng)典算法PageRank：根據(jù)網(wǎng)站的外部鏈接第1部分算法和算法分析第1章算法問題求解基礎(chǔ)第1部分算法和算法分析第1章算法問題求解基礎(chǔ)1.1算法概述1.2問題求解方法

1.3算法設(shè)計(jì)與分析

1.4遞歸和歸納

1.1算法概述1.1算法概述1.1算法概述1.1.1什么是算法

算法（algorithm）一個(gè)算法是對(duì)特定問題求解步驟的一種描述，它是指令的有限序列。此外，算法具有下列5個(gè)特征:1.1.1什么是算法算法（algorithm）輸入（input）：算法有零個(gè)或多個(gè)輸入量；輸出（output）：算法至少產(chǎn)生一個(gè)輸出量；確定性（definiteness）：算法的每一條指令都有確切的定義，沒有二義性；能行性（effectiveness）：算法的每一條指令必須足夠基本，它們可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)；有窮性（finiteness）：算法必須總能在執(zhí)行有限步之后終止。輸入（input）：算法有零個(gè)或多個(gè)輸入量；

歐幾里德算法(輾轉(zhuǎn)相除法)計(jì)算兩個(gè)整數(shù)m和n（0≤m＜n)的最大公約數(shù)，記為gcd(m,n)。歐幾里德算法(輾轉(zhuǎn)相除法)【程序1-1】

歐幾里德遞歸算法voidSwap（int&a，int&b）{intc=a；a=b；b=c；}intRGcd(intm,intn){if(m==0)returnn;returnRGcd(n%m,m);}intGcd(intm,intn){if(m>n)Swap(m,n);returnRGcd(m,n);}【程序1-1】歐幾里德遞歸算法【程序1-2】

歐幾里德迭代算法intGcd(intm,intn){ if(m==0)returnn;if(n==0)returnm; if(m>n)Swap(m,n); while(m>0){ intc=n%m;n=m;m=c; } returnn;}【程序1-2】歐幾里德迭代算法【程序1-3】Gcd的連續(xù)整數(shù)檢測(cè)算法intGcd(intm,intn){ if(m==0)returnn;if(n==0)returnm; intt=m>n?n:m; while(m%t||n%t)t--; returnt;}【程序1-3】Gcd的連續(xù)整數(shù)檢測(cè)算法中學(xué)的解題思路：（1）找到m的所有質(zhì)因數(shù)（2）找到n的所有質(zhì)因數(shù)（3）找到（1），（2）中的公因數(shù)（4）求公因數(shù)的積，該乘積為m、n的最大公約數(shù)中學(xué)的解題思路：1.2問題求解方法1.2問題求解方法1.2.1問題和問題求解問題求解（problemsolving）是尋找一種方法來實(shí)現(xiàn)目標(biāo)。問題求解過程（problemsolvingprocess）通過使用問題領(lǐng)域知識(shí)來理解和定義問題，選擇和使用適當(dāng)?shù)膯栴}求解策略、技術(shù)和工具，將一個(gè)問題描述轉(zhuǎn)換成問題解的過程。計(jì)算機(jī)求解問題的關(guān)鍵之一是尋找一種問題求解策略（problemsolvingstrategy），得到求解問題的算法，從而得到問題的解。

1.2.1問題和問題求解問題求解（problemsol1.2.2問題求解過程

理解問題（understandtheproblem）

設(shè)計(jì)方案（designaplan）

實(shí)現(xiàn)方案（carryouttheplan）

回顧復(fù)查（lookback）1.2.2問題求解過程理解問題（understand1.2.3系統(tǒng)生命周期

一個(gè)計(jì)算機(jī)程序的開發(fā)過程就是使用計(jì)算機(jī)求解問題的過程。軟件工程（softwareengineering）將軟件開發(fā)和維護(hù)過程分成若干階段，稱為系統(tǒng)生命周期（systemlifecycle）或軟件生命周期。1.2.3系統(tǒng)生命周期一個(gè)計(jì)算機(jī)程序的開發(fā)過程就是使用軟件生命周期劃分為:分析（analysis）設(shè)計(jì)（design）編碼（codingorprogramming）測(cè)試（testing）維護(hù)（maintenance）等5個(gè)階段。前4個(gè)階段屬于開發(fā)期，最后一個(gè)階段處于運(yùn)行期。軟件生命周期1.3算法設(shè)計(jì)與分析1.3算法設(shè)計(jì)與分析1.3.1算法問題求解過程

算法分類一個(gè)精確算法（exactalgorithm）總能保證求得問題的解。一個(gè)啟發(fā)式算法（heuristicalgorithm）通過使用某種規(guī)則、簡化或智能猜測(cè)來減少問題求解時(shí)間。證明正確性分析算法設(shè)計(jì)程序理解問題精確解或近似解選擇數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)策略設(shè)計(jì)算法1.3.1算法問題求解過程算法分類證明正確性分析算法設(shè)

對(duì)于最優(yōu)化問題，一個(gè)算法如果致力于尋找近似解而不是最優(yōu)解，被稱為近似算法（approximationalgorithm）。如果在算法中需做出某些隨機(jī)選擇，則稱為隨機(jī)算法（randomizedalgorithm）。對(duì)于最優(yōu)化問題，一個(gè)算法如果致力于尋找近似解而不是最優(yōu)解，1.3.2如何設(shè)計(jì)算法

使用計(jì)算機(jī)的問題求解策略主要指算法設(shè)計(jì)策略（algorithmdesignstrategy）。掌握一些基本的算法設(shè)計(jì)策略，判斷問題是否符合某種策略處理的問題