DaJiU03-問(wèn)題求解與算法2013-09-26

大學(xué)計(jì)算機(jī)--計(jì)算的思想和方法1計(jì)算機(jī)網(wǎng)絡(luò)技術(shù)及應(yīng)用》（第3版），郝興偉編著.北京：高等教育出版社課程簡(jiǎn)介課程定位核心通識(shí)課，計(jì)算機(jī)基礎(chǔ)教學(xué)公共核心基礎(chǔ)課程

授課對(duì)象

非計(jì)算機(jī)專(zhuān)業(yè)本科生教學(xué)目標(biāo)深入理解計(jì)算科學(xué)在科學(xué)研究和知識(shí)創(chuàng)新中的地位和作用。

全面培養(yǎng)個(gè)人的信息素養(yǎng)和計(jì)算思維能力。了解計(jì)算發(fā)展的基本過(guò)程，理解發(fā)展中的主要發(fā)明掌握問(wèn)題求解的一般思想和方法，理解常用的問(wèn)題求解算法。理解數(shù)據(jù)的概念，理解數(shù)據(jù)結(jié)構(gòu)的含義和作用理解計(jì)算機(jī)程序、計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的概念，理解程序編寫(xiě)和程序運(yùn)行的基本內(nèi)涵理解通信和計(jì)算機(jī)網(wǎng)路的思想，了解常用的網(wǎng)絡(luò)設(shè)備及其功能，理解主要的互聯(lián)網(wǎng)應(yīng)用了解目前計(jì)算機(jī)學(xué)科的發(fā)展前沿，體會(huì)學(xué)科交叉在科研中的價(jià)值和意義第1章緒論第2章計(jì)算與計(jì)算機(jī)第3章問(wèn)題求解與算法第4章數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)第5章計(jì)算機(jī)程序

第6章計(jì)算機(jī)網(wǎng)絡(luò)第7章計(jì)算科學(xué)前沿2大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社第3章問(wèn)題求解與算法3.1問(wèn)題與問(wèn)題求解

3.2算法與算法分析3.3算法設(shè)計(jì)及算法分類(lèi)3.4搜索問(wèn)題與查找算法3.5排序問(wèn)題及排序算法3.6網(wǎng)絡(luò)搜索問(wèn)題知識(shí)要點(diǎn)問(wèn)題，問(wèn)題求解，問(wèn)題歸約，與或圖，基元問(wèn)題，問(wèn)題求解系統(tǒng)，問(wèn)題求解策略，算法式，啟發(fā)式，問(wèn)題解決過(guò)程，抽象，數(shù)學(xué)模型，數(shù)學(xué)建模，哥尼斯堡七橋問(wèn)題

計(jì)算機(jī)求解問(wèn)題概念模型。

3大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社U3.1問(wèn)題與問(wèn)題求解人類(lèi)問(wèn)題求解的思維過(guò)程領(lǐng)域問(wèn)題及形式化描述

問(wèn)題的形式化表示問(wèn)題歸約表示問(wèn)題求解策略問(wèn)題求解系統(tǒng)抽象與數(shù)學(xué)建模計(jì)算機(jī)求解問(wèn)題模型問(wèn)題解決過(guò)程計(jì)算計(jì)問(wèn)題求解概念模型4大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社人類(lèi)問(wèn)題求解的思維過(guò)程5大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社領(lǐng)域問(wèn)題及形式化描述問(wèn)題與問(wèn)題求解問(wèn)題是指需要解決還沒(méi)有解決的事。問(wèn)題求解就是要找出解決問(wèn)題的方法，并借助于一定的工具得到問(wèn)題的答案或達(dá)到最終目標(biāo)。問(wèn)題的形式化表示問(wèn)題=｛現(xiàn)實(shí)，目標(biāo)｝題解=目標(biāo)－現(xiàn)實(shí)=｛A1，A2，…，An｝6大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社問(wèn)題歸約表示問(wèn)題歸約對(duì)于復(fù)雜的問(wèn)題，直接進(jìn)行問(wèn)題求解往往是困難的，問(wèn)題歸約就是對(duì)問(wèn)題進(jìn)行歸納和簡(jiǎn)化，從而把一個(gè)復(fù)雜問(wèn)題轉(zhuǎn)換為相對(duì)簡(jiǎn)單的問(wèn)題。三要素目標(biāo)：即問(wèn)題的初始描述。算子集：用來(lái)將給定問(wèn)題變換為若干子問(wèn)題的操作?；獑?wèn)題集：已有解或其解十分明顯可以直接描述的問(wèn)題。與或圖7大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社問(wèn)題求解策略19世紀(jì)末20世紀(jì)初，心理學(xué)家對(duì)問(wèn)題及問(wèn)題求解進(jìn)行了廣泛的研究算法式算法式是指按照邏輯來(lái)求解問(wèn)題的策略。如果問(wèn)題有解，算法式一定可以得到問(wèn)題的答案或解。例如，解一個(gè)6個(gè)字母的字謎，只要將這6個(gè)字母進(jìn)行全排列，一定可以找到這個(gè)字。為了找到這個(gè)字，最壞情況下需要嘗試720中不同的排列。常用的算法式策略有：枚舉、遞歸等方法啟發(fā)式根據(jù)以往解決問(wèn)題的經(jīng)驗(yàn)形成一些經(jīng)驗(yàn)規(guī)則。例如，計(jì)算機(jī)突然不能上網(wǎng)?？赡苁蔷W(wǎng)線沒(méi)接好，也可能是網(wǎng)絡(luò)協(xié)議問(wèn)題，或者是病毒造成的。啟發(fā)式不能保證一定得到答案。常用的啟發(fā)式策略手段目的分析順向工作逆向工作8大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社問(wèn)題求解系統(tǒng)求解問(wèn)題就是要求解一個(gè)問(wèn)題的結(jié)果，或找出一種從現(xiàn)實(shí)到目標(biāo)的行動(dòng)序列，并予以執(zhí)行。問(wèn)題求解狀態(tài)空間問(wèn)題的解活動(dòng)序列A2-A4-A69大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-1漢諾塔問(wèn)題（TowerofHanoiProblem）及其求解漢諾塔問(wèn)題（TowerofHanoiProblem）10大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社漢諾塔問(wèn)題解漢諾塔問(wèn)題（TowerofHanoiProblem）11大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社抽象與數(shù)學(xué)建模數(shù)學(xué)模型對(duì)實(shí)際問(wèn)題的數(shù)學(xué)抽象用數(shù)學(xué)符號(hào)、數(shù)學(xué)式子、程序、框圖等對(duì)實(shí)際問(wèn)題本質(zhì)屬性的抽象而又簡(jiǎn)潔的刻劃，用以描述客觀事物的特征、內(nèi)在聯(lián)系及發(fā)展和運(yùn)動(dòng)規(guī)律。數(shù)學(xué)建模（MathematicalModeling）應(yīng)用知識(shí)從實(shí)際問(wèn)題中進(jìn)行抽象、提煉出數(shù)學(xué)模型的過(guò)程稱(chēng)為數(shù)學(xué)建模12大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社哥尼斯堡七橋問(wèn)題13大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社模型的分類(lèi)按特性分靜態(tài)模型和動(dòng)態(tài)模型連續(xù)時(shí)間模型和離散時(shí)間模型非參數(shù)模型與參數(shù)化模型集中參數(shù)模型和分布參數(shù)模型隨機(jī)性模型和確定性模型線性模型和非線性模型按數(shù)學(xué)方法按應(yīng)用領(lǐng)域14大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社數(shù)學(xué)建模的基本步驟模型準(zhǔn)備模型假設(shè)模型建立模型求解模型分析模型檢驗(yàn)?zāi)Ｐ蛻?yīng)用15大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社問(wèn)題求解模型問(wèn)題解決過(guò)程16大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社計(jì)算機(jī)問(wèn)題求解概念模型問(wèn)題求解的心理學(xué)研究問(wèn)題歸約，采用分而治之等問(wèn)題求解策略，對(duì)問(wèn)題求解無(wú)論是復(fù)雜問(wèn)題，還是基元問(wèn)題，問(wèn)題求解的思想都是一樣的，即通過(guò)呈現(xiàn)問(wèn)題情景，根據(jù)我們的知識(shí)和經(jīng)驗(yàn)進(jìn)行判斷和推理，最后得到一個(gè)結(jié)果，即問(wèn)題的解。計(jì)算機(jī)問(wèn)題求解

計(jì)算機(jī)應(yīng)用系統(tǒng)17大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社第3章問(wèn)題求解與算法3.1問(wèn)題與問(wèn)題求解

3.2算法與算法分析

3.3算法設(shè)計(jì)及算法分類(lèi)3.4搜索問(wèn)題與查找算法3.5排序問(wèn)題及排序算法3.6網(wǎng)絡(luò)搜索問(wèn)題知識(shí)要點(diǎn)算法，算法描述，流程圖，N-S流程圖，偽代碼，算法分析，算法復(fù)雜性，P問(wèn)題，NP問(wèn)題，NP完全問(wèn)題，NP難度問(wèn)題，時(shí)間復(fù)雜性。

18大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社U3.2算法與算法分析算法及其描述算法的特征算法描述算法的正確性算法復(fù)雜性分析時(shí)間復(fù)雜性分析P問(wèn)題與NP問(wèn)題空間復(fù)雜性19大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法及其特征算法的概念算法（Algorithm）一詞最早出現(xiàn)在數(shù)學(xué)中，原意是關(guān)于數(shù)字的運(yùn)算法則。算法是問(wèn)題求解方法及過(guò)程的形式化描述。算法的特征確定性：算法中的每一條指令必須有確定的含義，不能產(chǎn)生二義性。可行性：算法描述的步驟在計(jì)算機(jī)上是可行的。有窮性：一個(gè)算法必須在執(zhí)行有窮步后結(jié)束，每一步必須在有窮的時(shí)間內(nèi)完成。輸入：一個(gè)算法可以有零個(gè)或多個(gè)輸入，這個(gè)取決于算法要實(shí)現(xiàn)的功能。輸出：一個(gè)算法執(zhí)行過(guò)程中或結(jié)束后要有輸出結(jié)果，或者產(chǎn)生相應(yīng)的動(dòng)作指令。20大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法描述-1自然語(yǔ)言描述算法的自然語(yǔ)言描述將問(wèn)題的求解步驟清晰的表述出來(lái)即可。在步驟描述上，要求語(yǔ)言簡(jiǎn)練，層次清晰。為表述方便，每一步可以加上標(biāo)號(hào)，例如Step1，Step2…等對(duì)于復(fù)雜的步驟，可以進(jìn)行進(jìn)一步展開(kāi)舉例21大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法的流程圖描述流程圖（FlowDiagram）由圖框和流程線組成的圖形，圖框表示各種類(lèi)型的操作，圖框中的文字和符號(hào)表示操作的內(nèi)容，流程線表示操作的先后次序。流程圖可以很好的表達(dá)順序、分支和重復(fù)邏輯，可以較好的描述數(shù)據(jù)處理、算法描述及系統(tǒng)功能描述等流程圖常用圖形符號(hào)22大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社流程圖舉例流程圖的優(yōu)點(diǎn)流程圖描述有簡(jiǎn)單直觀的特點(diǎn)，且可以很好的表達(dá)了順序、分支和重復(fù)邏輯結(jié)構(gòu)，這也是計(jì)算機(jī)程序的三種基本結(jié)構(gòu)，因此，采用流程圖來(lái)描述算法，可以很自然的將算法流程圖轉(zhuǎn)化成計(jì)算機(jī)程序。不足對(duì)于復(fù)雜的算法，流程圖的手工繪制和修改都比較麻煩23大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社N-S流程圖973年美國(guó)學(xué)者I.Nassi和B.Shneiderman提出了一種新的流程圖形式，這種流程圖完全去掉了流程線，算法的每一步都用一個(gè)矩形框來(lái)描述，把一個(gè)個(gè)矩形框按執(zhí)行的次序連接起來(lái)就是一個(gè)完整的算法描述。NS圖采用五種元素分別表達(dá)順序、條件、分支、While循環(huán)和Do-While循環(huán)，雖然去掉了流程線，但可讀性較差。24大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法的偽代碼描述偽代碼（Pseudocode）是一種介于自然語(yǔ)言和計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言（Pascal、C語(yǔ)言等）之間的文字和符號(hào)來(lái)描述算法的工具，并以編程語(yǔ)言的書(shū)寫(xiě)形式來(lái)描述算法。偽代碼不是用戶(hù)和分析師的工具，而是設(shè)計(jì)師和程序員的工具偽代碼沒(méi)有嚴(yán)格的語(yǔ)法規(guī)則，只是遵循簡(jiǎn)單的書(shū)寫(xiě)約定每一條指令占一行，指令后不跟任何符號(hào)（Pascal和C中語(yǔ)句要以分號(hào)結(jié)尾）；書(shū)寫(xiě)上的“縮進(jìn)”表示程序中的分支程序結(jié)構(gòu)，用縮進(jìn)取代傳統(tǒng)Pascal中的begin和end語(yǔ)句和C中的“{”和“}”來(lái)表示程序的塊結(jié)構(gòu)可以大大提高代碼的清晰性；同一模塊的語(yǔ)句有相同的縮進(jìn)量，次一級(jí)模塊的語(yǔ)句相對(duì)與其父級(jí)模塊的語(yǔ)句縮進(jìn)；變量名和保留字不區(qū)分大小寫(xiě)賦值語(yǔ)句用符號(hào)←表示，x←exp表示將exp的值賦給x使用與程序設(shè)計(jì)語(yǔ)言類(lèi)似的關(guān)鍵字表達(dá)循環(huán)結(jié)構(gòu)數(shù)組元素的存取有數(shù)組名后跟“[下標(biāo)]”表示，結(jié)構(gòu)變量或?qū)ο蟛捎米兞棵蠹狱c(diǎn)和域名方式訪問(wèn)25大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社舉例--輸入三個(gè)數(shù)，輸出其最大值問(wèn)題求解算法的偽代碼描述26大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法的正確性計(jì)算三角形面積算法算法的正確性層次對(duì)于一組數(shù)據(jù)能夠得出正確的結(jié)果。對(duì)于精心挑選的、苛刻的測(cè)試用例算法可以得到正確的結(jié)果。對(duì)于一切合法的輸入數(shù)據(jù)，算法得到的結(jié)果都是正確的。27大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法復(fù)雜性分析算法分析在傳統(tǒng)意義下，就是對(duì)算法進(jìn)行正確性、時(shí)間復(fù)雜性和空間復(fù)雜性的分析，從而來(lái)評(píng)價(jià)算法的優(yōu)劣，或估計(jì)算法實(shí)現(xiàn)后的運(yùn)行效果。時(shí)間復(fù)雜性分析空間復(fù)雜性分析28大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社時(shí)間復(fù)雜性分析算法的時(shí)間復(fù)雜性（TimeComplexity）是指根據(jù)該算法編寫(xiě)的程序在運(yùn)行過(guò)程中，從開(kāi)始到結(jié)束所需要的時(shí)間。從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本運(yùn)算的操作作為元操作，以該元操作重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間度量。例如，排序類(lèi)算法，用數(shù)據(jù)的比較和移動(dòng)作為元操作。一個(gè)算法中元操作重復(fù)執(zhí)行的次數(shù)與求解問(wèn)題的規(guī)模（問(wèn)題長(zhǎng)度）n呈某個(gè)函數(shù)關(guān)系T(n)定義3.1設(shè)f(n)和g(n)是從自然數(shù)集到非負(fù)實(shí)數(shù)集的兩個(gè)函數(shù)，如果存在一個(gè)自然數(shù)n0和一個(gè)常數(shù)c>0，使得n≥n0，f(n)≤cg(n)，則記為f(n)=O(g(n))，稱(chēng)g(n)是f(n)的上界；如果是n≥n0，f(n)<cg(n)，稱(chēng)g(n)是f(n)的嚴(yán)格上界，記為f(n)=o(g(n))。設(shè)T(n)是算法的執(zhí)行時(shí)間，n是問(wèn)題規(guī)模，f(n)為n的函數(shù)，若T(n)=O(f(n))，則稱(chēng)f(n)為算法的時(shí)間復(fù)雜性上界。時(shí)間復(fù)雜性通常用O(f(n))來(lái)表示算法的執(zhí)行時(shí)間與問(wèn)題長(zhǎng)度無(wú)關(guān)，則該算法的時(shí)間復(fù)雜度記為O(1)，表示常數(shù)時(shí)間復(fù)雜度29大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社舉例--算法的時(shí)間復(fù)雜性分析①語(yǔ)句（3）～（6）的運(yùn)行時(shí)間為常數(shù)時(shí)間，均為O(1),則總時(shí)間為O(1)②語(yǔ)句（2）為循環(huán)控制語(yǔ)句，執(zhí)行次數(shù)為n-i+1，每次循環(huán)執(zhí)行時(shí)間為（3）～（6)的時(shí)間，因此，總的時(shí)間為(n-i+1)·O(1)。③語(yǔ)句（1）為外重循環(huán)，執(zhí)行次數(shù)為n-1次，第i次時(shí)間消耗為(n-i+1)·O(1)因此有：30大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法時(shí)間復(fù)雜度與求解問(wèn)題長(zhǎng)度的關(guān)系常見(jiàn)算法時(shí)間復(fù)雜度假設(shè)計(jì)算機(jī)執(zhí)行一次基本操作需要的時(shí)間為1ms31大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社常見(jiàn)時(shí)間復(fù)雜度函數(shù)函數(shù)關(guān)系32大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社計(jì)算機(jī)速度對(duì)求解問(wèn)題長(zhǎng)度的影響計(jì)算機(jī)速度對(duì)求解問(wèn)題長(zhǎng)度的影響33大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社P問(wèn)題與NP問(wèn)題P問(wèn)題與NP問(wèn)題問(wèn)題求解算法的時(shí)間復(fù)雜度是該問(wèn)題實(shí)例規(guī)模n的多項(xiàng)式函數(shù)，則這種可以在多項(xiàng)式時(shí)間內(nèi)解決的問(wèn)題屬于P（Polynomial，多項(xiàng)式）類(lèi)問(wèn)題，通俗地稱(chēng)所有復(fù)雜度為多項(xiàng)式時(shí)間的問(wèn)題為易解問(wèn)題否則稱(chēng)為NP（NondeterministicPolynomial，非確定多項(xiàng)式）問(wèn)題非確定性（Non-Deterministic）問(wèn)題無(wú)法按部就班的計(jì)算得到NP問(wèn)題的分類(lèi)NP問(wèn)題，非確定性多項(xiàng)式問(wèn)題非確定問(wèn)題通常存在這樣的算法，它不能直接告訴答案是什么，但可以計(jì)算某個(gè)可能的結(jié)果是否正確。這個(gè)可以驗(yàn)證“猜算”的答案正確與否的算法，假如可以在多項(xiàng)式（polynomial）時(shí)間內(nèi)計(jì)算出來(lái)，就叫做非確定性多項(xiàng)式問(wèn)題，即NP問(wèn)題NP完全（NP-complete）問(wèn)題而如果這個(gè)問(wèn)題的所有可能答案，都是可以在多項(xiàng)式時(shí)間內(nèi)進(jìn)行正確與否的驗(yàn)算的話，就叫非確定多項(xiàng)式完全問(wèn)題，即NP-Complete問(wèn)題。NP難度（NP-hard）問(wèn)題非確定性多項(xiàng)式完全問(wèn)題可以用窮舉法得到答案，一個(gè)個(gè)檢驗(yàn)下去，最終便能得到結(jié)果。但是這樣算法的復(fù)雜程度，是指數(shù)關(guān)系，因此計(jì)算的時(shí)間隨問(wèn)題的復(fù)雜程度成指數(shù)的增長(zhǎng)，很快便變得不可計(jì)算了，這就是NP-hard問(wèn)題。34大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社NP-hard問(wèn)題舉例美國(guó)的數(shù)據(jù)加密標(biāo)準(zhǔn)DES（DataEncryptionStandard）。DES采用長(zhǎng)度為64位密鑰（實(shí)際密鑰56位，8位用于奇偶校驗(yàn)），對(duì)64位二進(jìn)制數(shù)據(jù)加密，得到64位密文數(shù)據(jù)。35大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社空間復(fù)雜性算法的空間復(fù)雜度是指算法運(yùn)行中對(duì)存儲(chǔ)空間的需求，記作：S(n)=O(f(n))交換兩個(gè)變量a和b內(nèi)的值36大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社第3章問(wèn)題求解與算法3.1問(wèn)題與問(wèn)題求解

3.2算法與算法分析3.3算法設(shè)計(jì)及算法分類(lèi)

3.4搜索問(wèn)題與查找算法3.5排序問(wèn)題及排序算法3.6網(wǎng)絡(luò)搜索問(wèn)題知識(shí)要點(diǎn)算法設(shè)計(jì)，窮舉法，遞推法，遞歸法，回溯法，迭代法，分治法，貪心法，動(dòng)態(tài)規(guī)劃法。

37大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社U3.3算法設(shè)計(jì)及算法分類(lèi)算法設(shè)計(jì)窮舉法遞推法遞歸法回溯法迭代法分治法貪心法動(dòng)態(tài)規(guī)劃法38大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法設(shè)計(jì)算法設(shè)計(jì)就是尋找問(wèn)題求解的方法，并用自然語(yǔ)言、流程圖或偽代碼等方法來(lái)描述算法的過(guò)程。時(shí)間復(fù)雜度更低，運(yùn)行效率更高的算法例如：5叉路口信號(hào)燈問(wèn)題枚舉所有的可能通路建立數(shù)學(xué)模型—圖問(wèn)題變換為圖論中的著色問(wèn)題39大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社窮舉法窮舉法，又稱(chēng)暴力算法，顧名思義就是對(duì)于要求解的問(wèn)題，列舉出問(wèn)題解空間的所有可能的情況，并逐個(gè)測(cè)試，找出符合問(wèn)題條件的解，從而得到問(wèn)題的解。通常情況是，窮舉法為一個(gè)NP難解問(wèn)題，即非確定性多項(xiàng)式難解問(wèn)題40大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-4百錢(qián)買(mǎi)百雞問(wèn)題問(wèn)題：公元5世紀(jì)末，我國(guó)古代數(shù)學(xué)家張丘建在他的《算徑》中提出了著名的“百錢(qián)買(mǎi)百雞問(wèn)題”：雞翁一，值錢(qián)五，雞母一，值錢(qián)三，雞雛三，值錢(qián)一，百錢(qián)買(mǎi)百雞，問(wèn)翁、母、雛各幾何？41大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-5：0-1背包問(wèn)題0-1背包問(wèn)題給定n種物品和一個(gè)背包，物品i的重量是Wi，其價(jià)值為Vi，背包的容量為Wm。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大？分析所謂0-1背包問(wèn)題，是指在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。采用窮舉法，將物品放入背包所有可能的情況包括放置1件,2件,3件，…，n件，共

2n-1種不同的選擇方案，對(duì)每種方案都計(jì)算一遍，再考慮背包的最大存放重量Wm，在滿足條件的情況下，計(jì)算包內(nèi)物品的總價(jià)值，求解總價(jià)值最大的情況。使用一個(gè)n位二進(jìn)制的計(jì)數(shù)器，來(lái)表示n件物品放入背包的情況，若第i位為0表示第i件物品未放入背包，為1表示第i件放入背包。所有的選擇方案正好構(gòu)成n位二進(jìn)制數(shù)的所有二進(jìn)制狀態(tài)，去掉一個(gè)全0，對(duì)應(yīng)數(shù)字1～2n-1。42大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法根據(jù)物品情況計(jì)算物品的總重量，若沒(méi)有超過(guò)包的限重，記錄此情況下的總價(jià)值，使用提高門(mén)檻法判斷此情況是否為已測(cè)試條件下總價(jià)值最大，若是則記錄下此時(shí)的總價(jià)值，從第1種情況開(kāi)始，逐個(gè)測(cè)試，直到測(cè)試完2n-1種的情況為止43大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社問(wèn)題的解空間窮舉法的基本思想就是遍歷這顆樹(shù)，枚舉所有的情況，進(jìn)行判斷，如果重量不超過(guò)W,且價(jià)值最大的方案就是問(wèn)題的解。在實(shí)際遍歷時(shí)，有很多情況是沒(méi)有意義的，此時(shí)，可以中途停止對(duì)某些不可能得到最優(yōu)解的子空間的進(jìn)一步搜索，從而提高搜索效率44大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社遞推法遞推算法是一種根據(jù)遞推關(guān)系進(jìn)行問(wèn)題求解的方法遞推關(guān)系，遞推關(guān)系可以抽象為一個(gè)簡(jiǎn)單的數(shù)學(xué)模型給定一個(gè)數(shù)的序列a0,a1,…,an,…若存在整數(shù)n0，使當(dāng)n>n0時(shí)，可以用等號(hào)（或大于號(hào)、小于號(hào)）將an與其前面的某些項(xiàng)ai（0<i<n)聯(lián)系起來(lái)，這樣的式子稱(chēng)為遞推公式，又稱(chēng)遞推關(guān)系。遞推算法基本思想是把一個(gè)復(fù)雜的龐大的計(jì)算過(guò)程轉(zhuǎn)化為簡(jiǎn)單過(guò)程的多次重復(fù)，該類(lèi)算法利用了計(jì)算機(jī)速度快和自動(dòng)化的特點(diǎn)。通過(guò)已知條件，利用特定的遞推關(guān)系可以得出中間推論，直至得到問(wèn)題的最終結(jié)果。順推法和逆推法45大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-6:斐波納契數(shù)列（FibonacciSequence）

斐波納契數(shù)列（FibonacciSequence），又稱(chēng)黃金分割數(shù)列:1、1、2、3、5、8、13、21、……遞推公式F1=0，F(xiàn)2=1，F(xiàn)n=F(n-1)+F(n-2)（n>=3，n∈N*）分析從斐波那契數(shù)列的定義可知，斐波那契數(shù)列的第1項(xiàng)為1，第2項(xiàng)也為2，遞推關(guān)系是當(dāng)前項(xiàng)等于前2項(xiàng)之和。因此，我們通過(guò)順推可以得到46大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社求斐波拉契數(shù)列的順推算法算法3-5求斐波拉契數(shù)列的順推算法//求斐波那契數(shù)列第10項(xiàng)的值并輸出f[1]=1f[2]=2n=3while(n<=10){

f[n]=f[n-1]+f[n-2]n=n+1}write(f[10])47大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-7:問(wèn)題一輛重型卡車(chē)要穿過(guò)800公里的沙漠，已知卡車(chē)每公里耗油1升，卡車(chē)總載油能力為400升，顯然卡車(chē)裝滿一次油是無(wú)法穿越沙漠的，因此卡車(chē)司機(jī)需要在沿途建立幾個(gè)儲(chǔ)油點(diǎn)，使卡車(chē)能夠順利穿越沙漠。要讓卡車(chē)以消耗最少的汽油穿越沙漠，試問(wèn)司機(jī)沿途最少需要建立幾個(gè)儲(chǔ)油點(diǎn)？每個(gè)儲(chǔ)油點(diǎn)需要存儲(chǔ)多少汽油？分析設(shè)沿途設(shè)置n個(gè)儲(chǔ)油點(diǎn)，用倒推法來(lái)解決這個(gè)問(wèn)題，從終點(diǎn)向起點(diǎn)倒推，可以逐一求出每個(gè)儲(chǔ)油點(diǎn)的位置及儲(chǔ)存量。48大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社分析（1）為了消耗最少的汽油，最后一個(gè)儲(chǔ)油點(diǎn)應(yīng)該離終點(diǎn)400公里，且此處儲(chǔ)油400升，即儲(chǔ)油點(diǎn)m=1處離終點(diǎn)dist[1]=400公里，儲(chǔ)油量oil[1]=400升。（2）為了在m=1處儲(chǔ)存400升汽油，卡車(chē)最少?gòu)膬?chǔ)油點(diǎn)m=2處開(kāi)兩趟載滿油的車(chē)到儲(chǔ)油點(diǎn)m=1處，則儲(chǔ)油點(diǎn)m=2處儲(chǔ)油量oil[2]=400*2=800升，其中，400升用于儲(chǔ)存在m=1處，400升用于從m=2到m=1處的油料運(yùn)輸。要將400生油從儲(chǔ)油點(diǎn)m=2處運(yùn)送到到儲(chǔ)油點(diǎn)m=1處，則從m=2到m=1處至少需開(kāi)兩趟，需要開(kāi)三次路程，因此有dist[2]=dist[1]+400/3公里。（3）為了在儲(chǔ)油點(diǎn)m=2處儲(chǔ)存800升汽油，卡車(chē)最少?gòu)膬?chǔ)油點(diǎn)m=3處開(kāi)三趟載滿油的車(chē)到儲(chǔ)油點(diǎn)m=2處，則儲(chǔ)油點(diǎn)m=3處儲(chǔ)油oil[3]=400*3=1200升，其中，800升用于儲(chǔ)存在m=2處，400升用于從m=3到m=2處的油料運(yùn)輸。儲(chǔ)油點(diǎn)m=3處到儲(chǔ)油點(diǎn)m=2處至少開(kāi)三趟需要開(kāi)五次路程，因此，dist[3]=dist[2]+400/5公里。（4）依次類(lèi)推，為了在m=k處儲(chǔ)存oil[k]=k*400升汽油，則儲(chǔ)油點(diǎn)m=k+1處儲(chǔ)油oil[k+1]=(k+1)*400，其中400升用于往返運(yùn)送的消耗。要在m=k處儲(chǔ)存k*400升油，從m=k+1處至m=k處至少需要k+1趟，最后一次無(wú)需返回m=k+1處，因此兩地往返最小需2(k+1)-1=2k+1次路程，則儲(chǔ)油點(diǎn)離終點(diǎn)dist[k+1]=dist[k]+400/(2*k+1)。（5）最后一個(gè)儲(chǔ)油點(diǎn)為m=n，它至起點(diǎn)的距離為800-dist[n]，儲(chǔ)油為oil[n]=n*400升，為了在m=n處儲(chǔ)n*400升汽油，卡車(chē)最少?gòu)钠瘘c(diǎn)開(kāi)n+1趟滿載車(chē)至m=n處，需要開(kāi)2(n+1)-1=2n+1次路程，總耗油量為(800-dist[n])*(2n+1)，即起點(diǎn)儲(chǔ)油量為oil[n]+(800-dist[n])*(2n+1)=n*400+(800-dist[n])*(2n+1)。49大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社儲(chǔ)油點(diǎn)部署問(wèn)題逆推算法算法3-6儲(chǔ)油點(diǎn)部署問(wèn)題逆推算法//問(wèn)題求解逆推算法k=1;

dist[1]=400;//從m=1處開(kāi)始倒推oil[1]=400;do{k=k+1;oil[k]=k*400;dist[k]=dist[k-1]+400/(2*k-1);}while(dist[k]<800)//從起始點(diǎn)開(kāi)始，依次輸出儲(chǔ)油點(diǎn)序號(hào)，距離起始點(diǎn)的距離，及儲(chǔ)油數(shù)量n=k;fork=1ton{

writeln(k,800-dist[n-k+1],oil[n-k+1])}50大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社遞歸法在問(wèn)題求解思想上，遞推是從已知條件出發(fā)，一步步的遞推出未知項(xiàng)，直到問(wèn)題的解。從思想上講，遞歸也是遞推的一種，只不過(guò)它是對(duì)待解問(wèn)題的遞推，直到把一個(gè)復(fù)雜的問(wèn)題遞推為簡(jiǎn)單的易解問(wèn)題。然后再一步步的返回去，從而得到原問(wèn)題的解。51大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-8：求斐波那契數(shù)列值的遞歸算法斐波那契數(shù)列遞推公式算法3-8求斐波那契數(shù)列遞歸算法//函數(shù)fib返回第n(n≥1)個(gè)斐波那契數(shù)列的值int

fib(intn){

if(n==1）return(1)

elseif(n==2)return(2)

elsereturn(fib(n-1)+fib(n-2))}52大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-9：Hanoi塔問(wèn)題遞歸算法要將N個(gè)盤(pán)子從第1根柱子上搬移到第3根柱子上，我們可以先把上面的N-1個(gè)盤(pán)子從第1根柱子上搬移到第2根柱子上，然后就可以把第1根柱子上最下面的盤(pán)子搬移到第3根柱子上，至于如何第1根柱子上的N-1個(gè)盤(pán)子從第1根柱子上搬移到第2根柱子上，可以先不考了。算法3-9Hanoi塔問(wèn)題遞歸算法//N為盤(pán)子數(shù)目//三根柱子分別為from，to和temp，分別表示起始柱子，目標(biāo)柱子和臨時(shí)柱子voidhanoitower(n,from,to,temp){if(n>0){//把from柱子上的n-1格盤(pán)子搬移到temp柱子上，用to柱做臨時(shí)柱子

hanoitower(n-1,from,temp,to);

movedisk(from,to);//把temp柱子上的n-1格盤(pán)子搬移到to柱子上，用from柱做臨時(shí)柱子hanoitower(n-1,temp,to,from);}}53大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社回溯法回溯法“試探－失敗返回－再試探”的問(wèn)題求解方法，例如某迷宮問(wèn)題在現(xiàn)實(shí)世界中，許多問(wèn)題不是通過(guò)確定的計(jì)算公式得到的，只能通過(guò)試探、回溯的方法來(lái)求解?；厮莘ㄔ噲D在問(wèn)題的所有解空間樹(shù)中，從根節(jié)點(diǎn)開(kāi)始，按照深度優(yōu)先的方法對(duì)樹(shù)進(jìn)行搜索。當(dāng)搜索到某一個(gè)節(jié)點(diǎn)時(shí)，判斷該節(jié)點(diǎn)是否包含在問(wèn)題的解集中，如果在，繼續(xù)深度搜索。如果不在，則回溯到該節(jié)點(diǎn)的父節(jié)點(diǎn)開(kāi)始下一個(gè)試探。如果確定了某個(gè)節(jié)點(diǎn)不在解集中，逐層向父節(jié)點(diǎn)回溯。54大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-10：八皇后問(wèn)題1850年，數(shù)學(xué)家高斯（Gauss）提出了這一問(wèn)題，即：在8×8格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。數(shù)學(xué)建模55大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社求解思路設(shè)棋盤(pán)的橫坐標(biāo)為i，縱坐標(biāo)為j。當(dāng)某個(gè)皇后占了位置(i,j)時(shí)，在這個(gè)位置的垂直方向、水平方向和對(duì)角線方向都不能再放其它皇后。定義三個(gè)整型數(shù)組：a[8]，b[15]，c[15]。數(shù)組a[8]標(biāo)識(shí)各列是否放置了皇后，如果a[j]=0，表示第j列沒(méi)有皇后，a[j]=1表示第j列已經(jīng)放置了皇后；數(shù)組b[15]標(biāo)識(shí)主對(duì)角線（左上至右下）是否放置了皇后，共15條主對(duì)角線，主對(duì)角線上格子的坐標(biāo)滿足i-j+7依次是14～0，正好對(duì)應(yīng)b[15]數(shù)組的15個(gè)元素下標(biāo)，若(i,j)位置的主對(duì)角線無(wú)皇后，則b[i-j+7]=0，有皇后則b[i-j+7]=1；數(shù)組c[15]標(biāo)識(shí)從對(duì)角線是否放置了皇后，共有15條從對(duì)角線，每條從對(duì)角線上格子的坐標(biāo)滿足i+j依次為0～14，對(duì)應(yīng)c[15]數(shù)組的15個(gè)元素下標(biāo)，如果某條從對(duì)角線上已經(jīng)有皇后，則為c[i+j]=1，否則為0。56大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法3-10八皇后問(wèn)題求解的回溯算法//試探第i個(gè)皇后，即第i行要放置的皇后位置voidqueen(inti){for(j=0;j<8;j++)//從第0列開(kāi)始從左到右依次試探可能的位置{if(a[j]==0&&b[i-j+7]==0&&c[i+j]==0)//如果無(wú)沖突

{

q[i,j]='Q';//(i,j)放皇后，即第i行的皇后放在第j列

a[j]=1;//在j列作標(biāo)記

b[i-j+7]=1;//(i,j)所在的主對(duì)角線作標(biāo)記

c[i+j]=1;//(i,j)所在的從對(duì)角線作標(biāo)記

if(i<7)queen(i+1);//如果行還沒(méi)有遍歷完，進(jìn)入下一行

else輸出當(dāng)前的擺放方案，即q數(shù)組;//當(dāng)前列擺放了皇后，要繼續(xù)試探當(dāng)前行下一個(gè)可能的位置，此時(shí)需要//將當(dāng)前列恢復(fù)為沒(méi)有擺皇后的狀態(tài)，嘗試下一個(gè)可能的擺放方案q[i,j]='*';a[j]=0;b[i-j+7]=0;c[i+j]=0;}//endif}//endfor}57大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社回溯法pk窮舉法從本質(zhì)上講，回溯法也是一種窮舉法，也是通過(guò)“枚舉－判斷”來(lái)尋找問(wèn)題的解，不同的是，窮舉法每次枚舉的都是問(wèn)題的一個(gè)完整解，而回溯法每次測(cè)試的是解的一部分。例如，在走迷宮問(wèn)題中，當(dāng)遇到岔路時(shí)，枚舉其中的一條路，來(lái)驗(yàn)證是否滿足約束條件（即查看該路是否可以通行），如果滿足，該路就加入到已有的部分解集中，從而得到更大的部分解集。如果一條路不能滿足約束條件，則選擇下一條路，如果沒(méi)有可選的路，則回溯到該岔路的上一個(gè)路口。持續(xù)該過(guò)程，直到部分解集擴(kuò)展為原問(wèn)題的一個(gè)解，即找到一條到出口的通路。利用遞歸編程，可以找出所有的問(wèn)題解。58大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社迭代法迭代法又稱(chēng)輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過(guò)程，跟迭代法相對(duì)應(yīng)的是直接法（或者稱(chēng)為一次解法），即一次性解決問(wèn)題。嚴(yán)格的講，和遞歸法一樣，迭代法是一種編程技術(shù)59大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-11：使用輾轉(zhuǎn)相除法求兩數(shù)的最大公約數(shù)

輾轉(zhuǎn)相除法，又稱(chēng)歐幾里得算法兩個(gè)整數(shù)的最大公約數(shù)（亦稱(chēng)公因子）是能夠同時(shí)整除它們的最大的正整數(shù)。60大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法3-11a求兩數(shù)的最大公約數(shù)的輾轉(zhuǎn)相除法減法實(shí)現(xiàn)算法3-11a求兩數(shù)的最大公約數(shù)的輾轉(zhuǎn)相除法減法實(shí)現(xiàn)//輾轉(zhuǎn)相除法求兩數(shù)a和b的最大公約數(shù)gint

gcd(a,b){while(a!=0&&b

!=0) {if（a>b）a=a-b /*迭代*/elseb=b-a; /*迭代*/}if(a!=0)returnaelsereturnb}61大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法3-11b求兩數(shù)的最大公約數(shù)的輾轉(zhuǎn)相除法模除實(shí)現(xiàn)算法3-11b求兩數(shù)的最大公約數(shù)的輾轉(zhuǎn)相除法模除實(shí)現(xiàn)//輾轉(zhuǎn)相除法求兩數(shù)a和b的最大公約數(shù)gint

gcd(a,b){t=a%b;while(t!=0) {a=b; /*迭代*/b=t;/*迭代*/t=a%b; }returnb}62大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-12求一元非線性方程f(x)=0的解分析求方程解最簡(jiǎn)單的方法是二分法（Bisectionmethod），又稱(chēng)二分區(qū)間法。其基本思想是：設(shè)f(x)在區(qū)間[a,b]上為連續(xù)函數(shù)，如果f(a)·f(b)<0，則f(x)在區(qū)間[a,b]上至少有一個(gè)根。如果f(x)在[a,b]是單調(diào)遞增或單調(diào)遞減的，則f(x)在區(qū)間[a,b]上只存在一個(gè)實(shí)根，63大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法3-12求方程f(x)=0在區(qū)間[a,b]內(nèi)的根的迭代算法算法3-12求方程f(x)=0在區(qū)間[a,b]內(nèi)的根的迭代算法Step1：求a，b的中點(diǎn)坐標(biāo)x=(a+b)/2。Step2：計(jì)算f(x)。Step3：若|f(x)|<ε（ε為一個(gè)指定的極小的值，控制求解精度，例如10-4），則轉(zhuǎn)Step6，否則繼續(xù)下面的迭代計(jì)算。Step4：修改有根區(qū)間

4.1若f(x)與f(a)同號(hào)，說(shuō)明x更接近方程的根，此時(shí)a←x，b不變；

4.2若f(x)與f(b)異號(hào)，此時(shí)a不變,b←x；Step5：轉(zhuǎn)Step1Step6：輸出x，即方程的近似解。Step7：結(jié)束。64大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社分治法各個(gè)擊破，分而治之（DivideandConquer）特征問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同問(wèn)題問(wèn)題分解出的各個(gè)子問(wèn)題是相互獨(dú)立的，即子問(wèn)題之間不包含公共子問(wèn)題。問(wèn)題規(guī)模縮小到一定程度時(shí)可以容易地解決問(wèn)題分解出的子問(wèn)題的解可以合并為該問(wèn)題的解65大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-13:問(wèn)題給定一個(gè)長(zhǎng)度為n的整數(shù)數(shù)組，編寫(xiě)一個(gè)求出其最大值和最小值的分治算法分析當(dāng)數(shù)組中只有1個(gè)數(shù)時(shí)，可以直接給出結(jié)果，如果有2個(gè)數(shù)時(shí)，則一次比較即可得出結(jié)果。當(dāng)n>2時(shí)，我們可以將數(shù)組分成兩個(gè)元素個(gè)數(shù)較小的數(shù)組，分別求解他們的最大和最小值，最后比較兩個(gè)數(shù)組的解來(lái)得到原問(wèn)題的解66大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社求數(shù)組中最大最小值的分治算法//a[0..n]：數(shù)組，s：子問(wèn)題數(shù)組開(kāi)始下標(biāo)，e：子問(wèn)題數(shù)組結(jié)束下標(biāo)//max：數(shù)組中元素的最大值，min：數(shù)組中元素的最小值maxmin(a,s,e,*max,*min){if(e-s<=1){//只有一個(gè)元素，或兩個(gè)元素，和全局的最大、最小值比較，以便更新if(a[s]>a[e]){if(a[s]>*max)*max=a[s];if(a[e]<*min)*min=a[e];}else{if(a[e]>*max)*max=a[e];if(a[s]<*min)*min=a[s];}return;}//當(dāng)n>2時(shí)，將數(shù)組從中間一分為二，變成兩個(gè)規(guī)模減半的子問(wèn)題，遞歸求解i=s+(e-s)/2;maxmin(a,s,i,*max,*min);maxmin(a,i+1,e,*max,*min);}67大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社貪心法貪婪法的基本思想是：從當(dāng)前情況出發(fā)根據(jù)某個(gè)優(yōu)化目標(biāo)做最優(yōu)選擇，而不考慮各種可能的整體情況，從而避免了為找最優(yōu)解要窮盡所有可能的問(wèn)題求解方法。在貪心算法中，選取一個(gè)量度標(biāo)準(zhǔn)作貪婪處理所得到該量度意義下的最優(yōu)解并不一定是問(wèn)題的最優(yōu)解，可能是次優(yōu)解。68大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-14：用貪心法求解0-1背包問(wèn)題分析：求解0-1背包問(wèn)題，采用窮舉法可以找到最優(yōu)解，但時(shí)間復(fù)雜度為O(2n)，是一個(gè)NP難解問(wèn)題。貪心算法的基本思路：為了使包內(nèi)物品的總價(jià)值最大，先計(jì)算出所有物品的單位價(jià)值，然后從單位價(jià)值由高到低的順序依次選擇物品放入背包，在不超過(guò)背包限重的情況下盡可能放更多的物品。按局部貪心的方法，各物品單位價(jià)值從高到低分別6、2、7、4、5、3、1，選取物品6、物品2、物品7、物品1，總重量恰好100，總價(jià)值為120。而事實(shí)上這并不是最優(yōu)解，最優(yōu)解是物品6、物品2、物品4，總重量雖然為90，但總價(jià)值是130。

69大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-15:用貪心法求背包問(wèn)題背包問(wèn)題與0-1背包問(wèn)題類(lèi)似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。背包問(wèn)題與0-1背包問(wèn)題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問(wèn)題可以用貪心算法求得最優(yōu)解，而0-1背包問(wèn)題用貪心算法求得的解則不一定是最優(yōu)解。貪心法求背包問(wèn)題的基本思想：首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)Wmax，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。70大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法3-15求解背包問(wèn)題的貪心算法Knapsack(n,maxweight,v[],w[],x[]){Sort(n,v,w);//對(duì)物品按照Vi/Wi由大到小排序for(i=0;i<n;i++)

x[i]=0;c=maxweight;for(i=0;i<n;i++){if(w[i]>c)break;//物品i不能完全放入背包，則退出x[i]=1;//將物品i放入背包c(diǎn)-=w[i];}if(i<=n-1)x[i]=c/w[i];//將物品i的部分放入背包，正好填滿背包}71大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社動(dòng)態(tài)規(guī)劃法多階段決策問(wèn)題把一個(gè)問(wèn)題看作是一個(gè)前后關(guān)聯(lián)具有鏈狀結(jié)構(gòu)的多階段過(guò)程就稱(chēng)為多階段決策過(guò)程，這種問(wèn)題就稱(chēng)為多階段決策問(wèn)題。72大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社動(dòng)態(tài)規(guī)劃（DynamicProgramming）方法用于求解包含重疊子問(wèn)題的最優(yōu)化問(wèn)題的方法。其基本思想是，將原問(wèn)題分解為若干個(gè)子問(wèn)題，求解每個(gè)子問(wèn)題，從這些子問(wèn)題的解得到原問(wèn)題的解。適用動(dòng)態(tài)規(guī)劃的問(wèn)題必須滿足最優(yōu)化原理和無(wú)后效性原則。最優(yōu)化原理無(wú)后向性,每個(gè)狀態(tài)都是過(guò)去歷史的一個(gè)完整總結(jié)

73大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社例3-16:求解0-1背包問(wèn)題的動(dòng)態(tài)規(guī)劃算法分析：0-1背包問(wèn)題是一種經(jīng)典的NP-hard組合優(yōu)化問(wèn)題對(duì)于0-1背包問(wèn)題，他具有典型的最優(yōu)子結(jié)構(gòu)性質(zhì)和子問(wèn)題重疊性質(zhì)，因此，可以使用動(dòng)態(tài)規(guī)劃法求解74大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社動(dòng)態(tài)規(guī)劃法與貪心算法和分治法的異同點(diǎn)動(dòng)態(tài)規(guī)劃和貪心算法的相同點(diǎn)是都將一個(gè)問(wèn)題的解決方案視為一系列決策的結(jié)果。不同點(diǎn)的是，在貪心算法中，貪心選擇通常自低向上進(jìn)行，每采用一次貪心選擇便做出一個(gè)不可撤回的決策；而在動(dòng)態(tài)規(guī)劃中，還要考察每個(gè)最優(yōu)決策序列中是否包含一個(gè)最優(yōu)子序列，動(dòng)態(tài)規(guī)劃算法通常自頂向下的方式進(jìn)行，以迭代的方式做相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。動(dòng)態(tài)規(guī)劃算法與分治法類(lèi)似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這些子問(wèn)題的解得到原問(wèn)題的解。與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題，經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的。若用分治法來(lái)解這類(lèi)問(wèn)題，則分解得到的子問(wèn)題數(shù)目太多，有些子問(wèn)題被重復(fù)計(jì)算了很多次，這就早造成了大量的時(shí)間消耗。動(dòng)態(tài)規(guī)劃法的基本思路是用一個(gè)表來(lái)記錄所有已解的子問(wèn)題的答案，不管該子問(wèn)題以后是否被用到，只要它被計(jì)算過(guò)，就將其結(jié)果填入表中。在需要時(shí)再找出已求得的答案，這樣就可以避免大量的重復(fù)計(jì)算。75大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社第3章問(wèn)題求解與算法3.1問(wèn)題與問(wèn)題求解

3.2算法與算法分析3.3算法設(shè)計(jì)及算法分類(lèi)3.4搜索問(wèn)題與查找算法

3.5排序問(wèn)題及排序算法3.6網(wǎng)絡(luò)搜索問(wèn)題知識(shí)要點(diǎn)搜索，關(guān)鍵字，主關(guān)鍵字，次關(guān)鍵字，順序查找，折半查找，平均查找長(zhǎng)度。

76大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社U3.4搜索問(wèn)題與查找算法搜索問(wèn)題順序查找折半查找77大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社搜索問(wèn)題搜索（Search），就是指仔細(xì)查找、搜尋的意思搜索的對(duì)象搜索的范圍基本概念文件記錄字段關(guān)鍵字主關(guān)鍵字搜索問(wèn)題給定一個(gè)文件（或表）F={R1,R2,…,Rn}，其中Ri是以Ki（i=1,2,…,n）為主關(guān)鍵字的記錄?，F(xiàn)給定一個(gè)主關(guān)鍵字K，在文件F中確定具有主關(guān)鍵字K的記錄R的地址或序號(hào)i，使得Ki=K。結(jié)果有兩種可能：一種是找到了主關(guān)鍵字值為K的記錄Ri，稱(chēng)為查找成功；第二種情況是，沒(méi)有找到主關(guān)鍵字值為K的記錄，稱(chēng)為“查找失敗”。78大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社順序查找順序查找就是在要查找范圍內(nèi)，對(duì)一個(gè)個(gè)對(duì)象進(jìn)行比較，看是否是需要查找的對(duì)象基本步驟從最后一條記錄開(kāi)始，按照記錄的邏輯次序，將給定的關(guān)鍵字K和當(dāng)前記錄的關(guān)鍵字逐個(gè)比較，若某個(gè)記錄的關(guān)鍵字和給定值相等，則查找成功，返回成功記錄的序號(hào)；反之，直到比較完第一條記錄，找不到與給定值相等的記錄，則查找失敗，返回查找失敗標(biāo)記。79大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法3-17線性表順序查找算法//在線性表st中查找關(guān)鍵字k，n為元素個(gè)數(shù)，//若查找成功，返回其在表中的序號(hào)，否則返回0int

SearchSequential(st[],n,k){st[0]=k;//設(shè)置“哨兵”

i=n;while(st[i]!=k)i--;returni;}80大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法分析平均查找長(zhǎng)度81大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社折半查找文件（或表）中的記錄是按照關(guān)鍵字有序的，假定關(guān)鍵字值滿足K1≤K2≤…≤Kn，折半查找的基本思想首先選取表的中間元素，設(shè)序號(hào)為m=

(1+n)/2

，元素Rm將數(shù)據(jù)表分成大致相等的兩部分{R1,R2,…,Rm-1}和{Rm+1,Rm+2,…,Rn}。先對(duì)Km和K作比較，比較結(jié)果有三種情況：（1）K=Km：查找成功，返回元素序號(hào)m。（2）K<Km：折半查找子表{R1,R2,…,Rm-1}。（3）K=Km：折半查找子表{Rm+1,Rm+2,…,Rn}。82大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法3-18線性表折半查找算法//在線性表st中折半查找關(guān)鍵字k，若成功返回其在表中的位置，否則返回0int

Serach_Binary(st[],n,k){low=1;high=n;while(low<=high){m=(low+high)/2;if(k==st[m])returnm;elseif(k>st[m])low=m+1;elsehigh=m-1;}return0;}83大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法分析二叉檢索樹(shù)的高度（層數(shù)）和元素的數(shù)目n滿足關(guān)系84大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社第3章問(wèn)題求解與算法3.1問(wèn)題與問(wèn)題求解

3.2算法與算法分析3.3算法設(shè)計(jì)及算法分類(lèi)3.4搜索問(wèn)題與查找算法3.5排序問(wèn)題及排序算法

3.6網(wǎng)絡(luò)搜索問(wèn)題知識(shí)要點(diǎn)排序，穩(wěn)定排序，內(nèi)部排序，選擇排序，交換排序，插入排序，歸并排序，基數(shù)排序，外部排序。

85大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社U3.5排序問(wèn)題及排序算法排序問(wèn)題選擇排序交換排序插入排序歸并排序基數(shù)排序86大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社排序問(wèn)題排序（Sorting），就是把任意文件（或表）按照指定的關(guān)鍵字排列成一個(gè)有序文件（或表）的過(guò)程，有時(shí)又稱(chēng)作“分類(lèi)”。假如給定一個(gè)記錄序列（或表）F={R1,R2,…,Rn}，其中Ri（i=1,2,…,n）為序列中的第i個(gè)記錄，關(guān)鍵字為Ki。所謂排序就是對(duì)記錄序列中的記錄重新排序成一個(gè)新的序列F‘={R1’,R2‘,…,Rn’}，使得它們的關(guān)鍵字值滿足非減（或非增）的順序。即對(duì)任意的i<j（i,j=1,2,…,n），有Ki‘

Kj’（或Ki‘

Kj’）?；靖拍罘€(wěn)定排序：當(dāng)初始時(shí)序列中Ki=Kj，且i<j時(shí)，排序后記錄Ri仍然在記錄Rj前，這樣的排序稱(chēng)為穩(wěn)定排序。內(nèi)部排序：是指被排序的記錄較少，在整個(gè)排序過(guò)程中，所有的記錄和中間結(jié)果都放在內(nèi)存中。外部排序：當(dāng)被排序的記錄數(shù)量較大時(shí)，記錄不能一次全部放在內(nèi)存中，在整個(gè)排序過(guò)程中，必須對(duì)記錄在內(nèi)存和外存之間來(lái)回傳遞和交換87大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社選擇排序基本思想：從被排序的文件（或表）中依次選出關(guān)鍵字最小、次小、…的記錄，從而實(shí)現(xiàn)排序。選擇分類(lèi)包括：簡(jiǎn)單選擇排序、樹(shù)形選擇排序（錦標(biāo)賽排序）和堆排序（HeapSorting）等簡(jiǎn)單選擇排序從1..n個(gè)記錄中選出關(guān)鍵字最小的記錄，和R1交換，最小的記錄放到第1個(gè)單元。從2..n個(gè)記錄中選出關(guān)鍵字最小的記錄，和R2交換，次小的記錄放到第2個(gè)單元。88大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法3-19簡(jiǎn)單選擇排序算法//對(duì)表f進(jìn)行簡(jiǎn)單選擇排序，n為元素個(gè)數(shù)int

SimpleSelectionSort(*f,n){for(i=1;i<n;i++){j=SelectionMin(f,i,n);//從i..n個(gè)元素中選擇最小的元素，序號(hào)為jif(i!=j)f[i]<—>f[j]}}89大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法分析簡(jiǎn)單選擇排序，共進(jìn)行n-1遍，每一遍從n-i+1個(gè)數(shù)中選擇一個(gè)最小的數(shù)。從n-i+1個(gè)數(shù)中選擇最小的數(shù)需要n-i次比較運(yùn)算，因此簡(jiǎn)單選擇排序總的比較次數(shù)為n(n-1)/2。時(shí)間復(fù)雜度為O(n2)。在選擇排序中，樹(shù)形選擇排序（錦標(biāo)賽排序）和堆排序（HeapSorting）是兩種性能較好的排序方法，時(shí)間復(fù)雜度為O(nlog2n)90大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社交換排序交換類(lèi)排序（ExchangeSorting）就是將兩兩元素進(jìn)行比較，如果發(fā)生逆序，即Ri>Rj（i<j），則將兩個(gè)元素交換，最后得到一個(gè)非遞減的序列（正序）。交換分類(lèi)有標(biāo)準(zhǔn)交換、成對(duì)交換和穿梭交換三種，比較著名的交換類(lèi)排序包括冒泡排序和快速排序。91大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社冒泡排序冒泡排序（BubblesSorting）屬于標(biāo)準(zhǔn)的交換分類(lèi)基本思想第1遍：首先將Rn和Rn-1進(jìn)行比較，若發(fā)生逆序，則交換；否則，比較Rn-1和Rn-2，直到R2和R1比較。這樣，第一遍結(jié)束后，將把關(guān)鍵值最小的元素移到了第一個(gè)單元。最小的元素就像“氣泡”一樣冒到了頂上，共比較n-1次。第2遍：和第1遍一樣，依次將Rn和Rn-1進(jìn)行比較、Rn-1和Rn-2，直到R3和R2比較。這樣，第2遍結(jié)束后，將把關(guān)鍵值次小的元素移到了第2個(gè)單元。共比較n-2次繼續(xù)上述過(guò)程，逐遍進(jìn)行，在進(jìn)行i遍時(shí)，在前i-1遍得到的結(jié)果中，Rn,Rn-1,Rn-2,…,Ri+1和Ri依次兩兩比較，如發(fā)生逆序，則交換位置。92大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法3-20冒泡排序（BubblesSorting）算法//對(duì)表f進(jìn)行冒泡排序，n為元素個(gè)數(shù)int

BubbleSort(*f,n){for(i=1;i<n;i++){flag=True;for(j=n;j>i;j--){if(f[j].key<f[j-1].key)//若逆序，則交換{temp=f[j-1];f[j-1]=f[j];

f[j]=temp;}if(flag)break;}}}93大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法分析在最好的情況下（原始序列即為非遞增有序）則整個(gè)排序共進(jìn)行一遍，比較n-1次。在最壞情況下，需要比較n-1遍，比較的次數(shù)分別是n-1,n-2,…3,2,1，總的比較次數(shù)C為：94大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社快速排序快速排序（QuickSorting）方法是由C.A.R.Hoare于1962年提出的，后來(lái)又有許多人提出了修正方案，這類(lèi)方法統(tǒng)稱(chēng)為快速排序（分類(lèi)）基本思想按照一定原則選擇某個(gè)元素作為控制記錄（軸元素），首先把控制元素移動(dòng)到其正確的位置，使得元素序列中所有比它小的元素都在它的前面，所有比它大的元素都在它的后面。按照同樣的原則處理左右兩個(gè)子序列，控制記錄不再移動(dòng)位置。95大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社Hoare最早提出的方案（1）選取中心記錄作為控制記錄，如序列中第一個(gè)記錄的序號(hào)為l,最后一個(gè)記錄的序號(hào)為u，則選取第m=

(l+u)/2

個(gè)記錄作為控制記錄。（2）從第一個(gè)記錄開(kāi)始自左向右搜索比控制記錄大的記錄（用指針i標(biāo)出）；從最后一個(gè)記錄開(kāi)始自右向左搜索比控制記錄小的記錄（用指針j標(biāo)出）；若i<j，交換Ri和Rj。繼續(xù)搜索，直到j(luò)<i為止。（3）j<i，停止搜索。此時(shí)，如果j

m，則控制記錄Rm和Rj交換位置（即j所標(biāo)記位置位軸元素的正確位置）；否則，即j<m，則Rm和Ri交換位置（即i所標(biāo)記位置位軸元素的正確位置）。這樣，Rm被放到了其正確的位置。（4）Rm把原序列分成左右兩個(gè)子序列，對(duì)兩個(gè)子序列，再按照上述過(guò)程處理，直到被分成的子序列的長(zhǎng)度都為1，整個(gè)排序過(guò)程結(jié)束。96大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社舉例設(shè)元素序列為｛2，5，8，3，7，10，4｝，快速排序過(guò)程如下97大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社插入排序插入排序（InsertSorting），是指將一個(gè)記錄插入到一個(gè)已經(jīng)排序好的有序序列中，從而得到一個(gè)新的、記錄個(gè)數(shù)加1的有序序列?；舅枷耄?）初始序列為｛R1｝，只有一個(gè)元素的序列一定是有序的。（2）然后，依次將R2，R3，…，Rn插入到上次的有序序列中，分別得到長(zhǎng)度為2,3,..,n的有序序列，從而實(shí)現(xiàn)長(zhǎng)度為n的記錄序列的排序。98大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法3-22插入排序算法//對(duì)順序表f作直接插入排序，n為元素個(gè)數(shù)int

InsertSort(*f){for(i=2;i<=n;i++)

InsertR(f,i-1,f[i]);}//將記錄r插入到長(zhǎng)度為i的有序表中，得到長(zhǎng)度為i+1的有序表int

InsertR(*f,inti,r){f[0]=r；//設(shè)置“哨兵”，元素從1號(hào)位置開(kāi)始存放

j=i;while(r<f[j]){f[j+1]=f[j];//元素后移一個(gè)位置

j--;}f[j+1]=r;}99大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法分析最好情況原始記錄序列本身是非遞減有序的（稱(chēng)為“正序”），則在插入過(guò)程（Insert過(guò)程）中只進(jìn)行一次比較，不發(fā)生數(shù)據(jù)的移動(dòng)，因此，總的比較次數(shù)為n-1次，數(shù)據(jù)移動(dòng)的次數(shù)為0。在最壞情況如果原始記錄序列是非遞增有序的（稱(chēng)為“逆序”），則在插入記錄Ri過(guò)程（Insert過(guò)程）中需進(jìn)行i+1次比較（包括一次和“哨兵”的比較），數(shù)據(jù)移動(dòng)i+1次（包括長(zhǎng)度為i的有序表往后移動(dòng)一個(gè)位置和將R移到正確的位置—第1個(gè)單元）總的比較次數(shù)和移動(dòng)次數(shù)均為其他插入排序折半插入排序、2-路插入排序、希爾排序（ShellSort）100大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社歸并排序把兩個(gè)或多個(gè)有序文件（或表）合并成一個(gè)有序文件（或表）的過(guò)程稱(chēng)歸并（Merge）。當(dāng)歸并文件有k個(gè)時(shí)，稱(chēng)為k路歸并歸并排序（MergeSorting）--重復(fù)利用歸并思想對(duì)任意文件（或表）進(jìn)行排序的過(guò)程二路歸并的基本步驟（1）將文件（或表）F={R1,R2,…,Rn}中的每一個(gè)記錄看作一個(gè)文件（或表），它們都是有序的（僅含一個(gè)記錄）。（2）把子文件（或子表）按照相鄰的位置分成若干對(duì)（如果文件或子表個(gè)數(shù)是奇數(shù)，最后一個(gè)單獨(dú)一組）。（3）對(duì)每對(duì)中的子文件（或子表）進(jìn)行二路歸并。歸并后，每個(gè)子文件都是有序的，且子文件的個(gè)數(shù)減少一半。（4）重復(fù)步驟（2）~（4），直到歸并成一個(gè)有序文件為止。101大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社二路歸并舉例2路歸并過(guò)程102大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社算法3-23二路歸并算法//a、b為兩個(gè)有序序列，長(zhǎng)度分別為m和n，將他們合并成一個(gè)長(zhǎng)度為m+n的有序序列cintMerge2(a[],b[],c[]){m=a.length;n=b.length;i=1;j=1;k=1;while(i<=m&&j<=n){if(a[i].key<b[j].key)

c[k]=a[i++];else

c[k]=b[j++];k++;}if(i<=m)//將a中剩余的記錄寫(xiě)到c中

while(i<=m)c[k++]=a[i++];if(j<=n)//將b中剩余的記錄寫(xiě)到c中while(j<=n)c[k++]=b[j++];}103大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社基數(shù)排序基數(shù)排序是一種借助于多關(guān)鍵字排序的思想實(shí)現(xiàn)的對(duì)單個(gè)邏輯關(guān)鍵字進(jìn)行排序的方法。多關(guān)鍵字，例如104大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社十進(jìn)制基數(shù)分類(lèi)假定被分類(lèi)的關(guān)鍵字值是十進(jìn)制整數(shù)，將每位數(shù)字視為一個(gè)關(guān)鍵字，個(gè)位為最低關(guān)鍵字，十位為次低關(guān)鍵字，以此類(lèi)推。進(jìn)行十進(jìn)位基數(shù)分類(lèi)的過(guò)程是：把輸出分成10個(gè)桶（0桶，1桶，…，9桶），整個(gè)分類(lèi)過(guò)程分成d遍（d為被分類(lèi)數(shù)字的最多位數(shù)）。第一遍：首先對(duì)最低關(guān)鍵字（個(gè)位）、進(jìn)行桶分類(lèi)，對(duì)序列中的每一個(gè)數(shù)由前向后將最低位數(shù)字相同的數(shù)字依次放在對(duì)應(yīng)的上述10個(gè)桶中（如個(gè)位為6的放在6桶中），直到所有數(shù)字都分完。第二遍：把上一遍各桶內(nèi)的數(shù)字，按照從0桶,1桶，…，9桶的編號(hào)次序，同一桶內(nèi)按由上倒下的次序收集起來(lái)，作為第二遍的輸入，再按次關(guān)鍵字（十位）的狀態(tài)把各個(gè)數(shù)分別放入0,1,2,…,9對(duì)應(yīng)的桶內(nèi)。然后再把各個(gè)桶內(nèi)的數(shù)字收集起來(lái)作為第三遍的輸入，繼續(xù)上述過(guò)程，直到按照最高關(guān)鍵字的狀態(tài)把所有數(shù)再分到對(duì)應(yīng)的桶內(nèi)。最后，按照0桶，1桶，2桶，…，9桶的順序把各桶內(nèi)的數(shù)據(jù)收集起來(lái)（同一桶內(nèi)按由上倒下的次序收集）就得到所要的結(jié)果。105大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社舉例設(shè)要分類(lèi)的記錄的關(guān)鍵字值為{26，56，11，68，80，34，75，52，86}106大學(xué)計(jì)算機(jī)—計(jì)算的思想和方法》（第3版），郝興偉編著.北京：高等教育出版社第3章問(wèn)題求解與算法3.1問(wèn)題與問(wèn)