DJ8--算法与程序设计-v1.ppt

大学计算机大学计算机第2页大学计算机基础大学计算机基础第一章基于计算机的问题求解第二章计算机信息数字化基础第三章计算机的工作原理与硬件体系结构第四章计算机软件平台第五章计算机网络平台第六章数据处理与数据库第七章计算与计算学科第八章算法与程序设计第九章实用软件第十章计算机科学前沿技术第3页第八章算法与程序设计问题导入问题导入: :奥巴马关于“100 万个 32位整数排序”问题的回答。 2008 年奥巴马当选美国总统后访问谷歌总部,: “获得总统这份工作很难,获得谷歌的工作也很难。为检验奥巴马的资格,如果为 100 万个 32位整数排序,最有效的办法是什么? ”奥巴马答: “总之,冒泡排序是错的。”第4页 算法 典型问题的算法设计 数据结构 程序设计第8章算法与程序设计第八章算法与程序设计第5页 算法 算法的定义“一个算法,就是一个有穷规则的集合,其中之规则规定了一个解决某一特定类型的问题的运算序列。”——当代著名计算机科学家 《 THE ART PUTER PROGRAMMING 》求解问题的分步骤方法输入数据输出结果算法非正式定义示意图?简单地说, 算法就是解决问题的有限步骤。第6页 算法的定义例 8-1 以黑蓝两色墨水交换为例问题描述:有黑和蓝两个墨水瓶,因错把黑墨水装在了蓝瓶子里,而蓝墨水错装在了黑瓶子里,要求将其互换。算法分析:因为两个瓶子的墨水不能直接交换,所以引入第三个墨水瓶。如果第三个墨水瓶为白色,其交换步骤如下?将黑瓶中的蓝墨水装入白瓶中; ?将蓝瓶中的黑墨水装入黑瓶中; ?将白瓶中的蓝墨水装入蓝瓶中; ?交换结束。 算法第7页 算法的定义?算法分两大类:数值运算算法非数值运算算法?数值运算是指对问题求数值解·如:多项式插值、微分方程求解、函数的定积分求解、上述的队列算法等,都属于数值运算范围。?非数值运算包括非常广泛的领域·如:资料检索、事务管理、数据处理等,上述的“黑蓝两色墨水交换”也是非数值运算算法。 算法第8页 算法的基本特征?算法具有以下基本特征: ?有穷性:一个算法必须在执行有限个操作步骤后终止?确定性:算法中每一步的含义必须是确切的,不可出现任何二义性?有效性:算法中的每一步操作都应该能有效执行,一个不可执行的操作是无效的?有零个或多个输入:这里的输入是指在算法开始之前所需要的初始数据,输入的多少取决于特定的问题?有一个或多个输出:所谓输出是指与输入有某种特定关系的量,在一个完整的算法中至少会有一个输出。 算法第9页 算法的表示方法 8-2 求解 sum=1+2+3+4+5 ……+( n-1 ) +n 算法用伪代码表示算法开始; 输入 n 的值; i ← 1; sum ← 0; 循环开始 i<=n { sum ← sum + i ; i ← i + 1 ;}循环结束输出 sum 的值; 算法结束; 算法第10页起止框判断框处理框输入/输出框注释框流向线连接点 算法的表示方法 算法