课标人教A版必修3全套算法案例.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人教A版高中数学必修3,多媒体课件,多思、创新、融合,1,2,复习回顾,基本结构,流程图,顺序结构,变量与赋值,循环结构,基本语句,循环语句,条件语句,WHILE语句,UNTIL语句,IF-THEN语句,语句适用结构,算法,条件结构,3,我们这节课就利用基本的算法程序来解决一些实际问题，进一步体会算法的程序思想。,案例1.,辗转相除法与更相减损术,4,在初中，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？,2,30,3,9 15,3 5,所以，18和30的最大公约数是：,236,互质,因数,但是，当我们处理较大数（如：8251与6105）的最大公因数时，如果利用这种方法可能计算量比较大，步骤比较多。下面我们介绍一种古老而有效的算法,辗转相除法,5,这种算法是,欧几里得,公元前300年左右首先提出的，因此又叫欧几里得算法,例1 求两个正数8251和6105的最大公约数。,分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数,解,8251610512146,显然8251和6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数,继续下去，我们得到：,欧几里得（公元前330-公元前275）：古希腊数学家，雅典人,欧几里得是,柏拉图,的学生，长期在亚历山大里亚教书。,公元前300年左右，代表作,几何原本,13卷问世，创立了著名的,欧氏几何,，至今仍为中学生必学的一门基础知识。欧几里得对光学也有一定研究。,6,6105214621813214618131333181333351483331482371483740则37为8251与6105的最大公约数,这就是辗转相除法，有除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以在有限步骤之后完成,你能写出它的算法程序吗？,7,利用辗转相除法求最大公约数的步骤如下：,第一步：,用较大的数m除以较小的数n得到一个商q,0,和一个余数r0；,第二步：,若r00，则n为m，n的最大公约数；若r00，则用除数n除以余数r0得到一个商q1和一个余数r1；,第三步：,若r10，则r1为m，n的最大公约数；若r10，则用除数r0除以余数r1得到一个商q2和一个余数r2,第n步：依次计算直至r,n,0，此时所得到的r,n,1即为所求的最大公约数,8,r=m,MOD,n,m=n,n=r,r=o?,否,是,程序图框,带余除法,INPUT“请输入m，n的值”；m，n,IF mn THEN,a=m,m=n,n=a,END IF,DO,r=m MOD N,m=n,n=r,LOOP UNTIL r=0,PRINT m,END,作用是什么？,为什么要用直到型循环结构？,9,练一练,1.利用辗转相除法求两数4081与20723的最大公约数，写出它的流程框图和BASIC程序,10,更相减损术,我国早期也有解决求最大公约数问题的算法,九章算术（公元50年100年或更早）是中国古代数学专著，承先秦数学发展的源流，进入汉朝后又经许多学者的删补才最后成书，这大约是公元一世纪的下半叶。它的出现，标志着中国古代数学体系的形成。,11,历代数学家把它尊为“算经之首”这是世界上最早的印刷本数学书。,九章算术共收有 246个数学问题，分为九章。分别是：方田、栗米、衰分、少广、商功、均输、盈不足、方程、勾股。,九章算术是世界上最早系统叙述了分数运算的著作；其中盈不足的算法更是一项令人惊奇的创造；“方程”章还在世界数学史上首次阐述了负数及其加减运算法则。,12,更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。,翻译出来为：,第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。,第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。,第三部：继续第二步，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数,13,例2 用更相减损术求98与63的最大公约数.,解 由于63不是偶数，把98和63以大数减小数，并辗转相减,98-6335,63-3528,35-287,28-714,14-77,所以，98与63的最大公约数是7,两种算法比较，你有什么发现？,14,比较辗转相除法与更相减损术的区别,（1）都是求最大公约数的方法，计算上,辗转相除法,以,除法,为主，,更相减损术,以,减法,为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。,（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到,15,练习,思考一.,用辗转相除法求下列各组数的最大公约数，并在自己编写的BASIC程序中验证。（1）225，135（2）98，196（3）72，168,思考二：,用更相减损法可否求上述3组数的最大公约数？可否利用更相减损法设计出程序框图及程序？若能，在电脑上测试自己的程序；若不能说明无法实现的理由。,思考三：,利用辗转相除法是否可以求两数的最大公倍数？试设计程序框图并转换成程序在BASIC中实现。,16,案例二（秦九韶算法）怎样求多项式,当x=5时的值？,据我们的计算统计可以得出我们共需要10次乘法运算，5次加法运算,我们把多项式变形为：再统计一下计算当时的值时需要的计算次数，可以得出仅需4次乘法和5次加法运算即可得出结果。显然少了6次乘法运算。这种算法就叫,秦九韶算法,。,17,秦九韶（1202-1261年），字道古，安岳县人。其父秦季栖，进士出身，官至工部郎中、秘书少监。秦九韶性敏慧，勤奋好学，幼年随父居中都（今北京），受到名师指导，学习日益增进。及长，随父迁湖州（今浙江吴兴县），在西门外修建住房，由秦九韶设计施工，堂分7间，后为列室，仅中堂1间，纵横7丈，极其宏伟宽敞，显示出他在建筑方面的才能,它的一般计算步骤如下：,18,把一个多项式,改写为：,19,求多项式的值时，首先计算最内层括号内的一次多项式的值，即：,再有内向外逐层计算一次多项式的值，即：,这样将求n次多项式f(x)的值转化为求n个一次多项式的值。,20,例3 设计利用秦九韶算法计算5次多项式,当,时的值的程序框图以及BASIC程序。,i=0,WHILE i5,INPUT ai,WEND,DO,v=a5,v=v*x0+a5-n,n=n+1,LOOP UNTIL n6,END,21,用秦九韶算法求这个多项式当,时的值。,3.已知一个5次多项式为,思考：（1）例1计算时需要多少次乘法计算？多少次加法计算？,（2）在利用秦九韶算法计算n次多项式当时需要多少次乘法计算和多少次加法计算？,练习,22,案例3.排序问题,你会使用这些字典吗？,23,为了便于查询和检索，常常需要根据要求将被查寻的对象按照一定的顺序排列，通常称为排序，,你会从这些书籍中查阅你想要的东西吗？,24,我们在一个已经排好循序的一系列数中插入一个数据，成为一个新的系列，且仍按原来的规则排序。,直接插入排序,要将8插入到1,3,5,7,9,11,13中，我们怎样考虑？,确定8在原系列中的位置，使8小于或等于原系列中右边的数据，大于或等于左边的数据,将这个位置空出来，将数据8插进去,1,3,5,7,9,11,13,8,25,例题分析,例3.将数列49,38,65,97,76,13,27,49按小到大的顺序排列,我们的想法是：,1.先排49，38的顺序：38，49,2.比较第三个数与它们的大小得到：38，49，65,3.比较第四个数与2的顺序得到：38，49，65，97,n.第n个数与前面数的关系，得到最后的排序：,13，27，38，49，49，65，76，97,26,反复使用直接插入排序算法，即首先把第一个数当作一个基准，插入第二个数变成有两个数据的有序列，再插入第三个数，依此类推，就完成了整个无序列的有序化。流程图如下：,你会设计它的BASIC算法吗？,27,1排序号：,数据序号,1,2,3,4,5,6,7,8,原始数据,49,38,65,97,76,13,27,49,上述数据我们还可以这样来排序：,28,2排序,数据序号,1,2,3,4,5,6,7,8,原始数据,49,38,65,97,76,13,27,49,现将1号数据49和2号数据38比较，因为4938所以，49和38的位置互换，变为：,数据序号,1,2,3,4,5,6,7,8,原始数据,38,49,65,97,76,13,27,49,第一次排序,第一步：1号2号排序,29,数据序号,1,2,3,4,5,6,7,8,原始数据,38,49,65,97,76,13,27,49,第二步：2号3号排序,因为4965所以这俩数的序号不变,数据序号,1,2,3,4,5,6,7,8,原始数据,38,49,65,97,76,13,27,49,30,第三步：比较3、4号数据,数据序号,1,2,3,4,5,6,7,8,原始数据,38,49,65,97,76,13,27,49,方法同第二步，因为6576，所以4、5号数据互换，则：,32,第五步：比较5、6号数据：,数据序号,1,2,3,4,5,6,7,8,原始数据,38,49,65,76,97,13,27,49,数据序号,1,2,3,4,5,6,7,8,原始数据,38,49,65,76,13,97,27,49,方法同第二步，9713则，交换5、6号数据，则：,33,第六步：比较6、7号数据,数据序号,1,2,3,4,5,6,7,8,原始数据,38,49,65,76,13,97,27,49,数据序号,1,2,3,4,5,6,7,8,原始数据,38,49,65,76,13,27,97,49,同理，上面的顺序可以变为：,同理第七步比较7、8号数据后可以变为：,34,这样就完成了第一次排序，它的基本特征是将最大数排到了最右边，然后再从头开始，进行第二次排序，将第二大的数据排到了倒数第二位，反复下去，就可以完成排序。一共要进行7次才能完成。我们叫它,冒泡排序（bubble sorting）,思考,你会用冒泡法将上面的数据按从大到小的顺序排列吗？,完成所有的排序需要多少步比较？,你还有其他的排序方法将上面的数据按从大到小的顺序排列吗？,35,练习,请你设计一个数据列为R1,R2,R10,要求从小到大的顺序排列？,1.画出一次冒泡排序的算法流程图,2.画出整个冒泡排序的算法流程图,36,一次排序,N-1次排完,整个排序流程图如图所示,37,说明,1.冒泡法排序完成n个数据的一次排序需要n-1次比较，完成整个排序需要(,n-1)！,次比较，对于数据较多时，计算量,很大,。,2.有些数据的冒泡法排序可能用更少的步骤可以完成，后面的步骤可能,毫无意义，但计算机必须完成。,3.交换数据时注意引入,第三方变量,。,38,案例4.进位制,并请这个人算出5个数 的和N，,在一种游戏中，魔术师请一个人随意想一个三位数,把N告诉魔术师，于是魔术师就能说出这个人所想的数,现在设N=3194，请你做魔术师，求出数 的值,将 也加到和N上，这样a、b、c就在每一位上都恰好出现两次，所以有,分析：,你知道它的原理吗？,39,从而 3194222(a+b+c)3194+1000，而a、b、c是整数,所以 15a+b+c18,因 222,15-3194=136,，,222,16-3194=358,，,222,17-3194=580,，,222,18-3194=802,其中只有3+5+8=16能满足式,事实上，这里面应用到了一个知识：,进位制,40,进位制是人们为了计数和运算方便而约定的计数系统，约定满二进一，就是二进制；满十进一，就是十进制，等等，也就是说,满几进一,就是几进制，几进制的,基数,就是几,大于1的整数,由于自然数有无限多个，对于每一个自然数如果都用一个独立的名称或符号来读出它或表示它，那是很不方便的，也是不可能做到的。因此，需要建立一种读数、写数制度-进位制,41,十进制数 表示实际数值为：,K进制数 实际表示数为：,在日常生活中，我们最熟悉的还是十进制数，据说这和古人曾以手指计数有关,为了区别进制，我们就用下标（k）表示k进制数,a n是09的数子,42,下面我们来用一个具体的例子来分析：,例4.将二进制数110 011,(2),化成十进制数,解 根据k进制数的实际意义，我们可以这样来转换：,43,INPUT a,b,c,i=1,b=0,WHILE i=n,t=GET ai,b=b+t*k(i-1),i=i+1,WEND,PRINT b,END,GET函数用于取出a的有数第i位,44,例5.不89化为二进制数,分析：89=2(2(2(2(22+1)+1)+0)+0)+1,=,=1 011 001,(2),2,89,1,2,44,0,2,22,0,2,11,1,2,5,1,2,2,0,2,1,1,0,所以上式可以表示为：1 011 001,综合：上述方法叫做k进制数的,除k取余法,45,练一练,5.把89化为五进制数,46,思考：1如何将十六进制数A1F721化为二进制数,一般方法：,k进制数,十进制数,n进制数,1010 0001 1111 0111 0010 0001,47,算法,程序图框,算法语句,辗转相除与更相减损术,秦 九 韶 算 法,排 序,进 位 制,48,