第一章算法初步 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 m0 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 的最大公约数
【解析】:51∵459-357=102,357-102=255,255-102=153,153-102=51,102-51=51, 51是459与357的最大公约数 (三)课后作业 基础型自主突破 1.用更相减损术求36与134的最大公约数,第一步为() A.134-36=98 B.134=3×36+26 C.先除以2,得到18与67D.134÷36=3(余26) 【解析】:C更相减损术的算法第一步要求若两数均为偶数则要用2约简,故选C 2.用辗转相除法”求得459和357的最大公约数是() B.9C. 【解析】:D459=357×1+102,357=102×3+51,102=51×2+0,故选D 3.用辗转相除法求294和84的最大公约数时,需要做除法的次数是( B 2 C 【解析】:B294=84×3+42,84=42×2,至此最大公约数便已求出,故选B 4.在m=mg+10≤Kn)中,若k是n、r的公约数,则k(m、n的公约数 A.一定是B.不一定是C.一定不是 不能确定 【解析】:A由辗转相除法的原理可知若k是n、r的公约数,则k一定是m的约数,所以k 定是m、n的公约数故选A 5.运行下面的程序,当输入n=840和m=1764时,输出结果是() INPUT m, n =m modn m-n LOOP UNTIL I =o PRINT m END B.12 C.168 D.252 【解析】:A∵1764=840×2+84,840=84×10,∴1764与840的最大公约数为84 能力型师生共研 6.下列各组数的最大公约数不正确的是() A.16和12的最大公约数是4 B.78和36的最大公约数是6 C.85和357的最大公约数是34D.105和315的最大公约数是105 【解析】:C用更相减损术求它们的最大公约数
【解析】：51 ∵459－357＝102，357－102＝255，255－102＝153，153－102＝51，102－51＝51， ∴51 是 459 与 357 的最大公约数. （三）课后作业 基础型自主突破 1．用更相减损术求 36 与 134 的最大公约数，第一步为( ) A．134－36＝98 B．134＝3×36＋26 C．先除以 2，得到 18 与 67 D．134÷36＝3(余 26) 【解析】：C 更相减损术的算法第一步要求若两数均为偶数则要用 2 约简，故选 C 2．用“辗转相除法”求得 459 和 357 的最大公约数是( ) A．3 B．9 C．17 D．51 【解析】：D 459＝357×1＋102，357＝102×3＋51，102＝51×2＋0，故选 D. 3．用辗转相除法求 294 和 84 的最大公约数时，需要做除法的次数是( ) A．1 B．2 C．3 D．4 【解析】：B 294＝84×3＋42，84＝42×2，至此最大公约数便已求出，故选 B. 4．在 m＝nq＋r(0≤r<n)中，若 k 是 n、r 的公约数，则 k ( )m、n 的公约数 A．一定是 B．不一定是 C．一定不是 D．不能确定 【解析】：A 由辗转相除法的原理可知若 k 是 n、r 的公约数，则 k 一定是 m 的约数，所以 k 一 定是 m、n 的公约数.故选 A. 5．运行下面的程序，当输入 n＝840 和 m＝1764 时，输出结果是( ) A．84 B．12 C．168 D．252 【解析】：A ∵1764＝840×2＋84，840＝84×10，∴1764 与 840 的最大公约数为 84. 能力型师生共研 6．下列各组数的最大公约数不正确的是( ) A．16 和 12 的最大公约数是 4 B．78 和 36 的最大公约数是 6 C．85 和 357 的最大公约数是 34 D．105 和 315 的最大公约数是 105 【解析】：C 用更相减损术求它们的最大公约数. INPUT m，n DO r=m MOD n m=n n=r LOOP UNTIL r=0 PRINT m END
(85,357)+(85,272)(85,187)+(85,102)+(85,17)→(68,17)+(51,17)(34,17)(17, 17),所以85和357的最大公约数是17,故选C 7.(1)用辗转相除法求840与1596的最大公约数 (2)用更相减损术求561与357的最大公约数 【解析】:(1)84(2)51 (1)1596=840+756,840=756+84,756=84×9 所以840与1596的最大公约数为84 (2)561-357=204 357-204=153 204-153=102 153-102=51 102-51=51 所以459与357的最大公约数为51 8.有甲、乙、丙三种溶液分别重147g、343g、133g,现要将它们分别全部装入小瓶中(最后一 个瓶子也装满),每个小瓶装入液体的质量相同,则每瓶最多装多少溶液? 【解析】:每个小瓶的溶液的质量应是147,343,133的公约数,最大质量即是其最大公约数 先求147与343的最大公约数 343-147=196 196-147=49 147-49=98 98-49=49 所以147与343的最大公约数是49 再求49与133的最大公约数: 133-49=84 49-35=14 35-14=21 21-14=7 14-7=7 所以49与133的最大公约数为7,因此147,343,133的最大公约数为7即每瓶最多装7g溶液 探究型多维突破
(85，357)→(85，272)→(85，187)→(85，102)→(85，17)→(68，17)→(51，17)→(34，17)→(17， 17)，所以 85 和 357 的最大公约数是 17，故选 C. 7．(1)用辗转相除法求 840 与 1596 的最大公约数． (2)用更相减损术求 561 与 357 的最大公约数． 【解析】：(1) 84 (2)51 (1)1596＝840＋756，840＝756＋84,756＝84×9 所以 840 与 1596 的最大公约数为 84. (2)561－357＝204 357－204＝153 204－153＝102 153－102＝51 102－51＝51 所以 459 与 357 的最大公约数为 51. 8．有甲、乙、丙三种溶液分别重 147g、343g、133g，现要将它们分别全部装入小瓶中（最后一 个瓶子也装满），每个小瓶装入液体的质量相同，则每瓶最多装多少溶液？ 【解析】：每个小瓶的溶液的质量应是 147，343，133 的公约数，最大质量即是其最大公约数. 先求 147 与 343 的最大公约数： 343－147＝196 196－147＝49 147－49＝98 98－49＝49 所以 147 与 343 的最大公约数是 49. 再求 49 与 133 的最大公约数： 133－49＝84 84－39＝35 49－35＝14 35－14＝21 21－14＝7 14－7＝7 所以 49 与 133 的最大公约数为 7，因此 147，343，133 的最大公约数为 7.即每瓶最多装 7 g 溶液. 探究型多维突破
9.求612、396、264的最大公约数 【解析】:12由辗转相除法可得:612=396×1+216,396=216×1+180,216=180×1+36,180=36×5, 所以612和396的最大公约数为36 又264=36×7+12,36=12×3,所以264和36的最大公约数为12; 综上三个数612,396,264的最大公约数是12 10.求225和135的最小公倍数 【解析】:675∵225=135×1+90,135=90×1+45,90=45×2, ∴45是225和135的最大公约数 225和135的最小公倍数为(225×13545=675 自助餐 1.930与868的最大公约数是 【解析】:62∵930=868×1+62,868=62×14,∴930与868的最大公约数为62 2.用更相减损术,求105与30的最大公约数时,需要做减法的次数是() 【解析】:C105-30=75,75-30=45,45-30=15,30-15=15故选C 3.如图所示的程序表示的算法是() INPUt m, n DO [=m MOD n-I LOOP UNTIL r=0 PRINT m END A.交换m、n的值 B.辗转相除法 C.更相减损术D.秦九韶算法 【解析】:B由本节课所学的辗转相除法的原理及其算法可知,故选B. 阅读程序:
9．求 612、396、264 的最大公约数. 【解析】：12 由辗转相除法可得：612=396×1+216，396=216×1+180，216=180×1+36，180=36×5， 所以 612 和 396 的最大公约数为 36； 又 264=36×7+12，36=12×3，所以 264 和 36 的最大公约数为 12； 综上三个数 612，396，264 的最大公约数是 12. 10．求 225 和 135 的最小公倍数. 【解析】：675 ∵225＝135×1＋90， 135＝90×1＋45， 90＝45×2， ∴45 是 225 和 135 的最大公约数. ∴225 和 135 的最小公倍数为(225×135)/45＝675. 自助餐 1．930 与 868 的最大公约数是________． 【解析】：62 ∵930＝868×1＋62， 868＝62×14，∴930 与 868 的最大公约数为 62. 2．用更相减损术，求 105 与 30 的最大公约数时，需要做减法的次数是( ) A．2 B．3 C．4 D．5 【解析】：C 105－30＝75，75－30＝45，45－30＝15，30－15＝15.故选 C. 3．如图所示的程序表示的算法是( ) A．交换 m、n 的值 B．辗转相除法 C．更相减损术 D．秦九韶算法 【解析】：B 由本节课所学的辗转相除法的原理及其算法可知，故选 B. 4．阅读程序：
INPUT“m,n=”:m,n IFn>m then END IF O T=m mod n LOOP UNTIL I=0 PRINT m END 若 INPUT语句中输入m、n的数据分别是72、168,则程序运行的结果为 【解析】:24该程序是用辗转相除法求两个数的最大公约数的算法程序,输入η2、168,即求 它们的最大公约数,可求出它们的最大公约数为24 5.若INT(x)表示不超过x的最大整数(如INT(43)=4,INT(4)=4),则下列程序的目的是( INPUTX,y WHILE m/n<INT(m/n) c=m-INT(m/n)n m-n WEND PRINT n END A.求x,y的最小公倍数 B.求x,y的最大公约数 C.求x被y除的商 D.求y除以x的余数 【解析】:B这个程序实质上就是辗转相除法,主要用于求两个正整数的最大公约数 6.分别用辗转相除法和更相减损术求1734和816的最大公约数. 【解析】:辗转相除法:1734=816×2+102,816=102×8+0, 所以1734与816的最大公约数是102 更相减损术:因为两数皆为偶数,首先除以2得到867和408 再求867与408的最大公约数 867-408=459 459-408=51 408-51=357 357-51=306 306-51=255
若 INPUT 语句中输入 m、n 的数据分别是 72、168，则程序运行的结果为________. 【解析】：24 该程序是用辗转相除法求两个数的最大公约数的算法程序，输入 72、168，即求 它们的最大公约数，可求出它们的最大公约数为 24. 5．若 INT(x)表示不超过 x 的最大整数(如 INT(4.3)＝4，INT(4)＝4)，则下列程序的目的是( ) A．求 x，y 的最小公倍数 B．求 x，y 的最大公约数 C．求 x 被 y 除的商 D．求 y 除以 x 的余数 【解析】：B 这个程序实质上就是辗转相除法，主要用于求两个正整数的最大公约数. 6．分别用辗转相除法和更相减损术求 1734 和 816 的最大公约数. 【解析】：辗转相除法：1734＝816×2＋102，816＝102×8+0， 所以 1734 与 816 的最大公约数是 102. 更相减损术：因为两数皆为偶数，首先除以 2 得到 867 和 408； 再求 867 与 408 的最大公约数. 867－408＝459 459－408＝51 408－51＝357 357－51＝306 306－51＝255 INPUT “m，n＝”；m，n IF n>m THEN t＝m m＝n n＝t END IF DO r＝m MOD n m＝n n＝r LOOP UNTIL r＝0 PRINT m END INPUT x，y m＝x n＝y WHILE m/n<>INT(m/n) c＝m－INT(m/n)*n m＝n n＝c WEND PRINT n END
255-51=204 204-51=153 153-51=102 102-51=51 所以1734与816的最大公约数是51×2=102
255－51＝204 204－51＝153 153－51＝102 102－51＝51 所以 1 734 与 816 的最大公约数是 51×2＝102