算法分析與設(shè)計(jì)多媒體課件-

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

AlgorithmDesignandAnalysis湖南商學(xué)院計(jì)算機(jī)與電子工程學(xué)院2009.52022/10/300-算法設(shè)計(jì)與分析

AlgorithmDesignand目錄Chapter1緒論Chapter2算法效率分析基礎(chǔ)

Chapter3分治法Chapter4減治法Chapter5變治法Chapter6時(shí)空權(quán)衡Chapter7動(dòng)態(tài)規(guī)劃Chapter8貪心法Chapter9回溯與分枝限界附：算法設(shè)計(jì)與分析實(shí)例動(dòng)畫(huà)集成2022/10/301-目錄Chapter6時(shí)空權(quán)衡附：算法設(shè)計(jì)與分析實(shí)例動(dòng)畫(huà)集

Chapter1緒論

Introduction

2022/10/302-Chapter1緒論

緒論什么是算法算法的實(shí)例算法研究的基本問(wèn)題為什么要學(xué)習(xí)算法已有的基礎(chǔ)—數(shù)據(jù)結(jié)構(gòu)返回總目錄2022/10/303-緒論什么是算法返回總目錄2022/10/233-什么是算法算法是為了解決某一問(wèn)題而設(shè)計(jì)的無(wú)疑義的指令序列，對(duì)于合法的輸入，能在有限的時(shí)間內(nèi)得出所需要的輸出。problemalgorithmcomputerinputoutput2022/10/304-什么是算法算法是為了解決某一問(wèn)題而設(shè)計(jì)的無(wú)疑算法滿足下列性質(zhì)輸入：有零個(gè)或多個(gè)外部量作為算法的輸入。輸出：算法產(chǎn)生至少一個(gè)量作為輸出。確定性：組成算法的每條指令清晰、無(wú)歧義。有限性：算法中每條指令的執(zhí)行次數(shù)有限，執(zhí)行每條指令的時(shí)間也有限。2022/10/305-算法滿足下列性質(zhì)輸入：有零個(gè)或多個(gè)外部量作為算法的輸入。算法的實(shí)例排序查找最短路徑最小生成樹(shù)旅行商問(wèn)題背包問(wèn)題皇后問(wèn)題漢諾塔2022/10/306-算法的實(shí)例排序2022/10/236-算法研究的基本問(wèn)題如何設(shè)計(jì)算法如何描述算法證明算法的正確性常用數(shù)學(xué)歸納法算法效率理論分析實(shí)證分析算法優(yōu)化2022/10/307-算法研究的基本問(wèn)題如何設(shè)計(jì)算法2022/10/237-為什么要學(xué)習(xí)算法理論學(xué)習(xí)上的重要性計(jì)科專(zhuān)業(yè)的核心課程計(jì)科專(zhuān)業(yè)的基礎(chǔ)課程實(shí)踐上的重要性2022/10/308-為什么要學(xué)習(xí)算法理論學(xué)習(xí)上的重要性2022/10/238-已有的基礎(chǔ)—數(shù)據(jù)結(jié)構(gòu)典型的問(wèn)題類(lèi)型排序查找字符串處理圖組合問(wèn)題幾何問(wèn)題數(shù)值問(wèn)題2022/10/309-已有的基礎(chǔ)—數(shù)據(jù)結(jié)構(gòu)典型的問(wèn)題類(lèi)型2022/10/239-已有的基礎(chǔ)—數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)表數(shù)組鏈表字符串棧和隊(duì)列圖樹(shù)集合和字典2022/10/3010-已有的基礎(chǔ)—數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)2022/10/2310-思考帶鎖的門(mén)走廊上n個(gè)帶鎖的門(mén)，從1到n一次編號(hào)，最初都關(guān)著，我們從門(mén)前經(jīng)過(guò)n次，每次都從1號(hào)門(mén)開(kāi)始，在第i次經(jīng)過(guò)時(shí)，我們改變i的倍數(shù)的門(mén)所狀態(tài)，這樣，最后一次經(jīng)過(guò)時(shí)，那些門(mén)開(kāi)著，那些門(mén)關(guān)著？有四個(gè)人過(guò)橋，他們都在橋的一端，17分鐘讓他們?nèi)客ㄟ^(guò)，必須攜帶手電筒，必須步行攜帶，每個(gè)人速度不同，甲過(guò)橋一分鐘，乙過(guò)橋2分鐘，丙過(guò)橋5分鐘，丁要10分鐘，2個(gè)人一起走需要的時(shí)間是較慢的人的時(shí)間，他們要如何走才能順利完成？2022/10/3011-思考帶鎖的門(mén)2022/10/2311-本章結(jié)束，返回總目錄2022/10/3012-本章結(jié)束，返回總目錄2022/10/2312-

Chapter2算法效率分析基礎(chǔ)

FoundationofAlgorithmAnalysis

2022/10/3013-Chapter2算法效率分析基礎(chǔ)

算法效率分析基礎(chǔ)研究的主要問(wèn)題方法時(shí)間效率的理論分析時(shí)間效率的實(shí)證分析最好、最壞與平均情況增長(zhǎng)速度非遞歸與遞歸分析過(guò)程返回總目錄2022/10/3014-算法效率分析基礎(chǔ)研究的主要問(wèn)題返回總目錄2022/10/23研究的主要問(wèn)題算法的正確性時(shí)間效率空間效率最優(yōu)性2022/10/3015-研究的主要問(wèn)題算法的正確性2022/10/2315-方法理論分析實(shí)證分析2022/10/3016-方法理論分析2022/10/2316-2.1時(shí)間效率的理論分析輸入規(guī)模基本運(yùn)算為什么要用基本運(yùn)算？如何找基本運(yùn)算？運(yùn)行時(shí)間基本運(yùn)算的執(zhí)行時(shí)間基本運(yùn)算的執(zhí)行次數(shù)輸入規(guī)模

T(n)≈

copC(n)2022/10/3017-2.1時(shí)間效率的理論分析輸入規(guī)模運(yùn)行時(shí)間基本運(yùn)算的執(zhí)行時(shí)間基輸入規(guī)模與基本操作舉例基本運(yùn)算輸入規(guī)模的度量問(wèn)題對(duì)節(jié)點(diǎn)或?qū)叺脑L問(wèn)節(jié)點(diǎn)數(shù)或者邊數(shù)典型的圖問(wèn)題除法n的大?。ń?jīng)常轉(zhuǎn)化為二進(jìn)制表示，即為二進(jìn)制的位數(shù)）對(duì)于給定的數(shù)n，判斷是否為素?cái)?shù)兩個(gè)數(shù)相乘矩陣的維度或者元素的個(gè)數(shù)兩個(gè)矩陣相乘關(guān)鍵字比較列表節(jié)點(diǎn)數(shù)目，例如n在長(zhǎng)度為n的列表中按關(guān)鍵字查找2022/10/3018-輸入規(guī)模與基本操作舉例基本運(yùn)算輸入規(guī)模的度量問(wèn)題對(duì)節(jié)點(diǎn)或?qū)厡?duì)時(shí)間效率的實(shí)證分析選擇特別的或者典型的輸入統(tǒng)計(jì)實(shí)際運(yùn)行時(shí)間(e.g.,milliseconds)統(tǒng)計(jì)基本操作執(zhí)行的次數(shù)對(duì)統(tǒng)計(jì)數(shù)據(jù)進(jìn)行分析2022/10/3019-對(duì)時(shí)間效率的實(shí)證分析選擇特別的或者典型的輸入2022/10/最好、最壞、平均情況很多算法的效率都取決于輸入的組織最壞情況:Cworst(n)–對(duì)于規(guī)模為n的輸入，最大的消耗最好情況:Cbest(n)–對(duì)于規(guī)模為n的輸入，最小的消耗平均情況:Cavg(n)–對(duì)于規(guī)模為n的輸入，“平均”的消耗基本操作執(zhí)行的次數(shù)體現(xiàn)在典型輸入中不是最好最壞情況的平均將規(guī)模n的實(shí)例劃分為幾種類(lèi)型，同種實(shí)例所需要的基本操作執(zhí)行次數(shù)一樣，然后我們得到或者假設(shè)各種輸入的概率分布，以推導(dǎo)出我們的平均次數(shù)2022/10/3020-最好、最壞、平均情況很多算法的效率都取決于輸入的組織2022例：順序查找最壞情況：n最好情況：1平均情況：(1+n)p/2+n(1-p)//在一個(gè)指定的數(shù)組中順序查找指定元素//輸入：A[0..n-1],k//輸出：指定查找元素在數(shù)組中的下標(biāo)，沒(méi)有返回-12022/10/3021-例：順序查找最壞情況：n//在一個(gè)指定的數(shù)組中順序查找指定元思考對(duì)于下面每種算法，1.指出輸入規(guī)模的合理度量，2.它的基本操作，對(duì)相同規(guī)模的輸入來(lái)說(shuō)，3.基本操作的執(zhí)行次數(shù)是否有所不同？

a、計(jì)算n個(gè)數(shù)的和b、計(jì)算n！

c、找出包含n個(gè)數(shù)字的列表的最大元素

c、兩個(gè)十進(jìn)制正整數(shù)相乘的筆算算法

d、歐幾里得法求公約數(shù)2022/10/3022-思考對(duì)于下面每種算法，1.指出輸入規(guī)模的合理度量，2.它的基選擇手套一個(gè)抽屜里有22只手套，5雙紅色的，4雙黃色的，2雙綠色的，黑暗中挑選，最優(yōu)情況下就最少選幾只能找到一對(duì)匹配的手套？最壞情況下呢？丟失的襪子假設(shè)洗了5雙不同的襪子后，發(fā)現(xiàn)兩只找不到了，當(dāng)然希望留下數(shù)量最多的完整的襪子，在最好的情況下，你會(huì)留下4雙襪子，最壞情況下只有3雙，假設(shè)10只襪子每只丟失的概率相同，請(qǐng)找出最好與最壞的發(fā)生概率，平均情況下能指望有幾雙？2022/10/3023-選擇手套2022/10/2323-增長(zhǎng)次數(shù)最重要的:考慮n→∞時(shí)，效率的乘積增長(zhǎng)速度例如：當(dāng)計(jì)算機(jī)的速度增加兩倍時(shí)，算法運(yùn)行的速度會(huì)有多快當(dāng)在兩倍的輸入規(guī)模下解決某問(wèn)題時(shí)，時(shí)間會(huì)增加多少

T(n)≈

copC(n)2022/10/3024-增長(zhǎng)次數(shù)最重要的:考慮n→∞時(shí)，效率的乘積增長(zhǎng)速度T(n時(shí)的重要增長(zhǎng)值比較一下logn與n2的區(qū)別2022/10/3025-n時(shí)的重要增長(zhǎng)值比較一下logn與n2的區(qū)別2022/1分析框架概要算法的效率用輸入規(guī)模函數(shù)進(jìn)行度量基本操作的執(zhí)行次數(shù)輸入規(guī)模相同情況下，有時(shí)候需要區(qū)分最好、最差和平均效率算法輸入規(guī)模趨向無(wú)窮大時(shí)，它的運(yùn)行時(shí)間函數(shù)的增長(zhǎng)次數(shù)2022/10/3026-分析框架概要算法的效率用輸入規(guī)模函數(shù)進(jìn)行度量2022/10/2.2增長(zhǎng)率漸進(jìn)表示我們關(guān)心的是算法的基本操作次數(shù)的增長(zhǎng)次數(shù)，并把它作為算法效率分析的主要指標(biāo)，為了進(jìn)行比較歸類(lèi)，引入下列3個(gè)符號(hào)：O(g(n)):增長(zhǎng)不會(huì)超過(guò)g(n)的一類(lèi)函數(shù)f(n)Θ(g(n)):增長(zhǎng)率與g(n)相同的一類(lèi)函數(shù)f(n)Ω(g(n)):增長(zhǎng)至少與g(n)相同的一類(lèi)函數(shù)f(n)2022/10/3027-2.2增長(zhǎng)率漸進(jìn)表示我們關(guān)心的是算法的基本操作次數(shù)的增長(zhǎng)次數(shù)Big-oh成立的條件是對(duì)于足夠大的n>n0，存在大于0的常數(shù)c，使得以上圖形滿足,后面符號(hào)的兩個(gè)條件相同P41例2022/10/3028-Big-oh成立的條件是對(duì)于足夠大的n>n0，存在大于0的常Big-omega2022/10/3029-Big-omega2022/10/2329-Big-theta2022/10/3030-Big-theta2022/10/2330-證明2022/10/3031-證明2022/10/2331-漸進(jìn)增長(zhǎng)的相關(guān)屬性f(n)O(f(n))f(n)O(g(n))ifg(n)(f(n))Iff(n)O(g(n))andg(n)O(h(n)),thenf(n)O(h(n))Iff1(n)O(g1(n))andf2(n)O(g2(n)),then f1(n)+f2(n)O(max{g1(n),g2(n)})

2022/10/3032-漸進(jìn)增長(zhǎng)的相關(guān)屬性f(n)O(f(n))2022/10使用極限比較增長(zhǎng)次數(shù)limT(n)/g(n)=0

orderofgrowthofT(n)<orderofgrowthofg(n)

c>0orderofgrowthofT(n)=orderofgrowthofg(n)

∞

orderofgrowthofT(n)>orderofgrowthofg(n)

Examples:

10nvs.n2

n(n+1)/2vs.n2

n→∞2022/10/3033-使用極限比較增長(zhǎng)次數(shù)limT(n)/g(n)=基本的漸進(jìn)效率分類(lèi)：1常數(shù)logn對(duì)數(shù)n線性nlognn-log-nn2平方n3立方2n指數(shù)n!階乘2022/10/3034-基本的漸進(jìn)效率分類(lèi)：1常數(shù)logn對(duì)數(shù)n線性nlognP461選擇合適的符號(hào)來(lái)指出順序查找算法時(shí)間效率類(lèi)型最優(yōu)最差平均情況作業(yè)2、52022/10/3035-P4612022/10/2335-2.3非遞歸算法時(shí)間效率分析過(guò)程使用變量n來(lái)描述輸入規(guī)模定義算法的基本操作在輸入規(guī)模為n的情況下，區(qū)分最壞、平均和最好情況對(duì)基本操作執(zhí)行的次數(shù)求和使用相關(guān)公式和規(guī)則對(duì)和進(jìn)行化簡(jiǎn)2022/10/3036-2.3非遞歸算法時(shí)間效率分析過(guò)程使用變量n來(lái)描述輸入規(guī)模20示例1：求最大元素2022/10/3037-示例1：求最大元素2022/10/2337-示例2：元素的唯一性問(wèn)題2022/10/3038-示例2：元素的唯一性問(wèn)題2022/10/2338-示例3：矩陣的乘法2022/10/3039-示例3：矩陣的乘法2022/10/2339-示例4.十進(jìn)制數(shù)轉(zhuǎn)化成二進(jìn)制數(shù)后的位數(shù)2022/10/3040-示例4.十進(jìn)制數(shù)轉(zhuǎn)化成二進(jìn)制數(shù)后的位數(shù)2022/10/2練習(xí)p511e、g其余作業(yè)2022/10/3041-練習(xí)p511e、g其余作業(yè)2022/10/232.4遞歸算法的時(shí)間效率分析過(guò)程遞歸算法：函數(shù)調(diào)用自身的情況稱(chēng)為遞歸。遞歸的條件：子問(wèn)題與原問(wèn)題是同樣的問(wèn)題，且更為簡(jiǎn)單不能無(wú)限制調(diào)用，必須有出口條件2022/10/3042-2.4遞歸算法的時(shí)間效率分析過(guò)程遞歸算法：2022/10/2確定一個(gè)變量來(lái)描述輸入規(guī)模確定算法的基本操作對(duì)于相同規(guī)模的不同輸入，在執(zhí)行時(shí)是否有不同的基本操作次數(shù)，如果有，那么最壞、平均和最好情況應(yīng)該分別考慮建立與適當(dāng)初始條件的遞歸聯(lián)系，表示基本操作的執(zhí)行次數(shù)使用反向迭代方法和初始條件解出遞歸式，至少要建立遞歸解的增長(zhǎng)率

2022/10/3043-確定一個(gè)變量來(lái)描述輸入規(guī)模2022/10/2343-N!定義:n!=12…(n-1)

nforn≥

1and0!=1遞歸的定義n!:F(n)=F(n-1)

nforn≥1andF(0)=1問(wèn)題規(guī)模？基本操作？運(yùn)算時(shí)間的遞推式？初始條件？2022/10/3044-N!定義:n!=12…(n-1)實(shí)例2：漢諾塔問(wèn)題實(shí)例3：十進(jìn)制正整數(shù)在二進(jìn)制表示中的數(shù)字個(gè)數(shù)

遞歸方法練習(xí)p58頁(yè)（1）ab、c、d、e做作業(yè)P64頁(yè)習(xí)題2.5（4）2022/10/3045-實(shí)例2：2022/10/2345-本章結(jié)束，返回總目錄2022/10/3046-本章結(jié)束，返回總目錄2022/10/2346-Chapter3分治法

DividandConquer2022/10/3047-Chapter3分治法

分治法分治法通用分治遞推式分治法實(shí)例返回總目錄2022/10/3048-分治法分治法返回總目錄2022/10/2348-分治法通用算法設(shè)計(jì)技術(shù)將問(wèn)題的實(shí)例劃分為同一個(gè)問(wèn)題的幾個(gè)較小實(shí)例對(duì)這些較小的實(shí)例求解合并這些較小問(wèn)題的解，已得到原始問(wèn)題的解分治算法很適合用遞歸來(lái)解決2022/10/3049-分治法通用算法設(shè)計(jì)技術(shù)2022/10/2349-分治法子問(wèn)題2的規(guī)模是n/2子問(wèn)題1的規(guī)模是n/2子問(wèn)題1的解原始問(wèn)題的解子問(wèn)題2的解原始問(wèn)題規(guī)模是n2022/10/3050-分治法子問(wèn)題2的規(guī)模是n/2子問(wèn)題1的規(guī)模是n/2子問(wèn)題1的通用分治遞推式T(n)=aT(n/b)+f(n)

其中，

f(n)

(nd),d0主定理:當(dāng)a<bd,T(n)

(nd)

當(dāng)a=bd,T(n)

(ndlogn)

當(dāng)a>bd,T(n)

(nlogba)

注意：對(duì)O和符號(hào)來(lái)說(shuō)類(lèi)似的結(jié)論也是成立的。例如:T(n)=4T(n/2)+nT(n)?

T(n)=4T(n/2)+n2T(n)?

T(n)=4T(n/2)+n3T(n)?2022/10/3051-通用分治遞推式T(n)=aT(n/b)+f(n)分治法實(shí)例歸并排序和快速排序二叉樹(shù)遍歷二分查找大整數(shù)乘法Strassen矩陣乘法凸包問(wèn)題2022/10/3052-分治法實(shí)例歸并排序和快速排序2022/10/2352-歸并排序?qū)?shù)組A[0..n-1]分成兩個(gè)相等數(shù)組，并分別用數(shù)組B和數(shù)組C備份分別對(duì)B,C進(jìn)行排序按照如下方法合并B,C到數(shù)組A：重復(fù)如下步驟，直到數(shù)組中沒(méi)有元素為止：比較兩個(gè)待合并數(shù)組的第一個(gè)元素將較小的元素添加到一個(gè)新創(chuàng)建的數(shù)組中，被復(fù)制數(shù)組中下標(biāo)后移。在未處理完的數(shù)組中，剩下的元素被復(fù)制到新創(chuàng)建數(shù)組的尾部。2022/10/3053-歸并排序?qū)?shù)組A[0..n-1]分成兩個(gè)相等數(shù)組，并分別用832971548329715483297154832971543829174523891457123457892022/10/3054-832971548兩個(gè)列表歸并成一個(gè)有序列表的算法2022/10/3055-兩個(gè)列表歸并成一個(gè)有序列表的算法2022/10/2355-歸并排序算法2022/10/3056-歸并排序算法2022/10/2356-歸并排序效率分析所有實(shí)例都有同一個(gè)效率:Θ(nlogn)最壞情況下的鍵值比較次數(shù)十分接近于任何基于比較的排序算法在理論上所能達(dá)到的最少次數(shù).

當(dāng)n=2k時(shí)c(n)=nlog2n-n+1空間需求:Θ(n)可以不用遞歸(自底而上）2022/10/3057-歸并排序效率分析所有實(shí)例都有同一個(gè)效率:Θ(nlogn快速排序選擇一個(gè)中軸

元素，我們這里選擇第一個(gè)元素對(duì)數(shù)組進(jìn)行排序，使得小于或等于中軸的元素位于子數(shù)組的第一部分，剩下的元素都大于或等于中軸元素的值。將中軸子與第一個(gè)子數(shù)組中的元素進(jìn)行交換---此時(shí)，中軸在最后的位置對(duì)兩個(gè)子數(shù)組進(jìn)行遞歸排序2022/10/3058-快速排序選擇一個(gè)中軸元素，我們這里選擇第一個(gè)元素2022/

01234567

5

3148297

53198247

3198247

53148297

53142897

53142897

23145897ijl=0,r=7

5ijijijijjiS=4

2314ijl=0,r=3

2314ij

2134ij

2134ij

1234S=1

1l=5,r=7

34ij

34ij

4l=0,r=0l=2,r=3S=2l=2,r=1l=3,r=3

897ij

879ij

879ij

789l=5,r=5

7

9l=7,r=7S=6快速排序操作的一個(gè)例子。(a)數(shù)組的變化，其中中軸用粗體表示；(b)快速排序的遞歸調(diào)用樹(shù)，調(diào)用的輸入值是子數(shù)組的邊界l和r，以及分區(qū)的分裂點(diǎn)位置s(a)(b)2022/10/3059-01234快排效率分析最好情況:從中間拆分—Θ(nlogn)最壞情況:已經(jīng)是排好序的數(shù)組—Θ(n2)平均情況:無(wú)序數(shù)組—Θ(nlogn)對(duì)該算法的改進(jìn):更好的選擇中軸:三平均分區(qū)法當(dāng)子數(shù)組足夠小時(shí)改用更簡(jiǎn)單的排序方法遞歸消去法可將該算法的運(yùn)行時(shí)間削減20%--25%考慮用該種方法來(lái)對(duì)大文件（n≥10000)來(lái)進(jìn)行內(nèi)部排序2022/10/3060-快排效率分析最好情況:從中間拆分—Θ(nlogn)二分查找對(duì)于有序數(shù)組的查找的一種高速算法

K vs A[0]...A[m]...A[n-1]如果K=A[m],停止查找;否則當(dāng)K<A[m]時(shí)，用同樣的方法在A[0..m-1]進(jìn)行查找；當(dāng)K>A[m]時(shí)，在A[m+1..n-1]中查找。

2022/10/3061-二分查找對(duì)于有序數(shù)組的查找的一種高速算法2022/10/23二分查找效率分析時(shí)間效率最壞情況下遞推式：Cw(n)=1+Cw(n/2),Cw(1)=1

經(jīng)過(guò)調(diào)整后：Cw(n)=

log2(n+1)

這是非?？斓?，例如：Cw(106)=20最適合用于查找已排序數(shù)組限制：必須是一個(gè)排序數(shù)組（不是鏈接數(shù)組）折半查找并不是分治法典型的特例2022/10/3062-二分查找效率分析時(shí)間效率2022/10/2362-二叉樹(shù)遍歷二叉樹(shù)時(shí)分治法的較好的結(jié)構(gòu)例1:遍歷(前序,中序,后序)AlgorithmInorder(T)ifT

Inorder(Tleft)print(rootofT)

Inorder(Tright)效率:Θ(n)2022/10/3063-二叉樹(shù)遍歷二叉樹(shù)時(shí)分治法的較好的結(jié)構(gòu)2022/10/2363二叉樹(shù)遍歷例2:計(jì)算二叉樹(shù)的高度

h(T)=max{h(TL),h(TR)}+1ifT

并且h()=-1效率:Θ(n)

2022/10/3064-二叉樹(shù)遍歷例2:計(jì)算二叉樹(shù)的高度h(T)=max{h大整數(shù)乘法兩位整數(shù)相乘可以用數(shù)組表示如：a1a2…an

b1b2…bnA=12345678901357986429B=87654321284820912836(d10)

d11d12…d1n(d20)

d21d22…d2n………………(dn0)

dn1dn2…dnn效率：O(n2)2022/10/3065-大整數(shù)乘法兩位整數(shù)相乘可以用數(shù)組表示如：a1a2…大整數(shù)乘法兩位數(shù)A=2135和B=4014可以這樣表示：將每個(gè)數(shù)字從中間一分為二它們的積可以用這個(gè)公式計(jì)算：AB=A1B1·10n

+(A1B2+A2B1)·10n/2+A2B2

A=(21·102+35),B=(40·102+14)

AB=(21·102+35)(40·102+14)

=2140·104+(2114+3540)·102+3514效率：

M(n)=4M(n/2),M(1)=1M(n)=

n22022/10/3066-大整數(shù)乘法兩位數(shù)A=2135和B=4014可以這樣大整數(shù)乘法(A1B2+A2B1)=(A1+A2)(B1+B2)-A1B1-A2B2AB=A1B1·10n

+(A1B2+A2B1)·10n/2+A2B2可以這樣做減少乘法：AB=A1B1

+(A1B2+A2B1)

+A2B2因?yàn)樯鲜鲋兄挥腥齻€(gè)乘法所以乘法次數(shù)M(n)的遞推式是：當(dāng)n>1時(shí)M(n)=3M(n/2),M(1)=1當(dāng)n=2k時(shí)M(2k)=3M(2k-1)=….=3k因?yàn)椋簁=log2nM(n)=nlog23=n1.5852022/10/3067-大整數(shù)乘法(A1B2+A2B1)=(A1大整數(shù)乘法A=21

35B=40

14

A1A2B1B2AB=21*35+（21*14+35*40）+35*14（21*14+35*40）=（21+35）*（40+24）-21*35-35*14例如：計(jì)算213540142022/10/3068-大整數(shù)乘法A=2135Strassen矩陣乘法A和B的乘積矩陣C中的元素C[i,j]定義為:

若依此定義來(lái)計(jì)算A和B的乘積矩陣C，則每計(jì)算C的一個(gè)元素C[i][j]，需要做n次乘法和n-1次加法。因此，算出矩陣C的個(gè)元素所需的計(jì)算時(shí)間為O(n3)傳統(tǒng)方法：O(n3)2022/10/3069-Strassen矩陣乘法A和B的乘積矩陣C中的元素C[i,jStrassen矩陣乘法使用與上例類(lèi)似的技術(shù)，將矩陣A，B和C中每一矩陣都分塊成4個(gè)大小相等的子矩陣。由此可將方程C=AB重寫(xiě)為：傳統(tǒng)方法：O(n3)分治法:由此可得：由此可見(jiàn)，單純采用分治法，沒(méi)有改進(jìn)2022/10/3070-Strassen矩陣乘法使用與上例類(lèi)似的技術(shù)，將矩陣A，B和Strassen矩陣乘法為了降低時(shí)間復(fù)雜度，必須減少乘法的次數(shù)。2022/10/3071-Strassen矩陣乘法為了降低時(shí)間復(fù)雜度，必須減少乘法的次復(fù)雜度分析T(n)=O(nlog7)=O(n2.81)較大的改進(jìn)2022/10/3072-復(fù)雜度分析2022/10/2372-Strassen矩陣乘法傳統(tǒng)方法：O(n3)分治法:O(n2.81)更快的方法??Hopcroft和Kerr已經(jīng)證明(1971)，計(jì)算2個(gè)２×２矩陣的乘積，7次乘法是必要的。因此，要想進(jìn)一步改進(jìn)矩陣乘法的時(shí)間復(fù)雜性，就不能再基于計(jì)算2×2矩陣的7次乘法這樣的方法了?；蛟S應(yīng)當(dāng)研究３×３或５×５矩陣的更好算法。在Strassen之后又有許多算法改進(jìn)了矩陣乘法的計(jì)算時(shí)間復(fù)雜性。目前最好的計(jì)算時(shí)間上界是O(n2.376)是否能找到O(n2)的算法？？？目前為止還沒(méi)有結(jié)果。2022/10/3073-Strassen矩陣乘法傳統(tǒng)方法：O(n3)Hopcroft凸包問(wèn)題（相關(guān)定義p84）什么是凸集合？對(duì)于平面的一個(gè)點(diǎn)集合（有限或無(wú)限），如果以集合中任意兩點(diǎn)p和q為端點(diǎn)的線段都屬于該集合，則稱(chēng)集合為凸的。定義：凸包：一個(gè)點(diǎn)集合s的凸包是包含s的最小凸集合。定理任意包含n>2個(gè)點(diǎn)（不共線的點(diǎn)）的集合s的凸包是以s中的某些點(diǎn)為頂點(diǎn)的多邊形（如果所有的的店都位于一條直線上，多邊形退化為一條線段，但它的2個(gè)端點(diǎn)讓人包含在s中）2022/10/3074-凸包問(wèn)題（相關(guān)定義p84）什么是凸集合？對(duì)于平面的一個(gè)點(diǎn)集合假設(shè)點(diǎn)按照x軸排序找出最左和最右的極點(diǎn)(leftmostandrightmost)遞歸的求凸包的上包:發(fā)現(xiàn)點(diǎn)Pmax

是離直線P1P2直線最遠(yuǎn)的點(diǎn)計(jì)算在直線P1Pmax左側(cè)的上包計(jì)算在直線PmaxP2左側(cè)的上包遞歸的計(jì)算下包2022/10/3075-假設(shè)點(diǎn)按照x軸排序2022/10/2375-p1p2凸包問(wèn)題1、最左邊的點(diǎn)p1和最右邊的p2一定是該集合凸包頂點(diǎn)。2022/10/3076-p1p2凸包問(wèn)題1、最左邊的點(diǎn)p1和最右邊的p2一定是該集合p1p2凸包問(wèn)題2、找到上包的頂點(diǎn)，它是距離直線最遠(yuǎn)的點(diǎn)，如果用兩條連接線的話，這個(gè)確定了最大的三角形pmaxp1p2。pmax2022/10/3077-p1p2凸包問(wèn)題2、找到上包的頂點(diǎn)，它是距離直線最遠(yuǎn)的點(diǎn)，如p1p2凸包問(wèn)題p1max3、找出距離p1pmax左邊最遠(yuǎn)的點(diǎn)p3。如此進(jìn)行下去，直到對(duì)應(yīng)的包左邊沒(méi)有點(diǎn)p32022/10/3078-p1p2凸包問(wèn)題p1max3、找出距離p1pmax左邊最遠(yuǎn)的p1p2凸包問(wèn)題p1maxp2max4、找出PmaxP2左邊最遠(yuǎn)的點(diǎn)p4。，按照改方法進(jìn)行，直到左邊沒(méi)有點(diǎn)p42022/10/3079-p1p2凸包問(wèn)題p1maxp2max4、找出PmaxP2左邊p1p2凸包問(wèn)題p1maxp2max連接所得到的這些點(diǎn)2022/10/3080-p1p2凸包問(wèn)題p1maxp2max連接所得到的這些點(diǎn)202p1p2凸包問(wèn)題p1maxp2max利用上述求上包的方法求出下包。2022/10/3081-p1p2凸包問(wèn)題p1maxp2max利用上述求上包的方法求2如何判斷離線段p1p2最遠(yuǎn)的點(diǎn)？假設(shè)p3為任意點(diǎn)X1y11X2y21X3y31該行列式的絕對(duì)值表示以這3點(diǎn)構(gòu)成的三角形面積，值為正，表示該點(diǎn)位于直線先左側(cè)2022/10/3082-如何判斷離線段p1p2最遠(yuǎn)的點(diǎn)？假設(shè)p3為任意點(diǎn)該行列式的絕本章結(jié)束，返回總目錄2022/10/3083-本章結(jié)束，返回總目錄2022/10/2383-Chapter4減治法Decrease-and-Conquer2022/10/3084-Chapter4減治法Decrease-and-Con減治法減治法減治法的類(lèi)型減治法與其它方法的區(qū)別返回總目錄2022/10/3085-減治法減治法返回總目錄2022/10/2385-減治法基本思路：將原問(wèn)題的實(shí)例轉(zhuǎn)化為規(guī)模較小的實(shí)例對(duì)規(guī)模較小的實(shí)例的求解將較小的實(shí)例的解擴(kuò)展到原實(shí)例能夠使用自頂向下或者是自底向上經(jīng)常被稱(chēng)為歸納法或者是增量法2022/10/3086-減治法基本思路：2022/10/2386-減治法的類(lèi)型減去一個(gè)常量（一般是１）插入排序圖形遍歷算法（深度優(yōu)先查找和廣度優(yōu)先查找）拓?fù)渑判?/p>

減去一個(gè)常量因子（一般是一半）折半查找和二分法矩陣的冪運(yùn)算俄式乘法減可變規(guī)模歐幾里得問(wèn)題部分選擇2022/10/3087-減治法的類(lèi)型減去一個(gè)常量（一般是１）2022/10/2387減去常量在這種減治法中，每次減去一個(gè)常量因子1。例如：插入排序

圖形遍歷算法（深度優(yōu)先查找和廣度優(yōu)先查找）拓?fù)渑判?022/10/3088-減去常量在這種減治法中，每次減去一個(gè)常量因子1。2022/1插入排序?qū)?shù)組A[0..n-1]，數(shù)組A[0..n-2]已經(jīng)排好序，然后在數(shù)組中A[0..n-2]中找一個(gè)合適的位置將A[n-1]插入經(jīng)常使用自底向上（非遞歸）例如:對(duì)6,4,1,8,5進(jìn)行排序

6|4185 46|185 146|85 1468|5 145682022/10/3089-插入排序?qū)?shù)組A[0..n-1]，數(shù)組A[0..n-2]已經(jīng)插入排序2022/10/3090-插入排序2022/10/2390-插入排序8945689029341745>比較45與89的大小2022/10/3091-插入排序8945689029341745>比較45與89的大插入排序8945689029341745>45<89，插入到89前面2022/10/3092-插入排序8945689029341745>45<89，插入到插入排序89689029341745比較68與前面的數(shù)的大小2022/10/3093-插入排序89689029341745比較68與前面的數(shù)的大小插入排序8968902934174568>68<892022/10/3094-插入排序8968902934174568>插入排序8968902934174568>89后移一個(gè)位置2022/10/3095-插入排序8968902934174568>插入排序8968902934174568<比較45與68的大小2022/10/3096-插入排序8968902934174568<比較45與68的大插入排序8968902934174568<將68插入到45后面2022/10/3097-插入排序8968902934174568<將68插入到45后插入排序89902934174568比較90與前面的數(shù)的大小2022/10/3098-插入排序89902934174568比較90與前面的數(shù)的大小插入排序89902934174568<89<902022/10/3099-插入排序89902934174568<插入排序89902934174568<將90插入到89后面的位置2022/10/30100-插入排序89902934174568<將90插入到89后面的插入排序89902934174568比較29與前面的數(shù)的大小2022/10/30101-插入排序89902934174568比較29與前面的數(shù)的大小插入排序………2022/10/30102-插入排序………2022/10/23102-插入排序34456889901729排好序后的數(shù)組2022/10/30103-插入排序34456889901729排好序后的數(shù)組2022/插入排序效率分析時(shí)間效率 Cworst(n)=n(n-1)/2

Θ(n2) Cavg(n)≈n2/4Θ(n2) Cbest(n)=n-1Θ(n)空間效率穩(wěn)定的最好排序方法二分法插入排序2022/10/30104-插入排序效率分析時(shí)間效率2022/10/23104-圖遍歷許多問(wèn)題要求自動(dòng)系統(tǒng)地遍歷圖所有的節(jié)點(diǎn)：Depth-firstsearch(DFS)深度優(yōu)先查找Breadth-firstsearch(BFS)廣度優(yōu)先查找2022/10/30105-圖遍歷許多問(wèn)題要求自動(dòng)系統(tǒng)地遍歷圖所有的節(jié)點(diǎn)：2022/10深度優(yōu)先遍歷(DFS)從任意頂點(diǎn)開(kāi)始訪問(wèn)圖的頂點(diǎn)，然后把改頂點(diǎn)標(biāo)記已訪問(wèn)，在每次迭代的的時(shí)候，緊接著訪問(wèn)與當(dāng)前頂點(diǎn)鄰接的未訪問(wèn)頂點(diǎn)，直到遇到一個(gè)死端。用一個(gè)堆棧第一次訪問(wèn)時(shí)入棧當(dāng)該頂點(diǎn)變成一個(gè)死端時(shí)出棧2022/10/30106-深度優(yōu)先遍歷(DFS)從任意頂點(diǎn)開(kāi)始訪問(wèn)圖的頂點(diǎn)，然后把改頂深度優(yōu)先遍歷(DFS)2022/10/30107-深度優(yōu)先遍歷(DFS)2022/10/23107-DFSDFStraversalstack:DFStree:aaabefcdgha入棧2022/10/30108-DFSDFStraversalstack:DFStreDFStraversalstack:DFStree:baababefcdghb入棧DFS2022/10/30109-DFStraversalstack:DFStree:bDFStraversalstack:DFStree:fbaabfabefcdghf入棧DFS2022/10/30110-DFStraversalstack:DFStree:fDFStraversalstack:DFStree:efbaabfeabefcdghe入棧DFS2022/10/30111-DFStraversalstack:DFStree:eDFStraversalstack:DFStree:fbaabfeabefcdghe出棧DFS2022/10/30112-DFStraversalstack:DFStree:fDFStraversalstack:DFStree:fbaabfeabefcdghf出棧DFS2022/10/30113-DFStraversalstack:DFStree:fDFStraversalstack:DFStree:baabfeabefcdghb出棧DFS2022/10/30114-DFStraversalstack:DFStree:bDFStraversalstack:DFStree:gbaabfebgabefcdghg入棧DFS2022/10/30115-DFStraversalstack:DFStree:gDFStraversalstack:DFStree:cgbaabfebgcabefcdghc入棧DFS2022/10/30116-DFStraversalstack:DFStree:cDFStraversalstack:DFStree:dcgbaabfebgcdabefcdghd入棧DFS2022/10/30117-DFStraversalstack:DFStree:dDFStraversalstack:DFStree:hdcgbaabfegcdhabefcdghh入棧DFS2022/10/30118-DFStraversalstack:DFStree:hDFStraversalstack:DFStree:hdcgbaabfegcdhabefcdghh出棧DFS2022/10/30119-DFStraversalstack:DFStree:hDFStraversalstack:DFStree:dcgbaabfegcdhabefcdghd出棧DFS2022/10/30120-DFStraversalstack:DFStree:dDFStraversalstack:DFStree:cgbaabfegcdhabefcdghc出棧DFS2022/10/30121-DFStraversalstack:DFStree:cDFStraversalstack:DFStree:gbaabfegcdhabefcdghg出棧DFS2022/10/30122-DFStraversalstack:DFStree:gDFSDFStraversalstack:DFStree:baabfegcdhabefcdghb出棧2022/10/30123-DFSDFStraversalstack:DFStreDFSDFStraversalstack:DFStree:aabfegcdhabefcdgha出棧2022/10/30124-DFSDFStraversalstack:DFStreDFSDFStraversalstack:DFStree:abfegcdhabefcdghDFS完成2022/10/30125-DFSDFStraversalstack:DFStre深度優(yōu)先遍歷(DFS)DFS能夠在兩種表示方式下實(shí)現(xiàn)：Θ(V2)鄰接矩陣Θ(|V|+|E|)鄰接表產(chǎn)生兩種節(jié)點(diǎn)序列：第一次訪問(wèn)的頂點(diǎn)（入棧）的次序頂點(diǎn)成為死端（出棧）的次序應(yīng)用：檢查圖的連通性和找出圖的連通分量量

檢查圖的無(wú)環(huán)性查找關(guān)節(jié)點(diǎn)和重連通分量搜索狀態(tài)空間的問(wèn)題解決方案（人工智能）2022/10/30126-深度優(yōu)先遍歷(DFS)DFS能夠在兩種表示方式下實(shí)現(xiàn)：20廣度優(yōu)先遍歷(BFS)訪問(wèn)所有和初始頂點(diǎn)鄰接的頂點(diǎn)使用隊(duì)列而不是堆棧類(lèi)似于層次遍歷2022/10/30127-廣度優(yōu)先遍歷(BFS)訪問(wèn)所有和初始頂點(diǎn)鄰接的頂點(diǎn)2022/廣度優(yōu)先遍歷(BFS)2022/10/30128-廣度優(yōu)先遍歷(BFS)2022/10/23128-BFSBFStraversalstack:BFStree:aabefcdgh

a入隊(duì)a2022/10/30129-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfebfeabefcdgh

a出隊(duì)，b、e、f入隊(duì)a2022/10/30130-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfeggabefcdgh

b出隊(duì)，g入隊(duì)bfe2022/10/30131-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfegabefcdgh

e出隊(duì)gfe2022/10/30132-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfegabefcdgh

f出隊(duì)gf2022/10/30133-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfegchchabefcdgh

g出隊(duì)，c、h入隊(duì)g2022/10/30134-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfegcdhdabefcdgh

c出隊(duì)，d入隊(duì)ch2022/10/30135-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfegcdhdabefcdgh

h出隊(duì)h2022/10/30136-BFSBFStraversalstack:BFStreBFSBFStraversalstack:BFStree:abfegcdhabefcdgh

d出隊(duì)，BFS完成d2022/10/30137-BFSBFStraversalstack:BFStre廣度優(yōu)先遍歷(BFS)BFS和DFS具有相同的效率，也并且能夠使用其他的圖來(lái)表示：鄰接矩陣:Θ(V2)鄰接表:Θ(|V|+|E|)只產(chǎn)生一種頂點(diǎn)序列(入隊(duì)和出隊(duì)的次序時(shí)一樣的)

應(yīng)用:和DFS一樣,但是BFS還能夠用來(lái)查找從一個(gè)頂點(diǎn)到其他所有頂點(diǎn)間邊的數(shù)量最少的路徑。2022/10/30138-廣度優(yōu)先遍歷(BFS)BFS和DFS具有相同的效率，也并無(wú)環(huán)有向圖和拓?fù)渑判驘o(wú)環(huán)有向圖:

有向圖沒(méi)有回邊

許多牽扯到先決條件的問(wèn)題都可以通過(guò)建立一個(gè)圖形模型來(lái)解決(施工項(xiàng)目,文檔版本控制)對(duì)于圖中的每一條邊來(lái)說(shuō)，邊的起始頂點(diǎn)總是排在邊的頂點(diǎn)結(jié)束之前.為了使拓?fù)渑判虺蔀榭赡?，圖必須是一個(gè)無(wú)環(huán)有向圖

abcd無(wú)環(huán)有向圖abcd非無(wú)環(huán)有向圖2022/10/30139-無(wú)環(huán)有向圖和拓?fù)渑判驘o(wú)環(huán)有向圖:有向圖沒(méi)有回邊許多牽扯到先拓?fù)渑判蚺e例將下列食物鏈按順序排列fishhumanshrimpsheepwheatplanktontiger2022/10/30140-拓?fù)渑判蚺e例將下列食物鏈按順序排列fishhumanshri基于DFS的算法基于DFS算法的拓?fù)渑判驁?zhí)行一次DFS遍歷，并記住頂點(diǎn)變成死端（退出遍歷棧）的順序?qū)⒃摯涡蚍催^(guò)來(lái)得到拓?fù)渑判虻囊粋€(gè)解遇到回邊?→不是無(wú)環(huán)有向圖!abefcdgh2022/10/30141-基于DFS的算法基于DFS算法的拓?fù)渑判騛befcdgh20源刪除算法源刪除算法

不斷的做一件事，再余下的有向圖中求一個(gè)源，他是一個(gè)沒(méi)有輸入邊的頂點(diǎn)，然后把它和所有從他出發(fā)的邊都刪除（如果有多個(gè)源，任意刪掉一個(gè)，如果不存在，算法就停止）。abefcdgh2022/10/30142-源刪除算法源刪除算法abefcdgh2022/10/2314拓?fù)渑判騠ishhumanshrimpsheepwheatplanktontiger2022/10/30143-拓?fù)渑判騠ishhumanshrimpsheepwheatp拓?fù)渑判騠ishhumanshrimpsheepwheattiger剔除plankton2022/10/30144-拓?fù)渑判騠ishhumanshrimpsheepwheatt拓?fù)渑判騠ishhumanshrimpsheeptiger剔除plankton剔除wheat2022/10/30145-拓?fù)渑判騠ishhumanshrimpsheeptiger剔拓?fù)渑判騠ishhumansheeptiger剔除plankton剔除wheat剔除shrimp2022/10/30146-拓?fù)渑判騠ishhumansheeptiger剔除plan拓?fù)渑判騢umansheeptiger剔除plankton剔除wheat剔除shrimp剔除fish2022/10/30147-拓?fù)渑判騢umansheeptiger剔除plankton拓?fù)渑判騢umantiger剔除plankton剔除wheat剔除shrimp剔除fish剔除sheep2022/10/30148-拓?fù)渑判騢umantiger剔除plankton剔除wh拓?fù)渑判騮iger剔除plankton剔除wheat剔除shrimp剔除fish剔除sheep剔除human2022/10/30149-拓?fù)渑判騮iger剔除plankton剔除wheat剔除拓?fù)渑判蛱蕹齪lankton剔除wheat剔除shrimp剔除fish剔除sheep剔除human剔除tiger求得的解是plankton，wheat，shrimp，fish，sheep，human，tiger2022/10/30150-拓?fù)渑判蛱蕹齪lankton剔除wheat剔除shri生成組合對(duì)象的算法1.生成排列對(duì)于n個(gè)元素，如何生成其排列呢？可以想像已經(jīng)生成了n-1個(gè)元素的排列，我們可以將第n個(gè)元素插入到n-1個(gè)元素所產(chǎn)生的全部排列中去開(kāi)始時(shí)將n從右往左插入到前面n-1生成的排列中去,然后每處理一個(gè)新的排列時(shí)，再調(diào)換方向。開(kāi)始： 1開(kāi)從右往左將2插入： 1221開(kāi)從右往左將3插入： 123132312 開(kāi)從左往右將3插入： 321231213 2022/10/30151-生成組合對(duì)象的算法1.生成排列開(kāi)始： 1用該方法生成排列有什么優(yōu)點(diǎn)呢？

滿足最小變化的要求2022/10/30152-用該方法生成排列有什么優(yōu)點(diǎn)呢？2022/10/23152-Johnson-Trotter算法生成排列該算法是一種有效的生成排列的算法將每個(gè)元素賦予一個(gè)方向，如果箭頭指向一個(gè)相鄰的較小元素，我們說(shuō)它在這個(gè)箭頭標(biāo)記的排列中是移動(dòng)的元素。例如32412022/10/30153-Johnson-Trotter算法生成排列該算法是一種有效的應(yīng)用該算法生成3個(gè)元素的所有排列過(guò)程如下將所有元素初始化為123，以后重復(fù)執(zhí)行2-5步驟如果存在移動(dòng)元素，則找到最大的移動(dòng)元素k把k和它所指向的相鄰元素互換跳轉(zhuǎn)所有大于k的元素的方向?qū)⑴帕屑拥搅斜碇?022/10/30154-應(yīng)用該算法生成3個(gè)元素的所有排列過(guò)程如下2022/10/23生成字典序排列的算法Johnson-Trotter算法生成的是最小變化的序該算法生成的不是字典順序的序列字典序列123，132，213，231，312，312如何生成字典序列呢？從右往左尋找到第一對(duì)升序序的數(shù)字ai,ai+1，然后在ai+1到an中找到最小的大于ai的數(shù)字，將其與ai交換，然后將ai與后面的其他數(shù)字進(jìn)行升序排列

四個(gè)數(shù)的字典序列1234124313241342……2022/10/30155-生成字典序排列的算法Johnson-Trotter算法生成的生成子集利用減1思想，集合分成2個(gè)部分，一個(gè)部分包含an，一個(gè)部分是其他n-1個(gè)元素的所有集合，通過(guò)把a(bǔ)i+1加入到每一個(gè)子集中來(lái)獲得全部n個(gè)元素的子集利用n個(gè)元素的2n個(gè)子集和長(zhǎng)度為n的所有2n個(gè)比特串之間的對(duì)象關(guān)系，二進(jìn)制比特串的第i位為1表示n個(gè)元素中的第i個(gè)元素在該集合中，為o表示不在該集合中，如3位的比特串010，表示該子集中只有第2個(gè)元素。如3個(gè)元素的a1a2a3所有子集 000001010011100101110111空集a3a2a2a3a1a1a3a1a2a1a2a32022/10/30156-生成子集利用減1思想，集合分成2個(gè)部分，一個(gè)部分包含an，一格雷碼格雷碼是一個(gè)數(shù)列集合，相鄰兩數(shù)間只有一個(gè)位元改變，為無(wú)權(quán)數(shù)碼，且格雷碼的順序不是唯一的。某些情況，例如從十進(jìn)制的3轉(zhuǎn)換成4時(shí)二進(jìn)制碼的每一位都要變，使數(shù)字電路產(chǎn)生很大的尖峰電流脈沖。而格雷碼則沒(méi)有這一缺點(diǎn)，它是一種數(shù)字排序系統(tǒng)，其中的所有相鄰整數(shù)在它們的數(shù)字表示中只有一個(gè)數(shù)字不同。它在任意兩個(gè)相鄰的數(shù)之間轉(zhuǎn)換時(shí)，只有一個(gè)數(shù)位發(fā)生變化。它大大地減少了由一個(gè)狀態(tài)到下一個(gè)狀態(tài)時(shí)邏輯的混淆。2022/10/30157-格雷碼格雷碼是一個(gè)數(shù)列集合，相鄰兩數(shù)間只有一個(gè)位元改變，為無(wú)如何生成格雷碼方法1：以二進(jìn)制為0值的格雷碼為第零項(xiàng)，第一項(xiàng)改變最右邊的位元，第二項(xiàng)改變右起第一個(gè)為1的位元的左邊位元，第三、四項(xiàng)方法同第一、二項(xiàng)，如此反覆，即可排列出n個(gè)位元的格雷碼。方法2：先生成n-1的二進(jìn)制格雷碼序列a，然后復(fù)制一份該代碼序列b，將0加在a序列的最左邊，將1加在序列b的最左邊，然后將修改后的b序列反序連接在修改后a序列后2022/10/30158-如何生成格雷碼2022/10/23158-減常量因子在這種減治法中，每次減去一個(gè)相同的常量因子。例如：假幣問(wèn)題俄式乘法2022/10/30159-減常量因子在這種減治法中，每次減去一個(gè)相同的常量因子。202假幣問(wèn)題（簡(jiǎn)單版本）在n枚外觀相同的硬幣中尋找一枚假幣.

有一架沒(méi)有刻度的天平但是能夠顯示兩邊的重量是否相等,如果相等，天平就不會(huì)傾斜，如果不相等，重的一邊就會(huì)傾斜

設(shè)計(jì)一個(gè)有效的算法來(lái)找出這枚假幣。假設(shè)這枚假幣比真幣要輕。2022/10/30160-假幣問(wèn)題（簡(jiǎn)單版本）在n枚外觀相同的硬幣中尋俄式乘法問(wèn)題:兩個(gè)正整數(shù)相乘該問(wèn)題能夠使用下面的公式進(jìn)行減半的運(yùn)算:對(duì)于每一個(gè)n:如果n是奇數(shù):n*m=*2m

n*m=*2m+mifn>1andmifn=1n2n–122022/10/30161-俄式乘法問(wèn)題:兩個(gè)正整數(shù)相乘對(duì)于每一個(gè)n:如果n是奇數(shù)俄式乘法Compute20*26

nm

2026105251041042208+1416416

520

Note:把所有n列中包含基數(shù)的m列元素進(jìn)行相加2022/10/30162-俄式乘法Compute20*26520Note:約瑟夫斯問(wèn)題問(wèn)題的提出2022/10/30163-約瑟夫斯問(wèn)題問(wèn)題的提出2022/10/23163-減可變因子在這種減治法當(dāng)中，每次迭代都減小規(guī)模不同的因子。例如:歐幾里得算法查找問(wèn)題—計(jì)算中值和選擇問(wèn)題2022/10/30164-減可變因子在這種減治法當(dāng)中，每次迭代都減小規(guī)模不同的因子。歐幾里得求最大公約數(shù)算法歐幾里得算法重復(fù)使用公式：gcd(m,n)=gcd(n,mmodn)例如:

gcd(80,44)=gcd(44,36)=gcd(36,8)=gcd(8,4)余數(shù)為0結(jié)束，取次數(shù)被除數(shù)作為最大公約數(shù)T(n)

O(logn)2022/10/30165-歐幾里得求最大公約數(shù)算法歐幾里得算法重復(fù)使用公式：2022/查找問(wèn)題在n個(gè)數(shù)中查找第k小的元素k=1ork=n中值:k=n/2

例如:4,1,10,9,7,12,8,2,15 中值=?中值是數(shù)理統(tǒng)計(jì)中用來(lái)求平均值的一個(gè)很好的方法事實(shí)上，它比其他類(lèi)似合并排序的算法要優(yōu)秀很多。2022/10/30166-查找問(wèn)題2022/10/23166-a[0]a[1]a[2]a[3]…a[j-1]…a[n-1]如果有一個(gè)數(shù)組a[n]，現(xiàn)要求出其中第k小元素a[0]a[1]a[2]a[3]……a[i]a[n-1]A:以數(shù)組第一個(gè)元素為標(biāo)準(zhǔn)，利用快速排序得到此數(shù)值在數(shù)組中的位置是第j個(gè)K<j-1K=j-1a[j-1]…a[n]a[0]…a[j-1]K>=j繼續(xù)步驟Aa[j-1]即為所求求第K小元素2022/10/30167-a[0]a[1]a[2]a[3]…a[j-1]…a[n-1411097128215K=[9/2]=5中值問(wèn)題2022/10/30168-411097128215K=[9/2]=5中值問(wèn)題2022/411097128215214971281015K=[9/2]=5中值問(wèn)題2022/10/30169-411097128215214971281015K=[9/2411097128215214971281015S=3<5,處理列表的右邊部分。K=[9/2]=5中值問(wèn)題2022/10/30170-411097128215214971281015S=3<5,411097128215214971281015S=3<5,處理列表的右邊部分。971281015K=[9/2]=5中值問(wèn)題2022/10/30171-411097128215214971281015S=3<5,411097128215214971281015S=3<5,處理列表的右邊部分。971281015K=[9/2]=5879121015中值問(wèn)題2022/10/30172-411097128215214971281015S=3<5,411097128215214971281015S=3<5,處理列表的右邊部分。971281015K=[9/2]=5879121015S=6>5,處理列表的左邊部分。中值問(wèn)題2022/10/30173-411097128215214971281015S=3<5,411097128215214971281015S=3<5,處理列表的右邊部分。971281015K=[9/2]=5879121015S=6>5,處理列表的左邊部分。8中值問(wèn)題2022/10/30174-411097128215214971281015S=3<5,411097128215214971281015S=3<5,處理列表的右邊部分。971281015K=[9/2]=5879121015S=6>5,處理列表的左邊部分。87中值問(wèn)題202