第一章算法初步课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《第一章算法初步课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第一章 算法 初步 课件
- 资源描述:
-
1、1 什么是算法 算法(algorithm)一词源于算术(algorism),算术方法的原义是一个由已知推求未知的运算过程。后来,人们把它推广到一般,指算法是在有限步骤内求解某一问题所使用的一组定义明确的规则,甚至把把进行某一工作的方法和步骤也称为算法。例如,人们在计算过程中,先乘除,后加减,从内到外去括号等规则,都是按部就班必须遵守的算法。人类最早关于算法的记录存在于在两河流域发现的公元前两三千年的泥板书上,其中的一个典型例子就是计算利息何时能够够等于本金。算法早期发展中值得一提的另一个成果应归功于古希腊的欧几里得,他提出的计算最大公约数的辗转相除法(又称欧几里得算法)至今仍在使用。欧几里得是
2、古代最有名望的学者之一,古希腊数学家,几何学的鼻祖。公元前300年左右,他所著几何原本13卷,是世界上最早公理化的数学著作。在几何原本中他充分总结了前人的生产经验和研究成果,从公理和公设出发,运用演绎法,经过逻辑推理和数学运算,创立了著名的欧几里得(简称欧氏几何)。在几何原本中,欧几里得还阐述了关于求两个整数的最大公约数的过程,这就是著名的欧几里得算法辗转相除法,其具体过程如下:设给定的两个正整数为m和n,求它们的最大公约数的步骤为:(1)以m除以n,令所得的余数为r(r必小于n);(2)若r0,则输出结果n,算法结束;否则,继续步骤(3)(3)令m=n,n=r,并返回步骤(1)继续进行。中国
3、古代数学研究中也有许多有关算法的成果。用我国传统的开方术求高次方程的近似根,是算法上的一大成就。此外,在社会上得到广泛使用的珠算口诀就可以看做是典型的算法,它把复杂的计算(例如除法)描述为一系列按口诀执行的简单的算珠拨动操作。中国古代数学以算法为主要特征,其中最具代表性的就是九章算术。九章算术是战国、秦、汉时期数学发展的总结,就其数学成就来说,堪称是世界数学名著。其内容按类分章,以数学问题的形式出现,包括分数四则运算、开平方与开立方(包括二次方程数值解法)、盈不足术、各种面积和体积公式、线性方程组解法、正负数运算的加减法则、勾股形解法(特别是勾股定理和求勾股数的方法)等。其中方程组解法和正负数
4、加减法则在世界数学发展上是遥遥领先的。就其特点来说,它形成了一个以筹算为中心,与古希腊数学完全不同的独立体系。在1114世纪约300年期间著名的数学家的著作中,如贾宪的黄帝九章算法细草,刘益的议古根源,秦九昭的数书九章,李治的测圆海镜和益古演段,杨辉的详解九章算法、日用算法和 杨辉算法中,算法的特点得到了进一步的强化和发展(其中包括发展了一套求高次方程近似根的方法。1)能行性能行性(effectiveness)算法的能行性包括两个方面:一是算法中的每算法的能行性包括两个方面:一是算法中的每一个步骤必须是一个步骤必须是能实现的能实现的。例如,在算法中,不允许。例如,在算法中,不允许出现分母为零的
5、情况;在实数范围内不能求一个负数出现分母为零的情况;在实数范围内不能求一个负数的平方根等。二是算法执行的结果要的平方根等。二是算法执行的结果要能达到预期的目能达到预期的目的的。通常,针对实际问题设计的算法,人们总是希望。通常,针对实际问题设计的算法,人们总是希望能够得到满意的结果。能够得到满意的结果。例如,某计算工具规定:大于例如,某计算工具规定:大于100的数认为是比的数认为是比1大很多,而小于大很多,而小于10的数不能认为是比的数不能认为是比1大很多;大很多;且在正常情况下出现的数或是大于且在正常情况下出现的数或是大于100,或是小于或是小于10.但指令但指令“输入一个输入一个X,若,若x
6、比比1大很多,则输大很多,则输出数字出数字1,否则输出数字,否则输出数字0”是不确定的。这是因是不确定的。这是因为,在正常的输入情况下,这一指令的执行可以为,在正常的输入情况下,这一指令的执行可以得到正确的结果,但在异常情况下(输入的得到正确的结果,但在异常情况下(输入的x在在10与与100之间),这一指令执行的结果就不确定之间),这一指令执行的结果就不确定了了 1210()121012101210()1210()1210算法的有穷性还应包括合理的执行时间的含义。如果一个算法的执行时间是有穷的,但却需要执行千万年显然这就失去了算法的实用价值。例如,克莱姆(Cramer)规则是求解线性代数方程组
7、的一种数学方法,但不能以此为算法,这是因为,虽然总可以根据克莱姆规则设计出一个计算过程用于计算所有可能出现的行列式,但这样的计算过程所需的时间实际上是不能容忍的。还例如,从理论上讲,总可以写出一个正确的弈棋程序,还例如,从理论上讲,总可以写出一个正确的弈棋程序,而且这也并不是一件很困难的工作。由于在一个棋盘上安而且这也并不是一件很困难的工作。由于在一个棋盘上安排棋子的方式总是有限的,而且,根据一定的规则在有排棋子的方式总是有限的,而且,根据一定的规则在有限次移动棋子之后比赛一定结束。因此弈棋程序可以考限次移动棋子之后比赛一定结束。因此弈棋程序可以考虑计算机每一次可能的移动,它的对手每一次可能的
8、应答,虑计算机每一次可能的移动,它的对手每一次可能的应答,以及计算机对这些移动的可能应答等等,直到每个可能的以及计算机对这些移动的可能应答等等,直到每个可能的移动停止下来为止。此外,由于计算机可以知道每次移动移动停止下来为止。此外,由于计算机可以知道每次移动的结果,因此总可以选择一种最好的移动方式。但即使如的结果,因此总可以选择一种最好的移动方式。但即使如此,这种弈棋程序还是不可能执行,因为所有这些可能移此,这种弈棋程序还是不可能执行,因为所有这些可能移动的次数太多,所要花费的时间不能容忍。由上述两个例动的次数太多,所要花费的时间不能容忍。由上述两个例子可以看出,虽然许多计算过程是有限的但仍有
9、可能无子可以看出,虽然许多计算过程是有限的但仍有可能无实用价值。实用价值。(4)算法必须拥有足够的情报算法必须拥有足够的情报 一个算法是否有效,还取决于为算法的执行所一个算法是否有效,还取决于为算法的执行所提供的情报是否足够。例如,对于指令提供的情报是否足够。例如,对于指令“如果小明是如果小明是学生,则输出字母学生,则输出字母Y,否则输出,否则输出N”。当算法执行过程。当算法执行过程中提供了小明一定不是学生的某种信息时,执行的结中提供了小明一定不是学生的某种信息时,执行的结果将输出字母果将输出字母N;当提供的只是部分学生的名单,且小;当提供的只是部分学生的名单,且小明恰在此名单之中,则执行的结
10、果将输出字母明恰在此名单之中,则执行的结果将输出字母Y。但如。但如果在提供的部分学生的名单中找不到小明的名字则果在提供的部分学生的名单中找不到小明的名字则在执行该指令时无法确定小明是否是学生。在执行该指令时无法确定小明是否是学生。狭义而言狭义而言,算法是专指用计算机解决某一算法是专指用计算机解决某一问 题 的 方 法 和 步 骤问 题 的 方 法 和 步 骤.著 名 计 算 机 科 学 家著 名 计 算 机 科 学 家D.E.Knuth在其在其计算机程序设计技巧计算机程序设计技巧一书一书中为算法所下的定义是:中为算法所下的定义是:“一个算法一个算法,就是一个就是一个有穷规则的集合有穷规则的集合
11、,其中之规则规定了一个解决某其中之规则规定了一个解决某一特定类型问题的运算系列一特定类型问题的运算系列”.1.算法的概念算法的概念复习回顾 。v用自然语言表达问题容易理解,但往往用自然语言表达问题容易理解,但往往不严格,易出现不严格,易出现“歧义性歧义性”,即对于同,即对于同一段文字,不同的人可能会有不同的理一段文字,不同的人可能会有不同的理解。例如请同学们理解解。例如请同学们理解“这个人连老张这个人连老张也不认识。也不认识。”这句话的含义。这句话的含义。算法的描述:自然语言算法的描述:自然语言新课引入为了使算法的程序或步骤表达得更为直观为了使算法的程序或步骤表达得更为直观,且不且不容易出现歧
12、异,我们更经常地用图形方式来表容易出现歧异,我们更经常地用图形方式来表达它达它.例如上一节例如上一节“例例1.任意给定一个大于任意给定一个大于1 1的整的整数数n,试设计一个程序或步骤对试设计一个程序或步骤对n是否为质数做是否为质数做出判定出判定”的算法可以用以下形式来表达的算法可以用以下形式来表达.开始开始输入输入ni=2i=i+1in或或r=0?n不是质数不是质数结束结束r=0?1否否是是求求n除以除以i的余数的余数1n是质数是质数是是否否这样的图我们称为程序框图这样的图我们称为程序框图i=i+1in或或r=0?否否是是求求n除以除以i的余数的余数输入输入ni=2n不是质数不是质数r=0?
13、n是质数是质数是是否否 尽管不同的算法千差万别尽管不同的算法千差万别,但它们都是由但它们都是由三种基本的逻辑结构构成的三种基本的逻辑结构构成的,这三种逻辑结构这三种逻辑结构就是就是顺序结构、选择结构、循环结构顺序结构、选择结构、循环结构.下面分下面分别介绍这三种结构别介绍这三种结构 三种不同的逻辑结构三种不同的逻辑结构.程序框图又称流程图程序框图又称流程图,是一种用规定的图是一种用规定的图形、指向线及文字说明来准确、直观地表示算形、指向线及文字说明来准确、直观地表示算法的图形法的图形.讲授新课1.程序框图的概念程序框图的概念2.常见的程序框图常见的程序框图图形符号图形符号名称名称功能功能流程线
14、流程线连接循环框连接循环框连结点连结点连接循环框图的两部分连接循环框图的两部分一、一、程序框图程序框图图形符号图形符号名称名称功能功能终端框终端框(起止框起止框)输入、输入、输出框输出框处理框处理框(执行框执行框)判断框判断框表示一个算法的表示一个算法的起始和结束起始和结束表示一个算法输表示一个算法输入和输出的信息入和输出的信息赋值、计算赋值、计算判断某一条件是否成判断某一条件是否成立立,成立时在出口处标成立时在出口处标明明“是是”或或“Y”,不不成立时标明成立时标明“否否”或或“N”.(1)(1)起止框起止框:框内填写开始、结束框内填写开始、结束,任何程序框任何程序框图中,起止框是必不可少的
15、;图中,起止框是必不可少的;(2)(2)输入、输出框输入、输出框:框内填写输入、输出的框内填写输入、输出的字母、符号等字母、符号等;(3)(3)处理框处理框(执行框执行框):):算法中需要的算式、算法中需要的算式、公式、对变量进行赋值等要用执行框表示公式、对变量进行赋值等要用执行框表示.(4)(4)判断框判断框:当算法要求在不同的情况下执当算法要求在不同的情况下执行不同的运算时,需要判断框行不同的运算时,需要判断框.框内填写框内填写判断条件判断条件.3.3.四种基本的框图及其功能用法四种基本的框图及其功能用法:为了使大家彼此之间能够读懂各自画出为了使大家彼此之间能够读懂各自画出的框图的框图,必
16、须遵守一些共同的规则必须遵守一些共同的规则,下面对一些下面对一些常用的规则作一简单的介绍常用的规则作一简单的介绍.(1)(1)使用标准的框图符号使用标准的框图符号.(2)(2)框图一般按从上到下、从左到右的方向画框图一般按从上到下、从左到右的方向画.(3)(3)除判断框外,大多数程序框图符号只有一除判断框外,大多数程序框图符号只有一个进入点和一个退出点,判断框是具有超过一个进入点和一个退出点,判断框是具有超过一个退出点的唯一符号个退出点的唯一符号.(4)(4)一类判断框是一类判断框是“是是”与与“否否”两分支的判两分支的判断断,而且有且仅有两个结果而且有且仅有两个结果;另一类是多分支判另一类是
17、多分支判断断,有几种不同的结果有几种不同的结果.4.画流程图的规则画流程图的规则(5)(5)在图形符号内描述的语言要非常简练清楚在图形符号内描述的语言要非常简练清楚.(7)(7)一个程序框图包括以下几部分一个程序框图包括以下几部分:表示相应操表示相应操作的程序框作的程序框;带箭头的流程线带箭头的流程线;程序框外必要的程序框外必要的文字说明文字说明(6)(6)起始框只允许一条流出线起始框只允许一条流出线,终止框只允许一终止框只允许一条流入线条流入线,输入框、输出框、处理框只有一条输入框、输出框、处理框只有一条流入线和一条流出线流入线和一条流出线,判断框有一条流入线和判断框有一条流入线和两条流出线
18、两条流出线,但任何时候只有一条流出线起作但任何时候只有一条流出线起作用用.二、二、顺序结构顺序结构及框图表示及框图表示1.顺序结构顺序结构:按照步骤依次执行的一个算法按照步骤依次执行的一个算法,称称为具有为具有“顺序结构顺序结构”的算法的算法,或者称为算法的或者称为算法的顺序结构顺序结构.语句语句A语句语句B2.顺序结构的流程图顺序结构的流程图 顺序结构是最简单的顺序结构是最简单的算法结构算法结构,语句与语句之间语句与语句之间,框与框之间是按从上到下框与框之间是按从上到下的顺序进行的的顺序进行的.它是由若干它是由若干个处理步骤组成的个处理步骤组成的,这是任这是任何一个算法都离不开的基何一个算法
展开阅读全文