算法設(shè)計(jì)實(shí)例教程 課件全套 第1-9章 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)-算法設(shè)計(jì)實(shí)例教程- 高級(jí)算法-算法設(shè)計(jì)實(shí)例教程

算法設(shè)計(jì)實(shí)例教程教學(xué)分析目錄CONCENTS123456789第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第2章基礎(chǔ)算法第3章排序算法第4章查找第5章字符串和高精度運(yùn)算第6章圖論算法第7章動(dòng)態(tài)規(guī)劃算法第8章計(jì)算幾何基礎(chǔ)第9章高級(jí)算法1.1.1數(shù)組本節(jié)介紹一種最基本的數(shù)據(jù)結(jié)構(gòu)——數(shù)組，稍微有一些編程基礎(chǔ)的讀者肯定對(duì)這一數(shù)據(jù)結(jié)構(gòu)不陌生。數(shù)組是一個(gè)由若干同類型變量組成的集合，在使用時(shí)只要滿足這個(gè)條件都可以看作數(shù)組的使用案例。數(shù)組（Array）是具有相同類型的數(shù)據(jù)元素的有序集合。數(shù)組中的每一數(shù)據(jù)元素通常稱為數(shù)組元素，數(shù)組元素用下標(biāo)識(shí)別，下標(biāo)的個(gè)數(shù)取決于數(shù)組的維數(shù)。數(shù)組是可以在內(nèi)存中連續(xù)存儲(chǔ)多個(gè)元素的結(jié)構(gòu)，在內(nèi)存中的分配也是連續(xù)的。常用數(shù)組類型為一維、二維數(shù)組1.1常見的數(shù)據(jù)結(jié)構(gòu)1.1.1數(shù)組（2）二維數(shù)組。對(duì)于二維數(shù)組，可以將其轉(zhuǎn)化為一維數(shù)組來考慮。可以將二維數(shù)組看作是元素為一維數(shù)組的一維數(shù)組。該數(shù)組以m行n列的矩陣形式表示。（1）一維數(shù)組。該數(shù)組具有n個(gè)元素，由于它的每個(gè)元素只有一個(gè)下標(biāo)，因此它是一維數(shù)組。1.數(shù)組的定義一維數(shù)組定義的一般形式為：類型符數(shù)組名[常量表達(dá)式]。1.1.1數(shù)組1inta[15]//定義了一個(gè)有15個(gè)整型元素的數(shù)組a二維數(shù)組定義的一般形式為：類型符

數(shù)組名[常量表達(dá)式][常量表達(dá)式]。具體實(shí)現(xiàn)如下：1floatb[3][5]//定義了一個(gè)浮點(diǎn)型的二維數(shù)組b，是一個(gè)3×5（3行5列）的數(shù)組2.數(shù)組的引用引用一維數(shù)組的表示形式為：數(shù)組名[下標(biāo)]。引用二維數(shù)組的表示形式為：數(shù)組名[下標(biāo)][下標(biāo)]。具體實(shí)現(xiàn)如下：1.1.1數(shù)組1inta[15]2k=a[10]//引用數(shù)組a中序號(hào)為10的元素，并將值賦給k1intc[3][5]

2c[2][4]=20//引用數(shù)組c中序號(hào)為2的行中序號(hào)為4的列的元素，并將該元素賦值為203.數(shù)組的初始化(1)直接賦初值在使用數(shù)組時(shí)，如果程序中涉及的數(shù)據(jù)簡單，程序員往往會(huì)直接給數(shù)組賦初值進(jìn)行初始化。直接賦初值進(jìn)行初始化一般有以下幾種類型。1.1.1數(shù)組1inta[5]={0,1,2,3,4}//對(duì)一維數(shù)組元素賦初值2intb[10]={0,1,2,3,4}//只給數(shù)組中一部分元素賦初值，其他元素為03intc[]={0,1,2,3,4}//初始化了一個(gè)有5個(gè)元素的數(shù)組c4intd[2][3]={{1,2,3},{0,1,2}}//分行給二維數(shù)組賦初值5inte[2][3]={{1},{0}}//給各行的第一列元素賦初值，其余元素自動(dòng)為06intf[][3]={1,2,3,0,1,2}//初始化了一個(gè)2行3列的數(shù)組f3.數(shù)組的初始化(2)循環(huán)方法在使用數(shù)組時(shí)，如果程序中涉及的數(shù)據(jù)量大且復(fù)雜，程序員會(huì)考慮用for循環(huán)進(jìn)行初始化。具體使用方法如下：1.1.1數(shù)組1inta[5]；

2for(inti=0;i<5;i++)

3{

4a[i]=I;

5}//初始化數(shù)組a，與inta[5]={0,1,2,3,4}效果相同3.數(shù)組的初始化(3)memset函數(shù)方法在使用數(shù)組時(shí)，為了優(yōu)化代碼結(jié)構(gòu)提高效率，程序員會(huì)考慮使用memset函數(shù)進(jìn)行初始化。memset包含在頭文件string.h中，函數(shù)原型為：memset(void*s,intch,size_tn)。函數(shù)解釋：將s所指向的某一塊內(nèi)存中的后n個(gè)字節(jié)的內(nèi)容全部設(shè)置為ch指定的ASCII值，第一個(gè)參數(shù)為指定的內(nèi)存地址，第三個(gè)參數(shù)指定塊的大小，這個(gè)函數(shù)通常為新申請(qǐng)的內(nèi)存做初始化工作，其返回值為s。具體用法如下：1.1.1數(shù)組1inta[5];

2memset(a,0,sizeof(int)*5);//初始化數(shù)組a[5]，將所有元素都賦為04.數(shù)組的銷毀1)循環(huán)方法同初始化一樣，利用for循環(huán)來清空數(shù)組來完成數(shù)組的銷毀。具體實(shí)現(xiàn)如下：1.1.1數(shù)組1chara[]”"aaaaaaaa";//定義字符數(shù)組2for(unsignedinti=0;i<strlen(a);i++)

3{

4 a[i]='\0';//for循環(huán)清空數(shù)組5}4.數(shù)組的銷毀2)memset函數(shù)方法數(shù)組的初始化中已經(jīng)介紹了memset函數(shù)的用法。以下是利用memset函數(shù)銷毀數(shù)組的具體實(shí)現(xiàn)：1.1.1數(shù)組1chara[]="aaaaaaaa";//定義字符數(shù)組2memset(a,0,sizeofa);//清空數(shù)組鏈表是由一個(gè)或多個(gè)包含數(shù)據(jù)域（Data）和指針域（Next）的結(jié)點(diǎn)（Node）連接而成的表結(jié)構(gòu)。數(shù)據(jù)域內(nèi)存儲(chǔ)的是元素本身的數(shù)據(jù)信息，指針域內(nèi)存儲(chǔ)的是下一個(gè)結(jié)點(diǎn)存儲(chǔ)位置信息，單個(gè)鏈表結(jié)點(diǎn)如圖1-1所示。指向鏈表的第一個(gè)結(jié)點(diǎn)為頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)表長度等附加信息。鏈表的最后一個(gè)節(jié)點(diǎn)為尾結(jié)點(diǎn)，尾結(jié)點(diǎn)指針域?yàn)榭眨∟ULL）。常見的鏈表類型有單鏈表、單向循環(huán)鏈表和雙向鏈表。1.1.2鏈表圖1-1單個(gè)鏈表結(jié)點(diǎn)結(jié)構(gòu)圖單鏈表中的每個(gè)結(jié)點(diǎn)的指針域只指向下一個(gè)結(jié)點(diǎn)，整個(gè)鏈表是無環(huán)的，如圖1-2所示1.1.2鏈表圖1-2單鏈表單向循環(huán)鏈表中，尾結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，鏈表中存在環(huán)，遍歷鏈表不會(huì)有NULL出現(xiàn)，如圖1-3所示。圖1-3單向循環(huán)鏈表雙向鏈表中的每個(gè)節(jié)點(diǎn)指針域分為前向指針（Prior）和后向指針（Next），前向指針指向該結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，后向指針則指向后一個(gè)結(jié)點(diǎn)，如圖1-4所示。圖1-4雙向鏈表1.初始化鏈表操作算法思想：在初始狀態(tài)，鏈表中沒有元素結(jié)點(diǎn)，只有一個(gè)頭結(jié)點(diǎn)，因此需要?jiǎng)討B(tài)產(chǎn)生頭結(jié)點(diǎn)，并將其后向指針置為空?？梢酝ㄟ^調(diào)用C語言的動(dòng)態(tài)分配庫函數(shù)malloc()，向系統(tǒng)申請(qǐng)結(jié)點(diǎn)，算法如下：1.1.2鏈表1intInit_L()

2{

3 LNode*H;

4 if(H=(LNode*)malloc(sizeof(LNode)))//頭結(jié)點(diǎn)5 {H->next=NULL;return1;}//設(shè)置后向指針為空6 elsereturn0;

7}1.堆棧堆棧（Stack）又稱棧，是限定僅在某一端進(jìn)行插入和刪除的特殊表結(jié)構(gòu)。允許進(jìn)行插入和刪除的一端稱為棧頂（Top），另一端則稱為棧底（Bottom）。處于棧頂位置的元素稱為棧頂元素，處于棧底位置的元素稱為棧底元素。不含任何元素的棧稱為空棧。將元素插入棧頂?shù)牟僮鹘凶鲞M(jìn)棧，將棧頂元素刪除的操作叫做出棧。圖1-5描述了堆棧的結(jié)構(gòu)，元素出棧如圖1-6所示，元素進(jìn)棧如圖1-7所示。：1.1.3堆棧和隊(duì)列圖1-5堆棧結(jié)構(gòu)圖

圖1-6出棧

圖1-7進(jìn)棧1.堆棧堆棧的基本操作除了進(jìn)棧、出棧外，還有初始化棧、判棧空、取棧頂元素、判棧滿等操作。初始條件：棧S不存在。操作結(jié)果：構(gòu)造一個(gè)空棧S。（1）初始化棧：InitStack(S)初始條件：棧S已存在且非滿。操作結(jié)果：若棧S不滿，則將元素x插入S的棧頂。（2）進(jìn)棧：Push(S,X)初始條件：棧S已存在且非空。操作結(jié)果：刪除棧S中的棧頂元素，也稱為＂退棧＂、＂刪除”或出““彈。（3）出棧：Pop(S)1.1.3堆棧和隊(duì)列2.隊(duì)列隊(duì)列（Queue）又稱隊(duì)，是限定僅在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的表結(jié)構(gòu)。允許插入的一端叫隊(duì)尾（Rear），允許刪除的一端叫隊(duì)頭（Front）。在隊(duì)尾插入數(shù)據(jù)元素的操作稱為入隊(duì)，從隊(duì)頭刪除數(shù)據(jù)元素的操作稱為出隊(duì)。這和我們?nèi)粘Ｉ钪械呐抨?duì)現(xiàn)象是一致的，比如火車站排隊(duì)買票，銀行排隊(duì)辦理業(yè)務(wù)等，都是先來的先辦理，晚來的則排在隊(duì)尾等待。1.1.3堆棧和隊(duì)列圖1-8隊(duì)列結(jié)構(gòu)圖1.樹樹（Tree）是n（n≥0）個(gè)結(jié)點(diǎn)構(gòu)成的有限集合（不妨用T表示）。當(dāng)n=0時(shí)，稱該樹為空樹（Emptytree）。當(dāng)n>0時(shí)也就是為非空樹，它有一個(gè)特殊的結(jié)點(diǎn)，稱之為該樹的根結(jié)點(diǎn)（Root），其余結(jié)點(diǎn)被分割成m個(gè)不相交的子集,,…，，其中每一個(gè)子集，又為一棵樹，分別稱之為T的子樹（Subtree）。如圖1-9所示，（a）表示只有根結(jié)點(diǎn)A的樹，（b）是由8個(gè)結(jié)點(diǎn)組成的樹，其根結(jié)點(diǎn)為結(jié)點(diǎn)A，它有3棵子樹且分別以B、C、D為根，而以B為根的子樹又可以分為2棵子樹且分別以E、F為根，以C為根的子樹又有一棵子樹且以G為根。1.1.4樹和圖圖1-9樹的示例樹有以下基本術(shù)語：1.1.4樹和圖(1)結(jié)點(diǎn)的度在樹中，結(jié)點(diǎn)擁有子樹的個(gè)數(shù)稱為結(jié)點(diǎn)的度。例如，在圖1-9(b)中，結(jié)點(diǎn)A的度為3,結(jié)點(diǎn)B的度為2，結(jié)點(diǎn)C的度為1，結(jié)點(diǎn)D的度為0。(2)樹的度樹的度是樹內(nèi)各結(jié)點(diǎn)的度的最大值。例如，在圖1-9(b)中，樹的度為3。(3)葉結(jié)點(diǎn)度為0的結(jié)點(diǎn)為葉結(jié)點(diǎn)，也稱為葉子或終端結(jié)點(diǎn)。例如，在圖1-9(b)中，結(jié)點(diǎn)D、F、G、H均為葉結(jié)點(diǎn)。二叉樹：1.1.4樹和圖二叉樹（Binarytree）是n(n≥0)個(gè)結(jié)點(diǎn)的有窮集合B與B上關(guān)系的集合R構(gòu)成的結(jié)構(gòu)。當(dāng)n=0時(shí)，稱該二叉樹為空二叉樹。當(dāng)n>0時(shí)也就是為非空二叉樹，它為包含了一個(gè)根結(jié)點(diǎn)以及兩棵不相交的、分別稱之為左子樹與右子樹的二叉樹。二叉樹有兩種特殊的形態(tài)，分別是滿二叉樹和完全二叉樹。二叉樹的遍歷：二叉樹是一種比較有用的折中方案，它進(jìn)行添加、刪除元素操作都很快，并且在查找元素方面也有很多的算法優(yōu)化，所以，二叉樹是數(shù)組和鏈表這兩種數(shù)據(jù)結(jié)構(gòu)的優(yōu)化方案，在處理大批量的動(dòng)態(tài)數(shù)據(jù)方面非常有用。二叉樹在查找元素時(shí)需要進(jìn)行遍歷，常見的遍歷方式有先序遍歷、中序遍歷和后序遍歷，下面將會(huì)詳細(xì)介紹。2.圖圖（Graph）是一種網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)，它由非空的頂點(diǎn)集合和描述頂點(diǎn)之間關(guān)系的集合組成。其形式化的定義如下：Graph=(V,E)V中的數(shù)據(jù)元素通常稱為頂點(diǎn)（Vertex），V是具有相同特性頂點(diǎn)的集合。E是兩個(gè)頂點(diǎn)之間關(guān)系——邊（Edge）的集合。1.1.4樹和圖圖1-11(a)中所有的邊都是沒有方向的，也就是說(vi,vj)和(vj,vi,)表示同一條邊，這樣的圖則稱為無向圖（undirectedgraph），無向圖里的邊都為無向邊。圖1-11(b)中所有的邊都是有方向的，也就是說<vi,vj>和<vj,vi>表示不同的邊，這樣的圖則稱為有向圖（directedgraph），有向圖里的邊都為有向邊，為了區(qū)別于無向邊，也稱為弧。有向邊<vi,vj>方向是從vi到vj，一般稱vi為弧尾（Tail）或初始點(diǎn)（initialnode），稱vj為弧頭（Head）或終端點(diǎn)（terminalnode）。1.1.4樹和圖圖1-11圖圖有以下基本術(shù)語：(1)鄰接點(diǎn)、相關(guān)邊若無向圖中的兩個(gè)頂點(diǎn)vi,vj之間存在一條邊(vi,vj)，則稱vi和vj互為鄰接點(diǎn)。同時(shí)稱邊(vi,vj)依附于頂點(diǎn)vi和頂點(diǎn)vj。邊(vi,vj)則是與頂點(diǎn)vi,和vj相關(guān)聯(lián)的邊。如圖1-11(a)無向圖G1中，與v5相關(guān)聯(lián)的邊是(v2,v5)，(v3,v5)，(v4,v5)。在有向圖中，若存在弧<vi,vj>，也稱相鄰接，但要區(qū)分弧的頭和尾。稱弧<vi,vj>與頂點(diǎn)vi和頂點(diǎn)vj相關(guān)聯(lián)。1.1.4樹和圖圖的遍歷：與樹的遍歷類似，圖的遍歷也是許多操作的基礎(chǔ)，例如，求連通分量、求最小生成樹和拓?fù)渑判虻榷家詧D的遍歷為基礎(chǔ)。1.1.4樹和圖從圖中指定的頂點(diǎn)出發(fā)，按照指定的搜索方法訪問圖的所有頂點(diǎn)且每個(gè)頂點(diǎn)僅被訪問一次，這個(gè)過程稱為圖的遍歷。圖的遍歷方法主要有兩種方法：深度優(yōu)先搜索遍歷（Depth-FirstSearch，DFS）和廣度優(yōu)先搜索遍歷（Breadth-FirstSearch，BFS）。1.1.4樹和圖(1)深度優(yōu)先搜索從圖中指定的頂點(diǎn)v出發(fā)，先訪問v，然后依次從v的未被訪問的鄰接點(diǎn)出發(fā)，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到為止。具體流程如下：連通圖的深度優(yōu)先搜索遍歷方法：a)首先訪問v，然后從v的未被訪問過的鄰接點(diǎn)中任取一個(gè)頂點(diǎn)w，訪問w；b)再從w的未被訪問過的鄰接點(diǎn)中任取一個(gè)頂點(diǎn)s，訪問s；1.1.4樹和圖(1)深度優(yōu)先搜索c)依此類推，直至一個(gè)頂點(diǎn)的所有鄰接點(diǎn)均被訪問過，則依照先前的訪問次序回退到最近被訪問過的頂點(diǎn)，若它還有未被訪問過的鄰接點(diǎn)，則從這些未被訪問過的鄰接點(diǎn)中任取一個(gè)重復(fù)以上過程，直至圖中所有頂點(diǎn)均被訪問過為止。非連通圖的深度優(yōu)先搜索遍歷方法：若是連通圖，則一次遍歷便可訪問圖中的所有頂點(diǎn)。若是非連通圖，則一次遍歷僅能訪問開始頂點(diǎn)所在連通分量中的所有頂點(diǎn)，其他連通分量中的頂點(diǎn)則無法訪問到。因此，對(duì)于非連通圖，在遍歷完一個(gè)連通分量之后，還要再選擇一個(gè)開始頂點(diǎn)，遍歷下一個(gè)連通分量，重復(fù)這個(gè)過程，直至圖中的所有頂點(diǎn)均被訪問過為止。散列表是表的特殊存儲(chǔ)形式。這種存儲(chǔ)形式體現(xiàn)不出元素之間的邏輯關(guān)系，元素完全是“孤立地、松散地”存儲(chǔ)在散列表中。散列表中進(jìn)行插入、刪除和查找等操作效率級(jí)高，因此被廣泛地應(yīng)用在程序設(shè)計(jì)中。散列表（Hashtable），也稱哈希表，是根據(jù)關(guān)鍵碼值而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過把關(guān)鍵碼值映射到表中一個(gè)位置來訪問記錄，來加快查找的速度。這個(gè)映射函數(shù)叫做散列函數(shù)，也稱哈希函數(shù)，記為H(key)，存放記錄的數(shù)組叫做散列表。在構(gòu)造散列表時(shí)，不同的關(guān)鍵字可能映射到表中同一個(gè)位置，這種現(xiàn)象稱為沖突。散列表中映射到同一位置的數(shù)據(jù)元素稱為同義詞。選擇不同的散列函數(shù)，造成沖突的情況會(huì)不同，當(dāng)然沖突是沒法完全避免的，也因此如何構(gòu)造合適的散列函數(shù)來減少?zèng)_突是編程者的重要工作。1.1.5散列表瑞士計(jì)算機(jī)科學(xué)家N.Wirth指出“程序＝數(shù)據(jù)結(jié)構(gòu)＋算法”。它描述了計(jì)算機(jī)程序是由組織信息的數(shù)據(jù)結(jié)構(gòu)和處理信息的算法組成。二者相輔相成，不可分割。1.2.1算法及性質(zhì)算法就是求解問題的一系列步驟的集合。它以一組值作為輸入，并產(chǎn)生一組值作為輸出。通常用計(jì)算機(jī)程序來實(shí)現(xiàn)算法，計(jì)算機(jī)執(zhí)行程序中的語句，實(shí)現(xiàn)對(duì)問題的求解。1.2算法算法的性質(zhì)：所有的算法都必須滿足以下性質(zhì)?？尚行裕核惴ㄖ忻枋龅牟僮鞫际怯靡呀?jīng)實(shí)現(xiàn)的基本運(yùn)算組成的。有窮性：算法必須在有限步或有限的時(shí)間內(nèi)完成。確定性：算法中每一條指令必須有確切的含義，不能有二義性。有輸入：算法應(yīng)該有零或多個(gè)輸入量。有輸出：算法應(yīng)該有一個(gè)或多個(gè)輸出量。算法的有窮性是算法和程序的分界點(diǎn)，程序并不要求在有限的步驟內(nèi)或有限的時(shí)間內(nèi)結(jié)束，比如操作系統(tǒng)，而算法卻有這個(gè)要求。。1.2算法算法的設(shè)計(jì)準(zhǔn)則：當(dāng)求解某類問題時(shí)，可能有多種算法供選擇。究竟哪個(gè)算法是“好”的算法，下面給出一些衡量準(zhǔn)則。1.2算法正確性：算法應(yīng)該達(dá)到預(yù)期的結(jié)果，滿足問題的需求。顯然，這是衡量算法的首要準(zhǔn)則。可讀性：算法應(yīng)該易于理解、易于實(shí)現(xiàn)和易于調(diào)試，以免造成歧義。健壯性：算法不但能夠處理合法數(shù)據(jù)，而且對(duì)輸入的非法數(shù)據(jù)也能夠做出反應(yīng)，不致產(chǎn)生不可預(yù)料的后果。高效性：算法執(zhí)行的時(shí)間要短（時(shí)間效率），占用的存儲(chǔ)空間要少（空間效率）。一個(gè)算法的性能優(yōu)劣往往通過算法復(fù)雜度來衡量。算法的復(fù)雜性體現(xiàn)在運(yùn)行該算法時(shí)計(jì)算機(jī)所需資源的多少上。在計(jì)算機(jī)中最重要的資源是時(shí)間資源和空間資源。因此，算法復(fù)雜度包括時(shí)間復(fù)雜度和空間復(fù)雜度兩個(gè)方面。時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量，計(jì)算工作量通常指算法執(zhí)行所需要耗費(fèi)的時(shí)間，時(shí)間越短，算法效率越高。而空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的存儲(chǔ)空間。1.2.2算法性能評(píng)價(jià)1.3本章小結(jié)算法設(shè)計(jì)實(shí)例教程教學(xué)分析目錄CONCENTS123456789第2章基礎(chǔ)算法第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第3章排序算法第4章查找第5章字符串和高精度運(yùn)算第6章圖論算法第7章動(dòng)態(tài)規(guī)劃算法第8章計(jì)算幾何基礎(chǔ)第9章高級(jí)算法2.1分治法2.1.1分治法的基本概念分治法，從字面意思理解就是分而治之，其本質(zhì)就是將一個(gè)原本規(guī)模較大的問題分解為若干規(guī)模較小且更容易求解的子問題，分別求解每個(gè)子問題，對(duì)求解出的結(jié)果進(jìn)行合并得到原問題的最終解答。第2章基礎(chǔ)算法2.1分治法2.1.1分治法的基本概念使用分治法設(shè)計(jì)算法，通常包括以下三個(gè)步驟：第2章基礎(chǔ)算法（1）分解：將要求解的問題劃分成若干規(guī)模較小的同類子問題，且每個(gè)子問題是相互獨(dú)立的；（2）求解：當(dāng)子問題的規(guī)模足夠小，能夠使用較簡單的方法解決時(shí)，對(duì)子問題進(jìn)行求解；（3）合并：合并子問題的解，構(gòu)成最終的答案時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述設(shè)有n＝2k個(gè)運(yùn)動(dòng)員要進(jìn)行網(wǎng)球循環(huán)賽?，F(xiàn)要設(shè)計(jì)一個(gè)滿足以下要求的比賽日程表：(1)每個(gè)選手必須與其他n-1個(gè)選手各賽一次；(2)每個(gè)選手一天只能賽一次；(3)循環(huán)賽一共進(jìn)行n-1天。輸入說明一個(gè)正整數(shù)n，表示參加比賽的運(yùn)動(dòng)員的數(shù)量，其中n=2K(k>0)。2.1.2分治法應(yīng)用舉例1：循環(huán)賽日程表輸出說明一個(gè)n×n的二維矩陣，其中第0列依次是每一位運(yùn)動(dòng)員的編號(hào)（運(yùn)動(dòng)員的編號(hào)從1開始），剩下的n-1列是循環(huán)賽的編排表，其中第i行第j（j>0）列的數(shù)值表示編號(hào)為i+1的運(yùn)動(dòng)員在第j天遇到的運(yùn)動(dòng)員的編號(hào)。輸入樣例8輸出樣例1234567821436587341278564321876556781234658721437856341287654321輸出說明輸入樣例輸出樣例算法分析下面我們從最簡單的情況（即，假設(shè)只有2名運(yùn)動(dòng)員）開始，分析循環(huán)賽日程表問題的結(jié)構(gòu)特征。當(dāng)只有兩位運(yùn)動(dòng)員時(shí)（即n=2），分別是：運(yùn)動(dòng)員1號(hào)和運(yùn)動(dòng)員2號(hào)，顯然他們之間只需要安排一場比賽就可以了，而這場比賽也只需要安排在第一天就可以結(jié)束，因此比賽日程安排可以用如下的一個(gè)2×2的二維矩陣A表示：2.1.2分治法應(yīng)用舉例1：循環(huán)賽日程表圖中所示，矩陣第0列的兩個(gè)元素A[0][0]和A[1][0]分別表示運(yùn)動(dòng)員的編號(hào)1號(hào)和2號(hào)，而第1列的元素值則表示第1天所有的對(duì)陣安排。其中，A[0][1]的值為2，表示1號(hào)選手在第1天遇到的是2號(hào)運(yùn)動(dòng)員，A[1][1]的值為1，表示2號(hào)選手在第1天遇到的是1號(hào)運(yùn)動(dòng)員。從這個(gè)分析，我們也可以得出一個(gè)顯然的結(jié)論，即這個(gè)日常安排表是一個(gè)對(duì)稱矩陣。當(dāng)n=4時(shí)，將有4位運(yùn)動(dòng)員參與循環(huán)賽。這4位運(yùn)動(dòng)員可以兩兩分為一組，比如1號(hào)與2號(hào)為一組，3號(hào)與4號(hào)為一組，每一組可以在同一天各自進(jìn)行循環(huán)賽。比如在比賽的第1天，在第一組是1號(hào)與2號(hào)，第二組是3號(hào)與4號(hào)比賽，因此數(shù)組的第1列的值分別為[2,1,4,3]。第二天和第三天兩組交叉運(yùn)動(dòng)員，數(shù)組的第2列的值分別為[2,1,4,3]第二天第一組的1號(hào)運(yùn)動(dòng)員分別對(duì)陣3號(hào)和4號(hào)，第二組的3號(hào)運(yùn)動(dòng)員分別對(duì)陣1號(hào)和2號(hào)。得到的日程安排表如下所示：圖2-12名運(yùn)動(dòng)員的對(duì)陣矩陣圖2-24名運(yùn)動(dòng)員的對(duì)陣矩陣通過觀察由4名運(yùn)動(dòng)員組成的比賽日程安排表，我們可以發(fā)現(xiàn)它可以分解為2個(gè)兩人組比賽日常表的組合，將矩陣右上角2×2子矩陣的值直接復(fù)制到左下角，同樣，矩陣左上角的2×2子矩陣也被復(fù)制到了右下角。由于這個(gè)4×4的矩陣具有的對(duì)稱性，我們只需要關(guān)注位于左上和右上的兩個(gè)2×2子矩陣的值的特點(diǎn)。左上的2×2子矩陣元素包括A[0][0]、A[0][1]、A[1][0]、A[1][1]，它代表的是1號(hào)運(yùn)動(dòng)員與2號(hào)運(yùn)動(dòng)員的賽程安排，填入的值分別為1、2、2、1。右上的2×2子矩陣元素包括A[0][2]、A[0][3]、A[1][2]、A[1][3]它代表的是3號(hào)運(yùn)動(dòng)員與4號(hào)運(yùn)動(dòng)員的賽程安排，填入的值分別為3、4、4、3。但是我們可以換個(gè)視角再來看這組值的特點(diǎn)，即A[0][0+2]、A[0+0][1+2]、A[1+0][0+2]、A[1+0][1+2]，它們的值分別是1+2、2+2、2+2、1+2。發(fā)現(xiàn)規(guī)律了嗎？右上子矩陣的值=左上的子矩陣+2。而這個(gè)2正是右上子矩陣相對(duì)于左上子矩陣在坐標(biāo)上的偏移量。由此，我們可以按照這樣的規(guī)律分別填寫每一個(gè)2×2子矩陣的值。2.1.2分治法應(yīng)用舉例1：循環(huán)賽日程表我們可以將該規(guī)律推廣到n=2k的情況。按照分治的策略，將所有運(yùn)動(dòng)員平均分為兩組，n個(gè)運(yùn)動(dòng)員的比賽日程表就可以通過兩個(gè)n/2個(gè)運(yùn)動(dòng)員的比賽日程表來決定。如果分解后的小組成員的數(shù)量依然大于2，則可以使用分治法繼續(xù)對(duì)運(yùn)動(dòng)員進(jìn)行分割，直到每一組都只包含兩個(gè)運(yùn)動(dòng)員，就可以直接得到一個(gè)2×2的比賽日程表。這是一個(gè)典型的可以用分治法來解決的問題。將一個(gè)原本規(guī)模為n的問題逐層分解，而且每個(gè)子問題的結(jié)構(gòu)都與原問題形式相同且相互獨(dú)立，直到子問題的解可以輕而易舉地獲得，就可以通過遞歸地解決這些子問題，然后合并各個(gè)子問題地解得到原問題的解。2.1.2分治法應(yīng)用舉例1：循環(huán)賽日程表時(shí)間限制：1000ms內(nèi)存限制：65536KB問題描述求兩個(gè)不超過200位的非負(fù)整數(shù)的積。輸入說明有兩行，每行是一個(gè)不超過200位的非負(fù)整數(shù)，沒有多余的前導(dǎo)0。輸出說明一行，即相乘后的結(jié)果。結(jié)果里不能有多余的前導(dǎo)0，即如果結(jié)果是342，那么就不能輸出為0342。輸入樣例1234567890098765432100輸出樣例12193263111263526900002.1.3分治法應(yīng)用

舉例2：大整數(shù)乘法算法分析由于編程語言提供的基本數(shù)值數(shù)據(jù)類型表示的數(shù)值范圍有限，當(dāng)兩個(gè)大數(shù)進(jìn)行相乘運(yùn)算時(shí)，很可能會(huì)超過計(jì)算機(jī)數(shù)值的表示范圍，從而導(dǎo)致計(jì)算溢出錯(cuò)誤。比如，一個(gè)longint類型數(shù)值由4個(gè)字節(jié)組成，其可以表示范圍是（-231~231-1，即-2147483648~2147483647）。當(dāng)兩個(gè)longint整型相乘，其結(jié)果最大會(huì)到達(dá)2的62次方，遠(yuǎn)遠(yuǎn)超過了longint類型能夠表示的范圍。因此，用直接的相乘運(yùn)算不能滿足較大規(guī)模的高精度數(shù)值計(jì)算，需要利用其他方法間接完成計(jì)算，于是產(chǎn)生了大數(shù)運(yùn)算。對(duì)兩個(gè)整數(shù)相乘，最直觀的方法就是列豎式。在程序中，我們可以定義兩個(gè)int類型的數(shù)組A和B，把兩個(gè)大整數(shù)按位進(jìn)行存儲(chǔ)，再把數(shù)組中的元素按照豎式的要求進(jìn)行逐位相乘得到中間結(jié)果，然后將所有的中間結(jié)果相加得到最終結(jié)果。但是這種方法的性能如何呢？我們可以計(jì)算一下它的算法復(fù)雜度。由于兩個(gè)大整數(shù)的所有數(shù)位都需要一一彼此相乘，假設(shè)整數(shù)A有m位，整數(shù)B有n位，則總共需要進(jìn)行m*n次相乘操作，即算法復(fù)雜度為O(m*n)。如果兩個(gè)大整數(shù)的位數(shù)相近，那么算法復(fù)雜度就是O(n2)。我們可以利用分治法設(shè)計(jì)找到比O(n2)復(fù)雜度更低的算法。假設(shè)需要相乘的兩個(gè)整數(shù)為：123456*54321首先將大整數(shù)按照數(shù)位平均分成高數(shù)位和低數(shù)位兩部分，如下圖所示：2.1.3分治法應(yīng)用舉例2：大整數(shù)乘法第一步，分解：將2個(gè)大整數(shù)A(n位）、B(m位)按照各自的位數(shù)分解為兩部分：AH和AL、BH和BL，其中AH表示大整數(shù)A的高位，AL表示大整數(shù)A的低位，它們的位數(shù)是n/2位；同樣的，BH表示大整數(shù)B的高位，BL表示大整數(shù)B的低位，它們的位數(shù)是m/2位。這兩個(gè)位數(shù)分別為n位和m位的大整數(shù)經(jīng)過拆分后的乘積運(yùn)算就轉(zhuǎn)換成了四個(gè)乘積運(yùn)算AH*BH、AH*BL、AL*BH、AL*BL，而每個(gè)乘數(shù)的位數(shù)變?yōu)榱嗽瓉淼囊话搿５诙?，求解子問題：繼續(xù)對(duì)每個(gè)乘法運(yùn)算進(jìn)行分解，直到分解后的乘數(shù)位數(shù)能夠直接運(yùn)算時(shí)停止分解，進(jìn)行乘法運(yùn)算并記錄結(jié)果。第三步，合并：將計(jì)算出的結(jié)果相加并回溯，求出最終結(jié)果。圖2-3大整數(shù)的分解示意圖2.2.1遞歸法的基本概念遞歸是計(jì)算機(jī)科學(xué)中一個(gè)非常基礎(chǔ)和關(guān)鍵的概念，也是我們?cè)谠O(shè)計(jì)算法時(shí)常用的基本技能。如果一個(gè)函數(shù)可以在其函數(shù)內(nèi)部調(diào)用本身，這種調(diào)用方式被稱為遞歸（recursive）。遞歸算法就是通過定義和使用遞歸函數(shù)來求解問題的計(jì)算方法。使用遞歸有時(shí)可以用簡單易理解的方式有效地解決一些復(fù)雜的問題問題，簡化代碼的編寫，提高程序的可讀性，但如果遞歸使用不當(dāng)反而會(huì)適得其反。為了使用遞歸算法，首先要設(shè)計(jì)遞歸函數(shù)。遞歸函數(shù)每次調(diào)用自身時(shí)必須要縮小計(jì)算問題的范圍，從而使得輸入變得更加精細(xì)，逐步接近問題的答案。2.2遞歸法下面通過一個(gè)例子來說明遞歸的思想。假設(shè)我們想要計(jì)算整數(shù)n的階乘n!，即計(jì)算1~n之間所有整數(shù)的乘積。比如1！=1，2!=2×1，3!=3×2×1，...，n!=n×(n-1)×(n-2)…×1。2.2遞歸法一種直觀的計(jì)算方法就是使用循環(huán)，如以下代碼所示：intF(intn){ints=1,i;if(n<=0)return0;for(i=1;i<=n;i++)s=s*i;returns;對(duì)于該問題我們也可以使用遞歸的方式加以描述，如下所示：使用遞歸方式定義的求階乘函數(shù)，如以下代碼所示：intF(intn){if(n==1)return1;returnn*F(n-1);}如上所示，要計(jì)算F(n)，要先計(jì)算F(n-1)，依次類推，這意味著每一次遞歸都通過嵌套調(diào)用函數(shù)自身來完成計(jì)算，而每次傳遞給被調(diào)用函數(shù)的參數(shù)會(huì)更接近終止條件。比如，在求解階乘的函數(shù)中，當(dāng)n==1時(shí)，該條件路徑中不再包含遞歸調(diào)用，此時(shí)就可以立刻得到本次函數(shù)調(diào)用的計(jì)算結(jié)果，我們將n==1作為遞歸調(diào)用的終止條件。F(1)完成計(jì)算后，會(huì)將計(jì)算結(jié)果通過return語句返回給調(diào)用它的F(2)，以此類推，通過函數(shù)調(diào)用的逐級(jí)返回，直到調(diào)用的起點(diǎn)就可以得到最終的答案，遞歸過程結(jié)束。。2.2遞歸法使用遞歸方式定義的求階乘函數(shù)，如以下代碼所示：intF(intn){if(n==1)return1;returnn*F(n-1);}F(5)的計(jì)算結(jié)果依賴于5*F(4)，而F(4)的結(jié)果依賴于4*F(3)，以此類推，直到F(1)，而根據(jù)函數(shù)定義，當(dāng)n==1時(shí)，函數(shù)直接返回1，因此F(1)是本輪遞歸調(diào)用的終點(diǎn)。然后函數(shù)依次帶著結(jié)果返回上一級(jí)調(diào)用，返回過程如下圖所示：2.2遞歸法下面以F(5)的計(jì)算過程為例，其函數(shù)遞歸調(diào)用的過程可以用如下的一條鏈表示：圖2-4F(5)的遞歸過程圖2-5F(5)的遞歸返回過程從上面調(diào)用和返回的過程可以看出，遞歸調(diào)用是一個(gè)先進(jìn)后出的過程，最先被調(diào)用的F(5)最后返回，而最后被調(diào)用的F(1)則最先返回。每一次函數(shù)調(diào)用的過程信息都會(huì)被系統(tǒng)自動(dòng)保存在一個(gè)叫做棧的內(nèi)存空間中，只有函數(shù)返回時(shí)，當(dāng)前函數(shù)所占用的?？臻g才會(huì)被釋放。顯然，隨著輸入?yún)?shù)n的增大，需要消耗的?？臻g也會(huì)越來越大。在現(xiàn)代計(jì)算機(jī)系統(tǒng)中，每個(gè)程序所能夠使用的?？臻g是一種有限的內(nèi)存資源，當(dāng)?？臻g消耗殆盡時(shí)，就會(huì)發(fā)生程序異常退出等嚴(yán)重錯(cuò)誤。2.2遞歸法因此，在使用遞歸策略設(shè)計(jì)遞歸算法時(shí)應(yīng)注意以下幾點(diǎn)：（2）遞歸雖然為編程提供了簡單的解決方案，但是由于每一次遞歸調(diào)用時(shí)都需要將函數(shù)的返回值、局部變量等信息保存在棧中，當(dāng)遞歸嵌套的次數(shù)太多時(shí)，有可能因?yàn)橄奶嗟膬?nèi)存而造成棧溢出錯(cuò)誤。下面通過具體的實(shí)例來分析遞歸的應(yīng)用。（1）遞歸函數(shù)每嵌套調(diào)用一次，都應(yīng)縮小求解問題的規(guī)模，直到子問題的規(guī)模小到能夠直接給出解答而不再進(jìn)行遞歸調(diào)用，稱之為遞歸結(jié)束條件；時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述編寫一個(gè)求斐波那契數(shù)列的遞歸函數(shù)，輸入n值，使用該遞歸函數(shù)，輸出如樣例輸出的斐波那契數(shù)列。輸入說明一個(gè)整型數(shù)n輸出說明題目可能有多組不同的測試數(shù)據(jù)，對(duì)于每組輸入數(shù)據(jù)，按題目的要求輸出相應(yīng)的斐波那契圖形。輸入樣例6輸出樣例0011011230112358011235813210112358132134552.2.2遞歸應(yīng)用舉例1：斐波那契數(shù)列算法分析斐波那契數(shù)列的定義如下：數(shù)列中第1個(gè)是0，第2個(gè)數(shù)是1，后續(xù)的每個(gè)數(shù)字都是其前兩個(gè)數(shù)字之和。例如，當(dāng)數(shù)列長度為6時(shí)，該數(shù)列的前6個(gè)數(shù)依次是：0、1、1、2、3、5。對(duì)于該問題，我們可以使用循環(huán)方式來實(shí)現(xiàn)，函數(shù)定義如下：longlongintfib_loop(intn){inti,tmp,num1=0,num2=1;//初始情況下，num1記錄第1項(xiàng)的值為0，num2記錄第2項(xiàng)的值為1if(n==0||n==1)returnn;//當(dāng)n為0或1時(shí)，函數(shù)直接返回結(jié)果else//否則循環(huán)計(jì)算前n-1項(xiàng)和n-2項(xiàng)for(i=0;i<n-1;i++){tmp=num1+num2;num1=num2;num2=tmp;}returntmp;}由于當(dāng)輸入?yún)?shù)為n時(shí)，函數(shù)內(nèi)部的循環(huán)體執(zhí)行了n次，所以循環(huán)算法的時(shí)間復(fù)雜度是O(n)。?，F(xiàn)在我們使用遞歸的方式來解決該問題。從代碼的表達(dá)形式上看，遞歸更能夠直接體現(xiàn)計(jì)算的本質(zhì)要求，從而簡化程序的設(shè)計(jì)?，F(xiàn)在我們要?jiǎng)?chuàng)建一個(gè)遞歸函數(shù)，當(dāng)輸入為n時(shí)，返回相應(yīng)的斐波那契數(shù)列的第n項(xiàng)數(shù)值。函數(shù)定義如下：longlongintfib_rec(intn){if(n==0||n==1)returnn;elsereturnfib_rec(n-1)+fib_rec(n-2);}從函數(shù)的定義可以看出，如果要計(jì)算數(shù)列的第n項(xiàng)，當(dāng)n為0或1時(shí)，函數(shù)能夠直接返回結(jié)果，而當(dāng)n≥2時(shí)，則只需要遞歸的調(diào)用函數(shù)自身，分別計(jì)算第n-1項(xiàng)和第n-2項(xiàng)。下面以fib_rec(5)的計(jì)算過程為例，其函數(shù)遞歸調(diào)用的過程可以用下圖表示：2.2.2遞歸應(yīng)用舉例1：斐波那契數(shù)列2.2.2遞歸應(yīng)用舉例1：斐波那契數(shù)列圖2-6F(5)的遞歸調(diào)用樹如圖所示，F(xiàn)(5)的計(jì)算結(jié)果依賴于F(3)和F(4)，而F(3)依賴于F(2)和F(1)，以此類推，得到一棵遞歸樹。其中，只有F(0)和F(1)是葉子節(jié)點(diǎn)，其他節(jié)點(diǎn)F(n)都是具有兩個(gè)子節(jié)點(diǎn)F(n-1)和F(n-2)的父節(jié)點(diǎn)。當(dāng)函數(shù)調(diào)用到達(dá)子節(jié)點(diǎn)后，遞歸調(diào)用結(jié)束，開始向父節(jié)點(diǎn)返回計(jì)算結(jié)果。在解決了生成斐波那契數(shù)列的第任意n項(xiàng)數(shù)的計(jì)算問題后，我們回到原問題的需求。該問題要求根據(jù)輸入數(shù)據(jù)n，輸出n行斐波那契數(shù)列，第1行數(shù)列長度為1，第2行長度為3，每一行都比前一行多兩個(gè)數(shù)，依次類推，第n行的長度為2*n-1。因此可以利用雙重循環(huán)依次輸出。時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述某商場正在舉辦飲料促銷活動(dòng)。每購買一瓶飲料可收集一個(gè)瓶蓋，憑3個(gè)瓶蓋可以再換一瓶該飲料，并且可以一直循環(huán)下去，但不允許賒賬。如果小明一開始購買了n瓶飲料，在不浪費(fèi)任何一個(gè)瓶蓋的情況下，盡可能地?fù)Q購，那么最后小明一共最多能得到多少瓶飲料。輸入說明一個(gè)整數(shù)n，表示最初購買的飲料數(shù)量（0<n<10000）輸出說明題目可能有多組不同的測試數(shù)據(jù)，對(duì)于每組輸入數(shù)據(jù)，輸出實(shí)際得到的飲料數(shù)。輸入樣例200300輸出樣例299449：2.2.4遞歸應(yīng)用舉例2：飲料換購2.2.4遞歸應(yīng)用舉例2：飲料換購算法分析假設(shè)小明當(dāng)前有n瓶飲料，則意味著有n個(gè)飲料瓶蓋子，若n＜3，則收集的瓶蓋數(shù)不足以進(jìn)行1次換購，因此通過換購得到的飲料數(shù)為0。若n≥3，則收集的瓶蓋數(shù)足夠參與換購，且每3個(gè)瓶蓋可以換一瓶，因此換購得到的飲料數(shù)為n/3，還余下n%3不足以參加換購，因此這一輪換購后得到的飲料瓶數(shù)為（n/3+n%3），而這正是參與下一輪的換購的飲料瓶蓋的數(shù)量。以此類推，每一輪能夠參與換購的瓶蓋數(shù)都取決于上一輪換購剩下的飲料瓶數(shù)量，而且換購的規(guī)則是一樣的，因此這是一個(gè)明顯的遞歸過程。由于每次換購都會(huì)使得剩下的飲料瓶數(shù)越來越少，因此遞歸的終止條件也很明顯，就是當(dāng)n小于3時(shí)，就不能再換購了，遞歸結(jié)束。由此，我們可以構(gòu)建一個(gè)遞歸表達(dá)式，用來計(jì)算當(dāng)飲料瓶數(shù)為n時(shí)，能夠換購得到的飲料瓶數(shù)量，如下：drink(n)用來計(jì)算當(dāng)飲料數(shù)為n時(shí)，能夠通過換購得到的新增飲料的數(shù)量。顯然，當(dāng)n小于3時(shí)，是無法換購得到任何飲料的。而當(dāng)n大于等于3時(shí)，首先可以用n個(gè)瓶蓋換得得n/3瓶飲料，然后用(n/3+n%3)個(gè)瓶蓋繼續(xù)參加下一輪的換購。時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述編寫程序，輸出前n個(gè)正整數(shù)的全排列（n<10）。輸入說明一個(gè)整數(shù)n（0<n<10）輸出說明輸出1到N的全排列。每種排列占一行，數(shù)字間無空格。排列的輸出順序?yàn)樽值湫?。輸入樣?輸出樣例1231322132313123212.2.4遞歸應(yīng)用舉例3：輸出全排列算法分析對(duì)n個(gè)有序排列的數(shù)進(jìn)行全排列輸出，可以使用遞歸的方式來解決。算法的核心是遞歸地交換元素在數(shù)列中的位置，即將每個(gè)元素放到余下n-1個(gè)元素組成的隊(duì)列最前方，然后對(duì)剩余元素進(jìn)行全排列，依次遞歸下去。比如包含3個(gè)有序數(shù)的基準(zhǔn)排列為：123首先將1放到數(shù)列開頭的位置（跟第1個(gè)元素交換），然后對(duì)原隊(duì)列中剩余的子隊(duì)列23使用遞歸的方式進(jìn)行全排列。得到結(jié)果：123;132其次將2放到最前方（跟第1個(gè)元素交換），然后排列余下的13，然后將2放回原處得到結(jié)果：213；231以此類推，直到原隊(duì)列中所有的數(shù)都作為輸出隊(duì)列的排頭進(jìn)行了全排列處理。2.3.1枚舉法的基本概念枚舉法，也稱為窮舉法或暴力求解法，是依賴于計(jì)算機(jī)的強(qiáng)大計(jì)算能力來窮盡每一種可能的情況，從而達(dá)到求解問題的目的。這種策略的效率并不高，但適用于一些沒有明顯規(guī)律可循，或者難以將問題分解為子問題的場合。枚舉法的本質(zhì)就是從所有候選答案中搜索正確的解，因?yàn)樵诮鉀Q某些問題時(shí)，可能沒有辦法按一定的規(guī)律從眾多的候選答案中找出正確的解，只能對(duì)所有的候選答案逐個(gè)進(jìn)行判斷，如果滿足要求，則找到了正確答案，否則繼續(xù)對(duì)下一個(gè)候選答案進(jìn)行判斷。由此我們可以知道，在使用窮舉算法時(shí)，如果候選答案的集合很大，那么明確候選答案的搜索范圍和搜索策略可以在一定程度上提高算法的策略，要盡可能避免做大量無效的搜索。2.3枚舉法時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述用小于等于n元去買100只雞，大雞5元/只，小雞3元/只,還有1/3元每只的一種小雞，分別記為x只,y只,z只。編程求解x,y,z所有可能解。輸入說明測試數(shù)據(jù)有多組，輸入n。輸出說明對(duì)于每組輸入,請(qǐng)輸出x,y,z所有可行解，按照x，y，z依次增大的順序輸出。輸入樣例40輸出樣例x=0,y=0,z=100x=0,y=1,z=99x=0,y=2,z=98x=1,y=0,z=99。2.3.2枚舉法應(yīng)用舉例1：百雞百錢算法分析按照窮舉法的策略，我們首先抽象出數(shù)學(xué)模型，建立方程組，設(shè)公雞為x，母雞為y,小雞為z，則三個(gè)變量滿足以下等式：雞：x+y+z=100錢：5x+3y+1/3z=100按照這個(gè)數(shù)學(xué)模型，我們可以建立一個(gè)三層的嵌套循環(huán)，依次判斷每一種可能的組合是否滿足等式的要求，代碼如下：#include<stdio.h>#include<stdlib.h>intmain(){intn;floatx,y,z;while(scanf("%d",&n)!=EOF){for(x=0;x*5<=n;x++)for(y=0;y*3<=n;y++)for(z=100;z>=0;z--)if(x*5+y*3+z/3<=n&&x+y+z==100)printf("x=%g,y=%g,z=%g\n",x,y,z);}return0;}時(shí)間限制：1000ms內(nèi)存限制：65536KB問題描述雞兔同籠,共有頭k個(gè),腳n只,求雞和兔各有多少只?輸入說明輸入兩個(gè)整數(shù)，其中k代表頭的個(gè)數(shù)，n代表腳的個(gè)數(shù)。輸出說明輸出雞的數(shù)量和兔的數(shù)量。輸入樣例1740輸出樣例雞有12只，兔有5只2.3.3枚舉法應(yīng)用舉例2：雞兔同籠問題算法分析針對(duì)這個(gè)問題，我們可以根據(jù)我們的常識(shí)（每只雞和兔子都有一個(gè)頭，雞有兩只腳，兔子有四只腳）建立一個(gè)方程組，設(shè)有x只雞，y只兔子，那么就可以利用x和y的關(guān)系建立如下等式：由于雞或者兔子的數(shù)量都不會(huì)超過k個(gè)，假設(shè)雞是x個(gè)，那兔子就是（k-x）個(gè)。我們可以把x的值依次用0~k之間的整數(shù)值逐個(gè)代入到第二個(gè)等式中加以檢驗(yàn)，符合等式成立條件的就是我們需要的答案，因此這道題可以使用枚舉法實(shí)現(xiàn)。時(shí)間限制：1000ms內(nèi)存限制：65535KB問題描述春天是鮮花的季節(jié)，水仙花就是其中最迷人的代表，數(shù)學(xué)上有個(gè)水仙花數(shù)，他是這樣定義的：“水仙花數(shù)”是指一個(gè)三位數(shù)，它的各位數(shù)字的立方和等于其本身，比如：153=1^3+5^3+3^3?，F(xiàn)在要求輸出所有在m和n范圍內(nèi)的水仙花數(shù)。輸入說明輸入數(shù)據(jù)有多組，每組占一行，包括兩個(gè)整數(shù)m和n（100<=m<=n<=999）。輸出說明對(duì)于每個(gè)測試實(shí)例，要求輸出所有在給定范圍內(nèi)的水仙花數(shù)，就是說，輸出的水仙花數(shù)必須大于等于m,并且小于等于n，如果有多個(gè)，則要求從小到大排列在一行內(nèi)輸出，之間用一個(gè)空格隔開;如果給定的范圍內(nèi)不存在水仙花數(shù)，則輸出no;每個(gè)測試實(shí)例的輸出占一行。輸入樣例100120300380輸出樣例no3703712.3.3枚舉法應(yīng)用舉例3：水仙花數(shù)2.3.3枚舉法應(yīng)用舉例3：水仙花數(shù)算法分析判斷一個(gè)數(shù)是否為水仙花數(shù)，只需要將該數(shù)的每一位依次取出，計(jì)算各位數(shù)字的立方和等于其本身。因此這道題只需要對(duì)給定范圍內(nèi)的每一個(gè)數(shù)據(jù)依次測試就可以了，如果符合要求就輸出該數(shù)。如果指定范圍內(nèi)一個(gè)水仙花數(shù)都沒有，就輸出no。代碼如下：#include<stdio.h>#include<stdlib.h>intmain(){intstart,end,i,a,b,c,flag=0;while(scanf("%d%d",&start,&end)!=EOF){flag=0;//設(shè)置一個(gè)標(biāo)志變量，值為0則表示目前還未找到水仙花數(shù)，否則值為1for(i=start;i<=end;i++){a=i/100;b=(i-a*100)/10;c=i%10;if(i==a*a*a+b*b*b+c*c*c){printf("%d",i);flag=1;}}flag?printf("\n"):printf("no\n");}return0;}時(shí)間限制：1000ms內(nèi)存限制：65535KB問題描述孿生素?cái)?shù)（也稱為孿生質(zhì)數(shù)、雙生質(zhì)數(shù)）是指一對(duì)素?cái)?shù)，它們之間相差2，它們之間的距離已經(jīng)近得不能再近了，就像孿生兄弟一樣。例如3和5，5和7，11和13，10016957和10016959等等都是孿生素?cái)?shù)。試求出給定區(qū)間的所有孿生素?cái)?shù)對(duì)。（按照第一個(gè)數(shù)的大小排序輸出）。輸入說明多組數(shù)據(jù)，每行數(shù)據(jù)兩個(gè)數(shù)a，b，代表a、b之間的區(qū)間(1<=a<=b<=1000000)輸出說明輸出區(qū)間內(nèi)所有的孿生素?cái)?shù)對(duì)。輸入樣例120輸出樣例3557111317192.3.3枚舉法應(yīng)用舉例4：孿生素?cái)?shù)2.3.3枚舉法應(yīng)用舉例4：孿生素?cái)?shù)算法分析在指定的數(shù)據(jù)范圍中尋找孿生素?cái)?shù)，可以使用枚舉法，逐一對(duì)范圍內(nèi)的數(shù)據(jù)做如下判斷：（1）這個(gè)數(shù)是否為素?cái)?shù)，（2）這個(gè)數(shù)加2是不是素?cái)?shù)？如果兩個(gè)條件都滿足，就說明它們是孿生素?cái)?shù)。那么如何判斷一個(gè)數(shù)n是否為素?cái)?shù)呢？方法一：正向判斷，凡是能被某個(gè)數(shù)整除的數(shù)都不是素?cái)?shù)，因此用整數(shù)區(qū)間[2,n-1]中的數(shù)逐一去整除n，如果都不能整除，則n是素?cái)?shù)。方法二：反向篩選，如果有某個(gè)數(shù)i，那么凡是值為i*j的數(shù)都不是素?cái)?shù)，將所有這些不是素?cái)?shù)的數(shù)標(biāo)記出來，剩下的數(shù)都是素?cái)?shù)。這種素?cái)?shù)測試方法就是著名埃拉托色尼篩選法。它是由大約公元前240年的希臘數(shù)學(xué)家埃拉托色尼設(shè)計(jì)的。（埃拉托色尼是亞歷山大城的圖書館館長，他是第一個(gè)計(jì)算出地球直徑的人。）時(shí)間限制: 1000ms內(nèi)存限制: 65535KB問題描述輸入兩個(gè)正整數(shù)，求其最大公約數(shù)。輸入說明測試數(shù)據(jù)有多組，每組輸入兩個(gè)正整數(shù)。輸出說明對(duì)于每組輸入,請(qǐng)輸出其最大公約數(shù)。輸入樣例4914輸出樣例72.3.4枚舉法應(yīng)用舉例5：最大公約數(shù)2.3.4枚舉法應(yīng)用舉例5：最大公約數(shù)算法分析能夠整除一個(gè)整數(shù)的整數(shù)稱為其的約數(shù)。比如12的約數(shù)有1、2、3、4、6和12。如果一個(gè)數(shù)既是數(shù)A的約數(shù)，又是數(shù)B的約數(shù)，稱為A，B的公約數(shù)。其中公約數(shù)中值最大的哪個(gè)整數(shù)被稱為最大公約數(shù)。方法一：枚舉法根據(jù)最大公約數(shù)的定義，可以使用枚舉法依次找到能夠同時(shí)整除兩個(gè)整數(shù)的整數(shù)，并找出其中的最大值。這個(gè)算法雖然能夠解決問題，但是效率較低，其最差情況下，算法復(fù)雜度為O(min(a,b))。方法二：歐幾里得算法（遞歸法）計(jì)算兩個(gè)整數(shù)最大公約數(shù)有一個(gè)著名的算法叫輾轉(zhuǎn)相除法。該算法是已知最古老的算法，最早被記錄在公元前300年前古希臘數(shù)學(xué)家歐幾里得的著作《幾何原本》中,所以被命名為歐幾里得算法。歐幾里得算法的計(jì)算原理基于以下定義：定理：兩個(gè)整數(shù)的最大公約數(shù)等于其中較小的那個(gè)數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。最大公約數(shù)（GreatestCommonDivisor）縮寫為GCD。gcd(a,b)=gcd(b,amodb)(不妨設(shè)a>b且r=amodb,r不為0)比如49和14，49除以14商3余7,那么49和14的最大公約數(shù)，等同于14和7的最大公約數(shù)。這樣，我們成功的把兩個(gè)較大整數(shù)之間的運(yùn)算簡化成兩個(gè)較小整數(shù)之間的運(yùn)算。以此類推，通過逐步遞歸的方式，直到兩個(gè)數(shù)之間可以直接整除，就可以得到最終的結(jié)果。遞歸方式的算法復(fù)雜度不太好算，可以近似為O(log(max(a,b)))。2.4.1貪心法的基本概念貪婪算法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪心法在求解問題時(shí)，一般都包含一系列步驟，每一步都有一組選擇，每次都選擇當(dāng)前最優(yōu)的選項(xiàng)。即，從問題的初始解開始，根據(jù)當(dāng)前已有的信息做出選擇，通過選擇局部最優(yōu)解的方式逐步逼近問題的目標(biāo)。雖然貪心法獲得的解答未必是最優(yōu)解，看似“目光短淺”，但是相比較通過窮舉所有可能而去找最優(yōu)解的方式，貪心法的效率更高。在一些情況下，貪心法能夠獲得最優(yōu)解的近似解。2.4貪心法采用貪心法求最優(yōu)化問題的算法，希望通過局部最優(yōu)的選擇達(dá)到全局最優(yōu)的選擇。我們?cè)谟龅骄唧w問題時(shí)，往往分不清對(duì)哪些問題可以用貪心算法，對(duì)哪些問題不可以用貪心算法。實(shí)際上，如果問題具有兩個(gè)特性：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，則可以用貪心算法。2.4貪心法（1）貪心選擇性質(zhì)。貪心選擇性質(zhì)指原問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇得到。應(yīng)用同一規(guī)則，將原問題變?yōu)橐粋€(gè)相似的、但規(guī)模更小的子問題，而后的每一步都是當(dāng)前最優(yōu)的選擇。這種選擇依賴于已做出的選擇，但不考慮對(duì)后續(xù)步驟的影響。因此運(yùn)用貪心算法解決的問題在程序的運(yùn)行過程中不需要回溯。當(dāng)達(dá)到算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，就停止算法，給出近似解。（2）最優(yōu)子結(jié)構(gòu)性質(zhì)。當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題是否可以用貪心算法求解的關(guān)鍵。時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述在超市購物，收銀員找零錢時(shí)，有10元、5元、2元和1元四種不同的紙幣可以選擇，收銀員需要找到一種紙幣數(shù)最少的找零錢方案。輸入說明測試數(shù)據(jù)有多組，輸入n。輸出說明對(duì)于每組輸入,請(qǐng)輸出最優(yōu)的零錢方案。輸入樣例43輸出樣例10:45:02:11:12.4.2貪心法應(yīng)用舉例1：找零錢2.4.2貪心法應(yīng)用舉例1：找零錢算法分析該問題的最優(yōu)子結(jié)構(gòu)是每次都選擇當(dāng)前小于零錢余額的最大面值的紙幣，代碼如下：intmain(){inti,money;intvalue[4]={1,2,5,10};intnum[4]={0};//記錄每種紙幣的數(shù)量while(scanf("%d",&money)!=EOF){for(i=3;i>=0;i--){num[i]=money/value[i];money=money-num[i]*value[i];}for(i=3;i>=0;i--)printf("%d:%d\n",value[i],num[i]);}return0;時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述輸入一個(gè)以字符串表示的非負(fù)整數(shù)n和一個(gè)整數(shù)k，移除這個(gè)數(shù)中的k位數(shù)字后，剩下的數(shù)字按原次序排列組成一個(gè)新的數(shù)。程序計(jì)算的結(jié)果是得到一個(gè)最小的數(shù)。提示：1≤k≤n.length≤105，除了0本身之外，n不含任何前導(dǎo)零。輸入說明第一行輸入一個(gè)整數(shù)n；第二行輸入一個(gè)整數(shù)k輸出說明輸出一個(gè)整數(shù)。輸入樣例14322193輸出樣例12192.4.3貪心法應(yīng)用舉例2：刪除K位數(shù)字算法分析現(xiàn)在以輸入1432219為例，假設(shè)k=1，即只刪除其中的一個(gè)數(shù)字，使得剩下的數(shù)按原順序組合后得到的數(shù)值最小，則結(jié)果應(yīng)為132219，即刪除4。假設(shè)k=2，刪除其中的兩個(gè)數(shù)字，則結(jié)果應(yīng)為12219，依次類推，我們發(fā)現(xiàn)最優(yōu)解就是從高位依次遍歷每一個(gè)數(shù)位，只要發(fā)現(xiàn)第一個(gè)數(shù)，它大于位于其右邊相鄰的數(shù)，就可以刪除這個(gè)數(shù)，因?yàn)閯h除之后高位減小。每一次選擇刪除一個(gè)數(shù)的時(shí)候，是在前一次刪除操作的基礎(chǔ)上進(jìn)行的，因?yàn)榱粝碌臄?shù)總是當(dāng)前最優(yōu)解，而且每一次選擇都是找到第一個(gè)左邊大于右邊的數(shù)，這符合貪心法中的最優(yōu)子結(jié)構(gòu)特征。在這個(gè)題中，局部的最優(yōu)解能夠得到最終的全局最優(yōu)解。2.5本章小結(jié)算法設(shè)計(jì)實(shí)例教程教學(xué)分析目錄CONCENTS123456789第3章排序算法第1章數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第2章基礎(chǔ)算法第4章查找第5章字符串和高精度運(yùn)算第6章圖論算法第7章動(dòng)態(tài)規(guī)劃算法第8章計(jì)算幾何基礎(chǔ)第9章高級(jí)算法排序算法是算法設(shè)計(jì)中最基本的算法之一。排序算法可以分為內(nèi)部排序和外部排序，內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄，在排序過程中需要訪問外存。常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。第3章排序算法排序算法的穩(wěn)定性：如果兩個(gè)數(shù)值相等的數(shù)，在排序前和排序后能保持兩個(gè)數(shù)在序列中前后位置順序不變的排序算法稱為穩(wěn)定排序，否則為不穩(wěn)定排序。例如，有Ai=Aj，排序前Ai在Aj的前面，排序后Ai仍然還在Aj的前面，這時(shí)候就稱為穩(wěn)定排序，否則，就稱為不穩(wěn)定排序。時(shí)間復(fù)雜度：對(duì)排序數(shù)據(jù)的總操作次數(shù)。反映當(dāng)n變化時(shí)，操作次數(shù)呈現(xiàn)什么規(guī)律?？臻g復(fù)雜度：指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所需存儲(chǔ)空間的度量，它也是數(shù)據(jù)規(guī)模n的函數(shù)。3.1排序的相關(guān)概念冒泡排序（BubbleSort）是一種簡單實(shí)用的排序算法。它是從隊(duì)列首部開始，依次比較兩個(gè)相鄰的數(shù)據(jù)，如果順序錯(cuò)誤就把它們進(jìn)行交換，直至沒有數(shù)據(jù)可以交換為止。在這個(gè)過程中，待排序的元素會(huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端，就如同水池中的氣泡最終會(huì)上浮到頂端一樣，故名“冒泡排序”。3.2冒泡排序在使用冒泡排序時(shí)，首先應(yīng)該確定是進(jìn)行升序排序還是降序排序。升序排序就是將待排列的數(shù)據(jù)按照從小到大的順序排序，當(dāng)升序排序時(shí)，需要較大的數(shù)向后“沉”，而將較小的數(shù)向前“冒”。降序排序則正好相反，它是將待排列得數(shù)據(jù)按照從大到小的順序排序，它需要較小的數(shù)向后“沉”，而將較大的數(shù)向前“冒”。第1步：比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。第2步：對(duì)每一對(duì)相鄰元素作同樣的工作，從開始第一對(duì)到結(jié)尾的最后一對(duì)。這步做完后，最后的元素會(huì)是最大的數(shù)。第3步：針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。第4步：持續(xù)每次對(duì)越來越少的元素重復(fù)步驟1~3，直到?jīng)]有任何一對(duì)數(shù)字需要比較。3.2.1冒泡排序算法描述例如，將序列“5，4，3，2，1”變成升序“1，2，3，4，5”的“冒泡排序”的示意圖如圖3.1。從圖中可以看出隨著“5”逐漸“沉”下去，“1”逐漸“冒”了上來。重復(fù)沉“4”“3”“2”“1”會(huì)冒到最頂上。3.2.1冒泡排序算法描述圖3.1冒泡原理示意【例3.1】冒泡排序時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述編寫一個(gè)程序：從鍵盤上輸入整數(shù)個(gè)數(shù)n（n<255），按照冒泡排序的思想，對(duì)n個(gè)整數(shù)進(jìn)行升序排序，最后輸出排序結(jié)果。輸入說明輸入的數(shù)據(jù)之間空一格，最后一個(gè)回車。輸出說明打印輸出的時(shí)候空一格。輸入樣例9876543210輸出樣例01234567893.2.2冒泡排序程序?qū)崿F(xiàn)舉例問題分析：首先需要建立一個(gè)int類型的數(shù)組arr存儲(chǔ)待排序數(shù)據(jù)，然后利用冒泡排序?qū)?shù)組中的數(shù)據(jù)進(jìn)行排序。如果是n個(gè)數(shù)排序，共需要n-1輪排序。這就需要建立一個(gè)循環(huán)結(jié)構(gòu)。設(shè)置一個(gè)循環(huán)控制變量i，通過控制變量i實(shí)現(xiàn)n-1輪排序。令i=1作為循環(huán)的初始條件，用“i<=n-1”作為循環(huán)控制表達(dá)式，用“i++”作為循環(huán)控制變量的改變。循環(huán)體完成數(shù)組的每輪排序比較。循環(huán)語句如下：for(i=1;i<=n-1;i++){//每輪比較的程序代碼}冒泡排序使用了兩層循環(huán)嵌套，外層循環(huán)稱為遍歷。例如，第一輪遍歷就是外層循環(huán)的第一次迭代。在每次內(nèi)層循環(huán)的迭代過程中，對(duì)列表中剩余的未排序元素進(jìn)行排序，直到最高值冒泡到最后為止。第一輪遍歷將進(jìn)行N-1次比較，第二輪遍歷將進(jìn)行N-2次比較，而每輪后續(xù)遍歷將比前一輪減少一次比較操作。當(dāng)待排序序列是有序的時(shí)候（最好情況），比較次數(shù)為n-1次，沒有數(shù)據(jù)交換，此時(shí)時(shí)間復(fù)雜度為O(n)；當(dāng)待排序序列是逆序的時(shí)候（最壞的情況），當(dāng)初始序列從大到小逆序時(shí)，需要進(jìn)行n-1趟排序，進(jìn)行n(n-1)/2次比較和交換，此時(shí)的時(shí)間復(fù)雜度為O(n2)。空間復(fù)雜度：冒泡排序只需要一個(gè)臨時(shí)變量來交換數(shù)據(jù)，所以為O(1)。3.2.3冒泡排序算法分析選擇排序(SelectionSort)是一種簡單直觀的排序算法。它的基本思想：首先在待排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

3.3選擇排序（SelectionSort）n個(gè)記錄的選擇排序可經(jīng)過n-1輪選擇排序得到有序結(jié)果。具體算法描述如下：3.3.1選擇排序算法描述第1步：待排序序列為R[1..n]，有序序列為空；第2步：第i趟排序(i=1,2,3…,n-1)開始時(shí)，當(dāng)前有序序列和無序序列（待排序列）分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無序序列中選出關(guān)鍵字最小的記錄R[k]，將它與無序序列的第1個(gè)記錄R交換，使R[1..i]和R(i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序序列和記錄個(gè)數(shù)減少1個(gè)的新無序序列；第3步：n-1趟結(jié)束，數(shù)組有序了。

例如，將序列“53，64，28，72，1”變成升序“1，28，53，64，72”的“選擇排序”的第一輪操作如圖3.3所示。從圖中可以看出隨著待排序序列中的元素“1”首先被“選擇”出來與數(shù)組下標(biāo)為0的元素“53”交換位置，然后在待排序序列“64，28，72，53”中繼續(xù)“選擇”最小的元素“28”與數(shù)組下標(biāo)為1的元素“64”交換位置，重復(fù)相同的操作，直至待排序序列完全有序。

圖3-3第一輪選擇排序示意圖3.3.1選擇排序算法描述【例3.2】選擇排序時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述編寫一個(gè)算法實(shí)現(xiàn)選擇排序思想，并將亂序數(shù)列變成升序數(shù)列。輸入說明第一行輸入數(shù)據(jù)元素的個(gè)數(shù)，第二行為待排序的數(shù)據(jù)元素，輸入的數(shù)據(jù)之間空一格，最后一個(gè)回車。輸出說明打印輸出的時(shí)候空一格，尾數(shù)后沒有空格。輸入樣例1071468952310輸出樣例12345678910

3.3.2選擇排序算法實(shí)現(xiàn)舉例3.3.2選擇排序算法實(shí)現(xiàn)舉例問題分析根據(jù)題意和選擇排序的基本思想，可以定義變量n存儲(chǔ)待排序的元素個(gè)數(shù)，然后根據(jù)第一行輸入的數(shù)值n動(dòng)態(tài)分配存儲(chǔ)空間大小arr=(int*)malloc(sizeof(int)*n)，而在選擇排序的過程中，在每一輪排序中找到數(shù)值最小的元素，并臨時(shí)存儲(chǔ)在minIdx中，直到本輪循環(huán)結(jié)束for(inti=0;i<n-1;i++){intminIdx=i;for(intj=i+1;j<n;j++){if(arr[minIdx]>arr[j]){minIdx=j;}}后把值最小元素“放”到arr[i]的位置。temp=arr[minIdx];arr[minIdx]=arr[i];arr[i]=temp;選擇排序是一種簡單直觀的排序算法，無論待排序序列是正序還是逆序，每?輪的最?（最大）值都需要?較到最后才能確定，那么，最壞情況和最好情況下都需要?較n-1次，再加上遍歷整個(gè)序列的O(n)，總的復(fù)雜度為O(n2)，平均復(fù)雜度也是O(n2)。所以，選擇排序比較適合數(shù)據(jù)規(guī)模不大的情形。空間復(fù)雜度方面，選擇排序只需要?個(gè)額外用來存放“臨時(shí)最?值”的空間，除此之外，不占用額外的內(nèi)存，所以空間復(fù)雜度為O(1)，同時(shí)，選擇排序是不穩(wěn)定排序。。

3.3.3選擇排序算法分析插入排序（Insertion-Sort）是一種簡單直觀的排序算法。它的工作原理是將未排好序的元素?個(gè)個(gè)地插?到已排好序（開始時(shí)為空）的序列中，插?時(shí)，需要與已排好序的元素進(jìn)?多次?較，直到找到合適（比前一個(gè)元素大，比后一個(gè)元素小或者比前一個(gè)元素小，比后一個(gè)元素大）的位置插?，?原來已排好序的部分元素可能需要進(jìn)?后移操作，最后形成有序序列。

3.4插入排序（InsertionSort）第4步：重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；第6步：重復(fù)步驟2~5，直到序列有序。

第5步：將新元素插入到該位置后；第2步：取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；第1步：從第一個(gè)元素開始，此時(shí)，只有一個(gè)元素，該元素可以看作已排序；第3步：如果該元素（已排序）大于新元素，將該元素移到下（后移）一位置；一般來說，插入排序一般都采用in-place在數(shù)組上實(shí)現(xiàn)。具體算法描述如下：3.4.1插入排序算法描述例如，將序列“5，4，3，2，1”變成升序“1，2，3，4，5”的“插入排序”的操作如圖3.4所示。3.4.1插入排序算法描述圖3-4插入排序示意圖【例3.4】插入排序時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述實(shí)現(xiàn)插入排序算法，并將亂序數(shù)列變成升序數(shù)列。輸入說明第一行輸入數(shù)據(jù)元素的個(gè)數(shù)，第二行為待排序的數(shù)據(jù)元素，輸入的數(shù)據(jù)之間空一格，最后一個(gè)回車。輸出說明打印輸出的時(shí)候空一格，尾數(shù)后沒有空格。輸入樣例1023846815473271450輸出樣例234152347685071843.4.2插入排序算法實(shí)現(xiàn)舉例3.4.2插入排序算法實(shí)現(xiàn)舉例算法分析定義兩個(gè)變量i和j分別的控制外層循環(huán)和內(nèi)層循環(huán)，然后依次取出待排序序列中的各個(gè)元素存儲(chǔ)在val中，用val與未排序序列中元素arr[j]比較，直到找到val的“位置”，經(jīng)過n1輪排序即可得到有序序列，核心參考代碼如下：1voidsort_array(int*arr,intn)

2{

3for(inti=1;i<n;i++){

4intval=arr[i];

5for(intj=i-1;j>=0;j--){

6if(val<arr[j]){//待插入的元素小于當(dāng)前元素的值，7arr[j+1]=arr[j];//當(dāng)前元素向后移動(dòng)一個(gè)位置8arr[j]=val;

9}

10else{

11break;

12}

13}

14}

15}空間復(fù)雜度：插入排序在實(shí)現(xiàn)上，一般采用in-place在數(shù)組上實(shí)現(xiàn)，即只需用到O(1)的額外空間，因而在從后向前掃描過程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。時(shí)間復(fù)雜度：最壞情況：當(dāng)待排序序列正好為逆序狀態(tài)，?先遍歷整個(gè)序列，然后?個(gè)個(gè)地將待插?元素放在已排序的序列最前?，之后的所有元素都需向后移動(dòng)?位，所以?較和移動(dòng)的時(shí)間復(fù)雜度都是O(n)，再加上遍歷整個(gè)序列的復(fù)雜度，總復(fù)雜度為O(n2)。最好情況：當(dāng)待排序序列正好為正序狀態(tài)，則遍歷完整個(gè)序列，當(dāng)插?元素時(shí)，只?較?次就夠了，所以時(shí)間復(fù)雜度為O(n)。平均情況：當(dāng)被插?的元素放在已排序的序列中間位置時(shí)，為平均情況，?較和移動(dòng)的時(shí)間復(fù)雜度為O(n2)，所以總的時(shí)間復(fù)雜度依然為O(n2)。穩(wěn)定性：插?排序的?較是從有序序列的末尾開始，也就是想要插?的元素和已經(jīng)有序的最?者開始?起，如果?它?則直接插?在其后?，否則?直往前找直到找到它該插?的位置。如果遇見?個(gè)和插?元素值相等的，那么插?元素把想插?的元素放在相等元素的后?。值相等元素的前后順序沒有改變，所以插?排序是穩(wěn)定的。3.4.3插入排序算法分析歸并排序是建立在歸并操作上的一種有效的排序算法。其基本思想是將已有序的子序列合并，得到完全有序的序列，即先使每個(gè)子序列有序，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為2-路歸并。歸并排序算法是基于分治策略而設(shè)計(jì)的。在被稱為劃分的第一階段中，算法將數(shù)據(jù)遞歸地分成兩部分，直到數(shù)據(jù)的規(guī)模小于定義的閾值。在被稱為歸并的第二階段中，算法不斷地進(jìn)行歸并和處理，直到得到最終的結(jié)果。3.5歸并排序（MergeSort）3.5.1歸并排序算法描述01第1步：把長度為n的輸入序列分成兩個(gè)長度為n/2的子序列；02第2步：對(duì)這兩個(gè)子序列分別采用歸并排序；03第3步：將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列。例如：將待排序序列[25,6,93,17,41,86,32,79,58]排成升序序列[6,17,25,32,41,58,79,86,93]的歸并操作如圖3.5所示。3.5.1歸并排序算法描述圖3-5歸并排序示意圖【例3.6】合并兩個(gè)序列時(shí)間限制：1000ms內(nèi)存限制：32MB問題描述輸入兩個(gè)遞增的序列，輸出合并這兩個(gè)序列后的遞增序列。輸入說明每個(gè)測試案例包括3行：第一行為1個(gè)整數(shù)n（1<=n<=1000000）表示這兩個(gè)遞增序列的長度。第二行包含n個(gè)整數(shù)，表示第一個(gè)遞增序列。第三行包含n個(gè)整數(shù)，表示第二個(gè)遞增序列。輸出說明對(duì)應(yīng)每個(gè)測試案例，輸出合并這兩個(gè)序列后的遞增序列。輸入樣例413572468輸出樣例12345678。3.5.2歸并排序算法實(shí)現(xiàn)舉例：算法分析將兩個(gè)遞增序列合并成為一個(gè)遞增序列，常規(guī)的操作是將第二個(gè)遞增追加到第一個(gè)遞增序列的后面，然后進(jìn)行冒泡排序就可以得到一個(gè)遞增序列。但是，當(dāng)問題規(guī)模增大時(shí)，時(shí)間復(fù)雜度急劇增加，本題嘗試用歸并排序思想來解決。因歸并的方法采用了分治的策略，性能大大提升，歸并排序和選擇排序一樣，性能不受輸入數(shù)據(jù)的影響，但其性能比選擇排序大大提升，因?yàn)槠鋾r(shí)間復(fù)雜度一直為O(nlogn），不過，帶來的代價(jià)是需要額外的內(nèi)存空間。時(shí)間復(fù)雜度：歸并排序的時(shí)間主要消耗在劃分序列和合并序列上，由于采?遞歸?式進(jìn)?合并，如果集合長度為n，那么劃分的層數(shù)就是logn，每一層進(jìn)行歸并操作的運(yùn)算量是n。所以，歸并排序的時(shí)間復(fù)雜度等于每一層的運(yùn)算量×層級(jí)數(shù)，即O(nlogn)，?且不管元素是否基本有序都需要進(jìn)行類似操作，所以該算法的最優(yōu)時(shí)間復(fù)雜度和最差時(shí)間復(fù)雜度及平均時(shí)間復(fù)雜度都相同?？臻g復(fù)雜度：歸并排序是需要用到額外空間的，但是每次歸并所創(chuàng)建的額外空間都會(huì)隨著方法結(jié)束而釋放，因此單次歸并操作開辟的最大空間是n。所以，歸并排序的空間復(fù)雜度是O(n)。歸并排序是穩(wěn)定排序算法。3.5.3歸并排序算法分析快速排序和冒泡排序一樣，也是交換類排序?法。其基本思想是通過一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。3.6快速排序（QuickSort）快速排序使用分治法來把一個(gè)序列分為兩個(gè)子序列。具體算法描述如下：3.6.1快速排序算法描述第1步：從數(shù)列中挑出一個(gè)元素，稱為“基準(zhǔn)”（pivot）；第2步：將所有元素比基準(zhǔn)值小的集中在基準(zhǔn)左邊（或者右邊），所有元素比基準(zhǔn)值大的集中在基準(zhǔn)的右邊（或者左邊，相同的數(shù)可以到任一邊）。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置，這個(gè)稱為分區(qū)（partition）操作；第3步：采用遞歸（recursive）思想把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序再一次進(jìn)行快速排序。第4步：重復(fù)以上過程，直到序列有序。例如：將待排序序列[59,16,83,97,21,45,3,74,68]排成升序序列[3,16,21,45,59,68,74,83,97]的快速排序的第一輪操作如圖3.6所示?？焖倥判虮闅v開始的時(shí)候是從后面j往前遍歷，當(dāng)元素值大于pivot時(shí)j--；元素值小于pivot時(shí)，j保持不變，并且將j指向的值替換i指向的值，i++；這時(shí)，i從前往后遍歷，小于pivot的值就i++；遇到大于pivot的元素時(shí)，i不變，并且將i指向的值替換j指向的值，j--，這樣交替進(jìn)行，直到