《唐良荣计算机导论计算思维和应用技术算法基课件》由会员分享，可在线阅读，更多相关《唐良荣计算机导论计算思维和应用技术算法基课件（68页珍藏版）》请在金锄头文库上搜索。
1、计算机导论计算思维和应用技术计算机4.1.34.1.3算法的评估算法的评估4.1.44.1.4算法复杂度算法复杂度4.1.14.1.1算法的定义算法的定义4.1.24.1.2算法的表示算法的表示4.1.1算法的定义1、算法的基本定算法的基本定义最早的算法：公元前2000年，古巴比伦数学家提出了一元二次方程及其解法。高德纳（DonaldErvinKnuth）：“算法知识远不是为了编写好的计算程序，它是一种具有一般意义的智能工具，必定有助于对其他学科的理解，不论化学、语言学或者是音乐等”。科尔曼（ThomasH.Cormen）：“算法就是任何定算法就是任何定义明确的明确的计算步算步骤，它接收一些值
2、或集合作为输入，并产生一些值或集合作为输出。这样，算法就是将输入转换为输出的一系列计算过程”。程序不一定都是算法，程序不一定满足有穷性。程序是算法在程序是算法在计算机上的算机上的实现。4.1.1算法的定义2、算法的基本特征算法的基本特征（1）有穷性算法必须在有穷步后结束。（2）确定性算法必须无二义性，不会产生理解偏差。算法任何时候都只有唯一的一条执行路径。（3）可行性算法描述的操作可以通过基本运算实现。（4）输入算法有0个或多个输入。有些数据在算法执行过程中输入，而有的数据被嵌入在算法之中。（5）输出算法有1个或多个输出。不同输入有不同输出，但是相同输入必须产生相同输出。4.1.1算法的定义【
3、案例】欧几里得经典算法：勾股定理证明。4.1.1算法的定义【扩展】算法设计和分析流程。计算机导论计算思维和应用技术第第4 4章章 算法基算法基础1.1.1计算机的发展4.1.2算法的表示算法表示形式：自然语言，伪代码，流程图，N-S图，PAD图，程序等。1、用自然用自然语言表示算法言表示算法优点：简单，便于阅读。缺点：文字冗长，容易出现歧义。【例4-1】：用自然语言描述计算并输出z=xy的流程：（1）输入变量x，y；（2）判断y是否为0；（3）如果y=0，则输出出错提示信息；（4）否则计算z=x/y；（5）输出z。4.1.2算法的表示2、用用伪代代码表示算法表示算法伪代代码是一种算法描述是一种
4、算法描述语言言。伪代码没有标准，用类似自然语言的形式表达；伪代码必须结构清晰、代码简单、可读性好。【例4-2】用伪代码描述：从键盘输入3个数，输出其中最大的数。（1）（2）（3）（4）（5）（6）（7）Begin输入A，B，CifABthenMaxAelseMaxBifCMaxthenMaxC输出MaxEnd/*算法伪代码开始*/*输入变量A、B、C*/*条件判断，如果A大于B，则赋值Max=A*/*否则将B赋值给Max*/*如果C大于Max，则赋值Max=C*/*输出最大数Max*/*算法伪代码结束*/4.1.2算法的表示3、用流程用流程图表示算法表示算法流程图由特定意义的图形构成，它能表示
5、程序的运行过程。流程图规定：圆边框表示算法开始或结束；矩形框表示处理功能；平行四边形框表示数据的输入或输出；菱形框表示条件判断；圆圈表示连接点；箭头线表示算法流程；Y（是）表示条件成立；N（否）表示条件不成立。4.1.2算法的表示【例4-3】用流程图表示：输入x、y，计算z=xy，输出z。4.1.2算法的表示4.1.2算法的表示【案例】同一算法的不同表达形式。伪代码表达算法：BeginIFX3THENY=5ELSEY=5+1.5（X-3）ENDIF;输出YEnd自然语言表达算法：开始如果X3；则Y=5；否则Y=5+1.5（X-3）输出Y结束4.1.2算法的表示4、用用N-S图表示算法表示算法N
6、-S流程图没有流程线，算法写在一个矩形框内；每个处理步骤用一个矩形框表示；处理步骤是语句序列；矩形框中可以嵌套另一个矩形框；N-S图限制了语句的随意转移，保证了程序的良好结构。4.1.2算法的表示【例4-4】输入整数m，判断它是否为素数。#includemain()intm,i,k;scanf(%d,&m);k=sqrt(m);for(i=2;ik+1)printf(%d是素数n,m);elseprintf(%d不是素数n,m);/*C语言源程序*/*读入整数m*/*求m平方根*/*循环开始*/*模运算*/*输出索数*/*提示信息*/4.1.2算法的表示5、用用PAD图表示算法表示算法PAD（
7、问题分析图）用树形结构图表示程序的控制流程。PAD图规定：最左端的纵线是程序主干线，对应程序的第一层结构；每增加一层，则向左扩展一条纵线；程序自上而下，自左向右依次执行；程序终止于最左边的主干线。4.1.2算法的表示【案例】判断三角形性质的PAD图。计算机导论计算思维和应用技术第第4 4章章 算法基算法基础1.1.1计算机的发展4.1.3算法的评估1、算法的算法的评价价标准准（1）正确性不含语法错误；对输入数据能够得出满足要求的结果；对精心选择的输入数据，能得出满足要求的结果；对一切合法输入，都可以得到符合要求的解。（2）可读性算法主要用于人们的阅读与交流，其次才是为计算机执行。算法算法简单则
8、程序程序结构也会构也会简单，这便于程序调试。（3）健壮性算法应具有容错处理。算法健壮性要求：输入非法数据或错误操作给出提示，而不是中断程序执行；返回表示错误性质的值，以便程序进行处理。4.1.3算法的评估（4）效率每个問題有多个算法存在，每个算法的计算量都会不同。在保证运算效率的前提下，力求算法简单。【例4-5】9个外观一样的金币.，其中一个赝品重量较轻。如果用天平秤鉴别真伪，一共需要称几次？算法1：天平左边金币固定，不断变换右边金币，最多称7次可鉴别出假币。算法2：天平两边各一个金币，每次变换两边金币，最多称4次可鉴别出假币。算法3:：天平左边3个，右边3个，留下3个，最多称2次可以鉴别出假
9、币。4.1.3算法的评估2、算法性能的度量算法性能的度量从算法时间复杂度和空间复杂度评价算法优劣。算法运行时间取决于以下因素：（1）硬件速度如CPU工作频率，CPU内核数，内存容量等。（2）程序语言编程语言级别越高，执行效率越低。（3）编译质量编译系统对程序优化较好时，生成的执行程序质量较高。（4）问题规模求100以内的素数与求10000以内的素数执行时间必然不同。可以将软件和硬件环境看作一个固定值；算法运行工作量只与问题规模相关，或者说它是问题规模的函数。计算机导论计算思维和应用技术第第4 4章章 算法基算法基础1.1.1计算机的发展4.1.4算法复杂度1、算法分析算法分析算法复杂度是衡量算
10、法难度的尺度。算法需要的资源越多，复杂度越高。算法复杂度包括时间复杂度和空间复杂度。复杂问题或高效算法一般不做算法分析，而是采用基准测试方法。能够分析清楚的算法，一般是简单或低效算法；难题（如货郎担问题）及高效算法很难分析清楚。4.1.4算法复杂度2、计算算法复算算法复杂度的困度的困难算法复杂度与问题规模大小有关；输入数据的分布也会影响算法复杂度。算法复杂度评价：最好、最坏、平均；通常着重于最坏情况下的算法复杂度。精确计算算法复杂度的困难：（1）由算法写出程序需要花费很大的精力；（2）会因为程序写的好坏，影响算法的质量；（3）测试数据很难对各个算法都公正；（4）好算法需要反复改进，反复测试，工
11、作量很大。4.1.4算法复杂度3、算法算法时间复复杂度的表示度的表示算法时间复杂度指程序从开始运行到结束需要的时间。问题规模为n，算法需要的时间为T(n)时，T(n)称为算法的“时间复复杂度度”。算法时间复杂度常用大大O表示（读为：大圈，Order，big-O）。算法时间复杂度与输入数据的规模模有关。如，二分查找算法复杂度是O（logn），表示二分查找需要通过logn量级的运算步骤，去查找一个规模为n的数组。如，算法复杂度为O(f(n)，表示当n增大时，运行时间最多以f(n)的速度增长。4.1.4算法复杂度常见算法复杂度级别如表4-1所示。类型复杂度说明案例多项式解(1)常数阶如向数组中写入数
12、据，总能在一个确定的时间内返回结果(logn)对数阶如对排序后的数据，用二分查找法确定位置(n)线性阶如在一队无序的数据列表中，用顺序查找的方法确定位置(nlogn)线性对数阶如快速排序，一般情况为(nlogn)，最坏情况为(n2)(n2)平方阶2层循环，如44矩阵要计算16次；如简单排序的复杂度(n3)立方阶3层循环，如444矩阵要计算64次指数解(2n)指数阶如汉诺塔问题，密码暴力破解问题(N!)阶乘阶如旅行商问题，汉密尔顿回路问题4.1.4算法复杂度【案例】算法时间复杂度增长趋势曲线。4.1.4算法复杂度设计算法要避免复杂度指数级递增。【案例】问题规模N与运算时间如下表。说明：表中假设计
13、算机每秒做109（10亿，GHz级）次基本运算。问题规模问题规模N=10N=10N=20N=20N=30N=30N=40N=40N=50N=50N=60N=60N110-8秒210-8秒310-8秒410-8秒510-8秒610-8秒N2110-7秒410-7秒910-7秒1610-7秒2510-7秒3610-7秒N3110-6秒810-6秒2710-6秒6410-6秒12510-6秒21610-6秒N6110-3秒6410-3秒0.729秒4秒15.6秒44.6秒2N110-6秒110-3秒1秒18.3分312.7小时36.5年3N610-5秒3秒27小时385年2276万年1344亿年4.
14、1.4算法复杂度4、算法算法时间复复杂度度计算案例算案例【例4-7】时间复杂度T(n)=O(1)的情况，如：temp=i;i=j;j=temp;以上语句的频度均为1，程序执行时间是与问题规模n无关的常数。算法时间复杂度为常数阶时，记作T(n)=O(1)。如果算法执行时间不随问题规模n的增加而增长，即使算法有上千条语句，其执行时间也是一个较大的常数。4.1.4算法复杂度【例4-8】时间复杂度T(n)=O(n)的情况。以上算法的时间复杂度为：T(n)=2+n+3(n-1)=4n-1=O(n)。(1)(2)(3)(4)(5)a=0;b=1;for(i=2;i=n;i+)s=a+b;b=a;a=s;/
15、*计算频度=2次*/*计算频度=n次*/*计算频度=n-1次*/*计算频度=n-1次*/*计算频度=n-1次*/4.1.4算法复杂度【例4-9】时间复杂度T(n)=O(logn)的情况。设语句2的频度是：f(n)，f(n)=n，f(n)=logn，取最大值f(n)=logn；算法的时间复杂度为：T(n)=O(logn)(1)(2)(3)i=1;while(i=n)i=i*2;/*计算频度=1次*/*计算频度=f(n)次*/*计算频度=n-1次*/4.1.4算法复杂度【例4-10】时间复杂度T(n)=O(n2)的情况。以上算法的时间复杂度为：T(n)=2n2+n+1=O(n2)；算法时间复杂度为
16、：T(n)=O(n2)。(1)(2)(3)(4)sum=0；for(i=1;i=n;i+)for(j=1;j1的整数：n！=(n*Fac(n-1)（基本公式）。4.2.1递归算法思想3、递归的的终止条件止条件当边界条件不满足时，递归就前进；当边界条件满足时，递归就开始回溯。可见递归实现了某种形式的循环。递归函数在每次调用后，必须越来越接近边界条件；当递归符合边界条件时，它不再调用自身，递推停止，并开始回溯；如果递归函数始终无法满足边界条件，则程序会因为内存单元溢出而失败退出。4.2.1递归算法思想4、阶乘的乘的递归过程分析程分析【例4-17】以阶乘3！的计算为例，说明递归的执行过程。（1）递推
17、过程计算3!时，先计算2!；将2!的计算值回代就可以求出3!的值（3!=3*2!）；程序并不知道2!的值是多少，因此需要先计算1!的值；将1!的值回代就可以求出2!的值（2!=2*1!）；而计算1!的值时，必须先计算0!；将0!的值回代就可以求出1!的值（1!=1*0!）。这时0！=1是阶乘的边界条件；递归满足这个边界条件时，递推过程结束。4.2.1递归算法思想（2）回溯过程递归满足边界条件后，递归开始进行回溯，即：（0！=1）（1！=1*1）（2！=2*1）（3！=3*2）；最终得出3！=6。4.2.1递归算法思想5、递归的的应用用（1）递归适用条件数据是按递归定义的（如阶乘、Fibonac
18、ci函数）；问题可以按递归算法求解（如回溯）；数据结构是按递归定义的（如树遍历）。（2）递归基本条件通过递归可以缩小问题的规模，而且存在递归基本公式；存在边界条件，递归达到边界条件时退出。（3）递归的缺点递归算法比常用算法运行效率低；递归次数过多容易时，容易造成内存单元不够而产生数据溢出。4.2.1递归算法思想6、递归算法程序算法程序设计案例案例【例4-18】递归函数算法的伪代码：Begin定义递归函数递归函数=基本公式if满足边界条件then返回;else调用本身（递归函数）;endif输出计算值End4.2.1递归算法思想【例4-19】用C语言求正整数n的阶乘值n！。阶乘的数学定义：求阶乘
19、值中N=3的执行过程。4.2.1递归算法思想求正整数n阶乘的C语言源程序。(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)#include#includevoidmain()intn,rs,fac(intn);printf(请输入计算阶乘的数n：);scanf(%d,&n);rs=fac(n);printf(n%d的阶乘结果为：%d,n,rs);intfac(n)if(n=0)return(1);returnn*fac(n-1);/*声明输入输出头文件*/*声明数据计算头文件*/*声明主函数*/*声明实参，n阶乘，rs阶乘值，fac阶乘函数*/*显示提示信息*/*读入阶乘
20、数n作为实参*/*调用自定义递归函数fac(n)*/*显示阶乘值rs*/*自定义递归函数，n为形参*/*判断边界条件，如果n=0，则返回值=1*/*否则按基本公式计算，并将值返回主函数*/4.2.1递归算法思想【案例】分形图的递归调用。自然界分形图4.2.1递归算法思想【案例】在HTML5中利用Canvas标签画递归画树。计算机导论计算思维和应用技术第第4 4章章 算法基算法基础1.1.1计算机的发展4.2.2迭代算法思想1、迭代的概念迭代的概念【案例】迭代现象广泛存在于工作和生活中。4.2.2迭代算法思想【案例】软件开发中的迭代过程。4.2.2迭代算法思想迭代是利用迭代是利用变量的原量的原值
21、推算出推算出变量的新量的新值。如果递归是自己调用自己，迭代就是A不停的调用B。迭代适合计算机做重复性操作重复性操作；在程序中，迭代一般用循环实现。4.2.2迭代算法思想2、迭代的基本策略迭代的基本策略（1）确定迭代模型在迭代中，存在一个不断由旧值递推出新值的迭代变量。（2）建立迭代关系式迭代关系式是变量的前一个值推出下一个值的基本公式。（3）迭代过程的控制不能让迭代过程无休止地重复执行（死循环）。迭代过程控制：迭代次数是确定值时，可以构建固定次数的循环来实现迭代过程的控制；迭代次数无法确定时，需要在程序循环体内判断结束迭代过程的条件。4.2.2迭代算法思想3、迭代算法程序迭代算法程序设计案例案
22、例【例4-20】阿米巴细菌3分钟分裂一次。将若干个阿米巴细菌放在一个盛满营养液的容器内，45分钟后容器内就充满了阿米巴细菌。已知容器最多可以装阿米巴细菌220个。请问，开始时往容器内放了多少个阿米巴细菌？4.2.2迭代算法思想解题算法：细菌3分钟分裂一次，45分钟后充满容器，需要分裂45/3=15次；细菌分裂15次后的数量是220个；倒推：第15次分裂后是220个，倒推出第14次分裂后的个数，再倒推出第13次分裂之后，第12次分裂之后，第1次分裂之前的个数。设第1次分裂之前的细菌数为x0个，第1次分裂之后为x1个，第2次分裂之后为x2个，第15次分裂之后为x15个，则有：x14=x15/2，x
23、13=x14/2，xn-1=xn/2；（n1）将上面倒推公式转换成如下迭代基本公式：x=x/2（x的初值为第15次分裂之后的个数220，即x=220）这个迭代基本公式重复执行15次，就可以倒推出第1次分裂之前的细菌个数。4.2.2迭代算法思想用一个固定次数的循环程序来实现对迭代过程的控制。程序伪代码如下：(1)(2)(3)(4)(5)(6)(7)(8)(9)Beginclsx=220fori=1to15x=x/2i=i+1endforprint“初始阿米巴细菌数为：”,xEnd/*伪代码开始*/*变量初始化*/*最终阿米巴细菌数量，迭代初始条件*/*设置循环（迭代）终止条件*/*利用迭代基本公
24、式进行计算*/*循环次数控制*/*循环结束*/*输出初始阿米巴细菌数*/*伪代码结束*/计算机导论计算思维和应用技术第第4 4章章 算法基算法基础1.1.1计算机的发展4.2.3递归与迭代的区别1、生活中的迭代和生活中的迭代和递归案例案例【案例】学生问王老师一个问题，王老师自己不知道答案，这时王老师问张老师；张老师说他也不知道，让王老师去问一问李老师；王老师又去问李老师，李老师将答案告诉王老师；王老师再将答案告诉学生；这样整个询问过程就完成了。在以上过程中，王、张、李老师之间的信息询问方式称为迭代查询。4.2.3递归与迭代的区别【案例】老板要去喜来登酒店，但不知道怎么走，于是问你（你是他的秘书
25、），你只知道酒店在市区内，但是具体地点不知道，于是你问张三；张三知道酒店在在芙蓉路，但是不清楚是多少号；于是张三去问李四，李四告诉张三酒店在478号；然后张三告诉你酒店在芙蓉路478号；你把结果告诉老板，喜来登酒店在市区的芙蓉路478号，这样整个询问过程就完成了。你、张三、李四之间的询问方式就称为递归查询。4.2.3递归与迭代的区别2、递归与迭代的主要区与迭代的主要区别（1）实现方式递归和迭代都重复执行某段程序代码；递归通过重复性的自身调用来实现；迭代采用循环实现。递归是从结果向初始值递推和回溯的过程；迭代是从初始值开始，经过有限次数循环，得到一个结果；简单的说，递归需要回溯，迭代不需要回溯。
26、（2）终止条件迭代不符合循环条件时就结束迭代；递归是达到边界条件时，开始回溯，直到递归结束。4.2.3递归与迭代的区别（3）内存资源迭代的空间复杂度为O(1)；递归空间复杂度是O(n)；递归嵌套层数较深时，会因为内存资源耗尽，导致系统崩溃。（4）运行效率实际上递归效率比迭代低。递归的函数调用需要额外的时间开销；迭代运行时间只因循环次数增加而增加，没有额外开销。（5）适应性递归适用于需要回溯的问题（如迷宫问题）；递归适用于空间为树形结构的问题等（如决策树问题）；迭代适用于不需要回溯的问题（如简单递增）。4.2.3递归与迭代的区别（6）算法转换理论上所有递归函数都可以转换为迭代函数，反之亦然；对算
27、法结构来说，递归并不总是能够转换为迭代结构。这就像动态的东西并不总是可以用静态的方法实现一样。【案例】链表使用递归定义很简单，但是使用数组（迭代的需要）时变得很晦涩。实际上，所有迭代都可以转换为递归；但递归不一定可以转换为迭代。计算机导论计算思维和应用技术第第4 4章章 算法基算法基础1.1.1计算机的发展4.2.4递归与迭代的应用1、利用利用递归和迭代和迭代进行行DNS查询网站通过域名（如）进行访问；因特网每台主机通过IP地址（如115.239.210.27）进行访问；域名与IP地址转换的系统称为域名系统（DNS）。DNS解析：115.239.210.27全球有13个根域名服务器系统负责解析
28、顶级域名（如：.com、.net、.cn、.tw等）；各个国家网络运营商负责本地域名（如：.baidu、.qq、.ibm等）的解析。4.2.4递归与迭代的应用【例4-21】访问网站时，本地网络公司的DNS服务器，会帮助客户端计算机解析域名对应的IP地址。DNS解析方法：从客户端到本地DNS服务器之间采用递归查询；而DNS服务器之间采用迭代查询。4.2.4递归与迭代的应用MatlabMatlab迭代法迭代法求平方根程序求平方根程序问题与与讨论讨论：（1）举例说明生活中算法的案例？（2）算法和程序有什么区别？（3）算法都能给出数学证明吗？（4）递归能够取代“循环”语句吗？（5）为什么二分查找速度很快？（6）如何将学生宿舍用树结构表示？问与答谢谢大家！谢谢大家！
