算法案例 人教版高中数学必修3教材教案.docx
《算法案例 人教版高中数学必修3教材教案.docx》由会员分享,可在线阅读,更多相关《算法案例 人教版高中数学必修3教材教案.docx(10页珍藏版)》请在冰点文库上搜索。
算法案例人教版高中数学必修3教材教案
1.3算法案例
授课时间:
第周年月日(星期)
三维目标
1.理解算法案例的算法步骤和程序框图.
2.引导学生得出自己设计的算法程序.
3.体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力.
重点难点
教学重点:
引导学生得出自己设计的算法步骤、程序框图和算法程序.
教学难点:
体会算法的基本思想,提高逻辑思维能力,发展有条理地思考与数学表达能力.
第1课时案例1辗转相除法与更相减损术
导入新课
思路1(情境导入)
大家喜欢打乒乓球吧,由于东、西方文化及身体条件的不同,西方人喜欢横握拍打球,东方人喜欢直握拍打球,对于同一个问题,东、西方人处理问题方式是有所不同的.在小学,我们学过求两个正整数的最大公约数的方法:
先用两个数公有的质因数连续去除,一直除到所得的商是互质数为止,然后把所有的除数连乘起来.当两个数公有的质因数较大时(如8251与6105),使用上述方法求最大公约数就比较困难.下面我们介绍两种不同的算法——辗转相除法与更相减损术,由此可以体会东、西方文化的差异.
思路2(直接导入)
前面我们学习了算法步骤、程序框图和算法语句.今天我们将通过辗转相除法与更相减损术来进一步体会算法的思想.
推进新课
新知探究
提出问题
(1)怎样用短除法求最大公约数?
(2)怎样用穷举法(也叫枚举法)求最大公约数?
(3)怎样用辗转相除法求最大公约数?
(4)怎样用更相减损术求最大公约数?
讨论结果:
(1)短除法
求两个正整数的最大公约数的步骤:
先用两个数公有的质因数连续去除,一直除到所得的商是两个互质数为止,然后把所有的除数连乘起来.
(2)穷举法(也叫枚举法)
穷举法求两个正整数的最大公约数的解题步骤:
从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数.
(3)辗转相除法
辗转相除法求两个数的最大公约数,其算法步骤可以描述如下:
第一步,给定两个正整数m,n.
第二步,求余数r:
计算m除以n,将所得余数存放到变量r中.
第三步,更新被除数和余数:
m=n,n=r.
第四步,判断余数r是否为0.若余数为0,则输出结果;否则转向第二步继续循环执行.
如此循环,直到得到结果为止.这种算法是由欧几里得在公元前300年左右首先提出的,因而又叫欧几里得算法.
(4)更相减损术
我国早期也有解决求最大公约数问题的算法,就是更相减损术.《九章算术》是中国古代的数学专著,其中的“更相减损术”也可以用来求两个数的最大公约数,即“可半者半之,不可半者,副置分母、子之数,以少减多,更相减损,求其等也.以等数约之.”翻译为现代语言如下:
第一步,任意给定两个正整数,判断它们是否都是偶数,若是,用2约简;若不是,执行第二步.
第二步,以较大的数减去较小的数,接着把所得的差与较小的数比较,并以大数减小数,继续这个操作,直到所得的数相等为止,则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数.
应用示例
例1用辗转相除法求8251与6105的最大公约数,写出算法分析,画出程序框图,写出算法程序.
解:
用两数中较大的数除以较小的数,求得商和余数:
8251=6105×1+2146.
由此可得,6105与2146的公约数也是8251与6105的公约数,反过来,8251与6105的公约数也是6105与2146的公约数,所以它们的最大公约数相等.
对6105与2146重复上述步骤:
6105=2146×2+1813.
同理,2146与1813的最大公约数也是6105与2146的最大公约数.继续重复上述步骤:
2146=1813×1+333,
1813=333×5+148,
333=148×2+37,
148=37×4.
最后的除数37是148和37的最大公约数,也就是8251与6105的最大公约数.
这就是辗转相除法.由除法的性质可以知道,对于任意两个正整数,上述除法步骤总可以在有限步之后完成,从而总可以用辗转相除法求出两个正整数的最大公约数.
算法分析:
从上面的例子可以看出,辗转相除法中包含重复操作的步骤,因此可以用循环结构来构造算法.
算法步骤如下:
第一步,给定两个正整数m,n.
第二步,计算m除以n所得的余数为r.
第三步,m=n,n=r.
第四步,若r=0,则m,n的最大公约数等于m;否则,返回第二步.
程序框图如右图:
程序:
INPUTm,n
DO
r=mMODn
m=n
n=r
LOOPUNTILr=0
PRINTm
END
强调:
从教学实践看,有些学生不能理解算法中的转化过程,例如:
求8251与6105的最大公约数,为什么可以转化为求6105与2146的公约数.因为8251=6105×1+2146,可以化为8251-6105×1=2164,所以公约数能够整除等式两边的数,即6105与2146的公约数也是8251与6105的公约数.
变式训练
你能用当型循环结构构造算法,求两个正整数的最大公约数吗?
试画出程序框图和程序.
解:
当型循环结构的程序框图如下图:
程序:
INPUTm,n
r=1
WHILEr>0
r=mMODn
m=n
n=r
WEND
PRINTm
END
例2用更相减损术求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.
强调:
更相减损术与辗转相除法的比较:
尽管两种算法分别来源于东、西方古代数学名著,但是二者的算理却是相似的,有异曲同工之妙.主要区别在于辗转相除法进行的是除法运算,即辗转相除;而更相减损术进行的是减法运算,即辗转相减,但是实质都是一个不断的递归过程.
变式训练
用辗转相除法或者更相减损术求三个数324,243,135的最大公约数.
解:
324=243×1+81,
243=81×3+0,
则324与243的最大公约数为81.
又135=81×1+54,81=54×1+27,
54=27×2+0,
则81与135的最大公约数为27.
所以,三个数324、243、135的最大公约数为27.
另法:
324-243=81,243-81=162,162-81=81,则324与243的最大公约数为81.
135-81=54,81-54=27,54-27=27,则81与135的最大公约数为27.
所以,三个数324、243.135的最大公约数为27.
例3
(1)用辗转相除法求123和48的最大公约数.
(2)用更相减损术求80和36的最大公约数.
解:
(1)辗转相除法求最大公约数的过程如下:
123=2×48+27,
48=1×27+21,
27=1×21+6,
21=3×6+3,
6=2×3+0,
最后6能被3整除,得123和48的最大公约数为3.
(2)我们将80作为大数,36作为小数,因为80和36都是偶数,要除公因数2.
80÷2=40,36÷2=18.
40和18都是偶数,要除公因数2.
40÷2=20,18÷2=9.
下面来求20与9的最大公约数,
20-9=11,
11-9=2,
9-2=7,
7-2=5,
5-2=3,
3-2=1,
2-1=1,
可得80和36的最大公约数为22×1=4.
强调:
对比两种方法控制好算法的结束,辗转相除法是到达余数为0,更相减损术是到达减数和差相等.
变式训练
分别用辗转相除法和更相减损术求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.
∴1734与816的最大公约数是51×2=102.
利用更相减损术可另解:
1734-816=918,
918-816=102,
816-102=714,
714-102=612,
612-102=510,
510-102=408,
408-102=306,
306-102=204,
204-102=102.
∴1734与816的最大公约数是102.
知能训练
求319,377,116的最大公约数.
解:
377=319×1+58,
319=58×5+29,
58=29×2.
∴377与319的最大公约数为29,再求29与116的最大公约数.
116=29×4.
∴29与116的最大公约数为29.
∴377,319,116的最大公约数为29.
拓展提升
试写出利用更相减损术求两个正整数的最大公约数的程序.
解:
更相减损术程序:
INPUT“m,n=”;m,n
WHILEm<>n
IFm>nTHEN
m=m-n
ELSE
m=n-m
ENDIF
WEND
PRINTm
END
课堂小结
(1)用辗转相除法求最大公约数.
(2)用更相减损术求最大公约数.
思想方法:
递归思想.
作业
分别用辗转相除法和更相减损术求261,319的最大公约数.
分析:
本题主要考查辗转相除法和更相减损术及其应用.使用辗转相除法可依据m=nq+r,反复执行,直到r=0为止;用更相减损术就是根据m-n=r,反复执行,直到n=r为止.
解:
辗转相除法:
319=261×1+58,
261=58×4+29,
58=29×2.
∴319与261的最大公约数是29.
更相减损术:
319-261=58,
261-58=203,
203-58=145,
145-58=87,
87-58=29,
58-29=29,∴319与261的最大公约数是29.