(考研復(fù)試)計(jì)算機(jī)算法與分析筆記

1、1：遞歸算法，分治法，貪心算法，動(dòng)態(tài)規(guī)劃，基本檢索和周游方法，回溯法，并行算法。 遞歸2：0/1背包問題：背包最大承受重量m，現(xiàn)在有n個(gè)物品為質(zhì)量m1,m2,m3mn，要從n個(gè)物品中挑選若干件，使放入背包的質(zhì)量之和為m。（0/1的意思就是，一個(gè)物品，要么取，要么不?。┮婚_始是mn放進(jìn)容量為m的包中，如果沒滿，就把m1到m（n-1）放入容量為m-mn的包中，如果滿了，就放棄mn，查看m（n-1）.knap（m，n），如果mn能放得進(jìn)去，就進(jìn)一步考慮knap（m-mn，n-1），如果mn放不進(jìn)去，就考慮knap（m，n-1）2：漢諾塔問題：hanoi(n-1,one,three,two)先把n-1

2、個(gè)盤子從1柱借助3柱移動(dòng)到2柱子，move(one,three)然后把1住上還身下的第n個(gè)盤子移到3柱hanoi(n-1,two,one,three)最后把2住上的n-1塊盤子借助1柱移動(dòng)到3柱。3：自然數(shù)拆分：任何一個(gè)大于1的自然數(shù)都可以劃分成若干個(gè)小于n的自然數(shù)之和。有n/2種拆分split（7）=1+split（6）=2+split（5）=3+split（4） 分治法4：求解一個(gè)輸入規(guī)模很大的問題，直接求解很麻煩，將輸入規(guī)模分成k個(gè)不同的子集合，得到k個(gè)不同可獨(dú)立求解的子問題，求出這些解之后，可以找到適當(dāng)?shù)姆椒ê喜⒊烧麄€(gè)問題的解。5：二分查找，二路歸并，快速分類，快速排序，6：找最大和最

3、小元素：就是把數(shù)組一分為2，選出左半邊的最大值和最小值，選出右半邊的最大值和最小值，然后兩個(gè)最大值相比，選出最大值，然后兩個(gè)最小值相比，選出最小值。maxmin（i,j,max,min）/i到j(luò)中的最大值和最小值。如果i=j，則說明max=min如果i=j-1，說明就兩個(gè)數(shù)字，直接判斷就是了。否則，就運(yùn)行 maxmin（i，mid，max，min）和maxmin（mid=1，j，max,min）7：找出第k小的元素（并把該元素放在位置k上，并且左邊的小于k，右邊的大于k）：用快速分類partition（m,j），返回值是x，x是首元素被劃分以后再數(shù)組中的位置，也就第x小的元素。那么再判斷，如果

4、x=k，就正確，如果x大于k，就partition(m,x)，如果x小于k，就partiotion（x+1，j）8：二次取中法：一位數(shù)組劃分成多個(gè)等長的一位數(shù)組，然后分別求中間值，然后諸多中間值再求中間值。9：用二次取中法求第k小元素。先用二次取中法求得中間值，然后判斷中間值是不是第k小的元素，如果不是，再對兩邊分別二次取中，遞歸。10：斯特拉森矩陣：把16*16的矩陣分塊，每個(gè)矩陣?yán)锩嬗?個(gè)小矩陣，每個(gè)小矩陣是8*8，然后用分塊矩陣相乘。 貪心算法11：現(xiàn)實(shí)世界中，有的問題有很多可以滿足約束條件的解，這些解就叫做可行解。為了衡量這些解，我們給出目標(biāo)函數(shù)，那些使目標(biāo)函數(shù)取極值的可行解稱之為最優(yōu)

5、解。這些問題可以用線性規(guī)劃，非線性規(guī)劃，動(dòng)態(tài)規(guī)劃等問題來解決，12：但是有些問題可以選出一種度量值，然后按照這種度量值對輸入排序，然后從排序中選出最優(yōu)解，這種分級處理方法就是貪心方法。13：背包問題：價(jià)值/重量 來衡量。14：帶有限期的作業(yè)排序：也是先看效益值，效益值從高到低依次加入，然后判斷是不是可行解。15：最優(yōu)歸并模式（哈夫曼樹）：30 20 10 三個(gè)記錄，如果先歸并30和20就要移動(dòng)50次，然后歸并10和50移動(dòng)60，一共110次。但是如果換種方法，先歸并20和10，移動(dòng)30次，然后歸并30和30，移動(dòng)60次，一共移動(dòng)90次。于是就要用哈弗曼樹的方法。16：最小生成樹：prim方法和

6、kruskal（克魯斯卡爾）方法單源最短路徑。 動(dòng)態(tài)規(guī)劃17：一個(gè)問題，活動(dòng)過程可以分為若干個(gè)階段，而且在任一階段后的行為都僅依賴于此階段的過程狀態(tài)，與此階段之前的過程如何達(dá)到這種狀態(tài)無關(guān)，這就是多段決策過程。多段決策過程的每個(gè)階段都可能有多重可供選擇的決策，必須從中選取一種決策，一旦各個(gè)階段的決策選定之后，就構(gòu)成了解決這種問題的一個(gè)決策序列。決策序列不同導(dǎo)致問題結(jié)果也不同，動(dòng)態(tài)規(guī)劃就是要選取最優(yōu)決策序列。18：最優(yōu)性原理：無論過程的初始狀態(tài)和初始決策是什么，其余的決策都必須相對于初始決策所產(chǎn)生的狀態(tài)構(gòu)成一個(gè)最優(yōu)決策序列，這是一個(gè)遞推。19：動(dòng)態(tài)規(guī)劃有向前處理（從最后的階段開始，逐步向前地推的

7、方式列出求前一階段決策值的遞推關(guān)系式）和向后處理20：多段圖問題：vi中的節(jié)點(diǎn)j到匯點(diǎn)的成本=諸多l(xiāng)中的最小值（j到l的成本+v（i+1）中的l到匯點(diǎn)的成本）也就是我從重慶到江西的成本等于重慶到湖南某個(gè)市的成本加上這個(gè)市到江西的成本。比如有源點(diǎn)s v2 v3 v4 匯點(diǎn)t，向前處理法就是：先算出v4的每個(gè)點(diǎn)到匯點(diǎn)的成本，然后通過v4的每個(gè)點(diǎn)到匯點(diǎn)的成本算出v3的每個(gè)點(diǎn)到匯點(diǎn)的最小成本，依次類推。這樣，v2判斷的時(shí)候只需要知道v3的每個(gè)點(diǎn)到匯點(diǎn)的成本即可，與v3到v4，v4到匯點(diǎn)的成本不用關(guān)心。21：最優(yōu)二叉排序樹：定義成本概念就是成功查找和不成功查找的概率乘以權(quán)值。那么最優(yōu)二叉排序樹，他的兩個(gè)子樹也應(yīng)該是最優(yōu)二叉排序樹。22：貨郎擔(dān)問題：就是求取最小成本的周游路線問題。假設(shè)是從1出發(fā)回到1，那么周游路線應(yīng)該是從1