常用算法电子课件

1、补充1常用的算法简介1算法算法是解决问题方法的精确描述,但并不是所有问题都有算法,有的问题经研究可行,则有相应的算法。有些问题不能说明可行,则没有相应的算法,但不是说明这类问题没有结果。例如：猜想问题,有结果,然而目前还没有算法。上述所谓的可行,就是指算法的研究。算法的性质解题算法是一有穷动作序列动作序列仅有一个初始的动作序列中每个动作的后继动作是确定的序列的终止表示问题得到解答或问题没有解答算法的分类数值算法非数值算法2数值算法和非数值算法数值算法迭代法：迭代法适用于方程或方程组求解,使用间接方法求方程 近似根的一种常用算法。递推法：详见后页递归法：详见后页插值法：详见后页差分法：通过差分方

2、程求解微分方程近似解。非数值算法穷举搜索法：搜索所有可能的情形,从中找出符合要求的解。递归法：详见后页回溯法：详见后页贪婪法：详见后页分治法： 思想是把一个规模为n的问题,分解为若干个规模较小的问题,使得从这些规模较小问题的解易于构造整个问题的解。3递推法递推法实际上是需要抽象为一种递推关系,然后按照递推关系式求解。递推法通常表现为两种方式：一个是简单到一般,另一个是将一个复杂问题逐步推到一个已知的简单的问题。这两种方式反映了两种不同的递推方向,前者往往用于计算级数,后者往往于回归配合成为递归。4插值法插值法称为内插法。往往只知道它在某区间中若干点的函数值,这时候做出适当的特定的函数,使得在这

3、些点上取已知值,并且在这区间内其他各点上就用这特定函数所取的值作为函数f(x)的近似值,这种方法成为插值法。如果这个特定函数是多项式,就称为插值多项式或内插多项式5贪婪法贪婪法是一种可以快速的得到满意解（但不一定是最优解）的方法。方法的贪婪性反映在对当前的情况,总是做最大限度的选择。即满足条件的均选人,然后分别展开,最后选得一个问题得解。这个方法不考虑回溯,也不考虑每次选择是否符合最优解的条件,但最终能得到接近最优结果的选择货郎担问题背包问题背包问题的基本描述是：有一个背包,能盛放的物品总重量为 S,设有 N 件物品,其重量分别为w1,w2,.,wn,希望从N件物品中选择若干件物品,所选物品的

4、重量之和恰能放入该背包,即所选物品的重量之和等于 S 。6回溯法回溯法是一种选优的搜索方法,按照选优的条件向前搜索,以达到目标,但是当搜索到某一步的时候,发现原先的选择并不优或者达不到目标,就退回一步重新选择,这种走不通就退回再走的技术就是回溯法。八皇后问题（也可以用递归等其他算法求解）会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上（有8*8个方格），使它们谁也不能被吃掉！这就是著名的八皇后问题。四色问题（也可以用递归等其他算法求解）人们在实践中得到的结论是：在每张地图上，最多使用四种颜色，就能给所有公共边界的地区着上不同的颜色。实践中有这样

5、的结果，要在理论上予以证明却不那么容易。这是数学史上的一个困扰人们多年的著名难题。为了圆满地解决图着色问题，人们已经奋斗了一百多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使用递推要

6、注意（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）当回归到原问题的解时,算法中所涉及的处理对象是关于当前问题的,即递归算法所涉及的参数与局部处理

7、对象是有层次的。当解一问题的时候,有它的一套参数与局部处理对象。当递推进入一个简单问题的时候。这套参数与局部对象便隐藏起来,在解简单问题的时候又有它自己的一套。当回归时,原问题的一套参数与局部处理对象又活跃起来了。（2）回归到原问题已经得到问题的解,回归并不引起其他动作。11递归的例子计算n!根据公式 n!=1 当n=0 =n*(n-1)! 当n!=0函数参数为nint f(int n) if (!n) return 1; else return (n*f(n-1); 12递归的例子斐波那契数列(fibonacci)f(1)=0f(1)=1f(n)=f(n-1)+f(n-2) (n=2)int

8、 f(int n) if (!n) return 0; else return(f(n-1)+f(n-2);13梵塔问题一个印度的古老传说：在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓梵塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片：一次只移动一片,不管在哪根针上,小片必须在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一根针上时,世界就将在一声霹雳中消灭,梵塔、庙宇和众生都将同归于尽。如果考虑一下把64片金片,由一根针上移到另一根针上,并且始终保持上小下

9、大的顺序,一共需要移动多少次,那么,不难发现,不管把哪一片移到另一根针上,移动的次数都要比移动上面一片增加一倍。这样,移动第1片只需1次,第2片则需2次,第3片需4次,第64片需2的63次方次。全部次数为：18446744073709551615次这和麦粒问题的计算结果是完全相同的! 假如每秒钟移动一次,共需要多长时间呢?一年大约有31556926秒,计算表明,移完这些金片需要5800多亿年! 14梵塔问题算法分析：用A、B、C分别表示三根针将n个盘由A移到C上的操作步骤为：（1）将A上的n-1个盘借助C移到B上（2）把A上剩下的一个盘由A移到C上（3）这样处理后,问题的规模减少1（4）如法炮

10、制,可将n个盘子移到C上。 显然这是递归算法问题。15穷举演算n = 3A B CA B CA B CA B C( 1 )( 2 ) A TO C( 3 ) A TO B(4) C TO B16穷举演算(续） A B C( 5 ) A TO C A B CA B CA B C( 6 ) B TO A (7 ) B TO C (8 ) A TO C 17梵塔问题:子程序/* 程序HANOI.C: 梵塔问题-*/#include #define N 3void move(int from, int to) printf(From %c to %cn, from, to);void hanoi(in

11、t 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=f

12、1(a); :return(3+c);19背包问题的递归算法#include#define N 7#define S 15int wN+1 = 0,1,4,3,4,5,2,7;int knap ( int s,int n) if(s = 0) return 1; if ( s0 & n1 ) return 0; 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

13、,精确到小数1000位例：使用幂级数展开,计算初等函数,要求有多位有效数字的算法假设要求小数点后1000位,n=450例如计算自然对数底e的值。为了保证1000位有效数字,计算采用竖式方法,即e与1/i!的值都用数组表示,每一位数对应一个数组元素。如：27182818284590452353540166666666666666666666er21求e,精确到小数1000位每计算r,即1/i!是将前次r除以i。所谓r除以i,就是对每个rj加上前位除以i的余数乘以10,其和对i的商做新的rj的值,而其余数再留给下一位使用。当计算得到一个r的值后加上e,最后再对e作处理即可。同时考虑进位因素,所以数

14、组末端有三位留作进位可能引起误差。（所以使用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

15、%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例: 打印年历算法分析：1、确定闰年 year%4=0 且 year%100！=0 或 year%400=02、确定元旦是星期几平年一年是52（52x7=354）个星期多一天 。所以平年元旦

16、的星期数是上一年元旦星期数加1。闰年又多一天，所以闰年元旦的星期数是上一年元旦星期数加2。1900年的元旦是星期一，所以year的星期几可以根据下列方法计算：n year -1900 相差n年 n = n +（n - 1 ）/4 +1 n年多n天，（n-1）/4个闰年数，再加1900年元旦的星期序号1n = n % 7 求出最后的星期数 26程序逻辑功能框图 输入年year调用isleap（）判断是否闰年调用子函数求元旦是星期几week_of_newyear_day()Month=12?Month=1打印当前月日历month=month+1是否27打印当前月处理框图 确定当月1日的位置确定月天

17、数len_of_month月天数 = 30天 小月31天 大月28天 平2月29天 闰2月day=月天数？打印当前日期是否7天换行day= day+1否是是day =1否28程序模块结构 主函数main()子函数求元旦的星期数week_of_newyears_day()子函数判别闰月Isleap（）29确定闰年子函数程序#include #define YES 1 /* 定义符号常数“是” */#define NO 0 /* 定义符号常数“否” */*- 函数 isleap(): 判断某年是否闰年 -*/int isleap(int year) int leap = NO; if(year%4

18、=0 & year%100!=0 | year%400=0) leap = YES; return leap; 30 /*- 函数 week_of_newyears_day(): 求元旦是星期几 -*/ int week_of_newyears_day(int year) int n = year-1900; n = n+(n-1)/4+1; n = n%7; return n; 31 /*- 主函数: 打印年历 -*/ main() int year, month, day, weekday, len_of_month, i; printf(nPlease input year: ); scanf(%d,&year);32/*- 打印年历 -*/ printf