2022年2022年计算机软件课件 2.pdf

《2022年2022年计算机软件课件 2.pdf》由会员分享，可在线阅读，更多相关《2022年2022年计算机软件课件 2.pdf（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、本文由该如何释怀贡献。新世纪计算机基础教育丛书主编谭浩强计算机软件技术基础课程介绍课时安排：课时安排：理论：理论：实验：实验：课程设计：课程设计：上课要求：需要同学在青海大学“教育在线”上课要求：需要同学在青海大学“教育在线”选课网址：网址：老师的联系方式：老师的联系方式：办公地点：办公地点：现教中心二楼计算机教研室：第章算法第章算章法算法的基本概念算法描述语言算法设计基本方法算法的复杂度分析第章算法算法的基本概念算法的基本特征算法是指解题方案的准确而完整的描述。算法是指解题方案的准确而完整的描述。能行性能行性（）能行性（）算法的能行性包括以下两个方面：算法的能行性包括以下两个方面：算法中的每

2、一个步骤必须能够实现。（）算法中的每一个步骤必须能够实现。算法执行的结果要能够达到预期的目的。（）算法执行的结果要能够达到预期的目的。，（）（）第章算法确定性（）确定性（）确定性算法的确定性，算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。也不允许有多义性。有穷性有穷性（）有穷性（）算法的有穷性，算法的有穷性，是指算法必须能在有限的时间内做完，内做完，即算法必须能在执行有限个步骤之后终止。终止。拥有足够的情报拥有足够的情报一个算法是否有效，一个算法是否有效，还取决于为算法所提供的情报是否足够。通常，报

3、是否足够。通常，算法中的各种运算总是要施加到各个运算对象上，施加到各个运算对象上，而这些运算对象又可能能具有某种初始状态，能能具有某种初始状态，这是算法执行的起点或是依据。或是依据。第章算法因此，因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的输出。数据有关，不同的输入将会有不同的输出。一般来说，当算法拥有足够的情报时，般来说，当算法拥有足够的情报时，此算法才是有效的，而当提供的情报不够时，是有效的，而当提供的情报不够时，算法并不有效。有效。综上所述，综上所述，算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，规则，并且每一个规则都是有效的，且是明确此顺序将

4、在有限的次数下终止。的，此顺序将在有限的次数下终止。第章算法算法的基本要素一个算法通常由两种基本要素组成：（）算法中对数据的运算和操作算术运算逻辑运算关系运算数据传输名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 7 页 - - - - - - - - - （）算法的控制结构一个算法的功能不仅取决于所选用的操作，一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。之间的执行顺序有关。算法中各操作之间的执行顺序称为控制结构。一个算法一般都可以用顺序、选择

5、、制结构。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。控制结构组合而成。第章算法算法描述语言符号与表达式符号与表达式符号是以字母开头的字母和数字的有限串，符号是以字母开头的字母和数字的有限串，主要用来表示变量名、数组名等，来表示变量名、数组名等，必要时也用来表示语句标号。例如：标号。例如：有时，为了使算法更清楚，算法中的某些指令或子过有时，为了使算法更清楚，程直接用叙述的方式给出。例如：程直接用叙述的方式给出。例如：中的最大项”其中是一个数组）“设是中的最大项”（其中是一个数组）插入到之中”其中是某个表）“将插入到之中”（其中是某个表）在算法中，算术运算符沿用数学中的表示法：

6、在算法中，算术运算符沿用数学中的表示法：关系运算符用、（）关系运算符用、（）逻辑运算符用（与）、（或）、（非）逻辑运算符用（与（或（非（第章算法赋值语句赋值语句赋值语句的形式为其中为变量名或数组元素，其中为变量名或数组元素，为算术表达式或逻辑表达式。表达式。如果如果和都是变量名或数组元素，则可用记号：都是变量名或数组元素，表示将和的内容互换。表示将的内容互换。如果想将表达式的计算结果同时赋给如果想将表达式的计算结果同时赋给与，则可用记号：第章算法控制转移语句控制转移语句无条件转移语句的形式：无条件转移语句的形式：标号条件转移语句的形式：条件转移语句的形式：或第章算法循环语句循环语句语句语句功能

7、等价于如下的语句：功能等价于如下的语句：语句：第章算法语句语句功能等价于如下的语句：语句当时，功能等价于如下的语句：第章算法当时，功能等价于如下的语句：功能等价于如下的语句：语句：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 7 页 - - - - - - - - - 第章算法其它语句其它语句：用于退出某个循环，：用于退出某个循环，使控制转到包含语句的最内层的或循环后面的语句的最内层的语句的最内层的或循环后面的一个语句去执行。一个语句去执行。（或）和（或，或）（）（，）

8、语句分别用于输入和输出。语句分别用于输入和输出。语句用于结束算法的执行语句用于结束算法的执行。语句用于结束算法的执行。如果算法是在最后一行之后结束，则可以省略语在最后一行之后结束，则可以省略语句。第章算法算法设计基本方法列举法根据提出的问题，列举所有可能的情况，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要哪些是不需要的。的，哪些是不需要的。因此，列举法常用于解决“是否存在”因此，列举法常用于解决“是否存在”或有多少种可能”等类型的问题，比如，“有多少种可能”等类型的问题，比如，求解不定方程的问题。求解不定方程的问题。第章算法例如：百元买百鸡问题。例如：百元买百鸡问题。

9、设每只母鸡值设每只母鸡值元，每只公鸡值元，两只小鸡值每只公鸡值两只小鸡值现要用元钱买只鸡，设计买鸡方案。元钱买只鸡元。现要用元钱买只鸡，设计买鸡方案。假设买母鸡只，公鸡只，小鸡只。假设买母鸡公鸡小鸡第章算法（）（）（）（），总循环次数为总循环次数为第章算法算法改进）（），总循环次数为（？）第章算法（），；（；）（；）（；）（；）；（）（，）；（，）；第章算法运行结果如下：运行结果如下：第章算法归纳法归纳法的基本思想是，通过列举少量的特殊情况。归纳法的基本思想是，通过列举少量的特殊情况。经过分析。最后找出一般的关系。显然，过分析。最后找出一般的关系。显然，归纳法要比列举法更能反映问题的本质，举法

10、更能反映问题的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 7 页 - - - - - - - - - 本质，并且可以解决列举量为无限的问题。但是，限的问题。但是，从一个实际问题中总结归纳出一般的关系，并不是一件容易的事情，的关系，并不是一件容易的事情，尤其是要归纳出一个数学模型更为困难。从本质上讲。个数学模型更为困难。从本质上讲。归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。察一些简单而特殊的情况，最后总结出一般性的结论。归纳是一种抽象，即从特殊现象中

11、找出一般关系。归纳是一种抽象，即从特殊现象中找出一般关系。但由于在归纳的过程中不可能对所有的情况进行列举，由于在归纳的过程中不可能对所有的情况进行列举，因此，最后由归纳得到的结论还只是一种猜测，因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的。察而得到的猜测得不到证实或最后证明猜测是错的。也是常有的事。也是常有的事。第章算法递推所谓递推，是指从已知的初始条件出发，所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果、推出所要求的各中间结果和最后结果、其

12、中初始条件或是问题本身已经给定，始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。题的分析与化简而确定。递推本质上也属于归纳法，纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的。实际问题的分析与归纳而得到的。递推关系式往往是归纳的结果。往往是归纳的结果。递推算法在数值计算中是极为常见的。但是，中是极为常见的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。法必须要注意数值计算的稳定性问题。第章算法例第章算法第章算法？，？第章算法第章算法递归将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再问题，归结为更简单的问题，归结为更简单的问

13、题，这个过程可以一直做下去，直到最简单的问题为止。做下去，直到最简单的问题为止。第章算法例编写一个过程，对于输入的参数例编写一个过程，对于输入的参数，依次打印输出自然数到。（）非递归算法（）；（；）；（，）；，；第章算法（）递归算法（）（）（）（！）（）；（，）；，；第章算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 7 页 - - - - - - - - - 递归算法调用过程详解（）（）（）（！）（）；（，）；（）（！）（）；（，）；第章算法减半递推技术所谓“减半”

14、是指将问题的规模减半，所谓“减半”，是指将问题的规模减半，而问题的性质不变。而问题的性质不变。所谓“递推”是指重复“减半”的过程。所谓“递推”，是指重复“减半”的过程。第章算法例二分法求方程实根的减半递推过程：例二分法求方程实根的减半递推过程：首先取给定区间的中点（）首先取给定区间的中点（）。然后判断（）是否为（）是否为然后判断（）是否为。（）则说明即为所求的根，若（），则说明即为所求的根，求解过程结束；如果（）则根据以下原则将原区间减半：（）如果（），则根据以下原则将原区间减半：（）（）则取原区间的前半部分；若（）（），则取原区间的前半部分；（）（）则取原区间的后半部分。若（）（），则取原区

15、间的后半部分。最后判断减半后的区间长度是否已经很小：最后判断减半后的区间长度是否已经很小：则过程结束，（）若，则过程结束，取（）为根的近似值；的近似值；，则重复上述的减半过程。若，则重复上述的减半过程。第章算法（，（，）（）（）（）（）；（）（）；（）（）（）；第章算法”（，（，），（）（）；，（）（）；，；（）（）；（）（）；（）（）（）（）（）；（）；（）（）；（）；（）（）；（）；（）（）；（）；（）；第章算法回溯法通过对问题的分析，找出一个解决问题通过对问题的分析，的线索，然后沿着这个线索逐步试探，的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，对于每一步的试探，若试探

16、成功，就得到问题的解，若试探失败，就逐步回退，到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。换别的路线再进行试探。第章算法算法的复杂度分析算法的时间复杂度算法的空间复杂度第章算法算法的时间复杂度指执行算法所需要的计算工作量指执行算法所需要的计算工作量用算法在执名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 7 页 - - - - - - - - - 行过程中所需基本运算的执行次数来度量算法的工作量。算法的工作量。算法的工作量用算法所执行的基本运算次数来度量而算

17、法所执行的基本运算次数是问题规模的函数。题规模的函数。算法的工作量算法的工作量（）其中是问题的规模。其中是问题的规模。第章算法平均性态平均性态（）平均性态指用各种特定的数如下的基本运算次数的带权平均值来度量算法的工作量。次数的带权平均值来度量算法的工作量。（）（）（）：表示算法规模为是，算法执行时所有可能表示算法规模为是输入的集合。输入的集合。（）：在输入为时所执行的基本运算次数。在输入为时所执行的基本运算次数时所执行的基本运算次数。（）：是出现的概率。出现的概率。第章算法最坏情况复杂性（）指在规模为指在规模为时，算法所执行的基本运算的最大次数。算法所执行的基本运算的最大次数。（）（）第章算法

18、例采用顺序搜索法，在长度为的一维数组中查找为采用顺序搜索法，在长度为的一维数组中查找为的元素。即从数组的第一个元素开始，的元素。即从数组的第一个元素开始，逐个与被查进行比较。值进行比较。基本运算为与数组元素的比较。基本运算为与数组元素的比较。第章算法平均性态分析第章算法最坏情况分析（）（）第章算法算法的空间复杂度算法的空间复杂度一般是指执行算法所需要的内存空间。的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。算法执行过程中所需要的额外空间。其中额外空间包括算法程序执行过程中的工作单位以及某种数据结构所需要的附

19、加存储空间。数据结构所需要的附加存储空间。如果额外空间量相对于问题规模来说是常数，量相对于问题规模来说是常数，则称该算法是原）工作的。地（）工作的。第章算法实验一在环境中实现一个简单算法实验目的：实验目的：编写一个简单的算法解决一个具体的问题并在编写一个简单的算法解决一个具体的问题并在环境中上机实现。对已学的语言设计知识作一回顾。境中上机实现。对已学的语言设计知识作一回顾。实验内容：实验内容：、给定三个整数、给定三个整数，试写出寻找其中数的一，个算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - -

20、 - - 第 6 页，共 7 页 - - - - - - - - - 。并分析在平均情况下和最坏情况下，个算法。并分析在平均情况下和最坏情况下，你的算法分别要做多少次比较？法分别要做多少次比较？第章算法实验报告格式要求：（可打印也可手写）：（可打印也可手写实验报告格式要求：（可打印也可手写）实验人：实验人：班级姓名学号实验名称：实验名称：实验地点和时间：实验地点和时间：实验环境：实验环境：实验内容：实验内容：自己编写的源程序代码。适当加以注释！自己编写的源程序代码。适当加以注释！实验结果（必须重要的评分标准）必须，实验结果必须，重要的评分标准实际上机过程中输入的数据和最终得到的数据。实际上机过程中输入的数据和最终得到的数据。碰到的问题（错误），如何改正。），如何改正碰到的问题（错误），如何改正。第章算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 7 页 - - - - - - - - -