2013苏教版必修31.4“算法案例”课件.pptVIP

本部分内容讲解结束 点此进入课件目录 按ESC键退出全屏播放 谢谢使用 * 第1章　算法初步 1．4　算法案例 学习目标 1.体会三个案例的算法思想； 2．会用辗转相除法求两个正数的最大公约数． 课堂互动讲练 知能优化训练 1.4　算法案例 课前自主学案 课前自主学案 温故夯基 1．三种循环语句的一般形式分别是什么？ 当型语句　　While P 　 循环体 End While 直到型语句 Do 　 循环体 Until　P End Do For语句 For I from “初值”To“终值”SteP“步长” 　 循环体 End For 2．当型循环与直到型循环语句的区别 (1)当型循环是先判断(条件)，后执行(循环体)，而直到型循环则是先执行(循环体)，后判断(条件)． (2)当型循环是当条件满足时执行循环体，不满足时结束循环，而直到型循环则是条件不满足时执行循环体，条件满足时结束循环． (3)直到型循环至少执行一次循环体，而当型循环可能一次也不执行循环体． 知新益能 1．辗转相除法 所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时的较小的数就是原来两个数的________________ 最大公约数． 2．更相减损术 所谓更相减损术就是对于给定的两个数，以两数中较大的数减去较小的数，然后将差和较小的数构成一对新数，再用较大的数减去较小的数，反复执行此步骤直到差和较小的数相等，此时相等的两数便为原来两数的______________ 最大公约数． 3．中国剩余定理(或孙子剩余定理) 其最早出现在我国《算经十书》之一的《孙子算经》中．原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二．问物几何？答曰：二十三．”自从《孙子算经》中提出这个“物不知数”问题之后，它便引起了人们很大的兴趣． 《孙子算经》中给出了求解的关键步骤，南宋数学家秦九韶对该问题加以推广，又发现了一种新的算法，叫“大衍求一术”．人们将这种问题的通用解法称为“_____________”或“中国剩余定理”． 孙子剩余定理 4．秦九韶算法 课堂互动讲练 考点突破 求两个数的最大公约数 求两个正整数的最大公约数可用辗转相除法或更相减损术．二者的主要区别在于辗转相除法进行的是除法运算，即辗转相除；而更相减损术进行的是减法运算，即辗转相减，它们在步骤上虽然略有不同，但在理论上是一致的，都是一个不断的递归过程． 用辗转相除法求612与468的最大公约数，并用更相减损术检验所得结果． 【思路点拨】　将612作大数，468作小数，执行辗转相除法和更相减损术即可． 【解】　用辗转相除法： 612＝468×1＋144,468＝144×3＋36,144＝36×4，即612和468的最大公约数是36. 用更相减损术： 612和468为偶数，∴两次用2约简得153和117,153－117＝36,117－36＝81,81－36＝45,45－36＝9,36－9＝27,27－9＝18,18－9＝9， 所以612和468的最大公约数为9×2×2＝36. 例1 【思维总结】　辗转相除法是当大数被小数除尽时，结束除法运算，较小的数就是最大公约数．更相减损术是先判断两个数是否均为偶数，若是，用2约简，否则用大数减小数，当大数减小数的差等于小数时减法停止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数． 自我挑战1　用辗转相除法、更相减损术求228,1995的最大公约数． 解：用辗转相除法： 1995＝8×228＋171 228＝1×171＋57 171＝3×57＋0 所以：57就是228和1995的最大公约数．用更相减损术： 1995－228＝1767 1767－228＝1539 1539－228＝1311 1311－228＝1083 1083－228＝855 855－228＝627 627－228＝399 399－228＝171 228－171＝57 171－57＝114 114－57＝57 57－57＝0 则57就是228,1995的最大公约数． 秦九韶算法 秦九韶算法适用于一般的多项式f(x)＝anxn＋an－1xn－1＋…＋a1x＋a0的求值问题，秦九韶算法的特点在于把求一个n次多项式的值转化为求n个一次多项式的值，即把求