算法分析与的设计第一章.ppt

算法分析与设计 授课教师：彭 卫 邮箱：pw7@163.com 欢迎大家一起讨论！！！ 参考书目 1. Anany Levitin (美) ,潘彦译. 算法设计与分析基础. 清华大学出版社,2004 2. 吴伟,方世昌等译. 算法设计技巧与分析. 电子工业出版社 3. D.E.Knuth,管记文译. 计算机程序设计技巧. 国防工业出版社.1978(第一卷),1982(第二卷) 4. 卢开澄. 计算机算法导引. 清华大学出版社,2000 5. 邹海明,余祥宣. 计算机算法基础. 华中理工大学出版社,1996 6. Jeffery J. McConell. Analysis of Algorithms: an active learning approach. 高等教育出版社,2003 7. T.H.Cormen C.E.Leiserson R.L.Rivest and C.Stein. Introduction to Algorithms, 2nd edition. 高等教育出版社,2002 8. 王晓东. 算法设计与分析. ? 清华大学出版社,2003? 9 徐士良. C常用算法程序集.? 清华大学出版社,1998 10. 王晓东. 计算机算法设计与分析. 电子工业出版社,2001 本课程所需知识 数据结构； 一门计算机语言C, Basic, Fortran,汇编,Delphi等； 一些高等数学方面的知识； 计算机基础知识； 冷静的头脑+热诚的心； 何谓算法 算法的定义 算法的概念 几个容易造成含糊的定义 算法； 计算机语言； 数据结构：计算机中存储、组织数据的方式，数据的自然本性决定了其数据结构； 一种有趣的说法，即： 程序：算法+数据结构； 事实上，有一本书就被称之为《程序=算法+数据结构》。 《算法设计与分析》课程目的 1.了解计算领域中不同问题的一系列标准算法； 2.学会分析各种算法的效率； 3.学会设计新算法； 算法的特点 1. 算法的每一个步骤都必须清晰、明确； 2.同一个问题，可能有几种不同的算法来解决； 3. 针对同一个问题的不同算法，也许会出现不同的计算效率； 什么是计算计算效率？ 一个例子 如何求出两个整数：m和n的最大公约数 （什么是公约数？什么是最大公约数？） 公约数：能同时被整除的称为公约数； 例如：16/4=8，则4为10和22的公约数 24/4=6， 10能被整除的整数有： 22能被整除的整数有： 10和22的公约数有：？ 最大公约数是：？ 如何使用计算机程序来计算最大公约数？ 一种最笨的、最简单、也是最可靠的计算最大公约数算法 算法的结构化表示（以便获得n和m的最大公约数）： 1.算出n的全部可被整除数； 2.算出m的全部可被整除数； 3.找出1，2步骤中的相同值； 4.找出3步骤中的最大值； 1. 知道如何编程实现吗？ 2. 伪代码表示？ 次笨的方法 1.求出n和m的最小值； 2.分别使用n和m来除以这个最小值； 3.若都能同时除尽，则可获得最大公约数，若不能，将这个数减1后再来除，直至同时除尽为止，即可找到最大公约数。 例如，求16和24的最大公约数； 1. 求出16和24中的最小值：16； 2. 则24/16,16/16,能否同时除尽？那么，16减1后再除，即24/15，15/15，能否除尽？还不行吗？那就再减1，…当减到8时，24/8，16/8，你能想到16和24的最大公约数是多少吗？ 次笨方法的结构化说明 1. 求出n和m的最小值，t=min(n,m); 2. 检查t值，如果t=0，则发出错误信息；如 ，则进行下一步； 3. 计算n/t，如为整数，可表示为mod(n/t)=0，则转向4；否则，转向5； 4. 如果mod(m/t)=0，则停止并返回值t；否则，转向5； 5. t=t-1并转向2； 要是同学们没有问题，则谈谈伪代码的时候终于来到了！ 伪代码 官方的说法：伪代码是一种算法描述语言。使用伪代码的目的是为了使被描述的算法可以容易地以任何一种编程语言（Pascal，C，Java，etc）实现。因此，伪代码必须结构清晰、代码简单、可读性好，并且类似自然语言。 介于自然语言与编程语言之间。 我的说法：就是为了让大家有一个共同语言，作用类似于世界语，以便让我们未来的程序师们可以互相理解； 幸运的是，伪代码并没有统一的规范，也即是可以按照个人的意思来编制。 可悲的例子，可恨的计算机语言们！（一个判断例子） IF (p=2) OR (j3) THEN ERROR; ELSE P=3;