11.1算法的概念.ppt

《11.1算法的概念.ppt》由会员分享，可在线阅读，更多相关《11.1算法的概念.ppt（72页珍藏版）》请在三一办公上搜索。

1、第一章 算法初步,算法自古就有，中国古代数学在世界数学史上一度占居领先地位她注重实际问题的解决，以算法为中心，寓理于算，其中蕴涵了丰富的算法思想算筹是中国古代的计算工具，在春秋时期已经很普遍，算盘在明代开始盛行中国古代涌现了许多著名的数学家，如三国、两晋的赵爽、刘徽，南北朝的祖冲之、祖暅父子，宋、元的秦九韶、杨辉、朱世杰等.著名的数学专著有九章算术、周髀算经、数书九章、四元玉鉴、黄帝九章算法细草、议古根源、数书九章、详解九章算法和杨辉算法等,内容简介,随着计算科学和信息技术的飞速发展，算法思想已经渗透到社会的方方面在以前的学习中，虽然没有出现算法这个名词，但实际上在数学学习中已经渗透了大量的算

2、法思想，如四则运算的过程、求解方程的步骤等等完成这些工作都需要一系列程序化的步骤，这就是算法的思想,1.1 算法与程序框图,本章共分3节,算法至今也没有一个严格的统一定义本节从大家熟悉的二元一次方程组的求解过程，引出算法的描述性的定义及算法的主要特征并通过质数的判定、用二分法求方程近似解等问题，进一步理解算法的基本含义并渗透算法思想,1.1.1 算法的概念,1.1.2 程序框图与算法的基本逻辑结构,1.1.1使用的自然语言形式的写法，通俗易懂，但不够准确，其基本结构也不清晰本节以框图形式介绍了算法的基本逻辑结构(顺序结构、条件结构和循环结构)，使得算法更直观、准确这三种基本逻辑结构是程序框图的

3、构成要素,1.2 基本算法语句,1.3 算法案例,当今世界，越来越多的事情要交付计算机完成但自然语言或程序框图描述的算法，计算机是无法“理解”的用算法语句描述算法是用计算机解决问题的前提条件一般的操作顺序是先设计算法，再按照程序框图表示算法，最后将程序框图转化为算法语句本节介绍了输入语句、输出语句、赋值语句、条件语句和循环语句.,算法学习的一个最大的特点就是操作实践性强了解经典的算法案例有助于深入理解算法的特征、进一步体会算法的思想本节列举了辗转相除法与更相减损术、秦九韶算法与进位制等案例,1.1 算法与程序框图,1.1.1 算法的概念,1.1.2 程序框图与算法的基本逻辑结构,1.1.1 算

4、法的概念,学习目标,1.通过已学过的二元一次方程组的方法，初步认识、体会算法的基本思想。,2.了解算法的含义、特征。,学习重点,根据求解数学问题的一般方法与步骤，体会算法的基本思想。,学习过程,我们完成任何事，都要有一个步骤，合理安排步骤，会达到事半功倍的效果。从数学的角度来讲，在解决某些问题时，需要设计出一系列可操作或可计算的步骤，通过实施这些步骤来解决问题，我们通常把这些步骤称为解决问题的一种算法。这种描述不是算法的定义，但反映了算法的基本思想。,一、实例,代入法、消元法,第一步：,第二步：,第三步：,第四步：,第五步：,解，得：,解，得：,得到方程组的解为,算法：就是解决一个特定问题的方

5、法与步骤,二、归类,第一步：,第二步：,第三步：,第四步：,第五步：,解(3)得：,解(4)得：,得到方程组的解为：,三、算法的基本思想及特征,一般地,对于一类问题的机械式地、统一地、按部就班地求解过程称为算法(algorithm)它是解决某一问题的程序或步骤.,按照这样的理解,我们可以设计出很多具体数学问题的算法.下面看几个例子:,所谓“算法”就是解题方法的精确描述.从更广义的角度来看,并不是只有“计算”的问题才有算法,日常生活中处处都有.如乐谱是乐队演奏的算法,菜谱是做菜肴的算法,珠算口诀是使用算盘的算法.,第一步:农夫带羊过河;,第二步:农夫独自回来;,第三步:农夫带狼过河;,第四步:农

6、夫带羊回来;,第五步:农夫带蔬菜过河;,第六步:农夫独自回来;,第七步:农夫带羊过河.,1、一个 带着一条、一头 和一篮 要过河,但只有一条小船.乘船时,农夫只能带一样东西.当农夫在场的时候,这三样东西相安无事.一旦农夫不在,狼会吃羊,羊会吃菜.请设计一个算法,使农夫能安全地将这三样东西带过河.,2、把大象装进冰箱里，一共分几步？,第一步：把冰箱门打开,第二步：把大象装进冰箱,第三步：把冰箱门关上,3、思考以下问题的算法：,一位商人有9枚银元，其中有1枚略轻的是假银元你能用天平（不用砝码）将假银元找出来吗？,解:1.把银元分成3组，每组3枚,2先将两组分别放在天平的两边如果天平不平衡，那么假银

7、元就放在轻的那一组；如果天平左右平衡，则假银元就在末称的第3组里,3取出含假银元的那一组，从中任取两枚放在天平的两边如果左右不平衡，则轻的那一边就是假银元；如果天平两边平衡，则没称的那一枚就是假银元,算法的特点：1.通用性：能用来解决同一类问题；2.确定性：每一步都应该是能有效执行且有确定的结果，而不应该是模棱两可的；3.有穷性：应能在有限步内解决问题.4.可行性：计算机可以解决,算法：在数学中，现代意义上的“算法”通常是指可以用计算机来解决的某一类问题的程序或步骤，这些程序和步骤必须是明确和有效的，而且能够在有限步之内完成,算法的表示形式有三种：自然语言、程序框图、程序设计语言,自然语言就是

8、人们日常使用的语言,可以是汉语、英语或数学语言等.用自然语言描述算法的优点是通俗易懂,当算法中的操作步骤都是顺序执行时比较容易理解.缺点是如果算法中包含判断和转向,并且操作步骤较多时,就不那么直观清晰了.,(1)自然语言,(2)程序框图,(3)程序语言,1.1.2 程序框图中讲解,1.2 基本算法语句中讲解,只能被1和它本身整除的大于1的整数叫质数,判断一个大于1的整数n是否为质数，用比这个整数小比1大的数去除n，如果不能整除，则n就是质数,第一步：用2除7，得余数为1，所以2不能整除7,第二步：用3除7，得余数为1，所以3不能整除7,第三步：用4除7，得余数为3，所以4不能整除7,第四步：用

9、5除7，得余数为2，所以5不能整除7,第五步：用6除7，得余数为1，所以6不能整除7,因此，7是质数,第一步：用2除35，得余数为1，所以2不能整除35,(2)设计一个算法，判断35是否为质数,第二步：用3除35，得余数为2，所以3不能整除35,第三步：用4除35，得余数为3，所以4不能整除35,第四步：用5除35，得余数为0，所以5能整除35,因此，35不是质数,探究,您能写出“判断整数n(n2)是否为质数”的算法么？,第一步：给定大于2的整数n,第二步：令i=2,第三步：用i除n，得余数r判断余数r是否为0，若是，则n不是质数，结束算法；否则，将i的值增加1，仍用i表示这个数,第四步：判断

10、i是否大于n-1，若是，则n是质数；否则，返回第三步,第三步：取区间中点,取d=0.005，可以得到以下表格：,区间(1.4140625，1.41796875)中的实数都是当精确度为0.005时的原方程的近似解,1、给出求1+2+3+4+5+6的一个算法.,解法1.按照逐一相加的程序进行.,第一步:计算1+2,得3;,第二步:将第一步中的运算结果3与3相加得6;,第三步:将第二步中的运算结果6与4相加得10;,第四步:将第三步中的运算结果10与5相加得15;,第五步:将第四步中的运算结果15与6相加得21.,思考：您能举出更多的算法的例子吗？,解法2.可以运用下面公式直接计算.,第一步:取n=

11、6,第二步:计算,第三步:输出计算结果.,点评:解法1繁琐,步骤较多;解法2简单，步骤较少.找出好的算法是我们的追求目标.,2、任意给定一个正实数,设计一个算法求以这个数为半径的圆的面积.,第一步:输入任意一个正实数r；,第二步:计算圆的面积:S=r 2;,第三步:输出圆的面积S.,3、任意给定一个大于1 的正整数n,设计一个算法求出n的所有因数.,第一步：依次以2(n-1)为除数去除n,检查余数是否为0,若是,则是n的因数;若不是,则不是n的因数.,第二步：在n的因数中加入1和n.,第三步：输出n的所有因数.,1.1.2程序框图与算法的基本逻辑结构,学习目标,1.理解程序框图的含义,能读懂程

12、序框图.,2.掌握程序框图的三种基本逻辑结构及其之间的联系.,3.初步会画一些简单的程序框图.,学习过程,1.程序框图,算法的表现形态不仅有自然语言,还有程序框图与程序.用自然语言描述算法的优点是通俗易懂,当算法中的操作步骤都是顺序执行时比较容易理解.缺点是如果算法中包含判断和循环,并且操作步骤较多时,就不那么直观清晰了.,又称流程图,是一种用程序框、流程线及文字说明来表示算法的图形.,程序框图,终端框（起止框）,表示一个算法的起始和结束,输入、输出框,表示一个算法输入和 输出的信息,处理框（执行框）,赋值、计算,判断框,判断某一条件是否成立,成立时在出口处标明“是”或“Y”；不成立时标明“否

13、”或“N”.,连接点,连接程序框图的两部分,流程线,连接程序框,四种基本框图的用法,为了使大家彼此之间能够读懂各自画出的框图,必须遵守一些共同的规则.,(1)使用标准的框图符号.(2)框图一般按从上到下、从左到右的方向画.(3)流程线是带有方向箭头的线,用以连接框图,直观地表示算法的流程.在程序框图中,任意两个程序框之间都存在流程线.(4)在程序框图中,除起止框外,任意一个程序框都只有一条流程线“流进”,输入输出框、处理框都只有一条流程线“流出”,但判断框一定是至少有两条流程线“流出”.(5)一个完整的程序框图包括以下几部分：表示相应操作的程序框、带箭头的流程线、程序框外必要的文字说明.以起止

14、框表示开始,以终止框表示结束.,画流程图的规则,“判断整数n(n2)是否为质数”的算法,第一步：给定大于2的整数n.,第二步：令i=2,第三步：用i除n,得余数r.判断余数r是否为0,若是,则n不是质数,结束算法；否则,将i的值增加1,仍用i表示这个数.,第四步：判断i是否大于n-1,若是,若是,则n是质数；否则,返回第三步.,自然语言,(1)给定大于2的整数n.,(2)令i=2,(3)用i除n,得余数r.判断余数r是否为0,若是,则n不是质数,结束算法；否则,将i的值增加1,仍用i表示这个数.,(4)判断i是否大于n-1,若是,则n是质数；否则,返回第三步.,程序框图,2.算法的基本逻辑结构

15、,尽管算法千差万别,但它们都是由三种基本的逻辑结构构成的,这三种逻辑结构就是顺序结构、条件结构、循环结构.,(1)顺序结构,由若干个依次执行的处理步骤组成的结构.它是任何一个算法都离不开的结构.,画顺序结构程序框图时注意事项,(1)在程序框图中,开始框和结束框不可少；(2)在算法过程中,第一步输入语句是必不可少的;(3)顺序结构在程序框图中的体现就是用流程线将程序框自上而下地连接起来,按顺序执行算法步骤.,算 法,第二步：计算,第三步：计算,第四步：输出三角形的面积S,框 图,开始,第一步：输入 的值,例3.已知一个三角形的三边边长分别为 利用海伦-秦九韶公式,(,),设计一个算法,求出它的面

16、积,并画出算法的程序框图.,“鸡兔同笼”是我国隋朝时期的数学著作孙子算经中的一个题目:“今有鸡兔同笼,上有三十五头,下有九十四足,问鸡兔各几何.”请您设计一个这类问题的通用算法.并画出算法的程序框图.,设有x只鸡,y只兔.则,解:鸡兔同笼,设鸡兔总头数为H,总脚数为F,求鸡兔各有多少只.算法分析如下：,解方程组,得,第一步:输入总头数H,总脚数F 第二步：计算鸡的个数x=(4H-F)/2第三步:计算兔的个数y=(F-2H)/2 第四步:输出x,y,开始,输出x,y,结束,x=(4H-F)/2,y=(F-2H)/2,输入H和F,解：算 法,程序框图,(2)条件结构,在一个算法中,经常会遇到一些条

17、件的判断,算法的流程根据条件是否成立有不同的流向.,符合条件就执行A,否则执行B,符合条件就执行A,否则执行条件结构后的步骤,例4.任意给定3个正实数,设计一个算法,判断以这3个正实数为三条边边长的三角形是否存在,并画出这个算法的程序框图.,算 法,程序框图,否,是,本题的编制程序让计算机执行时比较困难.,例5.设计一个求解一元二次方程 的算法，并画出程序框图表示.,算 法,第一步：输入三个系数,第二步：计算,程序框图,是,是,否,否,练习：设计一算法,求1+2+3+100.,第一步:确定首数、尾数、项数,第二步:利用公式“总和=(首数+尾数)项数/2”求和；,第三步:输出求和结果.,算法1,

18、第一步:从1开始将自然数1,2,3,100逐个相加,第二步:输出累加结果,1.上边的式子有怎样的规律呢？,2.怎么用程序框图表示呢？,S=S+i,S=0S=S+1S=S+2S=S+3S=S+100,思考,算法2,(3)循环结构,有些算法中,也经常出现从某处开始,按照一定条件,反复执行某些步骤的情况.这就是循环结构.反复执行的步骤称为循环体.,求1+2+3+100,第一步:令,第二步:若 成立,则执行第三步；否则,输出S,结束算法.,第三步:,循环结构的设计步骤,(1)确定循环结构的循环变量和初始条件;(2)确定算法中需要反复执行的部分,即循环体；(3)确定循环的终止条件.,循环结构的三要素,循

19、环变量,循环体、循环的终止条件.,循环结构一定包含条件结构,用以控制循环过程,避免出现“死循环”.判断框内写上条件,两个出口分别对应终止条件成立与否,其中一个指向循环体,经过循环体回到判断框的入口处.,循环结构分为当型循环结构和直到型循环结构,差异:循环终止条件不同,检验条件是否成立的先后次序也不同.,当型循环结构:先判断后执行循环体.,直到型循环结构:先执行循环体后判断条件是否成立.,当型循环结构,直到型循环结构,求1+2+3+n？,例7.某工厂2005年的生产总值为200万元,技术革新后预计以后每年的生产总值比上一年增加5%.设计一个程序框图，输出预计年生产总值超过300万元的最早年份.,

20、算法,直到型循环结构,当型循环结构,当型循环结构,直到型循环结构,3.程序框图的画法,通过以上两个知识点可以看出，画出一个算法的程序框图很有必要.我们可以借助三种基本逻辑结构来表示这样的算法，使得算法清楚、简练，便于阅读和交流.,一般地，一个算法的程序框图有以下几个步骤：,第一步：用自然语言表述算法步骤.,第二步：确定每一个算法步骤所包含的逻辑结构，并用相应的程序框图表示，得到该步骤的程序框图.,第三步：将所有步骤的程序框图用流程线连接起来，并加上终端框，得到表示整个算法的程序框图.,第三步：取区间中点,顺序结构,条件结构,循环结构,开始,结束,输入x,y=3x2+4x+5,输出y,已知函数y

21、=3x2+4x+5，设计一个算法，对于给定的任意实数x,计算函数值,并画出程序框图。,算法分析：,第一步：输入一个实数x；,第二步：计算y=3x2+4x+5；,第三步：输出函数值y。,程序框图：,例1,顺序结构,开始,输入a,a 0？,输出 m,结束,N,Y,设计一个算法，求任意 实数a的绝对值，并画出程序框图.,算法分析：,第一步：输入一个实数a；,第二步：判断a0 是否 成立。若是，则 m=a；否则，m=-a。,第三步：输出m.,m=a,m=-a,例2,程序框图：,条件结构,，画程序框图，对于输入的X值，输出相应的y值。,0(x0)已知函数y=1(0 x1)x(x1),开始,输入X,X0?

22、,y=0,x1?,y=x,y=1,输出y,结束,变式,条件结构的嵌套,设计一个算法，计算 1+2+3+10 的值，并画出程序框图。,算法分析：,第一步：令 i=1,s=0。,第二步：判断 i10是否成立。,第三步：s=s+i。,第四步：i=i+1,返回第二步。,例3,i10?,i=1,开始,输出s,结束,否,是,s=0,i=i+1,s=s+i,程序框图：,当型循环结构,若是，执行第三步；否则，输出s，结束算法。,设计一个算法，计算 1+2+3+10 的值，并画出程序框图。,算法分析：,第一步：令 i=1,s=0。,第四步：判断 i10是否成立。,第二步：s=s+i。,第三步：i=i+1。,例3

23、,i=1,开始,输出s,结束,s=0,程序框图：,直到型循环结构,若是，输出s，结束算法；否则，返回第二步。,i10?,i=i+1,s=s+i,否,是,对任意正整数n,设计,的值,并画出程序框图.,第五步,直到in时,输出S，,算法分析：,第二步,令 i=1,s=0;,第三步,s=s+1/i；,第四步,i=i+1；,否则返回第三步。,第一步,输入一个正整数n;,变式2,结束算法，,开始,输入一个正整数n,输出S,结束,S=0,i=1,S=S+1/i,i=i+1,in?,Y,N,一个算法求,程序框图：,设计一个算法：求,结束,输出?,开始,s=s+i,i=i+1,s22?,否,是,i=1,s=0

24、,的最小正整数n。,变式3,满足12 3 n 22,第五步,直到 时,输出，,算法分析：,第二步,令 i=1,s=0;,第三步,s=s+i；,第四步,i=i+1；,否则返回第三步。,第一步,输入一个正整数n;,结束算法，,程序框图：,in,S,S22,?,i-1,i-1,最后一个加数,输入一个正整数n,(P20BT2).某高中男子体育小组的50m跑成绩(单位:s)为:6.4,6.5,7.0,6.8,7.1,7.3,6.9,7.4,7.5.设计一个算法,从这些成绩中搜出小于6.8s的成绩.,算法分析:,第一步:把计数变量n的初值设为1.第二步:输入一个成绩r,判断r与6.8的大小.若r6.8,则执行下一步;若r9,则结束.,开始,n=1,程序框图,输入r,r6.8?,是,n=n+1,n9?,是,否,输出r,否,结束,直到型循环结构,