第一篇：计算机算法总结
算法总结
1.穷举法
穷举法，又称暴力算法，即列举问题解空间所有可能情况，并逐个测试，从而找出符合问题条件的解。这份通常是一种费时算法，人工手动求解困难，但计算机的出现使得穷举法有了用武之地。例如:密码破译通常用的是穷举法，即将密码进行逐个推算直到找到真正的密码为止。理论上讲，穷举法可以破解任何一种密码，但对于一个长度为n位的密码，其可能的密码有2^n种。可见，当n较大时穷举法将成为一个NP难度问题。典型例题
【百钱买百鸡问题】公元5世纪末，中国古代数学家张丘建在他的《算经》中提到了著名的―百钱买百鸡‖问题:鸡翁一，值钱五，鸡母一，值钱三，鸡雏三，值钱一，百钱买百鸡，问翁、母、雏各几何？
分析:设鸡翁、鸡母、鸡雏的个数各为x、y、z,百钱买百鸡问题可以用如下方程式表示: 5x+3y+z/3=100 x+y+z=100
1<=x<20,1<=y<33,3<=z<100,z mod3=0
对于百钱买白鸡问题，很容易用穷举法对x、y、z的取值，判断方程（1）、（2）及z mod3=0是否成立，若成立，则是问题的一个解。
百钱买白鸡问题求解算法: //百钱买白鸡问题穷举算法
//设鸡翁、鸡母、鸡雏的个数分别为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）
上述算法是一个三重循环，最内层的条件判断需要执行19*32*97次，即58976。在条件判断中，利用了整数的求模运算，如果将鸡雏的个数设为3z，可以避免该项判断，且可减少内重循环次数。即: for（z=1;z<34;z++）
if（x+y+3z==100）and（5x+3y+z==100）
writeln（x,y,3z）
【 0-1背包问题1】给定n种物品和一个背包，物品i的重量是Wi，其价值为Vi，背包的容量为Wm。应如何选择装入背包的物品，使得装入背包的物品总价值最大？
分析:所谓0-1背包问题，是指在选择装入背包的物品时，对每种物品i只有两种选择，即装入背包或不装入背包。另外，不能将物品i装入背包多次，也不能只装入部分的物品i。0-1背包问题是一种组合优化的NP完全问题，最容易想到方法的就是穷举法。
0-1背包问题求解的穷举算法。
//设数组w[0…n–1]存储n件物品的重量，数组c[0…n-1]存储 //n件物品的价值，数组b[0…n-1]为标识数组，若物品i未选 //择，则b[i-1]=0，否则b[i-1]=1 cmax=0
for（i=1;i<=2^n-1;i++）{
b[0..n-1]=将i转化为n位的二进制字符串 tempw=求和b[j]*w[j] tempc=求和b[j]*c[j]
If（tempw
tempb=b[0..n-1];cmax=tempc;} }
输出最佳方案tempb[0..n-1],cmax 结束
2.递推法
递推算法是一种根据递推关系进行问题求解的方法。递推关系可以抽象为一个简单的数学模型，即给定一个数的序列a0,a1,…,an若存在整数n0，使当n>n0时，可以用等号（或大于号，小于号）将an与其前面的某些项ai(0 递推算法是一种简单的算法，通过已知条件利用特定的递推关系可以得到中间推论，直至得到问题的最终结果。递推算法分为顺推法和逆推法两种。 【斐波那契数列算法1】斐波那契数列，又称为黄金分割数列。在数学上，斐波那契数列可以用递推方法定义，其递推公式为F1=0,F2=1,Fn=F(n-1)+F(n-2)(n>=3,n∈N*)。写一算法求斐波那契数列第10项的值。 分析:从斐波那契数列的定义可知，数列的第一项为一，第二项也为一，递推关系是当前项等于前二项之和。因此，通过顺推可以得到f(3)=f(1)+f(2)=2,f(4)=f(2)+f(3)=3,f(5)=f(3)+f(4)=5，以此类推，可以得到f(10)的值。求斐波那契数列的顺推算法: //求斐波那契数列第十项的值并输出 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.递归法 在问题求解思想上，递推是从已知条件出发，一步步递推出未知项，直到问题的解。递归也是递推的一种，只不过它是对待解问题的递推，直到把一个复杂的问题递推为简单的易解问题，然后再一步步返回，从而得到原问题的解。【斐波那契数列算法2】利用递归思想写出求斐波那契数列的递归算法。分析：在问题求解中，求解同一个问题的方法通常不止一个。根据递归法的思想，由斐波那契数列递推公式可以很容易地写出递归算法，伪代码描述如下。 求斐波那契数列递归算法: //函数fib返回第n(n>=1)个斐波那契数列的值 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）递归算法。 分析：可以把问题用初始状态和目标状态来表达，问题求解就是要找出搬移的次序和所有的中间状态。 Hanoi塔问题递归算法: //n为盘子数目 //三根柱子from、to和temp分别表示起始柱子、目标柱子和临时柱子 void hanoitower(n,from,to,temp){ if(n>0){ //把from柱子上的n-1个盘子搬移到temp柱子上，用to柱做临时柱子 hanoitower(n-1,from,temp,to);movedisk(from,to); //把temp柱子上的n-1个盘子搬移到to柱子上，用from柱做临时柱子 hanoitower(n-1,temp,to,from);} } 4.回溯法 试探-失败返回-再试探的问题求解方法称为回溯法，回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。对于用回溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得出结果。但是，回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解（并不一定是完整的，事实上这也就是构造约束函数的意义所在）与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。 【八皇后问题】八皇后问题是十九世纪著名数学家高斯于1850年提出的。问题是：在8*8的棋盘上摆放8个皇后，使其不能互相攻击，即任意的两个皇后不能处在同意行，同一列，或同意斜线上。可以把八皇后问题拓展为n皇后问题，即在n*n的棋盘上摆放n个皇后，使其任意两个皇后都不能处于同一行、同一列或同一斜线上。分析：显然，每一行可以而且必须放一个皇后，所以n皇后问题的解可以用一个n元向量X=（x1,x2,.....xn）表示，其中，1<= i<= n且1<= xi<= n，即第n个皇后放在第i行第xi列上。 由于两个皇后不能放在同一列上，所以，解向量X必须满足的约束条件为:xi≠ xj;若两个皇后的摆放位置分别是（i,xi）和（j,xj），在棋盘上斜率为-1的斜线上，满足条件i-j=xi-xj;在棋盘上斜率为1的斜线上，满足条件i+j=xi+xj;综合两种情况，由于两个皇后不能位于同一斜线上，所以，解向量X必须满足的约束条件为: |i-xi|≠ |j-xj| 八皇后问题求解的回溯算法: //试探第i个皇后，即第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列标记 b[i-j+7]=1; //(i,j)所在的主对角线做标记 c[i+j]=1; //(i,j)所在的从对角线做标记 if(i<7)queen(i+1);//如果行还没有遍历完，进入下一行 else输出当前的摆放方案,即q数组;//当前列摆放了皇后，要继续试探当前行下一个可能的位置，此时需要 //将当前列恢复为没有摆皇后的状态，尝试下一个可能的摆放方案 q[i,j]=’*’;a[j]=0;b[i-j+7]=0;c[i+j]=0;}//end if }//end for } 5.迭代法 迭代法又称辗转法，是一种不断用变量的旧值递推新值的过程，是用计算机解决问题的一种基本方法。迭代法也是一种编程技术方法，它运用了递推的思想方法，利用计算机运算速度快、适合做重复性操作的特点，重复执行一组指令，不断从变量的一个值推出它的下一个值。 【辗转相除法】使用辗转相除法求两数的最大公约数。 分析：辗转相除法, 又称欧几里德算法，是求两个正整数之最大公因子的算法。它是已知最古老的算法之一, 最早可追溯至公元前300年。它首次出现于欧几里德的《几何原本》中，而在中国则可以追溯至东汉出现的《九章算术》。 设两数为a、b(a>b），求a和b最大公约数(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，则继续用r2除r1，……如此下去，直到能整除为止。其最后一个非零除数即为（a，b）。 法1：求两数的最大公约数的辗转相除法减法实现: //辗转相除法求两数a和b的最大公约数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：求两数的最大公约数的辗转相除法模拟实现: //辗转相除法求两数a和b的最大公约数g int gcd(a,b){ t=a%b;while(t!=0){ a=b; /*迭代*/ b=t; /*迭代*/ t=a%b;} return b } 【解一元非线性方程】用迭代法求一元非线性方程f(x)=0的解 分析：当f(x)是超越函数或高次多项式时，f(x)=0称为非线性方程，此类方程除少数情形外，只能求近似解。求解非线性方程的最简单的方法是二分法（Bisection method），又称二分区间法。其基本思想是设f(x)在区间[a,b]上为连续函数，如果f(a)•f(b)<0，则f(x)在区间[a,b]上至少有一个根。如果f(x)在区间[a,b]上是单调的，则f(x)在区间[a,b]上只存在一个实根，如右图所示。求方程f(x)=0在区间[a,b]内的根的迭代算法: Step1:求a,b的中点坐标x=a+b/2。Step2:计算f(x)。 Step3:若|f(x)|<ε(ε为一个指定的极小值，用来控制求解精度，例如10^-4)，则转Step6,否则继续下面的迭代运算。Step4:修改有根区间 4.1若f(x)与f(a)同号，说明x更接近方程的根，此时a←x,b不变； 4.2若f(x)与f(b)异号,此时a不变，b←x； Step5:转Step1 Step6:输出x，即方程的近似解。Step7:结束。 6.分治法 在求解复杂问题时，分治法的基本思想是把一个复杂的问题分成若干相对独立而规模较小的子问题，如果某个子问题还比较复杂，再把子问题分成更小的子问题，直到分解后的每个子问题都可以简单的直接求为止，然后通过逐个解决这些较小的子问题而得到原问题的解，即各个击破，分而治之。许多问题可以通过分治法求解，典型的有归并排序算法，折半查找等。 分治法所能解决的问题一般具有以下几个特征： 1)该问题的规模缩小到一定的程度就可以容易地解决 2)该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。3)利用该问题分解出的子问题的解可以合并为该问题的解； 4)该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。【例题】给定一个长度为n的整数数组，编写一个求出其最大值和最小值的分治算法。分析：当数组中只有1个数时，可以直接给出结果；如果有两个数，则一次比较即可得出结果。当n>2时，可以将数组分成两个元素个数较小的数组，分别求解它们的最大值和最小值，最后比较两个数组的解来得到原问题的解，这样就分而治之了。 求数组中最大值和最小值的分治算法: #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.贪心法 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。基本思路： 1.建立数学模型来描述问题 ⒉把求解的问题分成若干个子问题。⒊对每一子问题求解，得到子问题的局部最优解。⒋把子问题的解局部最优解合成原来解问题的一个解。实现该算法的过程： 从问题的某一初始解出发； while 能朝给定总目标前进一步 do 求出可行解的一个解元素； 由所有解元素组合成问题的一个可行解。 【0-1背包问题2】有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品 A B C D E F G 重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg 价值 10$ 40$ 30$ 50$ 35$ 分析：用贪心算法解背包问题的基本步骤是，首先计算每种物品单位重量的价值Vi/Wi，然后依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超出C，则选择单位重量价值次高的物品，并尽可能多的装入背包。依此策略一直进行下去，直到背包装满为止。0-1背包问题的贪心算法: #include //x[]取值为0或1，x[i]=1当且仅当背包i背装载； //p[]是物品价值； //w[]是物品重量； //c表示背包的容量； //n表示物品的件数； 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<<“请输入物品的件数：”;cin>>n;cout<<“请输入背包的最大容量：”;cin>>c;cout<<“请依次输入各物品的价值与重量 n每个物品的价值与重量之间用空格隔开，回车后输入另一个物品：”< for(i=0;i cin>>p[i]>>w[i];} //调用函数 bagloading(x,p,w,c,n);//统计物品的总价值、总重量以及件数并输出 //统计装入物品的价值及重量并输出 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<<“所装物品总的价值为：”< cout<<“所装物品总的重量为：”< if(all>0) { cout<<“该背包共装入的这”< for(i=0;i if(x[i]==1) cout< } system(“pause”);return 0;} 8.动态规划法 在现实生活中，有一类活动可将其过程分为若干个互相联系的阶段，在它的每个阶段都要做出决策，从而使整个过程达到最好的活动效果。动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。 动态规划一般可分为线性动规，区域动规，树形动规，背包动规四类。 【0-1背包问题3】 分析：令V(i,j)表示在前i(1<=i<=n)个物品中能够装入容量为就j(1<=j<=C)的背包中的物品的最大价值，则可以得到如下的动态规划函数:(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个物品的重量大于背包的容量，则装人前i个物品得到的最大价值和装入前i-1个物品得到的最大价是相同的，即物品i不能装入背包；第(2)个式子表明:如果第i个物品的重量小于背包的容量，则会有一下两种情况：(a)如果把第i个物品装入背包，则背包物品的价值等于第i-1个物品装入容量位j-wi 的背包中的价值加上第i个物品的价值vi;(b)如果第i个物品没有装入背包，则背包中物品价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值最大的作为把前i个物品装入容量为j的背包中的最优解。 0-1背包问题的动态规划法: //计算 for(i=1;i 1.实验名称 本次实验的名称。 2.问题描述 对本次实验要解决的问题的描述。 例子：处理汉诺塔问题时，描述什么是汉诺塔问题。 3.解决思路 采用什么方法；为什么可以采用这个方法； 例子：处理棋盘覆盖问题时，采用什么方法：采用递归分治的方法处理； 为什么可以采用递归分治方法的原因（P21页图2-6下面一段，理解之后用自己的话表述）：由于将棋盘横、纵各一分为二之后，特殊方格必然位于四个小的棋盘之一，那么剩余的其余三个小棋盘是没有方格的，如果采用某种L型骨牌覆盖没有特殊方格的三个小棋盘的中心相连部分（参见图2-6的b），则三个小棋盘都各有1个特殊方格所覆盖。因此，这样处理之后，原来大棋盘覆盖的问题，就转化为四个小棋盘覆盖的问题，因此可以采用分治策略进行递归处理。 4.算法设计与分析 给出算法设计的基本思想，如：伪算法描述，递归方程等。并分析算法的时间复杂度（空间复杂度）。注意，一定要有文字说明。例子：快速排序 伪算法描述 QuickSort(int a[], int p, int r){ 如果待排序数组a[]中只有一个元素则直接返回； 如果待排序数组a[]中不止一个元素，则进行如下处理 { 对数组a[p:r]进行Partition划分，使得a[p:r]以a[p]为标准，划分为三个部分，即： 左半部分a[p:q-1]；划分基准a[q]=a[p]；右半部分a[q+1:r]； 对左半部分快速排序QuickSort(a, p, q-1); 对右半部分快速排序QuickSort(a, q+1, r)； } } 例子：0-1背包问题 递归关系或者递归方程。 给出P72页“2.递归关系”中的递归表达式，并给出文字说明。注意：伪算法描述，或者递归方程不一定全部需要。根据问题的不同，只给出伪算法，或者只给出递归方程都可以。两者同时给出也是可以的。 5.程序实现 依据第4部分，给出C语言（其他语言亦可）的程序实现，并进行算法时间（空间）复杂度分析。 程序实现部分要包括：程序代码、程序注释、程序运行结果（或者截图）。 例子：快速排序的partition函数 int Partition(Type a[], int p, int r){ int i=p, j= r+1; int x = a[p];//x=a[p]是对数组a进行划分的标准； /* 以下循环将数组a[p:r]以a[p]为标准进行划分，在划分完毕之后，* a[p]调整到数组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用来从数组a[p:r]的左边向右边扫描，如果a[++i]中的元素总是 * 小于基准元素的，则是符合划分标准的，因此，不用额外处理，* 循环一直继续,直到第一个不满足划分标准的a[++i]（即a[++i]>=i）* 出现，或者整个数组a[p:r]扫描完毕（即i while(a[++i] „„ 6.总结 不用每个实验写一个总结，可以在一次课作业的最后写一个总结。当然，如果需要，在每一个实验结尾都写一个总结也是可以的。总结的目的是自己知识学习的总结、解决问题的总结、编程的总结等等。 1.实验名称 本次实验的名称。 2.问题描述 对本次实验要解决的问题的描述。 例子：处理汉诺塔问题时，描述什么是汉诺塔问题。 3.解决思路 采用什么方法；为什么可以采用这个方法； 例子：处理棋盘覆盖问题时，采用什么方法：采用递归分治的方法处理； 为什么可以采用递归分治方法的原因（P21 页图 2-6 下面一段，理解之后用自己的话表述）：由于将棋盘横、纵各一分为二之后，特殊方格必然位于四个小的棋盘之一，那么剩余的其余三个小棋盘是没有方格的，如果采用某种 L 型骨牌覆盖没有特殊方格的三个小棋盘的中心相连部分（参见图 2-6 的 b），则三个小棋盘都各有 1 个特殊方格所覆盖。因此，这样处理之后，原来大棋盘覆盖的问题，就转化为四个小棋盘覆盖的问题，因此可以采用分治策略进行递归处理。 4.算法设计与分析 给出算法设计的基本思想，如：伪算法描述，递归方程等。并分析算法的时间复杂度（空间复杂度）。注意，一定要有文字说明。 例子：快速排序 伪算法描述 QuickSort(int a[], int p, int r){ 如果待排序数组 a[]中只有一个元素则直接返回； 如果待排序数组 a[]中不止一个元素，则进行如下处理 { 对数组 a[p:r]进行 Partition 划分，使得 a[p:r]以 a[p]为标准，划分为三个部分，即： 左半部分 a[p:q-1]；划分基准 a[q]=a[p]；右半部分 a[q+1:r]； 对左半部分快速排序 QuickSort(a, p, q-1); 对右半部分快速排序 QuickSort(a, q+1, r)； } } 例子：0-1 背包问题 递归关系或者递归方程。 给出 P72 页“2.递归关系”中的递归表达式，并给出文字说明。 注意：伪算法描述，或者递归方程不一定全部需要。根据问题的不同，只给出伪算法，或者只给出递归方程都可以。两者同时给出也是可以的。 5.程序实现 依据第 4 部分，给出 C 语言（其他语言亦可）的程序实现，并进行算法时间（空间）复杂度分析。 程序实现部分要包括：程序代码、程序注释、程序运行结果（或者截图）。 例子：快速排序的 partition 函数 int Partition(Type a[], int p, int r){ int i=p, j= r+1; int x = a[p]; //x=a[p]是对数组 a 进行划分的标准； /* 以下循环将数组 a[p:r]以 a[p]为标准进行划分，在划分完毕之后，* a[p]调整到数组 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 用来从数组 a[p:r]的左边向右边扫描，如果 a[++i]中的元素总是 * 小于基准元素的，则是符合划分标准的，因此，不用额外处理，* 循环一直继续,直到第一个不满足划分标准的 a[++i]（即 a[++i]>=i） * 出现，或者整个数组 a[p:r]扫描完毕（即 i */ while(a[++i] …… 6.总结 不用每个实验写一个总结，可以在一次课作业的最后写一个总结。当然，如果需要，在每一个实验结尾都写一个总结也是可以的。总结的目的是自己知识学习的总结、解决问题的总结、编程的总结等等。 第一部分 计算机算法常用术语中英对照 Data Structures 基本数据结构Dictionaries 字典Priority Queues 堆Graph Data Structures 图Set Data Structures 集合Kd-Trees 线段树 Numerical Problems 数值问题Solving Linear Equations 线性方程组 Fourier变换 Bandwidth Reduction 带宽压缩Matrix Multiplication 矩阵乘法Satisfiability 可满足性 Determinants and Permanents 行列式Linear Programming 线性规划Matching 匹配 Constrained and Unconstrained Optimization 最值问题Clique 最大团Cryptography 密码 Random Number Generation 随机数生成Shortest Path 最短路径recursion递归 Factoring and Primality Testing 因子分解/质数判定 Searching 查找Sorting 排序 Arbitrary Precision Arithmetic 高精度计算Calendrical Calculations 日期 Discrete Fourier Transform 离散Combinatorial Problems 组合问题 Median and Selection 中位数Generating Permutations 排列生成Generating Subsets 子集生成Generating Partitions 划分生成Generating Graphs 图的生成Job Scheduling 工程安排 Graph Problems--polynomial 图论-多项式算法Connected Components 连通分支Topological Sorting 拓扑排序Minimum Spanning Tree 最小生成树 Transitive Closure and Reduction 传递闭包Network Flow 网络流 Eulerian Cycle / Chinese Postman Euler回路/中国邮路 Edge and Vertex Connectivity 割边/割点Independent Set 独立集 Drawing Graphs Nicely 图的描绘Drawing Trees 树的描绘 Planarity Detection and Embedding平面性检测和嵌入Vertex Cover 点覆盖 Graph Problems--hard 图论-NP问题Traveling Salesman Problem 旅行商问题Hamiltonian Cycle Hamilton回路Graph Partition 图的划分 Vertex Coloring 点染色Edge Coloring 边染色 Graph Isomorphism 同构Steiner Tree Steiner树 Feedback Edge/Vertex Set 最大无环子图Computational Geometry 计算几何 Convex Hull 凸包Triangulation 三角剖分 Voronoi Diagrams Voronoi图Nearest Neighbor Search 最近点对查询Range Search 范围查询Point Location 位置查询 Intersection Detection 碰撞测试Bin Packing 装箱问题 Medial-Axis Transformation 中轴变换Polygon Partitioning 多边形分割 Simplifying Polygons 多边形化简Shape Similarity 相似多边形 Motion Planning 运动规划Maintaining Line Arrangements平面分割Minkowski Sum Minkowski和Set and String Problems 集合与串的问题Set Cover 集合覆盖Set Packing 集合配置 Approximate String Matching 模糊匹配Text Compression 压缩 DP—Dynamic Programming动态规划Longest Common Substring 最长公共子串Shortest Common Superstring 最短公共父串String Matching 模式匹配 Finite State Machine Minimization 有穷自动机简化 第二部分 数据结构英语词汇 数据抽象 data abstraction数据元素 data element数据对象 data object 数据项 data item数据类型 data type抽象数据类型 abstract data type 逻辑结构 logical structure物理结构 phyical structure线性结构 linear structure 非线性结构 nonlinear structure基本数据类型 atomic data type线性表 linear list 数组 array直接前趋 immediate predecessor队列 queue 串 string固定聚合数据类型 fixed-aggregate data type栈 stack 可变聚合数据类型 variable-aggregate data type树 tree图 grabh 查找，线索 searching更新 updating排序（分类)sorting 插入 insertion删除 deletion前趋 predecessor 后继 successor直接后继 immediate successor双端列表 deque(double-ended queue)循环队列 cirular queue指针 pointer先进先出表（队列）first-in first-out list 后进先出表（队列）last-in first-out list栈底 bottom栈定 top 压入 push弹出 pop队头 front队尾 rear上溢 overflow 下溢 underflow数组 array矩阵 matrix多维数组 multi-dimentional array 以行为主的顺序分配 row major order以列为主的顺序分配 column major order 三角矩阵 truangular matrix对称矩阵 symmetric matrix稀疏矩阵 sparse matrix 转置矩阵 transposed matrix链表 linked list线性链表 linear linked list单链表 single linked list多重链表 multilinked list 循环链表 circular linked list双向链表 doubly linked list十字链表 orthogonal list广义表 generalized list 链 link指针域 pointer field链域 link field头结点 head node头指针 head pointer 尾指针 tail pointer串 string空白（空格）串 blank string空串（零串）null string子串 substring树 tree子树 subtree森林 forest根 root叶子 leaf 结点 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有序数 ordered tree 无序数 unordered tree判定树 decision tree双链树 doubly linked tree 数字查找树 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 强连通图 strongly connected graph 弱连通图 weakly connected graph加权图 weighted graph 有向无环图 directed acyclic graph 稀疏图 spares graph稠密图 dense graph 重连通图 biconnected graph二部图 bipartite graph边 edge顶点 vertex 弧 arc路径 path回路（环）cycle弧头head弧尾 tail源点 source 终点 destination汇点 sink权 weight连接点 articulation point 初始结点 initial node终端结点 terminal node相邻边 adjacent edge 相邻顶点 adjacent vertex关联边 incident edge入度 indegree 出度 outdegree最短路径 shortest path有序对 ordered pair 无序对 unordered pair简单路径 simple path简单回路 simple cycle 连通分量 connected component邻接矩阵 adjacency matrix邻接表 adjacency list 邻接多重表 adjacency multilist遍历图 traversing graph生成树 spanning tree 最小（代价）生成树 minimum(cost)spanning tree生成森林 spanning forest 拓扑排序 topological sort偏序 partical order拓扑有序 topological order AOV网 activity on vertex networkAOE网 activity on edge network 关键路径 critical path匹配 matching最大匹配 maximum matching 增广路径 augmenting path增广路径图 augmenting path graph查找 searching 线性查找（顺序查找）linear search(sequential search)二分查找 binary search 分块查找 block search散列查找 hash search平均查找长度 average search length 散列表 hash table散列函数 hash funticion直接定址法 immediately allocating method 数字分析法 digital analysis method平方取中法 mid-square method 折叠法 folding method 除法 division method随机数法 random number method排序 sort 内部排序 internal sort外部排序 external sort插入排序 insertion sort 随小增量排序 diminishing increment sort选择排序 selection sort堆排序 heap sort 快速排序 quick sort归并排序 merge sort 基数排序 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 目录结构 directory structure树型索引 tree index 算法分析与设计总结报告 71110415 钱玉明 在计算机软件专业中，算法分析与设计是一门非常重要的课程，很多人为它如痴如醉。很多问题的解决，程序的编写都要依赖它，在软件还是面向过程的阶段，就有程序=算法+数据结构这个公式。算法的学习对于培养一个人的逻辑思维能力是有极大帮助的，它可以培养我们养成思考分析问题，解决问题的能力。作为IT行业学生，学习算法无疑会增强自己的竞争力，修炼自己的“内功”。 下面我将谈谈我对这门课程的心得与体会。 一、数学是算法的基础 经过这门课的学习，我深刻的领悟到数学是一切算法分析与设计的基础。这门课的很多时间多花在了数学公式定理的引入和证明上。虽然很枯燥，但是有必不可少。我们可以清晰的看到好多算法思路是从这些公式定理中得出来的，尤其是算法性能的分析更是与数学息息相关。其中有几个定理令我印象深刻。 ①主定理 本门课中它主要应用在分治法性能分析上。例如：T(n)=a*T(n/b)+f(n)，它可以看作一个大问题分解为a个子问题，其中子问题的规模为b。而f(n)可看作这些子问题的组合时的消耗。这些可以利用主定理的相关结论进行分析处理。当f(n)量级高于nlogba时，我们可以设法降低子问题组合时的消耗来提高性能。反之我们可以降低nlogba的消耗，即可以扩大问题的规模或者减小子问题的个数。因此主定理可以帮助我们清晰的分析出算法的性能以及如何进行有效的改进。 ②随机算法中的许多定理的运用 在这门课中，我学到了以前从未遇见过的随机算法，它给予我很大的启示。随机算法不随机，它可通过多次的尝试来降低它的错误率以至于可以忽略不计。这些都不是空穴来风，它是建立在严格的定理的证明上。如素数判定定理是个很明显的例子。它运用了包括费马小定理在内的各种定理。将这些定理进行有效的组合利用，才得出行之有效的素数判定的定理。尤其是对寻找证据数算法的改进的依据，也是建立在3个定理上。还有检查字符串是否匹配也是运用了许多定理：指纹的运用，理论出错率的计算，算法性能的评价也都是建立在数学定理的运用上。 这些算法都给予了我很大启发，要想学好算法，学好数学是必不可少的。没有深厚的数学功力作为地基，即使再漂亮的算法框架，代码实现也只能是根底浅的墙上芦苇。 二、算法的核心是思想 我们学习这门课不是仅仅掌握那几个经典算法例子，更重要的是为了学习蕴含在其中的思想方法。为什么呢？举个例子。有同学曾问我这样一个问题：1000只瓶子装满水，但有一瓶有毒，且毒发期为1个星期。现在用10只老鼠在一个星期内判断那只瓶子有毒，每只老鼠可以喝多个瓶子的水，每个瓶子可以只喝一点。问如何解决？其实一开始我也一头雾水，但是他提醒我跟计算机领域相关，我就立马有了思路，运用二进制。因为计算机的最基本思想就是二进制。所以说，我们不仅要学习算法，更得学习思想方法。 ①算法最基本的设计方法包括分治法，动态规划法，贪心法，周游法，回溯法，分支定界法。我们可利用分治法做快速排序，降低找n个元素中最大元和最小元的量级，降低n位二进制x和y相乘的量级，做Strassen矩阵乘法等等。它的思想就是规模很大的问题分解为规模较小的独立的子问题，关键是子问题要与原问题同类，可以采取平衡法来提高性能。 动态规划法是把大问题分解为子问题，但是子问题是重复的，后面的问题可以利用前面解决过的问题的结果。如构造最优二叉查找树，解决矩阵连乘时最小计算次数问题，寻找最长公共子序列等等。 贪心法就是局部最优法，先使局部最优，再依次构造出更大的局部直至整体。如Kruscal最小生成树算法，求哈夫曼编码问题。 周游法就是简单理解就是采取一定的策略遍历图中所有的点，典型的应用就是图中的深度优先搜索(DFS)和广度优先搜索(BFS)。 回溯法就是就是在满足一定的条件后就往前走，当走到某步时，发现不满足条件就退回一步重新选择新的路线。典型的应用就是8皇后问题，平面点集的凸包问题和0-1背包问题。 分支定界法：它是解决整数规划问题一种最常用的方法。典型应用就是解决整数规划问题。 ②评价算法性能的方法如平摊分析中的聚集法，会计法和势能法。聚集法就是把指令分为几类，计算每一类的消耗，再全部叠加起来。会计法就是计算某个指令时提前将另一个指令的消耗也算进去，以后计算另一个指令时就不必再算了。势能法计算每一步的势的变化以及执行这步指令的消耗，再将每一步消耗全部累计。 这几种方法都是平摊分析法，平摊分析的实质就是总体考虑指令的消耗时间，尽管某些指令的消耗时间很大也可以忽略不计。上述三种方法难易程度差不多，每种方法都有属于它的难点。如聚集法中如何将指令有效分类，会计法中用什么指令提前计算什么指令的消耗，势能法中如何选取势能。因此掌握这些方法原理还不够，还要学会去应用，在具体的问题中去判断分析。 三、算法与应用紧密相关 我认为学习算法不能局限于书本上的理论运算，局限于如何提高性能以降低复杂度，我们要将它与实际生活联系起来。其实算法问题的产生就来自于生活，设计出高效的算法就是为了更好的应用。如寻找最长公共子序列算法可以应用在生物信息学中通过检测相似DNA片段的相似成分来检测生物特性的相似性，也可以用来判断两个字符串的相近性，这可应用在数据挖掘中。快速傅立叶变换（FFT）可应用在计算多项式相乘上来降低复杂度，脱线min算法就是利用了Union-Find这种结构。还有图中相关算法，它对于解决网络流量分配问题起了很大的帮助，等等。 这些应用给了我很大的启发：因为单纯讲一个Union-Find算法，即使了解了它的实现原理，遇到具体的实际问题也不知去如何应用。这就要求我们要将自己学到的算法要和实际问题结合起来，不能停留在思想方法阶段，要学以致用，做到具体问题具体分析。 四、对计算模型和NP问题的理解 由于对这部分内容不是很理解，所以就粗浅的谈一下我的看法。 首先谈到计算模型，就不得不提到图灵计算，他将基本的计算抽象化，造出一个图灵机，得出了计算的本质。并提出图灵机可以计算的问题都是可以计算的，否则就是不可计算的。由此引申出一个著名论题：任何合理的计算模型都是相互等价的。它说明了可计算性本身不依赖于任何具体的模型而客观存在。 NP问题比较复杂，我认为它是制约算法发展的瓶颈，但这也是算法分析的魅力所在。NP问题一般可分为3类，NP-C问题，NP-hard问题以及顽型问题。NP-C它有个特殊的性质，如果存在一个NP-C问题找到一个多项式时间的解法，则所有的NP-C问题都能找到多项式时间解法。如哈密顿回路问题。NP-hard主要是解决最优化问题。它不一定是NP问题。这些问题在规模较小时可以找出精确解，但是规模大时，就因时间太复杂而找不到最优解。此时一般会采用近似算法的解法。顽型问题就是已经证明不可能有多项式时间的算法，如汉诺塔问题。 最后谈谈对这门课程的建议 ①对于这门算法课，我认为应该加强对算法思想方法的学习。所以我建议老师可不可以先抛出问题而不给出答案，讲完一章，再发课件。让我们先思考一会儿，或者给出个奖励机制，谁能解决这个问题，平时成绩加分。这在一定程度上会将强我们思考分析问题的能力。因为我感觉到，一个问题出来，未经过思考就已经知晓它的答案，就没什么意思，得不到提高，而且也不能加深对问题的思考和理解。下次遇到类似的问题也就没有什么印象。而且上课让我们思考，点名回答问题可以一定程度上有效的防止不认真听课的现象。 ②作业安排的不是很恰当。本门课主要安排了三次作业，个人感觉只有第一次作业比较有意思。后面两次作业只是实现一下伪代码，没有太多的技术含量。而且对于培养我们的解决问题的能力也没有太多的帮助，因为这间接成为了程序设计题，不是算法设计题。 ③本门课的时间安排的不太恰当，因为本学期的课程太多，压力太大。没有太多的时间去学习这门课程。因为我相信大家都对它感兴趣，比较重视，想花功夫，但苦于没时间。所以可不可以将课程提前一个学期，那时候离散数学也已经学过，且课程的压力也不是很大。错开时间的话，我觉得应该能够更好提高大家算法分析设计的能力。第二篇：《计算机算法》实验报告
第三篇：《计算机算法》实验报告范文(例文)
第四篇：计算机算法常用术语中英对照
第五篇：算法总结
点击咨询 