《(精品)ch1算法概述(2).ppt》由会员分享,可在线阅读,更多相关《(精品)ch1算法概述(2).ppt(40页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、算法设计与分析Design and Analysis to Algorithms王 璐dqx_中原工学院计算机学院2010-91关于本课程算法是计算机学科中最具有方法论性质的核心概念,被誉为计算机学科的灵魂。课程目的:计算机算法设计与分析导引以算法设计为主,介绍算法设计的主要方法和基本思想;并简要介绍算法分析概念不是程序设计课,也不是数学课授课形式:上课(5%)+作业(10%)+实验(10%)+期末考试75%教材算法设计与分析 吕国英主编 清华大学出版社参考书算法设计与分析 王晓东编 电子工业出版社学时:38(理教)+6(实验)学时2与数据结构的区别:考虑问题的角度:数据结构关心不同的数据结构
2、在解题中的作用和效率;算法关心解题方法思路及不同设计技术的适用性和效率。考虑问题的高度:数据结构关心的是解具体问题,算法不仅如此,它提供一种解决问题的通用方法。与其他课程的关系高级程序设计语言(高级程序设计语言(C,C+)数据结构数据结构 算法设计算法设计与与分析分析 3 广播操图解是广播操的算法;菜谱是做菜的算法;歌谱是一首歌曲的算法;空调说明书是空调使用的算法等.算法是什么?4例例1 1:给出求:给出求1+2+3+4+51+2+3+4+5的一个算法。的一个算法。算法1 按照逐一相加的程序进行。第一步 计算1+2,得到3;第二步 将第一步中的运算结果3与3相加,得到6;第三步 将第二步中的运
3、算结果6与4相加,得到10;第四步 将第三步中的运算结果10与5相加,得到15。5算法2 可以运用公式直接计算;第一步 取n=5;第二步 计算第三步 输出运算结果。6例2:三个牧师和三个野人过河,只有一条能装下两人的船,在河的任一边或者船上,若野人人数大于牧师人数,那么牧师就会有被吃掉的危险。你能不能找出一种安全的渡河算法呢?第一步 两个野人先过河,一个野人回来;第二步 再两个野人过河,一个野人回来;第三步 两个牧师过河,一个野人和一个牧师回来;第四步 两个牧师过河,一个野人回来;第五步 两个野人过河,一个野人回来;第六步 两个野人过河。7算法算法广义:广义:在解决问题时,按照某种机械步骤一定
4、可以得到问题结果(有解时给出问题的解,无解时给出无解的结论)的处理过程。狭义:狭义:用计算机解决问题的方法和步骤的描述。8本课程为计算机科学与技术学科本科生的专业课。How to study?通过该课程的学习,对计算机常用算法有一个全 盘的了解,掌握通用算法的一般设计方法。学会对算法的时间和空间复杂性进行分析,掌握提高算法效率的方法和途径。(评价有效算法)9 一般计算机对现实问题无能为力,需要人类对问题抽象化、形式化后才能去机械的执行。学习目标:学习目标:“用计算机求解问题用计算机求解问题”问题分析:准确、完整地理解和描述问题 数学模型建立算法设计与选择:创造性的活动算法表示:思想的表示形式算
5、法分析:算法时空特性分析算法实现程序调试:测试结果整理文档编制10证明正确性分析算法设计程序理解问题精确解或近似解选择数据结构算法设计策略设计算法问题求解(Problem Solving)的过程11第1章 算法概述121.1 算法 算法的定义是由若干条指令组成的有穷序列,且满足下述性质。输入:有零个或多个外部量作为算法的输入。输出:算法产生至少一个量作为输出。确定性:组成算法的每条指令清晰、无歧义。可行性:能够由计算机实现有限性:一个算法在执行有限步之后必须结束,即所包含的计算步骤是有限的。程序(计算过程),例如:操作系统通俗的讲,算法是指解决问题的一种方法或过程。例:四则运算13求两个正整数
6、的最大公约数。求两个正整数的最大公约数。例例1.11.1(1)计算gcd(m,n)的短除(枚举)法算法设计:计算机没有“宏观”能力来“看出”公约数,但通过“枚举尝试”(逐个尝试)就可以“试出”m,n有哪些是公约数,并将这些公约数“累乘”,就能得到最大公约数。14算法描述如下:main()int m,n,d,i;input(m,n);d=1;/变量d是为累乘因数而设置的;for(i=2;i=m and i=n;i+)/“枚举”可能的公约数 while (m mod i=0 and n mod i=0)/“试”i是否为公约数 d=d*i;m=m/i;n=n/i;print(d,“is maxima
7、l common divisor”);为什么用为什么用while?15(2)计算gcd(m,n)的连续整数检测(枚举)算法第一步:将minm,n的值赋给d。第二步:m除以d,若余数为0,进入第三步;否则第四步。第三步:n除以d,若余数为0,返回d值(结果);否则第四步。第四步:把d的值减1,返回第二步。例如:对于60和24这两个数,该算法会先尝试24,然后是23,这样一直尝试到12,算法结束。16(3)欧几里德算法gcd(m,n)=gcd(n,m mod n)gcd(24,18)=gcd(18,6)=gcd(6,0)=6输入 正整数m和n 输出 m和n的最大公因子1.如果n=0,计算停止返回m
8、,m即为结果;否则继续2。2.记r为m除以n的余数,即r=m mod n。3.把n赋值给m,把r赋值给n,继续1。伪代码如下:Euclid(m,n)while n 0 r=m n;m=n;n=r;Beginn=0?r=m mod nm=nn=rendNY同一个算法有不同的表达方式!17算法设计需要考虑的质量指标正确性在给定有效输入后,算法经过有限时间的计算并产生正确的答案,就称算法是正确的。可读性健壮性(robustness)容错性,即在输入错误、磁盘故障、网络过载或有意攻击等异常和危险情况下,能否不死机、不崩溃 高效率与低存储量需求18 下面是初学者易发生的问题,提前指出以引起注意:通过输入
9、语句增加算法的通用性。易忽略细节造成“死循环”。出现语序方面的错误,特别是双重循环中指令常有嵌套错误。注意学习和总结。用大脑“运行”算法是学习算法很好的方法。解题时要学会择优。简单说择优要考虑四个方面:可读性、可修改性、时间效率和空间效率。19从算法到实现-算法基本技巧举例a.算术运算的妙用例1.2 开灯问题b.巧用“标志量”例1.3 判定输入n个数据互不相等c.信息数字化例1.4 警察抓小偷20a.算术运算的妙用-例1.2开灯问题算术运算:加减乘除。例1.2 开灯问题从前,有从1到n依次编号的n个同学和n 盏灯。1号同学将所有的灯都关掉;2号同学将编号为2的倍数的灯都打开;3号同学则将编号为
10、3的倍数的灯作相反处理(该号灯如打开的,则关掉;如关闭的,则打开);以后的同学都将自己编号的倍数的灯,作相反处理。问:经n个同学操作后,哪些灯是打开的?21问题分析:1)用数组表示某种状态,这里定义有n个元素的a数组,它的每个下标变量ai视为一灯,i表示其编号。ai=1表示灯处于打开状态,ai=0表示灯处于关闭状态。此用法也称为此用法也称为“乒乓开关乒乓开关”。简化逻辑表达式、减少条件判简化逻辑表达式、减少条件判断断2)实现将第i 灯作相反处理的操作:条件语句if表示:if ai =1 ai=0;if ai =0 ai=1;通过算术运算更简练、逼真:ai=1-ai。a.算术运算的妙用-例1.2
11、问题分析/建模22a.算术运算的妙用-例1.2-算法设计建立一个充分大的数组int a1000;输入n的数值;关闭所有灯,即a1an置为0;第2个学生-第n个学生(学生i)进行操作:操作对象:数组a,灯编号含因数i(即i的倍数),即ai*k;操作:ai*k=1-ai*k;输出灯的开关状态。23void main()int n,a1000,i,k;scanf(%d,&n);for(i=1;i=n;i+)ai=0;for(i=2;i=n;i+)k=1;/倍数 while(i*k=n)ai*k=1-ai*k;k=k+1;for(i=1;i第n-1个(每个元素i)操作与第i+1第n元素(每个元素j)比
12、较,若相等则标志量置0,循环中断;若flag=1,则无重复;反之,有重复。b 巧用“标志量”-例1.3-算法设计26b 巧用“标志量”-例1.3 实现void main()int a100,i,j,flag,n;scanf(%d,&n);for(i=1;i=n;i=i+1)scanf(%d,&ai);flag=1;for(i=1;i=n-1;i=i+1)for(j=i+1;j=n;j=j+1)if(ai=aj)flag=0;break;if(flag=1)printf(No repeatn);else printf(Repeatn);27c 信息数字化-例1.4 警察抓小偷一些表面上看是非数值
13、的问题,但经过进行数字化后,就可方便进行算法设计。例1.5 警察抓小偷警察局抓了a,b,c,d四名偷窃嫌疑犯,其中只有一人是小偷。审问中 a说:“我不是小偷。”b说:“c是小偷。”c说:“小偷肯定是d。”d说:“c在冤枉人。”现在已经知道四个人中三人说的是真话,一人说的是假话,问到底谁是小偷?28c 信息数字化-例1.4-问题分析问题分析:可通过循环,每次假设一名嫌疑犯为小偷,代入问题系统,检验是否只有一句假话。这种让所有可能解都进行检验,以求得真解的方法称为“枚举尝试法”,也是“蛮力法”、“暴力法”。为方便设计程序,将a,b,c,d将四个人进行编号,号码分别为1,2,3,4。29c 信息数字
14、化-例1.4-算法设计算法设计:用变量x存放小偷的编号,则x的取值范围从1取到4,就假设了他们中的某人是小偷的所有情况。四个人所说的话就可以分别写成:a说的话:x1b说的话:x=3c说的话:x=4d说的话:x4或not(x=4)注意:在x的枚举过程中,当这四个逻辑式的值相加等于3时,即表示“四个人中三人说的是真话,一人说的是假话”。if(x!=1)+(x=3)+(x=4)+(x!=4)=3)30c 信息数字化-例1.4-实现#include stdafx.hvoid main()int x;for(x=1;x=4;x=x+1)if(x!=1)+(x=3)+(x=4)+(x!=4)=3)prin
15、tf(%c is a thief,char(64+x);31算法=控制结构+原操作表示算法的语言主要有:自然语言流程图盒图PAD图伪代码计算机程序设计语言1.2 算法描述 321自然语言自然语言是人们日常所用的语言。自然语言描述算法的缺点:自然语言的歧义性易导致算法执行的不确定性。自然语言语句一般太长导致描述的算法太长。当算法中循环和分支较多时就很难清晰表示。不便翻译成程序设计语言理解的语言。33 2 2流程图流程图 主要缺点:使算法设计人员过早考虑算法控制流程,而不去考虑全局结构,不利于逐步求精。随意性太强,结构化不明显。不易表示数据结构。层次感不明显。NYr等于等于0?输出输出n的值的值输
16、入正整数输入正整数m和和n开始开始结束结束m n;n rrm被被n除的余数除的余数rm被被n除的余数除的余数343盒图(NS流程图)(1)盒图具有以下优点:层次感强、嵌套明确。支持自顶向下、逐步求精。容易转换成高级语言源算法。(2)主要缺点:不易扩充和修改,不易描述大型复杂算法。输入正整数输入正整数m和和n rm被被n除的余数除的余数 m n;n rrm被被n除的余数除的余数 当当r不等于不等于 0输出输出n的值的值 35 PAD图的主要优点:设计出来的算法必是结构化的。PAD图描绘的算法结构清晰。用PAD图表现的算法逻辑,易读、易懂、易记。容易用软件工具自动将PAD图转换成高级语言源算法。既
17、可用于表示算法逻辑,也可用于描绘数据结构。支持自顶向下、逐步求精。缺点:由于是图形符号书写、编辑、录入不方便。4 4 PADPAD图图 问题分析图(Problem Analysis Diagram,简称PAD)表示的算法是一个二维树形结构图,层次感强、嵌套明确且有明确的控制流程。36例:问题分析图实例问题分析图实例375伪代码 伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法的工具。它不用图形符号,因此书写方便,格式紧凑,易于理解,便于用计算机程序设计语言实现。如:类SPARKS/类C/类C386程序设计语言的缺点:算法的基本逻辑流程难于遵循。与自然语言一样,程序设计语言也是基于串行的,当算法的逻辑流程较为复杂时这个问题就变得更加严重。特定程序设计语言编写的算法限制了与他人的交流,不利于问题的解决。要花费大量的时间去熟悉和掌握某种特定的程序设计语言。要求描述计算步骤的细节而忽视算法的本质。需要考虑语法细节,而扰乱算法设计的思路。考虑到程序设计语言不断更新,不适于描述算法。算法设计一般不用程序设计语言直接描述。39小结什么是算法;算法特性;问题求解的步骤及算法在其中的重要地位;算法设计基本技巧;算法描述40
限制150内