第一篇：計(jì)算機(jī)算法總結(jié)

算法總結(jié)

1.窮舉法

窮舉法，又稱暴力算法，即列舉問題解空間所有可能情況，并逐個(gè)測(cè)試，從而找出符合問題條件的解。這份通常是一種費(fèi)時(shí)算法，人工手動(dòng)求解困難，但計(jì)算機(jī)的出現(xiàn)使得窮舉法有了用武之地。例如:密碼破譯通常用的是窮舉法，即將密碼進(jìn)行逐個(gè)推算直到找到真正的密碼為止。理論上講，窮舉法可以破解任何一種密碼，但對(duì)于一個(gè)長(zhǎng)度為n位的密碼，其可能的密碼有2^n種。可見，當(dāng)n較大時(shí)窮舉法將成為一個(gè)NP難度問題。典型例題

【百錢買百雞問題】公元5世紀(jì)末，中國(guó)古代數(shù)學(xué)家張丘建在他的《算經(jīng)》中提到了著名的―百錢買百雞‖問題:雞翁一，值錢五，雞母一，值錢三，雞雛三，值錢一，百錢買百雞，問翁、母、雛各幾何？

分析:設(shè)雞翁、雞母、雞雛的個(gè)數(shù)各為x、y、z,百錢買百雞問題可以用如下方程式表示: 5x+3y+z/3=100 x+y+z=100

1<=x<20,1<=y<33,3<=z<100,z mod3=0

對(duì)于百錢買白雞問題，很容易用窮舉法對(duì)x、y、z的取值，判斷方程（1）、（2）及z mod3=0是否成立，若成立，則是問題的一個(gè)解。

百錢買白雞問題求解算法: //百錢買白雞問題窮舉算法

//設(shè)雞翁、雞母、雞雛的個(gè)數(shù)分別為x、y、z for（x=1;x<20;x++）

for（y=1;y<33;y++）

for（z=3;z<100;z++）

if（x+y+z= =100）and（5x+3y+z/3==100）and（z mod 3==0）

writeln（x,y,z）

上述算法是一個(gè)三重循環(huán)，最內(nèi)層的條件判斷需要執(zhí)行19*32*97次，即58976。在條件判斷中，利用了整數(shù)的求模運(yùn)算，如果將雞雛的個(gè)數(shù)設(shè)為3z，可以避免該項(xiàng)判斷，且可減少內(nèi)重循環(huán)次數(shù)。即: for（z=1;z<34;z++）

if（x+y+3z==100）and（5x+3y+z==100）

writeln（x,y,3z）

【 0-1背包問題1】給定n種物品和一個(gè)背包，物品i的重量是Wi，其價(jià)值為Vi，背包的容量為Wm。應(yīng)如何選擇裝入背包的物品，使得裝入背包的物品總價(jià)值最大？

分析:所謂0-1背包問題，是指在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有兩種選擇，即裝入背包或不裝入背包。另外，不能將物品i裝入背包多次，也不能只裝入部分的物品i。0-1背包問題是一種組合優(yōu)化的NP完全問題，最容易想到方法的就是窮舉法。

0-1背包問題求解的窮舉算法。

//設(shè)數(shù)組w[0…n–1]存儲(chǔ)n件物品的重量，數(shù)組c[0…n-1]存儲(chǔ) //n件物品的價(jià)值，數(shù)組b[0…n-1]為標(biāo)識(shí)數(shù)組，若物品i未選 //擇，則b[i-1]=0，否則b[i-1]=1 cmax=0

for（i=1;i<=2^n-1;i++）{

b[0..n-1]=將i轉(zhuǎn)化為n位的二進(jìn)制字符串 tempw=求和b[j]*w[j] tempc=求和b[j]*c[j]

If（tempwcmax）{

tempb=b[0..n-1];cmax=tempc;} }

輸出最佳方案tempb[0..n-1],cmax 結(jié)束

2.遞推法

遞推算法是一種根據(jù)遞推關(guān)系進(jì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

遞推算法是一種簡(jiǎn)單的算法，通過已知條件利用特定的遞推關(guān)系可以得到中間推論，直至得到問題的最終結(jié)果。遞推算法分為順推法和逆推法兩種。

【斐波那契數(shù)列算法1】斐波那契數(shù)列，又稱為黃金分割數(shù)列。在數(shù)學(xué)上，斐波那契數(shù)列可以用遞推方法定義，其遞推公式為F1=0,F2=1,Fn=F(n-1)+F(n-2)(n>=3,n∈N*)。寫一算法求斐波那契數(shù)列第10項(xiàng)的值。

分析:從斐波那契數(shù)列的定義可知，數(shù)列的第一項(xiàng)為一，第二項(xiàng)也為一，遞推關(guān)系是當(dāng)前項(xiàng)等于前二項(xiàng)之和。因此，通過順推可以得到f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3,f(5)=f(3)+f(4)=5，以此類推，可以得到f(10)的值。求斐波那契數(shù)列的順推算法:

//求斐波那契數(shù)列第十項(xiàng)的值并輸出 f[1]=1 f[2]=2 n=3

while（n<=10）{

f[n]=f[n-1]+f[n-2]

n=n+1 }

write(f[10])

3.遞歸法

在問題求解思想上，遞推是從已知條件出發(fā)，一步步遞推出未知項(xiàng)，直到問題的解。遞歸也是遞推的一種，只不過它是對(duì)待解問題的遞推，直到把一個(gè)復(fù)雜的問題遞推為簡(jiǎn)單的易解問題，然后再一步步返回，從而得到原問題的解。【斐波那契數(shù)列算法2】利用遞歸思想寫出求斐波那契數(shù)列的遞歸算法。分析：在問題求解中，求解同一個(gè)問題的方法通常不止一個(gè)。根據(jù)遞歸法的思想，由斐波那契數(shù)列遞推公式可以很容易地寫出遞歸算法，偽代碼描述如下。

求斐波那契數(shù)列遞歸算法: //函數(shù)fib返回第n(n>=1)個(gè)斐波那契數(shù)列的值 int fib(int n){ if(n ==1)return(1)else if(n ==2)return(2)else return(fib(n-1)+fib(n-2))} 【Hanoi塔問題】Hanoi塔問題（Tower of Hanoi Problem）遞歸算法。

分析：可以把問題用初始狀態(tài)和目標(biāo)狀態(tài)來表達(dá)，問題求解就是要找出搬移的次序和所有的中間狀態(tài)。

Hanoi塔問題遞歸算法: //n為盤子數(shù)目

//三根柱子from、to和temp分別表示起始柱子、目標(biāo)柱子和臨時(shí)柱子 void hanoitower(n,from,to,temp){ if(n>0){

//把from柱子上的n-1個(gè)盤子搬移到temp柱子上，用to柱做臨時(shí)柱子 hanoitower(n-1,from,temp,to);movedisk(from,to);

//把temp柱子上的n-1個(gè)盤子搬移到to柱子上，用from柱做臨時(shí)柱子 hanoitower(n-1,temp,to,from);} }

4.回溯法

試探-失敗返回-再試探的問題求解方法稱為回溯法，回溯算法的基本思想是：從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)則退回來，換一條路再試。對(duì)于用回溯法求解的問題，首先要將問題進(jìn)行適當(dāng)?shù)霓D(zhuǎn)化，得出狀態(tài)空間樹。這棵樹的每條完整路徑都代表了一種解的可能。通過深度優(yōu)先搜索這棵樹，枚舉每種可能的解的情況；從而得出結(jié)果。但是，回溯法中通過構(gòu)造約束函數(shù)，可以大大提升程序效率，因?yàn)樵谏疃葍?yōu)先搜索的過程中，不斷的將每個(gè)解（并不一定是完整的，事實(shí)上這也就是構(gòu)造約束函數(shù)的意義所在）與約束函數(shù)進(jìn)行對(duì)照從而刪除一些不可能的解，這樣就不必繼續(xù)把解的剩余部分列出從而節(jié)省部分時(shí)間。

【八皇后問題】八皇后問題是十九世紀(jì)著名數(shù)學(xué)家高斯于1850年提出的。問題是：在8*8的棋盤上擺放8個(gè)皇后，使其不能互相攻擊，即任意的兩個(gè)皇后不能處在同意行，同一列，或同意斜線上?？梢园寻嘶屎髥栴}拓展為n皇后問題，即在n*n的棋盤上擺放n個(gè)皇后，使其任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。分析：顯然，每一行可以而且必須放一個(gè)皇后，所以n皇后問題的解可以用一個(gè)n元向量X=（x1,x2,.....xn）表示，其中，1<= i<= n且1<= xi<= n，即第n個(gè)皇后放在第i行第xi列上。

由于兩個(gè)皇后不能放在同一列上，所以，解向量X必須滿足的約束條件為:xi≠ xj;若兩個(gè)皇后的擺放位置分別是（i,xi）和（j,xj），在棋盤上斜率為-1的斜線上，滿足條件i-j=xi-xj;在棋盤上斜率為1的斜線上，滿足條件i+j=xi+xj;綜合兩種情況，由于兩個(gè)皇后不能位于同一斜線上，所以，解向量X必須滿足的約束條件為: |i-xi|≠ |j-xj| 八皇后問題求解的回溯算法:

//試探第i個(gè)皇后，即第i行要放置的皇后位置 void queen(int i){ for(j=0;j<8;j++)

//從第0列開始從左到右依次試探可能的位置 { if(a[j]==0&&c[i+j]==0 //如果無沖突 { 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);//如果行還沒有遍歷完，進(jìn)入下一行 else輸出當(dāng)前的擺放方案,即q數(shù)組;//當(dāng)前列擺放了皇后，要繼續(xù)試探當(dāng)前行下一個(gè)可能的位置，此時(shí)需要 //將當(dāng)前列恢復(fù)為沒有擺皇后的狀態(tài)，嘗試下一個(gè)可能的擺放方案 q[i,j]=’*’;a[j]=0;b[i-j+7]=0;c[i+j]=0;}//end if }//end for } 5.迭代法

迭代法又稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過程，是用計(jì)算機(jī)解決問題的一種基本方法。迭代法也是一種編程技術(shù)方法，它運(yùn)用了遞推的思想方法，利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，重復(fù)執(zhí)行一組指令，不斷從變量的一個(gè)值推出它的下一個(gè)值。

【輾轉(zhuǎn)相除法】使用輾轉(zhuǎn)相除法求兩數(shù)的最大公約數(shù)。

分析：輾轉(zhuǎn)相除法, 又稱歐幾里德算法，是求兩個(gè)正整數(shù)之最大公因子的算法。它是已知最古老的算法之一, 最早可追溯至公元前300年。它首次出現(xiàn)于歐幾里德的《幾何原本》中，而在中國(guó)則可以追溯至東漢出現(xiàn)的《九章算術(shù)》。

設(shè)兩數(shù)為a、b(a>b），求a和b最大公約數(shù)(a，b）的步驟如下：用b除a，得a÷b=q......r1(0≤r1）。若r1=0，則（a，b)=b；若r1≠0，則再用r1除b，得b÷r1=q......r2(0≤r2）.若r2=0，則（a，b)=r1，若r2≠0，則繼續(xù)用r2除r1，……如此下去，直到能整除為止。其最后一個(gè)非零除數(shù)即為（a，b）。

法1：求兩數(shù)的最大公約數(shù)的輾轉(zhuǎn)相除法減法實(shí)現(xiàn): //輾轉(zhuǎn)相除法求兩數(shù)a和b的最大公約數(shù)g int gcd(a,b){ while(a!=0&&b!=0){ if(a>b)a=a-b

/*迭代*/ else b=b-a;

/*迭代*/ } if(a!=0)return a else return b } 法2：求兩數(shù)的最大公約數(shù)的輾轉(zhuǎn)相除法模擬實(shí)現(xiàn): //輾轉(zhuǎn)相除法求兩數(shù)a和b的最大公約數(shù)g int gcd(a,b){ t=a%b;while(t!=0){ a=b;

/*迭代*/ b=t;

/*迭代*/ t=a%b;} return b } 【解一元非線性方程】用迭代法求一元非線性方程f(x)=0的解 分析：當(dāng)f(x)是超越函數(shù)或高次多項(xiàng)式時(shí)，f(x)=0稱為非線性方程，此類方程除少數(shù)情形外，只能求近似解。求解非線性方程的最簡(jiǎn)單的方法是二分法（Bisection method），又稱二分區(qū)間法。其基本思想是設(shè)f(x)在區(qū)間[a,b]上為連續(xù)函數(shù)，如果f(a)?f(b)<0，則f(x)在區(qū)間[a,b]上至少有一個(gè)根。如果f(x)在區(qū)間[a,b]上是單調(diào)的，則f(x)在區(qū)間[a,b]上只存在一個(gè)實(shí)根，如右圖所示。求方程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ù)下面的迭代運(yùn)算。Step4:修改有根區(qū)間

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

4.2若f(x)與f(b)異號(hào),此時(shí)a不變，b←x； Step5:轉(zhuǎn)Step1

Step6:輸出x，即方程的近似解。Step7:結(jié)束。

6.分治法

在求解復(fù)雜問題時(shí)，分治法的基本思想是把一個(gè)復(fù)雜的問題分成若干相對(duì)獨(dú)立而規(guī)模較小的子問題，如果某個(gè)子問題還比較復(fù)雜，再把子問題分成更小的子問題，直到分解后的每個(gè)子問題都可以簡(jiǎn)單的直接求為止，然后通過逐個(gè)解決這些較小的子問題而得到原問題的解，即各個(gè)擊破，分而治之。許多問題可以通過分治法求解，典型的有歸并排序算法，折半查找等。

分治法所能解決的問題一般具有以下幾個(gè)特征：

1)該問題的規(guī)?？s小到一定的程度就可以容易地解決

2)該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。3)利用該問題分解出的子問題的解可以合并為該問題的解； 4)該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子問題?！纠}】給定一個(gè)長(zhǎng)度為n的整數(shù)數(shù)組，編寫一個(gè)求出其最大值和最小值的分治算法。分析：當(dāng)數(shù)組中只有1個(gè)數(shù)時(shí)，可以直接給出結(jié)果；如果有兩個(gè)數(shù)，則一次比較即可得出結(jié)果。當(dāng)n>2時(shí)，可以將數(shù)組分成兩個(gè)元素個(gè)數(shù)較小的數(shù)組，分別求解它們的最大值和最小值，最后比較兩個(gè)數(shù)組的解來得到原問題的解，這樣就分而治之了。

求數(shù)組中最大值和最小值的分治算法: #include

void minmax(int array[], int begin, int end, int &min, int &max, int &count){

int mid =(begin + end)/2;if(begin == end){ count++;

if(array[mid] < min){

min = array[mid];} else {

if(array[mid] > max)max = array[mid];count++;} return;}

minmax(array, begin, mid, min ,max, count);minmax(array, mid + 1, end, min ,max, count);} void main(){

int array[10] = {9,8,7,6,5,4,3,2,1,0};int min = array[0], max =-1, count = 0;minmax(array, 0,9,min,max,count);

printf(“min = %d, max = %d, count = %dn”, min,max,count);}

7.貪心法

貪心算法（又稱貪婪算法）是指，在對(duì)問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。基本思路：

1.建立數(shù)學(xué)模型來描述問題 ⒉把求解的問題分成若干個(gè)子問題。⒊對(duì)每一子問題求解，得到子問題的局部最優(yōu)解。⒋把子問題的解局部最優(yōu)解合成原來解問題的一個(gè)解。實(shí)現(xiàn)該算法的過程：

從問題的某一初始解出發(fā)；

while 能朝給定總目標(biāo)前進(jìn)一步 do 求出可行解的一個(gè)解元素；

由所有解元素組合成問題的一個(gè)可行解。

【0-1背包問題2】有一個(gè)背包，背包容量是M=150。有7個(gè)物品，物品不可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過總?cè)萘?。物?A B C D E F G 重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg 價(jià)值 10$ 40$ 30$ 50$ 35$ 分析：用貪心算法解背包問題的基本步驟是，首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超出C，則選擇單位重量?jī)r(jià)值次高的物品，并盡可能多的裝入背包。依此策略一直進(jìn)行下去，直到背包裝滿為止。0-1背包問題的貪心算法:

#include #include #include #include “time.h” #include “windows.h” #include #include #define num 100 void bagloading(int x[],float p[],float w[],float c,int n){

//x[]取值為0或1，x[i]=1當(dāng)且僅當(dāng)背包i背裝載；

//p[]是物品價(jià)值；

//w[]是物品重量；

//c表示背包的容量；

//n表示物品的件數(shù)； float t,k,pw[num];int i,j,m,kk;for(i=0;i

while(m>0)

{

kk=0;

for(j=0;j

if(pw[j]

{

t=p[j];

p[j]=p[j+1];

p[j+1]=t;

k=w[j];

w[j]=w[j+1];

w[j+1]=k;

kk=j;

}

m=kk;

}

//按p/w次序從大到小選擇物品

i=0;

while(i

{

x[i]=1;

c-=w[i];

i++;

} } int main(){

int n,all;float c,p1,w1;float p[num];float w[num];int x[num];int i;cout<<“請(qǐng)輸入物品的件數(shù)：”;cin>>n;cout<<“請(qǐng)輸入背包的最大容量：”;cin>>c;cout<<“請(qǐng)依次輸入各物品的價(jià)值與重量 n每個(gè)物品的價(jià)值與重量之間用空格隔開，回車后輸入另一個(gè)物品：”<

for(i=0;i

cin>>p[i]>>w[i];} //調(diào)用函數(shù)

bagloading(x,p,w,c,n);//統(tǒng)計(jì)物品的總價(jià)值、總重量以及件數(shù)并輸出

//統(tǒng)計(jì)裝入物品的價(jià)值及重量并輸出

all=0;p1=0.0;w1=0.0;for(i=0;i

if(x[i]==1)

{

all++;

p1=p1+p[i];

w1=w1+w[i];

}

cout<

cout<<“所裝物品總的價(jià)值為：”<

cout<<“所裝物品總的重量為：”<

if(all>0)

{

cout<<“該背包共裝入的這”<

for(i=0;i

if(x[i]==1)

cout<

} system(“pause”);return 0;} 8.動(dòng)態(tài)規(guī)劃法

在現(xiàn)實(shí)生活中，有一類活動(dòng)可將其過程分為若干個(gè)互相聯(lián)系的階段，在它的每個(gè)階段都要做出決策，從而使整個(gè)過程達(dá)到最好的活動(dòng)效果。動(dòng)態(tài)規(guī)劃(dynamic programming)是運(yùn)籌學(xué)的一個(gè)分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學(xué)方法。20世紀(jì)50年代初美國(guó)數(shù)學(xué)家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優(yōu)化問題時(shí)，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——?jiǎng)討B(tài)規(guī)劃。

動(dòng)態(tài)規(guī)劃一般可分為線性動(dòng)規(guī)，區(qū)域動(dòng)規(guī)，樹形動(dòng)規(guī)，背包動(dòng)規(guī)四類。

【0-1背包問題3】

分析：令V(i,j)表示在前i(1<=i<=n)個(gè)物品中能夠裝入容量為就j(1<=j<=C)的背包中的物品的最大價(jià)值，則可以得到如下的動(dòng)態(tài)規(guī)劃函數(shù):(1)V(i,0)=V(0,j)=0

(2)V(i,j)=V(i-1,j)j

V(i,j)=max{V(i-1,j),V(i-1,j-wi)+vi)} j>wi(1)式表明：如果第i個(gè)物品的重量大于背包的容量，則裝人前i個(gè)物品得到的最大價(jià)值和裝入前i-1個(gè)物品得到的最大價(jià)是相同的，即物品i不能裝入背包；第(2)個(gè)式子表明:如果第i個(gè)物品的重量小于背包的容量，則會(huì)有一下兩種情況：(a)如果把第i個(gè)物品裝入背包，則背包物品的價(jià)值等于第i-1個(gè)物品裝入容量位j-wi 的背包中的價(jià)值加上第i個(gè)物品的價(jià)值vi;(b)如果第i個(gè)物品沒有裝入背包，則背包中物品價(jià)值就等于把前i-1個(gè)物品裝入容量為j的背包中所取得的價(jià)值。顯然，取二者中價(jià)值最大的作為把前i個(gè)物品裝入容量為j的背包中的最優(yōu)解。

0-1背包問題的動(dòng)態(tài)規(guī)劃法: //計(jì)算

for(i=1;ij,第i個(gè)物品不裝入背包 value[i][j]=value[i-1][j];//w[i]<=j,且第i個(gè)物品裝入背包后的價(jià)值>value[i-1][j],則記錄當(dāng)前最大價(jià)值 int temp=value[i-1][j-w[i]]+v[i];if(w[i]<=j && temp>value[i][j])value[i][j]=temp;} }

第二篇：《計(jì)算機(jī)算法》實(shí)驗(yàn)報(bào)告

1.實(shí)驗(yàn)名稱

本次實(shí)驗(yàn)的名稱。

2.問題描述

對(duì)本次實(shí)驗(yàn)要解決的問題的描述。

例子：處理漢諾塔問題時(shí)，描述什么是漢諾塔問題。

3.解決思路

采用什么方法；為什么可以采用這個(gè)方法； 例子：處理棋盤覆蓋問題時(shí)，采用什么方法：采用遞歸分治的方法處理；

為什么可以采用遞歸分治方法的原因（P21頁圖2-6下面一段，理解之后用自己的話表述）：由于將棋盤橫、縱各一分為二之后，特殊方格必然位于四個(gè)小的棋盤之一，那么剩余的其余三個(gè)小棋盤是沒有方格的，如果采用某種L型骨牌覆蓋沒有特殊方格的三個(gè)小棋盤的中心相連部分（參見圖2-6的b），則三個(gè)小棋盤都各有1個(gè)特殊方格所覆蓋。因此，這樣處理之后，原來大棋盤覆蓋的問題，就轉(zhuǎn)化為四個(gè)小棋盤覆蓋的問題，因此可以采用分治策略進(jìn)行遞歸處理。

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

給出算法設(shè)計(jì)的基本思想，如：偽算法描述，遞歸方程等。并分析算法的時(shí)間復(fù)雜度（空間復(fù)雜度）。注意，一定要有文字說明。例子：快速排序 偽算法描述

QuickSort(int a[], int p, int r){ 如果待排序數(shù)組a[]中只有一個(gè)元素則直接返回； 如果待排序數(shù)組a[]中不止一個(gè)元素，則進(jìn)行如下處理 {

對(duì)數(shù)組a[p:r]進(jìn)行Partition劃分，使得a[p:r]以a[p]為標(biāo)準(zhǔn)，劃分為三個(gè)部分，即：

左半部分a[p:q-1]；劃分基準(zhǔn)a[q]=a[p]；右半部分a[q+1:r]；

對(duì)左半部分快速排序QuickSort(a, p, q-1);

對(duì)右半部分快速排序QuickSort(a, q+1, r)； } }

例子：0-1背包問題

遞歸關(guān)系或者遞歸方程。

給出P72頁“2.遞歸關(guān)系”中的遞歸表達(dá)式，并給出文字說明。注意：偽算法描述，或者遞歸方程不一定全部需要。根據(jù)問題的不同，只給出偽算法，或者只給出遞歸方程都可以。兩者同時(shí)給出也是可以的。

5.程序?qū)崿F(xiàn)

依據(jù)第4部分，給出C語言（其他語言亦可）的程序?qū)崿F(xiàn)，并進(jìn)行算法時(shí)間（空間）復(fù)雜度分析。

程序?qū)崿F(xiàn)部分要包括：程序代碼、程序注釋、程序運(yùn)行結(jié)果（或者截圖）。

例子：快速排序的partition函數(shù) int Partition(Type a[], int p, int r){

int i=p, j= r+1;

int x = a[p];//x=a[p]是對(duì)數(shù)組a進(jìn)行劃分的標(biāo)準(zhǔn)；

/* 以下循環(huán)將數(shù)組a[p:r]以a[p]為標(biāo)準(zhǔn)進(jìn)行劃分，在劃分完畢之后，* a[p]調(diào)整到數(shù)組a[p:r]的中間位置q，有a[q]=a[p]；q左邊所有的* 元素均小于a[p]，即a[p:q-1]中的任意元素都小于a[p]；q右邊

* 所有的元素均大于a[p]，即a[q+1:r]中的元素都大于a[p]。

* /

while(true){ /* i用來從數(shù)組a[p:r]的左邊向右邊掃描，如果a[++i]中的元素總是 * 小于基準(zhǔn)元素的，則是符合劃分標(biāo)準(zhǔn)的，因此，不用額外處理，* 循環(huán)一直繼續(xù),直到第一個(gè)不滿足劃分標(biāo)準(zhǔn)的a[++i]（即a[++i]>=i）* 出現(xiàn)，或者整個(gè)數(shù)組a[p:r]掃描完畢（即i

while(a[++i]

??

6.總結(jié)

不用每個(gè)實(shí)驗(yàn)寫一個(gè)總結(jié)，可以在一次課作業(yè)的最后寫一個(gè)總結(jié)。當(dāng)然，如果需要，在每一個(gè)實(shí)驗(yàn)結(jié)尾都寫一個(gè)總結(jié)也是可以的。總結(jié)的目的是自己知識(shí)學(xué)習(xí)的總結(jié)、解決問題的總結(jié)、編程的總結(jié)等等。

第三篇：《計(jì)算機(jī)算法》實(shí)驗(yàn)報(bào)告范文(例文)

1.實(shí)驗(yàn)名稱 本次實(shí)驗(yàn)的名稱。

2.問題描述 對(duì)本次實(shí)驗(yàn)要解決的問題的描述。

例子：處理漢諾塔問題時(shí)，描述什么是漢諾塔問題。

3.解決思路 采用什么方法；為什么可以采用這個(gè)方法； 例子：處理棋盤覆蓋問題時(shí)，采用什么方法：采用遞歸分治的方法處理； 為什么可以采用遞歸分治方法的原因（P21 頁圖 2-6 下面一段，理解之后用自己的話表述）：由于將棋盤橫、縱各一分為二之后，特殊方格必然位于四個(gè)小的棋盤之一，那么剩余的其余三個(gè)小棋盤是沒有方格的，如果采用某種 L 型骨牌覆蓋沒有特殊方格的三個(gè)小棋盤的中心相連部分（參見圖 2-6 的 b），則三個(gè)小棋盤都各有 1 個(gè)特殊方格所覆蓋。因此，這樣處理之后，原來大棋盤覆蓋的問題，就轉(zhuǎn)化為四個(gè)小棋盤覆蓋的問題，因此可以采用分治策略進(jìn)行遞歸處理。

4.算法設(shè)計(jì)與分析 給出算法設(shè)計(jì)的基本思想，如：偽算法描述，遞歸方程等。并分析算法的時(shí)間復(fù)雜度（空間復(fù)雜度）。注意，一定要有文字說明。

例子：快速排序 偽算法描述 QuickSort(int a[], int p, int r){ 如果待排序數(shù)組 a[]中只有一個(gè)元素則直接返回； 如果待排序數(shù)組 a[]中不止一個(gè)元素，則進(jìn)行如下處理 {

對(duì)數(shù)組 a[p:r]進(jìn)行 Partition 劃分，使得 a[p:r]以 a[p]為標(biāo)準(zhǔn)，劃分為三個(gè)部分，即：

左半部分 a[p:q-1]；劃分基準(zhǔn) a[q]=a[p]；右半部分 a[q+1:r]；

對(duì)左半部分快速排序 QuickSort(a, p, q-1);

對(duì)右半部分快速排序 QuickSort(a, q+1, r)； } }

例子：0-1 背包問題 遞歸關(guān)系或者遞歸方程。

給出 P72 頁“2.遞歸關(guān)系”中的遞歸表達(dá)式，并給出文字說明。

注意：偽算法描述，或者遞歸方程不一定全部需要。根據(jù)問題的不同，只給出偽算法，或者只給出遞歸方程都可以。兩者同時(shí)給出也是可以的。

5.程序?qū)崿F(xiàn) 依據(jù)第 4 部分，給出 C 語言（其他語言亦可）的程序?qū)崿F(xiàn)，并進(jìn)行算法時(shí)間（空間）復(fù)雜度分析。

程序?qū)崿F(xiàn)部分要包括：程序代碼、程序注釋、程序運(yùn)行結(jié)果（或者截圖）。

例子：快速排序的 partition 函數(shù) int Partition(Type a[], int p, int r){

int i=p, j= r+1;

int x = a[p];

//x=a[p]是對(duì)數(shù)組 a 進(jìn)行劃分的標(biāo)準(zhǔn)；

/* 以下循環(huán)將數(shù)組 a[p:r]以 a[p]為標(biāo)準(zhǔn)進(jìn)行劃分，在劃分完畢之后，* a[p]調(diào)整到數(shù)組 a[p:r]的中間位置 q，有 a[q]=a[p]；q 左邊所有的* 元素均小于 a[p]，即 a[p:q-1]中的任意元素都小于 a[p]；q 右邊

* 所有的元素均大于 a[p]，即 a[q+1:r]中的元素都大于 a[p]。

* /

while(true){ /* i 用來從數(shù)組 a[p:r]的左邊向右邊掃描，如果 a[++i]中的元素總是 * 小于基準(zhǔn)元素的，則是符合劃分標(biāo)準(zhǔn)的，因此，不用額外處理，* 循環(huán)一直繼續(xù),直到第一個(gè)不滿足劃分標(biāo)準(zhǔn)的 a[++i]（即 a[++i]>=i）

* 出現(xiàn)，或者整個(gè)數(shù)組 a[p:r]掃描完畢（即 i

*/

while(a[++i]

…… 6.總結(jié) 不用每個(gè)實(shí)驗(yàn)寫一個(gè)總結(jié)，可以在一次課作業(yè)的最后寫一個(gè)總結(jié)。當(dāng)然，如果需要，在每一個(gè)實(shí)驗(yàn)結(jié)尾都寫一個(gè)總結(jié)也是可以的?？偨Y(jié)的目的是自己知識(shí)學(xué)習(xí)的總結(jié)、解決問題的總結(jié)、編程的總結(jié)等等。

第四篇：計(jì)算機(jī)算法常用術(shù)語中英對(duì)照

第一部分 計(jì)算機(jī)算法常用術(shù)語中英對(duì)照

Data Structures 基本數(shù)據(jù)結(jié)構(gòu)Dictionaries 字典Priority Queues 堆Graph Data Structures 圖Set Data Structures 集合Kd-Trees 線段樹 Numerical Problems 數(shù)值問題Solving Linear Equations 線性方程組 Fourier變換

Bandwidth Reduction 帶寬壓縮Matrix Multiplication 矩陣乘法Satisfiability 可滿足性 Determinants and Permanents 行列式Linear Programming 線性規(guī)劃Matching 匹配 Constrained and Unconstrained Optimization 最值問題Clique 最大團(tuán)Cryptography 密碼 Random Number Generation 隨機(jī)數(shù)生成Shortest Path 最短路徑recursion遞歸 Factoring and Primality Testing 因子分解/質(zhì)數(shù)判定 Searching 查找Sorting 排序 Arbitrary Precision Arithmetic 高精度計(jì)算Calendrical Calculations 日期

Discrete Fourier Transform 離散Combinatorial Problems 組合問題

Median and Selection 中位數(shù)Generating Permutations 排列生成Generating Subsets 子集生成Generating Partitions 劃分生成Generating Graphs 圖的生成Job Scheduling 工程安排

Graph Problems--polynomial 圖論-多項(xiàng)式算法Connected Components 連通分支Topological Sorting 拓?fù)渑判騇inimum Spanning Tree 最小生成樹

Transitive Closure and Reduction 傳遞閉包Network Flow 網(wǎng)絡(luò)流

Eulerian Cycle / Chinese Postman Euler回路/中國(guó)郵路

Edge and Vertex Connectivity 割邊/割點(diǎn)Independent Set 獨(dú)立集

Drawing Graphs Nicely 圖的描繪Drawing Trees 樹的描繪

Planarity Detection and Embedding平面性檢測(cè)和嵌入Vertex Cover 點(diǎn)覆蓋

Graph Problems--hard 圖論-NP問題Traveling Salesman Problem 旅行商問題Hamiltonian Cycle Hamilton回路Graph Partition 圖的劃分

Vertex Coloring 點(diǎn)染色Edge Coloring 邊染色

Graph Isomorphism 同構(gòu)Steiner Tree Steiner樹

Feedback Edge/Vertex Set 最大無環(huán)子圖Computational Geometry 計(jì)算幾何

Convex Hull 凸包Triangulation 三角剖分

Voronoi Diagrams Voronoi圖Nearest Neighbor Search 最近點(diǎn)對(duì)查詢Range Search 范圍查詢Point Location 位置查詢

Intersection Detection 碰撞測(cè)試Bin Packing 裝箱問題

Medial-Axis Transformation 中軸變換Polygon Partitioning 多邊形分割

Simplifying Polygons 多邊形化簡(jiǎn)Shape Similarity 相似多邊形

Motion Planning 運(yùn)動(dòng)規(guī)劃Maintaining Line Arrangements平面分割Minkowski Sum Minkowski和Set and String Problems 集合與串的問題Set Cover 集合覆蓋Set Packing 集合配置

Approximate String Matching 模糊匹配Text Compression 壓縮

DP—Dynamic Programming動(dòng)態(tài)規(guī)劃Longest Common Substring 最長(zhǎng)公共子串Shortest Common Superstring 最短公共父串String Matching 模式匹配

Finite State Machine Minimization 有窮自動(dòng)機(jī)簡(jiǎn)化

第二部分 數(shù)據(jù)結(jié)構(gòu)英語詞匯

數(shù)據(jù)抽象 data abstraction數(shù)據(jù)元素 data element數(shù)據(jù)對(duì)象 data object

數(shù)據(jù)項(xiàng) data item數(shù)據(jù)類型 data type抽象數(shù)據(jù)類型 abstract data type 邏輯結(jié)構(gòu) logical structure物理結(jié)構(gòu) phyical structure線性結(jié)構(gòu) linear structure 非線性結(jié)構(gòu) nonlinear structure基本數(shù)據(jù)類型 atomic data type線性表 linear list

數(shù)組 array直接前趨 immediate predecessor隊(duì)列 queue

串 string固定聚合數(shù)據(jù)類型 fixed-aggregate data type棧 stack

可變聚合數(shù)據(jù)類型 variable-aggregate data type樹 tree圖 grabh

查找，線索 searching更新 updating排序（分類)sorting

插入 insertion刪除 deletion前趨 predecessor

后繼 successor直接后繼 immediate successor雙端列表 deque(double-ended queue)循環(huán)隊(duì)列 cirular queue指針 pointer先進(jìn)先出表（隊(duì)列）first-in first-out list 后進(jìn)先出表（隊(duì)列）last-in first-out list棧底 bottom棧定 top

壓入 push彈出 pop隊(duì)頭 front隊(duì)尾 rear上溢 overflow 下溢 underflow數(shù)組 array矩陣 matrix多維數(shù)組 multi-dimentional array 以行為主的順序分配 row major order以列為主的順序分配 column major order 三角矩陣 truangular matrix對(duì)稱矩陣 symmetric matrix稀疏矩陣 sparse matrix 轉(zhuǎn)置矩陣 transposed matrix鏈表 linked list線性鏈表 linear linked list單鏈表 single linked list多重鏈表 multilinked list 循環(huán)鏈表 circular linked list雙向鏈表 doubly linked list十字鏈表 orthogonal list廣義表 generalized list

鏈 link指針域 pointer field鏈域 link field頭結(jié)點(diǎn) head node頭指針 head pointer 尾指針 tail pointer串 string空白（空格）串 blank string空串（零串）null string子串 substring樹 tree子樹 subtree森林 forest根 root葉子 leaf 結(jié)點(diǎn) node深度 depth層次 level雙親 parents孩子 children 兄弟 brother 祖先 ancestor 子孫 descentdant 二叉樹 binary tree平衡二叉樹 banlanced binary tree 滿二叉樹 full binary tree完全二叉樹 complete binary tree

遍歷二叉樹 traversing binary tree二叉排序樹 binary sort tree

二叉查找樹 binary search tree線索二叉樹 threaded binary tree

哈夫曼樹 Huffman tree有序數(shù) ordered tree

無序數(shù) unordered tree判定樹 decision tree雙鏈樹 doubly linked tree

數(shù)字查找樹 digital search tree樹的遍歷 traversal of tree先序遍歷 preorder traversal中序遍歷 inorder traversal后序遍歷 postorder traversal圖 graph

子圖 subgraph有向圖 digraph(directed graph)無向圖 undigraph(undirected graph)完全圖 complete graph連通圖 connected graph非連通圖 unconnected graph

強(qiáng)連通圖 strongly connected graph 弱連通圖 weakly connected graph加權(quán)圖 weighted graph 有向無環(huán)圖 directed acyclic graph 稀疏圖 spares graph稠密圖 dense graph

重連通圖 biconnected graph二部圖 bipartite graph邊 edge頂點(diǎn) vertex

弧 arc路徑 path回路（環(huán)）cycle弧頭head弧尾 tail源點(diǎn) source 終點(diǎn) destination匯點(diǎn) sink權(quán) weight連接點(diǎn) articulation point

初始結(jié)點(diǎn) initial node終端結(jié)點(diǎn) terminal node相鄰邊 adjacent edge

相鄰頂點(diǎn) adjacent vertex關(guān)聯(lián)邊 incident edge入度 indegree

出度 outdegree最短路徑 shortest path有序?qū)?ordered pair

無序?qū)?unordered pair簡(jiǎn)單路徑 simple path簡(jiǎn)單回路 simple cycle

連通分量 connected component鄰接矩陣 adjacency matrix鄰接表 adjacency list

鄰接多重表 adjacency multilist遍歷圖 traversing graph生成樹 spanning tree 最?。ù鷥r(jià)）生成樹 minimum(cost)spanning tree生成森林 spanning forest 拓?fù)渑判?topological sort偏序 partical order拓?fù)溆行?topological order

AOV網(wǎng) activity on vertex networkAOE網(wǎng) activity on edge network

關(guān)鍵路徑 critical path匹配 matching最大匹配 maximum matching

增廣路徑 augmenting path增廣路徑圖 augmenting path graph查找 searching 線性查找（順序查找）linear search(sequential search)二分查找 binary search

分塊查找 block search散列查找 hash search平均查找長(zhǎng)度 average search length 散列表 hash table散列函數(shù) hash funticion直接定址法 immediately allocating method 數(shù)字分析法 digital analysis method平方取中法 mid-square method 折疊法 folding method 除法 division method隨機(jī)數(shù)法 random number method排序 sort

內(nèi)部排序 internal sort外部排序 external sort插入排序 insertion sort

隨小增量排序 diminishing increment sort選擇排序 selection sort堆排序 heap sort 快速排序 quick sort歸并排序 merge sort 基數(shù)排序 radix sort外部排序 external sort平衡歸并排序 balance merging sort二路平衡歸并排序 balance two-way merging sort 多步歸并排序 ployphase merging sort置換選擇排序 replacement selection sort

文件 file主文件 master file順序文件 sequential file索引文件 indexed file 索引順序文件 indexed sequential file索引非順序文件 indexed non-sequential file 直接存取文件 direct access file多重鏈表文件 multilist file倒排文件 inverted file 目錄結(jié)構(gòu) directory structure樹型索引 tree index

第五篇：算法總結(jié)

算法分析與設(shè)計(jì)總結(jié)報(bào)告

71110415 錢玉明

在計(jì)算機(jī)軟件專業(yè)中，算法分析與設(shè)計(jì)是一門非常重要的課程，很多人為它如癡如醉。很多問題的解決，程序的編寫都要依賴它，在軟件還是面向過程的階段，就有程序=算法+數(shù)據(jù)結(jié)構(gòu)這個(gè)公式。算法的學(xué)習(xí)對(duì)于培養(yǎng)一個(gè)人的邏輯思維能力是有極大幫助的，它可以培養(yǎng)我們養(yǎng)成思考分析問題，解決問題的能力。作為IT行業(yè)學(xué)生，學(xué)習(xí)算法無疑會(huì)增強(qiáng)自己的競(jìng)爭(zhēng)力，修煉自己的“內(nèi)功”。

下面我將談?wù)勎覍?duì)這門課程的心得與體會(huì)。

一、數(shù)學(xué)是算法的基礎(chǔ)

經(jīng)過這門課的學(xué)習(xí)，我深刻的領(lǐng)悟到數(shù)學(xué)是一切算法分析與設(shè)計(jì)的基礎(chǔ)。這門課的很多時(shí)間多花在了數(shù)學(xué)公式定理的引入和證明上。雖然很枯燥，但是有必不可少。我們可以清晰的看到好多算法思路是從這些公式定理中得出來的，尤其是算法性能的分析更是與數(shù)學(xué)息息相關(guān)。其中有幾個(gè)定理令我印象深刻。

①主定理

本門課中它主要應(yīng)用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一個(gè)大問題分解為a個(gè)子問題，其中子問題的規(guī)模為b。而f(n)可看作這些子問題的組合時(shí)的消耗。這些可以利用主定理的相關(guān)結(jié)論進(jìn)行分析處理。當(dāng)f(n)量級(jí)高于nlogba時(shí)，我們可以設(shè)法降低子問題組合時(shí)的消耗來提高性能。反之我們可以降低nlogba的消耗，即可以擴(kuò)大問題的規(guī)?；蛘邷p小子問題的個(gè)數(shù)。因此主定理可以幫助我們清晰的分析出算法的性能以及如何進(jìn)行有效的改進(jìn)。

②隨機(jī)算法中的許多定理的運(yùn)用

在這門課中，我學(xué)到了以前從未遇見過的隨機(jī)算法，它給予我很大的啟示。隨機(jī)算法不隨機(jī)，它可通過多次的嘗試來降低它的錯(cuò)誤率以至于可以忽略不計(jì)。這些都不是空穴來風(fēng)，它是建立在嚴(yán)格的定理的證明上。如素?cái)?shù)判定定理是個(gè)很明顯的例子。它運(yùn)用了包括費(fèi)馬小定理在內(nèi)的各種定理。將這些定理進(jìn)行有效的組合利用，才得出行之有效的素?cái)?shù)判定的定理。尤其是對(duì)尋找證據(jù)數(shù)算法的改進(jìn)的依據(jù)，也是建立在3個(gè)定理上。還有檢查字符串是否匹配也是運(yùn)用了許多定理：指紋的運(yùn)用，理論出錯(cuò)率的計(jì)算，算法性能的評(píng)價(jià)也都是建立在數(shù)學(xué)定理的運(yùn)用上。

這些算法都給予了我很大啟發(fā)，要想學(xué)好算法，學(xué)好數(shù)學(xué)是必不可少的。沒有深厚的數(shù)學(xué)功力作為地基，即使再漂亮的算法框架，代碼實(shí)現(xiàn)也只能是根底淺的墻上蘆葦。

二、算法的核心是思想

我們學(xué)習(xí)這門課不是僅僅掌握那幾個(gè)經(jīng)典算法例子，更重要的是為了學(xué)習(xí)蘊(yùn)含在其中的思想方法。為什么呢？舉個(gè)例子。有同學(xué)曾問我這樣一個(gè)問題：1000只瓶子裝滿水，但有一瓶有毒，且毒發(fā)期為1個(gè)星期?，F(xiàn)在用10只老鼠在一個(gè)星期內(nèi)判斷那只瓶子有毒，每只老鼠可以喝多個(gè)瓶子的水，每個(gè)瓶子可以只喝一點(diǎn)。問如何解決？其實(shí)一開始我也一頭霧水，但是他提醒我跟計(jì)算機(jī)領(lǐng)域相關(guān)，我就立馬有了思路，運(yùn)用二進(jìn)制。因?yàn)橛?jì)算機(jī)的最基本思想就是二進(jìn)制。所以說，我們不僅要學(xué)習(xí)算法，更得學(xué)習(xí)思想方法。

①算法最基本的設(shè)計(jì)方法包括分治法，動(dòng)態(tài)規(guī)劃法，貪心法，周游法，回溯法，分支定界法。我們可利用分治法做快速排序，降低找n個(gè)元素中最大元和最小元的量級(jí)，降低n位二進(jìn)制x和y相乘的量級(jí)，做Strassen矩陣乘法等等。它的思想就是規(guī)模很大的問題分解為規(guī)模較小的獨(dú)立的子問題，關(guān)鍵是子問題要與原問題同類，可以采取平衡法來提高性能。

動(dòng)態(tài)規(guī)劃法是把大問題分解為子問題，但是子問題是重復(fù)的，后面的問題可以利用前面解決過的問題的結(jié)果。如構(gòu)造最優(yōu)二叉查找樹，解決矩陣連乘時(shí)最小計(jì)算次數(shù)問題，尋找最長(zhǎng)公共子序列等等。

貪心法就是局部最優(yōu)法，先使局部最優(yōu)，再依次構(gòu)造出更大的局部直至整體。如Kruscal最小生成樹算法，求哈夫曼編碼問題。

周游法就是簡(jiǎn)單理解就是采取一定的策略遍歷圖中所有的點(diǎn)，典型的應(yīng)用就是圖中的深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)。

回溯法就是就是在滿足一定的條件后就往前走，當(dāng)走到某步時(shí)，發(fā)現(xiàn)不滿足條件就退回一步重新選擇新的路線。典型的應(yīng)用就是8皇后問題，平面點(diǎn)集的凸包問題和0-1背包問題。

分支定界法：它是解決整數(shù)規(guī)劃問題一種最常用的方法。典型應(yīng)用就是解決整數(shù)規(guī)劃問題。

②評(píng)價(jià)算法性能的方法如平攤分析中的聚集法，會(huì)計(jì)法和勢(shì)能法。聚集法就是把指令分為幾類，計(jì)算每一類的消耗，再全部疊加起來。會(huì)計(jì)法就是計(jì)算某個(gè)指令時(shí)提前將另一個(gè)指令的消耗也算進(jìn)去，以后計(jì)算另一個(gè)指令時(shí)就不必再算了。勢(shì)能法計(jì)算每一步的勢(shì)的變化以及執(zhí)行這步指令的消耗，再將每一步消耗全部累計(jì)。

這幾種方法都是平攤分析法，平攤分析的實(shí)質(zhì)就是總體考慮指令的消耗時(shí)間，盡管某些指令的消耗時(shí)間很大也可以忽略不計(jì)。上述三種方法難易程度差不多，每種方法都有屬于它的難點(diǎn)。如聚集法中如何將指令有效分類，會(huì)計(jì)法中用什么指令提前計(jì)算什么指令的消耗，勢(shì)能法中如何選取勢(shì)能。因此掌握這些方法原理還不夠，還要學(xué)會(huì)去應(yīng)用，在具體的問題中去判斷分析。

三、算法與應(yīng)用緊密相關(guān)

我認(rèn)為學(xué)習(xí)算法不能局限于書本上的理論運(yùn)算，局限于如何提高性能以降低復(fù)雜度，我們要將它與實(shí)際生活聯(lián)系起來。其實(shí)算法問題的產(chǎn)生就來自于生活，設(shè)計(jì)出高效的算法就是為了更好的應(yīng)用。如尋找最長(zhǎng)公共子序列算法可以應(yīng)用在生物信息學(xué)中通過檢測(cè)相似DNA片段的相似成分來檢測(cè)生物特性的相似性，也可以用來判斷兩個(gè)字符串的相近性，這可應(yīng)用在數(shù)據(jù)挖掘中。快速傅立葉變換（FFT）可應(yīng)用在計(jì)算多項(xiàng)式相乘上來降低復(fù)雜度，脫線min算法就是利用了Union-Find這種結(jié)構(gòu)。還有圖中相關(guān)算法，它對(duì)于解決網(wǎng)絡(luò)流量分配問題起了很大的幫助，等等。

這些應(yīng)用給了我很大的啟發(fā)：因?yàn)閱渭冎v一個(gè)Union-Find算法，即使了解了它的實(shí)現(xiàn)原理，遇到具體的實(shí)際問題也不知去如何應(yīng)用。這就要求我們要將自己學(xué)到的算法要和實(shí)際問題結(jié)合起來，不能停留在思想方法階段，要學(xué)以致用，做到具體問題具體分析。

四、對(duì)計(jì)算模型和NP問題的理解

由于對(duì)這部分內(nèi)容不是很理解，所以就粗淺的談一下我的看法。

首先談到計(jì)算模型，就不得不提到圖靈計(jì)算，他將基本的計(jì)算抽象化，造出一個(gè)圖靈機(jī)，得出了計(jì)算的本質(zhì)。并提出圖靈機(jī)可以計(jì)算的問題都是可以計(jì)算的，否則就是不可計(jì)算的。由此引申出一個(gè)著名論題：任何合理的計(jì)算模型都是相互等價(jià)的。它說明了可計(jì)算性本身不依賴于任何具體的模型而客觀存在。

NP問題比較復(fù)雜，我認(rèn)為它是制約算法發(fā)展的瓶頸，但這也是算法分析的魅力所在。NP問題一般可分為3類，NP-C問題，NP-hard問題以及頑型問題。NP-C它有個(gè)特殊的性質(zhì)，如果存在一個(gè)NP-C問題找到一個(gè)多項(xiàng)式時(shí)間的解法，則所有的NP-C問題都能找到多項(xiàng)式時(shí)間解法。如哈密頓回路問題。NP-hard主要是解決最優(yōu)化問題。它不一定是NP問題。這些問題在規(guī)模較小時(shí)可以找出精確解，但是規(guī)模大時(shí)，就因時(shí)間太復(fù)雜而找不到最優(yōu)解。此時(shí)一般會(huì)采用近似算法的解法。頑型問題就是已經(jīng)證明不可能有多項(xiàng)式時(shí)間的算法，如漢諾塔問題。

最后談?wù)剬?duì)這門課程的建議

①對(duì)于這門算法課，我認(rèn)為應(yīng)該加強(qiáng)對(duì)算法思想方法的學(xué)習(xí)。所以我建議老師可不可以先拋出問題而不給出答案，講完一章，再發(fā)課件。讓我們先思考一會(huì)兒，或者給出個(gè)獎(jiǎng)勵(lì)機(jī)制，誰能解決這個(gè)問題，平時(shí)成績(jī)加分。這在一定程度上會(huì)將強(qiáng)我們思考分析問題的能力。因?yàn)槲腋杏X到，一個(gè)問題出來，未經(jīng)過思考就已經(jīng)知曉它的答案，就沒什么意思，得不到提高，而且也不能加深對(duì)問題的思考和理解。下次遇到類似的問題也就沒有什么印象。而且上課讓我們思考，點(diǎn)名回答問題可以一定程度上有效的防止不認(rèn)真聽課的現(xiàn)象。

②作業(yè)安排的不是很恰當(dāng)。本門課主要安排了三次作業(yè)，個(gè)人感覺只有第一次作業(yè)比較有意思。后面兩次作業(yè)只是實(shí)現(xiàn)一下偽代碼，沒有太多的技術(shù)含量。而且對(duì)于培養(yǎng)我們的解決問題的能力也沒有太多的幫助，因?yàn)檫@間接成為了程序設(shè)計(jì)題，不是算法設(shè)計(jì)題。

③本門課的時(shí)間安排的不太恰當(dāng)，因?yàn)楸緦W(xué)期的課程太多，壓力太大。沒有太多的時(shí)間去學(xué)習(xí)這門課程。因?yàn)槲蚁嘈糯蠹叶紝?duì)它感興趣，比較重視，想花功夫，但苦于沒時(shí)間。所以可不可以將課程提前一個(gè)學(xué)期，那時(shí)候離散數(shù)學(xué)也已經(jīng)學(xué)過，且課程的壓力也不是很大。錯(cuò)開時(shí)間的話，我覺得應(yīng)該能夠更好提高大家算法分析設(shè)計(jì)的能力。