度高中数学新课标人版A版必修3课件 1.3 算法与案例 (共30张PPT).ppt

基本结构基本结构程序框图程序框图顺序结构顺序结构变量与赋值变量与赋值循环结构循环结构基本语句基本语句循环语句循环语句条件语句条件语句WHILE语句语句UNTIL语句语句IF-THEN语句语句语句适用结构语句适用结构算法算法条件结构条件结构我们这节课就利用基本的算法程序来解决一我们这节课就利用基本的算法程序来解决一些实际问题，进一步体会算法的程序思想。些实际问题，进一步体会算法的程序思想。案例案例1.辗转相除法与更相减损术辗转相除法与更相减损术在初中，我们已经学过求最大公约数的知识，在初中，我们已经学过求最大公约数的知识，你能求出你能求出18与与30的最大公约数吗？的最大公约数吗？ 218 30 3 9 15 3 5所以，所以，18和和30的最大公约数是：的最大公约数是：236互质互质因数因数但是，当我们处理较大数（如：但是，当我们处理较大数（如：8251与与6105）的最大公因）的最大公因数时，如果利用这种方法可能计算量比较大，步骤比较多。数时，如果利用这种方法可能计算量比较大，步骤比较多。下面我们介绍一种古老而有效的算法下面我们介绍一种古老而有效的算法辗转相除法辗转相除法这种算法是这种算法是欧几里得欧几里得公元前公元前300年左右首先提出的，因此又年左右首先提出的，因此又叫欧几里得算法叫欧几里得算法例例1 求两个正数求两个正数8251和和6105的最大公约数。的最大公约数。 分析：分析：8251与与6105两数都比较大，而且没有明显的公约数，两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数如能把它们都变小一点，根据已有的知识即可求出最大公约数 解解8251610512146 显然显然8251和和6105的最大公约数也必是的最大公约数也必是2146的约数，的约数，同样同样6105与与2146的公约数也必是的公约数也必是8251的约数，所以的约数，所以8251与与6105的最大公约数也是的最大公约数也是6105与与2146的最大的最大公约数公约数 继续下去，我们得到：继续下去，我们得到：欧几里得（公元前欧几里得（公元前330-公元前公元前275）：古希）：古希腊数学家，雅典人腊数学家，雅典人欧几里得是欧几里得是柏拉图柏拉图的学生，长期在亚的学生，长期在亚历山大里亚教书。历山大里亚教书。公元前公元前300年左右，代表作年左右，代表作几何原本几何原本13卷问世，创立了著名的卷问世，创立了著名的欧氏几何欧氏几何，至今，至今仍为中学生必学的一门基础知识。欧几里仍为中学生必学的一门基础知识。欧几里得对光学也有一定研究。得对光学也有一定研究。61056105214621462 21813181321462146181318131 1333333181318133333335 51481483333331481482 2373714814837374 40 0则则3737为为82518251与与61056105的最大公约数的最大公约数 这就是辗转相除法，有除法的性质可以知道，这就是辗转相除法，有除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以对于任意两个正整数，上述除法步骤总可以在有限步骤之后完成在有限步骤之后完成利用辗转相除法求最大公约数的步骤如下：利用辗转相除法求最大公约数的步骤如下： 第一步：第一步：给定两个正整数给定两个正整数m,n.第二步：第二步：计算计算m除以除以n的余数的余数.第三步：第三步：m=n,n=r.第四步：若第四步：若r r0,0,则则m,nm,n的最大公约数等于的最大公约数等于m;m;否则否则, ,返回第二返回第二步步. .r= m MOD nm=nn=rr=o?否否是是程序图框程序图框带余除法带余除法INPUT “请输入请输入m，n的值的值”；m，nDO r=m MOD N m=n n=rLOOP UNTIL r=0PRINT mEND为什么要用为什么要用直到型循环直到型循环结构？结构？1.1.利用辗转相除法求两数利用辗转相除法求两数40814081与与2072320723的最大公约的最大公约数数 ，写出它的流程框图和，写出它的流程框图和BASICBASIC程序程序更相减损术更相减损术 我国早期也有解决求最大公约数问题的算法我国早期也有解决求最大公约数问题的算法 九章算术九章算术（公元（公元50年年100年或更早年或更早 ）是中国古代数学专著，）是中国古代数学专著，承先秦数学发展的源流，进入汉承先秦数学发展的源流，进入汉朝后又经许多学者的删补才最后朝后又经许多学者的删补才最后成书，这大约是公元一世纪的下成书，这大约是公元一世纪的下半叶。它的出现，标志着中国古半叶。它的出现，标志着中国古代数学体系的形成。代数学体系的形成。 历代数学家把它尊为历代数学家把它尊为“算经之首算经之首”这是世这是世界上最早的印刷本数学书。界上最早的印刷本数学书。 九章算术九章算术共收有共收有 246246个数学问题，分个数学问题，分为九章。分别是：方田、栗米、衰分、少广、为九章。分别是：方田、栗米、衰分、少广、商功、均输、盈不足、方程、勾股。商功、均输、盈不足、方程、勾股。 九章算术九章算术是世界上最早系统叙述了分是世界上最早系统叙述了分数运算的著作；其中盈不足的算法更是一项数运算的著作；其中盈不足的算法更是一项令人惊奇的创造；令人惊奇的创造；“方程方程”章还在世界数学章还在世界数学史上首次阐述了负数及其加减运算法则。史上首次阐述了负数及其加减运算法则。更相减损术求最大公约数的步骤如下：可半者半之，不可半更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。以等数约之。翻译出来为：翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，第一步：任意给出两个正数；判断它们是否都是偶数。若是，用用2约简；若不是，执行第二步。约简；若不是，执行第二步。第二步：以较大的数减去较小的数，接着把较小的数与所第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数的数相等为止，则这个数（等数）就是所求的最大公约数例例1 1 用更相减损术求用更相减损术求9898与与6363的最大公约数的最大公约数. . 解解 由于由于6363不是偶数，把不是偶数，把9898和和6363以大数减小数，以大数减小数，并辗转相减并辗转相减 98-6398-63353563-3563-35282835-2835-287 728-728-7141414-714-77 7所以，所以，98与与63的最大公约数是的最大公约数是7 比较辗转相除法与更相减损术的区别比较辗转相除法与更相减损术的区别 （1）都是求最大公约数的方法，计算上）都是求最大公约数的方法，计算上辗转相除法辗转相除法以以除法除法为为主，主，更相减损术更相减损术以以减法减法为主，计算次数上辗转相除法计算次为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除）从结果体现形式来看，辗转相除法体现结果是以相除余数为余数为0则得到，而更相减损术则以减数与差相等而得到则得到，而更相减损术则以减数与差相等而得到思考一思考一. .用辗转相除法求下列各组数的最大公约数，用辗转相除法求下列各组数的最大公约数，并在自己编写的并在自己编写的BASICBASIC程序中验证。程序中验证。（1 1）225225，135 135 （2 2）9898，196 196 （3 3）7272，168168思考二：思考二：用更相减损法可否求上述用更相减损法可否求上述3组数的最大公约数？可组数的最大公约数？可否利用更相减损法设计出程序框图及程序？若能，在电脑上否利用更相减损法设计出程序框图及程序？若能，在电脑上测试自己的程序；若不能说明无法实现的理由。测试自己的程序；若不能说明无法实现的理由。思考三：思考三：利用辗转相除法是否可以求两数的最大公倍数？利用辗转相除法是否可以求两数的最大公倍数？试设计程序框图并转换成程序在试设计程序框图并转换成程序在BASICBASIC中实现。中实现。 案例二（秦九韶算法）怎样求多项式案例二（秦九韶算法）怎样求多项式1)(2354xxxxxxf当当x=5时的值？时的值？据我们的计算统计可以得出我们共需要据我们的计算统计可以得出我们共需要10次乘法运算，次乘法运算，5次次加法运算加法运算 我们把多项式变形为：我们把多项式变形为： 再统计一下计算当时的值时需要的计算次数，可以得出仅需再统计一下计算当时的值时需要的计算次数，可以得出仅需4次乘法和次乘法和5次加法运算即可得出结果。显然少了次加法运算即可得出结果。显然少了6次乘法运算。次乘法运算。这种算法就叫这种算法就叫秦九韶算法秦九韶算法。1)1 (1 (1 ()(2xxxxxxf秦九韶（秦九韶（1202-1261年），年），字道古，安岳县人。其父秦字道古，安岳县人。其父秦季栖，进士出身，官至工部季栖，进士出身，官至工部郎中、秘书少监。秦九韶性郎中、秘书少监。秦九韶性敏慧，勤奋好学，幼年随父敏慧，勤奋好学，幼年随父居中都（今北京），受到名居中都（今北京），受到名师指导，学习日益增进。及师指导，学习日益增进。及长，随父迁湖州（今浙江吴长，随父迁湖州（今浙江吴兴县），在西门外修建住房，兴县），在西门外修建住房，由秦九韶设计施工，堂分由秦九韶设计施工，堂分7间，间，后为列室，仅中堂后为列室，仅中堂1间，纵横间，纵横7丈，极其宏伟宽敞，显示出丈，极其宏伟宽敞，显示出他在建筑方面的才能他在建筑方面的才能 01210123120132211012211)()()()(aaxaxaxaaxaxaxaxaaxaxaxaxaaxaxaxaxaxfnnnnnnnnnnnnnnnnnnn把一个多项式把一个多项式012211)(axaxaxaxaxfnnnnnn改写为：改写为：求多项式的值时，首先计算最内层括号内的一次多项式的求多项式的值时，首先计算最内层括号内的一次多项式的值，即：值，即：11nnaxav01323212avvaxvvaxvvnnnn再有内向外逐层计算一次多项式的值，即：再有内向外逐层计算一次多项式的值，即：这样将求这样将求n次多项式次多项式f(x)的值转化为求的值转化为求n个一次多项式的值。个一次多项式的值。例例2 2 已知一个已知一个5 5次多项式为次多项式为 5432( )423.52.61.70.8f xxxxxx当当5x 用秦九韶算法求这个多项式的值。用秦九韶算法求这个多项式的值。 012345( )(42)3.5)2.6)1.7)0.84;4 5 222;223.5 113.5;113.5 5 2.6564.9;564.9 5 1.72826.2;2826.2 5 0.8 14130.2.,5 ,f xxxxxxvvvvvvx 根据秦几韶算法,把多项式改写成如下形式:按照从内到外的顺序,依次计算一次多项式当绵值:所以当时多项式的值等于14130.2.用秦九韶算法求这个多项式当用秦九韶算法求这个多项式当 时的值。时的值。8 . 07 . 16 . 25 . 325)(2345xxxxxxf5x3. 3. 已知一个已知一个5 5次多项式为次多项式为思考：（思考：（1）例）例1计算时需要多少次乘法计算？多少次加法计算时需要多少次乘法计算？多少次加法计算？计算？ （2）在利用秦九韶算法计算）在利用秦九韶算法计算n次多项式当时需要多少次次多项式当时需要多少次乘法计算和多少次加法计算？乘法计算和多少次加法计算？进位制是人们为了计数和运算方便而约定的计数系统，约进位制是人们为了计数和运算方便而约定的计数系统，约定满二进一，就是二进制；满十进一，就是十进制，等等，定满二进一，就是二进制；满十进一，就是十进制，等等，也就是说也就是说满几进一满几进一就是几进制，几进制的就是几进制，几进制的基数基数就是几就是几大于大于1的整数的整数由于自然数有无限多个，对于每一个自然数如果都用一个由于自然数有无限多个，对于每一个自然数如果都用一个独立的名称或符号来读出它或表示它，那是很不方便的，独立的名称或符号来读出它或表示它，那是很不方便的，也是不可能做到的。因此，需要建立一种读数、写数制度也是不可能做到的。因此，需要建立一种读数、写数制度- - -进位制进位制 12232n1n1nna10a10a10a10a 十进制数十进制数 表示实际数值为：表示实际数值为：1231nnaaaaa 12232n1n1nnakakakaka K进制数进制数 实际表示数为：实际表示数为：)k(1231nnaaaaa 在日常生活中，我们最熟悉的还是十进制数，据说这和古在日常生活中，我们最熟悉的还是十进制数，据说这和古人曾以手指计数有关人曾以手指计数有关为了区别进制，我们就用下标为了区别进制，我们就用下标（k）表示）表示k进制数进制数a n是是09的数子的数子下面我们来用一个具体的例子来分析：下面我们来用一个具体的例子来分析：例例3.将二进制数将二进制数110 011(2)化成十进制数化成十进制数解解 根据根据k进制数的实际意义，我们可以这样来转换：进制数的实际意义，我们可以这样来转换：51121161321212120202121011 110012345(2) INPUT a,b,cb=0i=1T=a MOD 10DO b=b+t*k(i-1) a=a10 t=a MOD 10 i=i+1LOOP UNTIL inPRINT bEND例4 设计一个算法,把k进制数a(共n位)转化为十进制数b.缺少算法分析和程序框图例例5.把把89化为二进制数化为二进制数分析：分析：89=2(2(2(2(22+1)+1)+0)+0)+1 = =1 011 001(2)28912440222021112512202 11 0所以上式可以表示为：所以上式可以表示为：1 011 001综合：上述方法叫做综合：上述方法叫做k进制数的进制数的除除k取余法取余法5.把把89化为五进制数化为五进制数思考：思考：1如何将十六进制数如何将十六进制数A1F721化为二进制数化为二进制数一般方法：一般方法：k进制数进制数十进制数十进制数n进制数进制数1010 0001 1111 0111 0010 0001算法算法程序图框程序图框算法语句算法语句辗转相除与更相减损术辗转相除与更相减损术秦秦 九九 韶韶 算算 法法进进 位位 制制