第一章算法初步 13算法案例 第1课时 、教学目标 1.核心素养 在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力,在利用算法解决数学 问题的过程中培养理性的精神和动手实践的能力 2.学习目标 (1)通过求较大的两个数的最大公约数感知其中蕴含的数学原理 (2)理解辗转相除法与更相减损术并进行算法分析 3.学习重点 掌握辗转相除法与更相减损术求最大公约数的方法,理解二者的区别与联系 4.学习难点 认识并把握辗转相除法程序框图与程序语言 二、教学设计 (一)课前设计 1.预习任务 任务1 阅读教材P34-P37,思考:你会求两个较为简单数的最大公约数吗? 任务2 辗转相除法与更相减损术中蕴含的数学原理是什么? 2.预习自测 1.有关辗转相除法,下列说法正确的是() A.它和更相减损术一样是求多项式值的一种方法 B.基本步骤是用较大的数m除以较小的数n得到除式m=mg+r,直至rm为止 C.基本步骤是用较大的数m除以较小的数n得到除式m=q+(0≤Kn),反复进行,直到r=0 为止 D.以上说法都错误 【解析】:C由辗转相除法的含义可得,故选C 2.用更相减损术求36与134的最大公约数,第一步为() A.134-36=98
第一章 算法初步 1.3 算法案例 第 1 课时 一、教学目标 1．核心素养 在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学 问题的过程中培养理性的精神和动手实践的能力． 2．学习目标 （1）通过求较大的两个数的最大公约数感知其中蕴含的数学原理． （2）理解辗转相除法与更相减损术并进行算法分析． 3．学习重点 掌握辗转相除法与更相减损术求最大公约数的方法，理解二者的区别与联系． 4．学习难点 认识并把握辗转相除法程序框图与程序语言． 二、教学设计 （一）课前设计 1．预习任务 任务 1 阅读教材 P34－P37，思考：你会求两个较为简单数的最大公约数吗？ 任务 2 辗转相除法与更相减损术中蕴含的数学原理是什么？ 2．预习自测 1．有关辗转相除法，下列说法正确的是( ) A．它和更相减损术一样是求多项式值的一种方法 B．基本步骤是用较大的数 m 除以较小的数 n 得到除式 m＝nq＋r，直至 r<n 为止 C．基本步骤是用较大的数 m 除以较小的数 n 得到除式 m＝qn＋r(0≤r<n)，反复进行，直到 r＝0 为止 D．以上说法都错误 【解析】：C 由辗转相除法的含义可得，故选 C. 2．用更相减损术求 36 与 134 的最大公约数，第一步为( ) A．134－36＝98
B.134=3×36+26 C.先除以2,得到18与67 D.134÷36=3(余26) 【解析】:C利用更相减损术求两个数的最大公约数时,若两个数都是偶数,则首先将两个数都 除以2之后再作减法,故选C (二)课堂设计 知识回顾 (1)最大公因数:两个数的所有公因数中最大的一个数 (2)本课的辗转相除法与更相减损术对于求两数的最大公约数有什么意义? 问题探究 问题探究一如何求两个较大的数的最大公约数? ●活动一回顾旧知 在初中,我们已经学过求两数的最大公约数,你能求出18与30的最大公约数吗? 易知18与30的公约数有:2、3、6,所以18与30的最大公约数是6 我们都是利用找公约数的方法来求最大公约数,如果两个数数比较大而且根据我们的观察又不能 得到一些公约数,我们又应该怎样求它们的最大公约数?比如求8251与6105的最大公约数? ●活动二突破探索 方法分析:8251与6105两数都比较大,而且没有明显的公约数,如能把它们都变小一点,根据 已有的知识即可求出最大公约数 8251=6105×1+2146 显然8251的最大公约数也必是2146的约数,同样6105与2146的公约数也必是8251的约数, 所以8251与6105的最大公约数也是6105与2146的最大公约数以此类推: 步骤: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的最大公约数 问题探究二什么是辗转相除法与更相减损术,其算法是什么? 将上述求两个较大的数的最大公约数的方法推广至一般,以上求最大公约数的方法就是辗转相除
B．134＝3×36＋26 C．先除以 2，得到 18 与 67 D．134÷36＝3(余 26) 【解析】：C 利用更相减损术求两个数的最大公约数时，若两个数都是偶数，则首先将两个数都 除以 2 之后再作减法，故选 C． （二）课堂设计 1．知识回顾 （1）最大公因数：两个数的所有公因数中最大的一个数． （2）本课的辗转相除法与更相减损术对于求两数的最大公约数有什么意义？ 2．问题探究 问题探究一 如何求两个较大的数的最大公约数？ ●活动一 回顾旧知 在初中，我们已经学过求两数的最大公约数，你能求出 18 与 30 的最大公约数吗？ 易知 18 与 30 的公约数有：2、3、6，所以 18 与 30 的最大公约数是 6. 我们都是利用找公约数的方法来求最大公约数，如果两个数数比较大而且根据我们的观察又不能 得到一些公约数，我们又应该怎样求它们的最大公约数？比如求 8251 与 6105 的最大公约数？ ●活动二 突破探索 方法分析：8251 与 6105 两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据 已有的知识即可求出最大公约数. 8251＝6105×1＋2146 显然 8251 的最大公约数也必是 2146 的约数，同样 6105 与 2146 的公约数也必是 8251 的约数， 所以 8251 与 6105 的最大公约数也是 6105 与 2146 的最大公约数.以此类推： 步骤：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 的最大公约数. 问题探究二 什么是辗转相除法与更相减损术，其算法是什么？ 将上述求两个较大的数的最大公约数的方法推广至一般，以上求最大公约数的方法就是辗转相除
法利用辗转相除法求最大公约数的步骤如下: 第一步:用较大的数m除以较小的数n得到一个商q和一个余数n 第二步:若=0,则n为m,n的最大公约数;若≠0,则用除数n除以余数h得到一个商q1和 个余数r; 第三步:若F=0,则r为m,n的最大公约数;若n≠0,则用除数h除以余数得到一个商q2和 一个余数n2; 依次计算直至r=0,此时所得到的zn1即为所求的最大公约数 例1求下列两个数的最大公约数①378和90;②225和135 解:①378=90×4+18,90=18×5+0, ∴378与90的最大公约数是18 ②225=135×1+90, 135=90×1+45, 90=45×2 ∴45是225和135的最大公约数 我国早期也有解决求最大公约数问题的算法,就是更相减损术 更相减损术求最大公约数的步骤如下: 可半者半之,不可半者,副置分母子之数,以少减多,更相减损,求其等也,以等数约之 翻译出来为: 第一步:任意给出两个正数;判断它们是否都是偶数若是,用2约简;若不是,执行第二步 第二步:以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数继续这 个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数 例2分析下列解法错因,并用更相减损术正确写出求36和20的最大公约数的解法 错解:用更相减损术步骤如下: 36-20=16 20-16=4, 16-4=1 12-4=8 8-4=4 故36与20的最大公约数为4
法.利用辗转相除法求最大公约数的步骤如下： 第一步：用较大的数 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 ； …… 依次计算直至 n r ＝0，此时所得到的 n r −1 即为所求的最大公约数. 例 1 求下列两个数的最大公约数①378 和 90；②225 和 135. 解：①378＝90×4＋18，90＝18×5＋0， ∴378 与 90 的最大公约数是 18. ②225＝135×1＋90， 135＝90×1＋45， 90＝45×2. ∴45 是 225 和 135 的最大公约数． 我国早期也有解决求最大公约数问题的算法，就是更相减损术. 更相减损术求最大公约数的步骤如下： 可半者半之，不可半者，副置分母子之数，以少减多，更相减损，求其等也，以等数约之. 翻译出来为： 第一步：任意给出两个正数；判断它们是否都是偶数.若是，用 2 约简；若不是，执行第二步. 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这 个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数. 例 2 分析下列解法错因，并用更相减损术正确写出求 36 和 20 的最大公约数的解法. 错解：用更相减损术步骤如下： 36－20＝16， 20－16＝4， 16－4＝12， 12－4＝8， 8－4＝4， 故 36 与 20 的最大公约数为 4
解:错因:本题结果虽正确,但解题过程是错误的.错误的根源在于没有完全掌握更相减损术 的规则.更相减损术要求若两数均为偶数则要用2约简.本题出错正是忽略这一过程所致 正确解法:∵36和20都是偶数, ∴两次用2约简得9和5 用更相减损的步骤如下: 9-5=4, 5-4=1 3-1=2 ∴36和20的最大公约数为4 3.课堂总结 【知识梳理】 (1)辗转相除法的算法步骤: 第一步:给定的两个正整数, 第二步:用较大的数除以较小的数,若余数为零,则较小的数即这时的除数就是两个数的最大公 约数;若余数不为零,则将较小的数和余数构成新的一对数,继续上面的除法,直到大数被小数 除尽,则这时的除数就是原来两个数的最大公约数 (2)更相减损术是另一种求两数最大公约数的方法其算法步骤是: 第一步:任意给出两个正数;判断它们是否都是偶数若是,用2约简;若不是,执行第二步 第二步:以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数继续这 个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数 【重难点突破】 (1)辗转相除法与更相减损术的区别与联系 ①都是求最大公约数的方法 ②计算上辗转相除法以除法为主,更相减损术以减法为主; 计算次数上辗转相除法计算次数相对较少,特别当两个数字大小区别较大时计算次数的区别较明 从结果体现形式来看,辗转相除法体现结果是以相除余数为0则得到,而更相减损术则以减数与 差相等而得到 (2辗转相除法的程序框图与程序语言
解：错因：本题结果虽正确，但解题过程是错误的．错误的根源在于没有完全掌握更相减损术 的规则．更相减损术要求若两数均为偶数则要用 2 约简．本题出错正是忽略这一过程所致． 正确解法：∵36 和 20 都是偶数， ∴两次用 2 约简得 9 和 5. 用更相减损的步骤如下： 9－5＝4， 5－4＝1， 4－1＝3， 3－1＝2， 2－1＝1， ∴36 和 20 的最大公约数为 4. 3．课堂总结 【知识梳理】 (1)辗转相除法的算法步骤： 第一步：给定的两个正整数， 第二步：用较大的数除以较小的数，若余数为零，则较小的数即这时的除数就是两个数的最大公 约数；若余数不为零，则将较小的数和余数构成新的一对数，继续上面的除法，直到大数被小数 除尽，则这时的除数就是原来两个数的最大公约数. (2)更相减损术是另一种求两数最大公约数的方法.其算法步骤是： 第一步：任意给出两个正数；判断它们是否都是偶数.若是，用 2 约简；若不是，执行第二步. 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这 个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数. 【重难点突破】 (1)辗转相除法与更相减损术的区别与联系 ①都是求最大公约数的方法 ②计算上辗转相除法以除法为主，更相减损术以减法为主； 计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明 显. 从结果体现形式来看，辗转相除法体现结果是以相除余数为 0 则得到，而更相减损术则以减数与 差相等而得到. (2)辗转相除法的程序框图与程序语言
〔开始 求m除以m的余数r n=) 输出m 程序 INPUT"m=".m INPUT n=:n IF m<n then x=m mEn END IF rm mod n WHILE r0 rm mod n m-n n-l WEND PRINT m END 4.随堂检测 1.用辗转相除法求得168与486的最大公约数是() 【解析】:C486=168×2+150,168=150×1+18,150=18×8+6,18=6×3,所以168与486的 最大公约数是6,故选C 2.用更相减损术求459和357的最大公约数
程序： INPUT “m=”;m INPUT “n=”;n IF m<n THEN x=m m=n n=x END IF r=m MOD n WHILE r<>0 r=m MOD n m=n n=r WEND PRINT m END 4．随堂检测 1．用辗转相除法求得 168 与 486 的最大公约数是( ) A．3 B．4 C．6 D．16 【解析】：C 486＝168×2＋150，168＝150×1＋18，150＝18×8＋6，18＝6×3，所以 168 与 486 的 最大公约数是 6，故选 C. 2．用更相减损术求 459 和 357 的最大公约数