1.3算法案例 第1课时 求最大公约数.pptVIP

1.3 算法案例 第1课时 求最大公约数必修三淮阳红旗中学 顾敬霞 〖 教学目标〗1.理解辗转相除法与更相减损术蕴含的数学原理;2.会灵活运用两种方法求得最大公约数;3.在解决数学问题的方法的过程中培养严谨的逻辑思维能力. 3 59 15〖创设情景，揭示课题〗18 3023∴18和30的最大公约数是2×3=6.先用这两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.案例1 辗转相除法与更相减损术[问题1]：在小学，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？ 〖创设情景，揭示课题〗[问题2]:我们都是利用找公约数的方法来求最大公约数，如果两个数比较大而且根据我们的观察又不能得到一些公约数，我们又应该怎样求它们的最大公约数？比如求8251与6105的最大公约数? 1.辗转相除法操作方法： 对于任意给定的两个正整数，用较大的数除以较小的数， 若余数不为零，则将余数与较小的数构成一对新数，继续 上面的除法依次下去，直到余数为零，最后式子的除数是 所求的最大公约数例1 求两个正数225和135的最大公约数。解：225＝135×1＋90;135＝90×1＋45;90＝45×2则45为225与135的最大公约数。 例2 求两个正数8251和6105的最大公约数。解：8251＝6105×1＋2146;6105＝2146×2＋1813;2146＝1813×1＋333;1813＝333×5＋148;333＝148×2＋37;148＝37×4＋0.则37为8251与6105的最大公约数。 以上我们求最大公约数的方法就是辗转相除法。也叫欧几里德算法，它是由欧几里德在公元前300年左右首先提出的。 2.更相减损术: 我国早期也有解决求最大公约数问题的算法，就是更相减损术。 步骤据记载：第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。 例1 用更相减损术求98与63的最大公约数.解：由于63不是偶数，把98和63以大数减小数，并辗转相减 即：98－63＝35; 63－35＝28; 35－28＝7; 28－7＝21; 21－7＝14; 14－7＝7.所以，98与63的最大公约数是7。 例2：用更相减损术求两个正数84与72的最大公约数解：由于84和72都是偶数，用2约简两次为21和18即：21－18＝3; 18－3＝15; 15－3＝12; 12－3＝9; 9－3＝6; 6－3＝3.注意 3×4=12 84与72的最大公约数是12。 用辗转相除法或更相减损术求下列两组正整数的最大公约数①378 90 ②153 119学以致用:答案: 18 17 辗转相除法和更相减损术的区别与联系名称辗转相除法更相减损术区别①以除法为主②两个整数的差值较大时运算次数较少③余数为零时得结果①以减法为主②两个整数的差值较大时运算次数较多③两数相等时得结果④相减前要进行是否都是偶数的判断联系①都是求最大公约数的方法②实质都是递归的过程③算法都要用循环结构来实现 1、下列说法中正确的是（ ） ①辗转相除法也叫欧几里得算法 ②辗转相除法的基本步骤是用较大的数除以较小的数 ③求最大公约数的方法，除了辗转相除法以外，没有其他方法 ④编写辗转相除法的程序，要用到循环语句 A 1个 B 2个 C 3个 D 4个2、下列说法错误的是（ ） A.辗转相除法与更相减损术都是用来求最大公约数的 B.更相减损术与辗转相除法相比，计算次数较多，因此此算法不好不能用此法 C.更相减损术是我国古代数学专著《九章算术》中提出的 D.更相减损术的基本步骤是用较大数减去较小数3、利用更相减损术或辗转相除法求1734和816的最大公约数学生天地： 自练 互讲 互学 布置作业课后作业： 1、习题1.3 ： T1、2 2、导学案 <基础题> < 提高题> 3、试着写出更相减损术和辗转相除法求最大公约数的算法步骤和对 应的程序框图和程序语句 惟有埋头，才能出头，急于出人头地，除了自寻苦恼之外，不会真正得到什么。——莎翁