大学计算机算法基础PPT课件.ppt

《大学计算机算法基础PPT课件.ppt》由会员分享，可在线阅读，更多相关《大学计算机算法基础PPT课件.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于大学计算机算法基础第一张，PPT共二十五页，创作于2022年6月2022/10/2024.1 算法基本概念1.算法的概念为解决一个问题而采取的方法和步骤，称为算法。用计算机来解决问题的方法和步骤，称为计算机算法。分为数值运算算法和非数值运算算法。第二张，PPT共二十五页，创作于2022年6月4.2 算法的组成要素一个算法含有两大要素：操作步骤操作步骤：对于计算机算法而言，包括组成算法的各条指令，也就是对数据的运算和操作。控制结构：控制结构：控制算法中各操作步骤地执行顺序。通常有三种结构：顺序结构选择结构循环结构第三张，PPT共二十五页，创作于2022年6月2022/10/204控制结构及算

2、法举例1、顺序结构：例1：求圆的面积的算法设r表示圆的半径，s表示圆的面积步骤1：输入半径r的值步骤2：s=3.14 r r步骤3：输出s的值多个步骤由上到下依次执行，顺序不能打乱，称为顺序结构多个步骤由上到下依次执行，顺序不能打乱，称为顺序结构第四张，PPT共二十五页，创作于2022年6月2、选择结构：例2：求两个整数a和b中的大者的算法：输入a、b的值：如果ab，则执行S3；否则转去执行S4：输出a的值，结束：输出b的值，结束其中，和根据条件只能执行一个，称为选择结构其中，和根据条件只能执行一个，称为选择结构第五张，PPT共二十五页，创作于2022年6月3、循环结构例3：求出50！的算法设

3、t为被乘数，i为乘数s1：使t=1s2：使i=2s3：tits4：i+1 is5：转去执行s3s6:输出t的值当当i50i50时，时，为下一次乘法做准备为下一次乘法做准备重复执行重复执行多次，多次，循环结构循环结构第六张，PPT共二十五页，创作于2022年6月2022/10/207顺序结构、选择结构、循环结构是表示一个算法的基本结构。由以上3种基本结构组成的算法，称为“结构化”的算法，可以解决任何复杂的问题。第七张，PPT共二十五页，创作于2022年6月4.3 算法的基本特征1）有穷性 算法中的步骤是有限的2）可行性 算法中的每一个步骤必须是可执行的3）确定性 算法中的每一个步骤必须是含义确切

4、的4）有零个或多个输入5）有一个或多个输出第八张，PPT共二十五页，创作于2022年6月4.3 算法的表示方法自然语言流程图伪代码计算机编程语言第九张，PPT共二十五页，创作于2022年6月算法的流程图表示法传统流程图第十张，PPT共二十五页，创作于2022年6月顺序结构、选择结构和循环结构流程图第十一张，PPT共二十五页，创作于2022年6月2022/10/2012例如：50！的流程图开始开始t=1i=2t=tii=i+1i=50输出输出t结束结束YN第十二张，PPT共二十五页，创作于2022年6月N-SN-S图：图：三种控制结构的三种控制结构的N-S图图第十三张，PPT共二十五页，创作于2

5、022年6月1=t2=iit=ti+1=i直到直到i50输出结果输出结果50！的N-S图第十四张，PPT共二十五页，创作于2022年6月2022/10/2015算法的伪代码表示法伪代码描述50！：1 t1 t2 i2 iwhile i=50while i=50t*i t i+1 i t*i t i+1 i print tprint t 用介于自然语言和计算机语言之间的文字和符号来描述算法第十五张，PPT共二十五页，创作于2022年6月算法的计算机语言表示法计算机语言（C语言）描述50！：#include#include void main()void main()double t,i;doub

6、le t,i;t=1;i=2;t=1;i=2;while(i=50)while(i=50)t=t*i;t=t*i;i=i+1;i=i+1;printf(“%.0f”,t);printf(“%.0f”,t);必须严格遵守计算机语言的语法规则第十六张，PPT共二十五页，创作于2022年6月4.5 常用的算法介绍列举法：列举法：根据提出的问题，列举所有可能情况，并用问题中给定的条件检验哪些是需根据提出的问题，列举所有可能情况，并用问题中给定的条件检验哪些是需要，哪些是不需要。例如：求水仙花数。要，哪些是不需要。例如：求水仙花数。递推法：递推法：从已知的初始条件出发，逐次推出所要求的各中间结果和最后结

7、从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。果。递归法：递归法：将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过将问题逐层分解，最后归结为一些最简单的问题。这种将问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。后，再沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。回溯法：回溯法：通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步通过对问题的分析，找出一个解决问题的线索，然后沿着这个

8、线索逐步试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再逐步试探。的路线再逐步试探。第十七张，PPT共二十五页，创作于2022年6月4.6 算法的复杂度解决一个问题，可以有很多算法，如何评价一个算法的好坏？首先算法正确，具有算法的5个基本特征还需考虑：执行算法消耗的时间执行算法消耗的存储空间具有可读性，易于理解健壮性第十八张，PPT共二十五页，创作于2022年6月评价方法：事前估算事后统计评价结果：称为“算法复杂度”算法复杂度可以分为时间复杂度和空间复杂度第十九张，PPT共二十五页，创作于2022年6月2022

9、/10/20201.算法的时间复杂度通常把算法中进行简单操作的次数的多少称为算法的时间复杂度算法的时间复杂度往往是问题规模的函数，即 T(n)=O(f(n)其中，n表示问题的规模,f(n)为问题的规模函数 例如：求n的阶乘算法的时间复杂度为：T(n)=n-1 通常表示：T(n)=O(n)第二十张，PPT共二十五页，创作于2022年6月算法的时间复杂度还跟问题的输入数据有关，所以算法的时间复杂度可以用两种形式表达：平均时间复杂度最坏情况时间复杂度第二十一张，PPT共二十五页，创作于2022年6月2022/10/20大学计算机基础22平均时间复杂度平均时间复杂度能够计算出所有输入对应的算法时间复杂

10、度的平均值。若用t(x)表示输入为x时的算法时间复杂度，用E(x)表示出现输入x的数学期望，则算法平均时间复杂度A(n)可以表示为：第二十二张，PPT共二十五页，创作于2022年6月2022/10/2023最坏情况时间复杂度最坏情况时间复杂度是指在所有输入对应的算法时间复杂度中运算次数最多的时间耗费。如果W(n)表示算法最坏情况时间复杂度，则 W(n)=maxt(x)第二十三张，PPT共二十五页，创作于2022年6月2022/10/20242.算法的空间复杂度算法的空间复杂度是指执行该算法所需的内存空间，记作 S(n)=O(f(n)S(n)除了跟存储程序的指令、常数、变量和输入数据的空间大小有关外，还跟存储一些为实现计算所需信息的辅助空间的大小有关。第二十四张，PPT共二十五页，创作于2022年6月2022/10/20感感谢谢大大家家观观看看第二十五张，PPT共二十五页，创作于2022年6月