算法案例

-1-1.3算法案例【教学分析】：在学生学习了算法的初步知识，理解了表示算法的算法步骤、程序框图和程序三种不同的方式以后，再结合典型算法案例，让学生经历设计算法解决问题的全过程，体验算法在解决问题中的重要作用，体会算法的基本思想，提高逻辑思维能力，发展有条理地思考与数学表达能力。【学情分析】：学生已经学习了算法的初步知识，对基本的算法有一定的了解，但是，学生整体基础一般，在数学学习中缺乏数学思维，计算能力欠缺，所以在本节内容的学习中依然有一定的难度，应多给时间学生自己动手实践，从实践中总结规律和方法。【教学目标】：1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。2.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。3.掌握秦九韶算法及进位制之间的转化。4.理解三种算法的程序框图及程序的转化。【教学重难点】：重点：理解辗转相除法与更相减损术求最大公约数的方法。难点：把辗转相除法与更相减损术的方法转换成程序框图与程序语言。【教学过程】：情境导入：1.教师首先提出问题：在初中，我们已经学过求最大公约数的知识，你能求出18与30的公约数吗？2.接着教师进一步提出问题，我们都是利用找公约数的方法来求最大公约数，如果公约数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数？这就是我们这一堂课所要探讨的内容。新知探究：1.辗转相除法例1求两个正数8251和6105的最大公约数。（分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数）解：8251＝6105×1＋2146显然8251的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数。6105＝2146×2＋18132146＝1813×1＋3331813＝333×5＋148333＝148×2＋37148＝37×4＋0则37为8251与6105的最大公约数。以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。利用辗转相除法求最大公约数的步骤如下：-2-第一步：用较大的数m除以较小的数n得到一个商q0和一个余数r0；第二步：若r0＝0，则n为m，n的最大公约数；若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1；第三步：若r1＝0，则r1为m，n的最大公约数；若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2；……依次计算直至rn＝0，此时所得到的rn-1即为所求的最大公约数。练习：利用辗转相除法求两数4081与20723的最大公约数（答案：53）2.更相减损术我国早期也有解决求最大公约数问题的算法，就是更相减损术。更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母·子之数，以少减多，更相减损，求其等也，以等数约之。翻译出来为：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。例2用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减，即：98－63＝3563－35＝2835－28＝728－7＝2121－7＝1414－7＝7所以，98与63的最大公约数是7。练习：用更相减损术求两个正数84与72的最大公约数。（答案：12）可请学生上台展示结果比较辗转相除法与更相减损术的区别：（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。（2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到3.秦九韶算法秦九韶计算多项式的方法-3-令，则有，其中.这样，我们便可由依次求出；显然，用秦九韶算法求n次多项式的值时只需要做n次乘法和n次加法运算巩固实例：教材38页例二，师生共同完成，学生体验秦九韶算法的具体应用4.进位制进位制是一种记数方式，用有限的数字在不同的位置表示不同的数值.可使用数字符号的个数称为基数，基数为n，即可称n进位制，简称n进制.现在最常用的是十进制，通常使用10个阿拉伯数字0-9进行记数.对于任何一个数，我们可以用不同的进位制来表示.比如：十进数57，可以用二进制表示为111001，也可以用八进制表示为71、用十六进制表示为39，它们所代表的数值都是一样的.表示各种进位制数一般在数字右下脚加注来表示,如111001(2)表示二进制数,34(5)表示5进制数.（1）.k进制转换为十进制的方法：，（2）.十进制转化为k进制数b的步骤为：第一步，将给定的十进制整数除以基数k，余数便是等值的k进制的最低位；第二步，将上一步的商再除以基数k，余数便是等值的k进制数的次低位；第三步，重复第二步，直到最后所得的商等于0为止，各次所得的余数，便是k进制各位的数，最后一次余数是最高位，即除k取余法.要点诠释：1、在k进制中，具有k个数字符号.如二进制有0，1两个数字.2、在k进制中，由低位向高位是按“逢k进一”的规则进行计数.3、非k进制数之间的转化一般应先转化成十进制，再将这个十进制数转化为另一种进制的数，有的也可以相互转化.【巩固练习】：1．求324、243、135这三个数的最大公约数。求三个数的最大公约数可以先求出两个数的最大公约数，第三个数与前两个数的最大公约数的最大公约数即为所求。2．用更相减损术求98与63的最大公约数解：由于63不是偶数，把98和63以大数减小数，并辗转相减98－63＝3563－35＝2835－28＝7-4-28－7＝2121－7＝2114－7＝7所以，98和63的最大公约数等于73．已知一个五次多项式为8.07.16.25.325)(2345xxxxxxf用秦九韶算法求这个多项式当x=5的值。解：将多项式变形：8.0)7.1)6.2)5.3)25(((()(xxxxxxf按由里到外的顺序，依此计算一次多项式当x=5时的值：50v，272551v，5.1385.35272v，9.6896.255.1383v2.34517.159.6894v，2.172558.052.34515v所以，当x=5时，多项式的值等于17255.24．将二进制数110011(2)化成十进制数解：根据进位制的定义可知012345)2(21212020212111001112116132151所以，110011（2）=51。【课堂小结】：本节学习了用辗转相除法和更相减损术求两个数的最大公约数以及用秦九韶算法求多项式的值和不同进制的数之间的相互转化，分析比较辗转相除法和更相减损术在具体应用中的区别与联系，体会算法在解决实际问题中的应用，体验学习数学的乐趣！【板书设计】：【教学反思】本节内容比较多，而且主要是算法的具体应用，在授课过程中应以学生自主探究为主，让学生在实际演练中体会不同方法的具体应用，把书本知识转化为自己的知识，真正做到学以致用。1.3算法案例一、辗转相除法例1二、更相减损术例2三、秦九韶算法四、进位制五、巩固练习：小结作业-5-