人教A版高中数学必修3第一章 算法初步1.3 算法案例教案

第一章 算法初步
1.3 算法案例
第1课时
一、教学目标
1．核心素养
在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力．
2．学习目标
（1）通过求较大的两个数的最大公约数感知其中蕴含的数学原理．
（2）理解辗转相除法与更相减损术并进行算法分析．
3．学习重点
掌握辗转相除法与更相减损术求最大公约数的方法，理解二者的区别与联系．
4．学习难点
认识并把握辗转相除法程序框图与程序语言．
二、教学设计
（一）课前设计
1．预习任务
任务1
阅读教材P34－P37，思考：你会求两个较为简单数的最大公约数吗？
任务2
辗转相除法与更相减损术中蕴含的数学原理是什么？
2．预习自测
1．有关辗转相除法，下列说法正确的是( )
A．它和更相减损术一样是求多项式值的一种方法
B．基本步骤是用较大的数m除以较小的数n得到除式m＝nq＋r，直至rC．基本步骤是用较大的数m除以较小的数n得到除式m＝qn＋r(0≤rD．以上说法都错误
【解析】：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．知识回顾
（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的最大公约数.
问题探究二 什么是辗转相除法与更相减损术，其算法是什么？
将上述求两个较大的数的最大公约数的方法推广至一般，以上求最大公约数的方法就是辗转相除法.利用辗转相除法求最大公约数的步骤如下：
第一步：用较大的数除以较小的数得到一个商和一个余数；
第二步：若＝0，则为，的最大公约数；若≠0，则用除数除以余数得到一个商和一个余数；
第三步：若＝0，则为，的最大公约数；若≠0，则用除数除以余数得到一个商和一个余数；
……
依次计算直至＝0，此时所得到的即为所求的最大公约数.
例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，
4－1＝3，
3－1＝2，
2－1＝1，
∴36和20的最大公约数为4.
3．课堂总结
【知识梳理】
(1)辗转相除法的算法步骤：
第一步：给定的两个正整数，
第二步：用较大的数除以较小的数，若余数为零，则较小的数即这时的除数就是两个数的最大公约数；若余数不为零，则将较小的数和余数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时的除数就是原来两个数的最大公约数.
(2)更相减损术是另一种求两数最大公约数的方法.其算法步骤是：
第一步：任意给出两个正数；判断它们是否都是偶数.若是，用2约简；若不是，执行第二步.
第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数.继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数.
【重难点突破】
(1)辗转相除法与更相减损术的区别与联系
①都是求最大公约数的方法
②计算上辗转相除法以除法为主，更相减损术以减法为主；
计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显.
从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到，而更相减损术则以减数与差相等而得到.
(2)辗转相除法的程序框图与程序语言
程序：
INPUT “m=”;m
INPUT “n=”;n
IF mm=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的最大公约数.
【解析】：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≤rA．一定是 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 用更相减损术求它们的最大公约数.
(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×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的数据分别是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
255－51＝204
204－51＝153
153－51＝102
102－51＝51
所以1 734与816的最大公约数是51×2＝102.