补充常用的算法简介优秀文档

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,补充1,常用的算法简介,1,算法,算法是解决问题方法的精确描述,但并不是所有问题都有算法,有的问题经研究可行,则有相应的算法。有些问题不能说明可行,则没有相应的算法,但不是说明这类问题没有结果。例如：猜想问题,有结果,然而目前还没有算法。上述所谓的可行,就是指算法的研究。,算法的性质,解题算法是一有穷动作序列,动作序列仅有一个初始的动作,序列中每个动作的后继动作是确定的,序列的终止表示问题得到解答或问题没有解答,算法的分类,数值算法,非数值算法,2,数值算法和非数值算法,数值算法,迭代法：,迭代法适用于方程或方程组求解,使用间接方法求方程 近似根的一种常用算法。,递推法：,详见后页,递归法：,详见后页,插值法：,详见后页,差分法：,通过差分方程求解微分方程近似解。,非数值算法,穷举搜索法：,搜索所有可能的情形,从中找出符合要求的解。,递归法：,详见后页,回溯法：,详见后页,贪婪法：,详见后页,分治法：,思想是把一个规模为n的问题,分解为若干个规模较小的问题,使得从这些规模较小问题的解易于构造整个问题的解。,3,递推法,递推法实际上是需要抽象为一种递推关系,然后按照递推关系式求解。递推法通常表现为两种方式：一个是简单到一般,另一个是将一个复杂问题逐步推到一个已知的简单的问题。这两种方式反映了两种不同的递推方向,前者往往用于计算级数,后者往往于回归配合成为递归。,4,插值法,插值法称为内插法。往往只知道它在某区间中若干点的函数值,这时候做出适当的特定的函数,使得在这些点上取已知值,并且在这区间内其他各点上就用这特定函数所取的值作为函数f(x)的近似值,这种方法成为插值法。如果这个特定函数是多项式,就称为插值多项式或内插多项式,5,贪婪法,贪婪法是一种可以快速的得到满意解（但不一定是最优解）的方法。方法的贪婪性反映在对当前的情况,总是做最大限度的选择。即满足条件的均选人,然后分别展开,最后选得一个问题得解。这个方法不考虑回溯,也不考虑每次选择是否符合最优解的条件,但最终能得到接近最优结果的选择,货郎担问题,背包问题,背包问题的基本描述是：有一个背包,能盛放的物品总重量为 S,设有 N 件物品,其重量分别为w1,w2,.,wn,希望从N件物品中选择若干件物品,所选物品的重量之和恰能放入该背包,即所选物品的重量之和等于 S。,6,回溯法,回溯法是一种选优的搜索方法,按照选优的条件向前搜索,以达到目标,但是当搜索到某一步的时候,发现原先的选择并不优或者达不到目标,就退回一步重新选择,这种走不通就退回再走的技术就是回溯法。,八皇后问题（也可以用递归等其他算法求解）,会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8*8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。,四色问题（也可以用递归等其他算法求解）,人们在实践中得到的结论是：在每张地图上，最多使用四种颜色，就能给所有公共边界的地区着上不同的颜色。,实践中有这样的结果，要在理论上予以证明却不那么容易。这是数学史上的一个困扰人们多年的著名难题。为了圆满地解决图着色问题，人们已经奋斗了一百多,7,递归算法(重点掌握）,递归是一种特别有用的工具,不仅在数学中广泛应用,在日常生活中也常常遇到。,8,递归算法,在数学中几个熟知的数学定义：,(2)若t1,t2是树，则 也是树,9,递归,递归算法包括,递推,和,回归,两部分：,递推,就是为了得到问题的解,将它推到比原问题更简单的问题求解。,例如：n!=f(n),为了计算f(n),将它推到比原问题更简单的问题f(n-1),即f(n)=f(n-1)*n,而计算f(n-1)比计算f(n)简单,因为f(n-1)比f(n)更加接近已知解0!=1,使用递推要注意,（1）递推应有终止之时,例如当n=0时,0!=1为递推终止条件,所谓终止条件就是指在此条件下问题的解时明确的,缺少终止条件会使算法失败。,（2）简单问题表示离递推终止条件更接近的问题。简单的问题与原问题其解的算法是一致的,其差别主要反映在参数上,例如,f(n-1)比计算f(n)更简单,因为f(n-1)比f(n)参数少1。参数变化使问题递推到有明确解。,10,递归算法,回归,指当简单问题得到解后,回归到原问题的解上来。例如,当计算完(n-1)!后,回归计算n*(n-1)!,即得到n!的值。,使用回归要注意,（1）当回归到原问题的解时,算法中所涉及的处理对象是关于当前问题的,即递归算法所涉及的参数与局部处理对象是有层次的。当解一问题的时候,有它的一套参数与局部处理对象。当递推进入一个简单问题的时候。这套参数与局部对象便隐藏起来,在解简单问题的时候又有它自己的一套。当回归时,原问题的一套参数与局部处理对象又活跃起来了。,（2）回归到原问题已经得到问题的解,回归并不引起其他动作。,11,递归的例子,计算n!,根据公式,n!=1 当n=0,=n*(n-1)!当n!=0,函数参数为n,int f(int n),if(!n),return 1;,else,return(n*f(n-1);,12,递归的例子,斐波那契数列(fibonacci),f(1)=0,f(1)=1,f(n)=f(n-1)+f(n-2)(n=2),int f(int n),if(!n),return 0;,else,return(f(n-1)+f(n-2);,13,梵塔问题,一个印度的古老传说：在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓梵塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片,不管在哪根针上,小片必须在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,梵塔、庙宇和众生都将同归于尽。,14,梵塔问题,算法分析：,用A、B、C分别表示三根针,将n个盘由A移到C上的操作步骤为：,（1）将A上的n-1个盘借助C移到B上,（2）把A上剩下的一个盘由A移到C上,（3）这样处理后,问题的规模减少1,（4）如法炮制,可将n个盘子移到C上。,显然这是递归算法问题。,15,穷举演算,n=3,A,B,C,A,B,C,A,B,C,A,B,C,(1),(2)A TO C,(3)A TO B,(4)C TO B,16,穷举演算(续）,A,B,C,(5)A TO C,A,B,C,A,B,C,A,B,C,(6)B TO A,(7)B TO C,(8)A TO C,17,梵塔问题:子程序,/*程序HANOI.C:梵塔问题-*/,#include,#define N 3,void move(int from,int to),printf(From%c to%cn,from,to);,void hanoi(int n,int p1,int p2,int p3),if(n=1),move(p1,p3);,else,hanoi(n-1,p1,p3,p2);,move(p1,p3);,hanoi(n-1,p2,p1,p3);,/*测试用主函数 */,main(),hanoi(N,A,B,C);,18,函数的递归调用,定义：在调用一个函数的过程中又直接或间,接地调用了该函数本身。,注意：递归调用容易出现无休止,的调用而使函数不能结束。,int f1(int x),int y,z;,:,z=f2(y);,:,return(2*z);,int f2(int t),int a,c;,:,c=f1(a);,:,return(3+c);,19,背包问题的递归算法,#include,#define N 7,#define S 15,int wN+1=0,1,4,3,4,5,2,7;,int knap(int s,int n),if(s=0)return 1;,if(s0,if(knap(s-wn,n-1),printf(%4d,wn);,return 1;,return knap(s,n-1);,main(),if(knap(S,N),printf(OK!n);,else,printf(N0!n);,20,补充数组难点例子：求e,精确到小数1000位,例：使用幂级数展开,计算初等函数,要求有多位有效数字的算法,假设要求小数点后1000位,n=450例如计算自然对数底e的值。,为了保证1000位有效数字,计算采用竖式方法,即e与1/i!的值都用数组表示,每一位数对应一个数组元素。如：,2,7,1,8,2,8,1,8,2,8,4,5,9,0,4,5,2,3,5,3,5,4,0,1,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,e,r,21,求e,精确到小数1000位,每计算r,即1/i!是将前次r除以i。所谓r除以i,就是对每个rj加上前位除以i的余数乘以10,其和对i的商做新的rj的值,而其余数再留给下一位使用。,当计算得到一个r的值后加上e,最后再对e作处理即可。同时考虑进位因素,所以数组末端有三位留作进位可能引起误差。（所以使用1004长度的数组）,22,求e,精确到小数1000位,cale(int e1004),int r1004;,int i,j;,int c;,e0=1;,r0=1;,for(j=1;j 1004;j+)/,初始化,e,r,ej=0;,rj=0;,23,求e,精确到小数1000位,for(i=1;i 450;i+)/计算1/i!,并累加,c=0;,for(j=0;j 1004;j+)/r除以i,c=c*10+rj;,rj=c/i;,c=c%i;,for(j=0;j0;j-)/处理进位,c+=ej;,ej=c%10;/留下余数,c=c/10;/商进一位,e0+=c;,printf(n%3d.n,e0);,printf();,for(j=0;j1001;j+)/输出e的值,printf(%ld,ej);,if(j%5=0)/处理格式,5位空一格,printf();,if(j%10=0)/处理格式,50位空一行,printf(n);,/end for j,/end for cale,25,同时考虑进位因素,所以数组末端有三位留作进位可能引起误差。,例如：n!=f(n),为了计算f(n),将它推到比原问题更简单的问题f(n-1),即f(n)=f(n-1)*n,而计算f(n-1)比计算f(n)简单,因为f(n-1)比f(n)更加接近已知解0!=1,year%4=0 且 year%100！,printf(n);,算法是解决问题方法的精确描述,但并不是所有问题都有算法,有的问题经研究可行,则有相应的算法。,序列中每个动作的后继动作是确定的,ej=c%10;/留下余数,#define N 3,斐波那契数列(fibonacci),当回归时,原问题的一套参数与局部处理对象又活跃起来了。,leap=YES;,return knap(s,n-1);,例:打印年历,算法分析：,1、确定闰年,year%4=0 且 year%100！=0 或 year%400=0,2、确定元旦是星期几,平年一年是52（52x7=354）个星期多一天。所以平年元旦的星期数是上一年元旦星期数加1。,闰年又多一天，所以闰年元旦的星期数是上一年元旦星期数加2。,1900年的元旦是星期一，所以year的星期几可以根据下列方法计算：,n year-1900,相差n年,n=n+（n-1）/4+1,n年多n天，（n-1）/4个闰年数，再加1900年元旦的星期序号1,n=n%7,求出最后的星期数,26,return 0;,else,A B C,斐波那契数列(fibonacci),weekday=weekday+1;,return 1;,所谓r除以i,就是对每个rj加上前位除以i的余数乘以10,其和对i的商做新的rj的值,而其余数再留给下一位