计算机应用基础——第9章 程序设计基础.ppt

《Web编程技术》 《计算机应用基础》教案 江西财经大学信息管理学院 tj_jiang@163.com 第9章 程序设计基础 程序是指挥计算机工作的“指令集”。 程序＝算法+数据结构 算法是处理问题的方法和策略，策略的优劣事关解决问题的效率。 数据结构是用来描述问题的数学模型，是算法设计的基础。 程序设计基础 算法与程序设计概述 数据结构 常用查找与排序方法 算法与程序设计概述 程序 在现实生活中，程序的直观特征是按事先安排的步骤，一步步完成一系列动作，这种对活动过程的步骤描述就是一个“程序”。 计算机程序就是要由计算机进行解释和执行的程序。它表示的是计算机处理事务的时间顺序和处理问题的步骤。组成计算机程序的基本单位一般称为指令，因此简单的说，程序就是事先编制好的具有特定功能的指令序列。 算法与程序设计概述 程序设计 对于初学者来说，往往把程序设计简单地理解为只是编写一个程序，这是不全面的。使用计算机解决实际问题，通常是先要对问题进行分析并建立数学模型，然后考虑数据的组织方式和算法，并用某一种程序设计语言编写程序最后调试程序，使之运行后能产生预期的结果。这个过程称为程序设计。 “公式” 程序设计=计算机编程语言+数据结构+算法 说明：程序设计是高强度的脑力劳动，实践 性极强，不是听会的，也不是看会的，而是练 会的，一定要上机动手编程。 算法与程序设计概述 算法 算法是程序的灵魂，程序是用计算机语言对算法的一种实现，不管采用何种计算机语言来进行程序设计，也不管计算机语言如何发展，用它来编制程序，实现问题的求解都依赖于某一特定的算法。 算法与算法复杂度 算法 一个算法必须满足以下五个重要特性： 有穷性：对于任意一组合法输入值，在执行有 穷步骤之后一定能结束，即：算法中的每个步骤 都能在有限时间内完成。 确定性：对于每种情况下所应执行的操作，在 算法中都有确切的规定，使算法的执行者或阅读 者都能明确其含义及如何执行。并且在任何条件 下，算法都只有一条执行路径。 算法与算法复杂度 算法 有效性：算法中描述的每一步操作都应该能有效地执行，都可以通过已经实现的基本操作，在运算有限次后得到确定的结果。 有输入：作为算法加工对象的量值，通常体现为算法中的一组变量。有些输入量需要在算法执行过程中输入，而有的算法表面上可以没有输入，实际上已被嵌入算法之中。 有输出：它是一组与“输入”有确定关系的量值是算法进行信息加工后得到的结果。 算法与算法复杂度 算法 为解决同一个问题，有多种不同的方法和步 骤，即多个算法。例如，求1+2+…+100的结果， 有人是先求1+2，再把和加上3，再加4，……，一 直加到100；而高斯采取的办法是，先将这100个 数分为若干个组：(100)、(1, 99)、(2, 98)、……、 (49, 51)、(50)，前面50个组每个组的和都是100， 因此结果为50*100+50。当然还有其他的方法。 算法的评价 解决同一个问题的算法可以有多种，不同人员的设计不尽相同，其效率也存在差别，一个不好算法可能导致程序要运行几天、几个月甚至几年，一个好的算法可能只要几分种、几秒钟就可以完成。 在设计算法时，应当遵循以下原则: 首先是保证算法的正确性 其次要具有良好的可读性 第三，算法应具有健壮性 另外，算法执行时间的高效性和努力降低对存储空间的需求也是算法设计追求的目标。 算法与算法复杂度 算法 一般而言，方法有优劣之分，算法的优劣可 以有多种不同的评价标准。例如，可以从时间上 来评价，也可以从空间上来评价，或者从其他的 角度来评价。人们当然愿意选择较优的算法。因 此，为了有效解题，不仅需要保证算法的正确 性，还要考虑算法的质量，选择合适的算法。 　 算法与算法复杂度 算法复杂度－－时间复杂度、空间复杂度 　 从时间上来评价算法的优劣，即执行时间短的 算法效率高,用算法的时间复杂度来度量。所谓算 法的时间复杂度是指执行算法所需要的计算工作 量。可以用算法在执行过程中所需基本运算的执 行次数来度量算法的工作量。 　从空间上来评价即为算法所需辅助空间越少越 好,用算法的空间复杂度来度量。一个算法的空间 复杂度，一般是指执行这个算法所需要的内存空 间。一个算法所占用的存储空间包括算法程序所 占的空间、输入的初始数据所占的存储空间以及 算法执行过程中所需要的额外空间。 算法的表示方法 算法的描述 用自然语言表示 用传统(标准)流程图表示 用N-S盒图表示(取消流程线) 用伪代码表示。 算法的表示方法 算法的描