河北省武邑中学高中数学 1.3.1算法案例辗转相除法与更相减损术教案 新人教A版必修3
备课人 授课时间
课题 §1.3.1算法案例——辗转相除法与更相减损术
课标要求 理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
教
学
目
标 知识目标 在辗转相除法与更相减损术求最大公约数的学习过程中对比我们常见的约分求公因式的方法，比较它们在算法上的区别，并从程序的学习中体会数学的严谨，领会数学算法计算机处理的结合方式，初步掌握把数学算法转化成计算机语言的一般步骤。
技能目标 通过具体的实例，掌握循环语句的具体应用，利用循环语句表达具体问题的过程，体会算法的基本思想借助框图中的循环结构，借助Scilab语言中的循环语句来设计程序，进一步体会算法的重要性和有效性
情感态度价值观 在学习古代数学家解决数学问题的方法的过程中培养严谨的逻辑思维能力，在利用算法解决数学问题的过程中培养理性的精神和动手实践的能力。
重点 理解辗转相除法与更相减损术求最大公约数的方法。
难点 把辗转相除法与更相减损术的方法转换成程序框图与程序语言。
教 问题与情境及教师活动 学生活动
学
过
程
及
方
法 一．复习引入
思考1：18与30的最大公约数是多少？你是怎样得到的？
（1）短除法
求两个正整数的最大公约数的步骤：先用两个数公有的质因数连续去除，一直除到所得的商是两个互质数为止，然后把所有的除数连乘起来.
（2）穷举法（也叫枚举法）
穷举法求两个正整数的最大公约数的解题步骤：从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数.
思考2：:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难
二．研探新知
探究一:辗转相除法
思考1：对于8251与6105这两个数，注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公
word
1 / 5 必修3第一章1.3算法案例:案例3进位制
[教学目标]：
（1） 了解各种进位制与十进制之间转换的规律，会利用各种进位制与十进制之间的联系进行各种进位制之间的转换。
（2） 学习各种进位制转换成十进制的计算方法，研究十进制转换为各种进位制的除k去余法，并理解其中的数学规律。
[教学重点]各进位制表示数的方法及各进位制之间的转换
[教学难点]除k取余法的理解
[情感态度价值观] 学生通过合作完成任务，领悟十进制，二进制的特点，了解计算机与二进制的联系，进一步认识到计算机与数学的联系,培养他们的合作精神和严谨的态度。
[教学方法] 讲解法、尝试法、归纳法、讨论法、
[教学用具] 多媒体电脑
[学法] 学习各种进位制特点的同时探讨进位制表示数与十进制表示数的区别与联系，熟悉各种进位制表示数的方法，从而理解十进制转换为各种进位制的除k取余法。
[教学过程]
一、创设情景，揭示课题
辗转相除法和更相减损术，是求两个正整数的最大公约数的算法，秦九韶算法是求多项式的值的算法，将这些算法转化为程序，就可以由计算机来完成相关运算。人们为了计数和运算方便，约定了各种进位制，本节课我们来共同学习《进位制》
你都了解那些进位制？比如说？
在日常生活中，我们最熟悉、最常用的是十进位制，据说这与古人曾以手指计数有
关；由于计算机的计算与记忆元件特点，计算机上通用的是二进位制；一周七天是
七进位；一年十二个月〔生肖、一打〕是十二进制；旧式的称是十六进制；〔老称一
斤为16两，故而有了半斤八两之说〕、24进制〔节气〕一小时六十分、角度的单位
是六十进位制。
二进制是有德国数学家莱布尼兹发明的。第一台计算机ENIAC〔埃尼阿克〕用的就是
十进制。计算机之父冯·诺伊曼研究后，提出改进意见，用二进制替代十进制。
主要原因①二进制只有0和1两个数字，要得到两种不同稳定状态的电子器件很容 word
2 / 5 易，而且制造简单，可靠性高；②各种计数法中，二进制运算规那么简单。如：十进
时 案例2 秦九韶算法
（一）导入新课
思路1（情境导入）
大家都喜欢吃苹果吧，我们吃苹果都是从外到里一口一口的吃，而虫子却是先钻到苹果里面从里到外一口一口的吃，由此看来处理同一个问题的方法多种多样.怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？方法也是多种多样的，今天我们开始学习秦九韶算法.
思路2（直接导入）
前面我们学习了辗转相除法与更相减损术， 今天我们开始学习秦九韶算法.
（二）推进新课、新知探究、提出问题
（1）求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值有哪些方法？比较它们的特点.
（2）什么是秦九韶算法？
（3）怎样评价一个算法的好坏？
讨论结果：
（1）怎样求多项式f(x)=x5+x4+x3+x2+x+1当x=5时的值呢？
一个自然的做法就是把5代入多项式f(x)，计算各项的值，然后把它们加起来，这时，我们一共做了1+2+3+4=10次乘法运算，5次加法运算.
另一种做法是先计算x2的值，然后依次计算x2·x，（x2·x）·x，（（x2·x）·x）·x的值，这样每次都可以利用上一次计算的结果，这时，我们一共做了4次乘法运算，5次加法运算.
第二种做法与第一种做法相比，乘法的运算次数减少了，因而能够提高运算效率，对于计算机来说，做一次乘法运算所用的时间比做一次加法运算要长得多，所以采用第二种做法，计算机能更快地得到结果.
（2）上面问题有没有更有效的算法呢？我国南宋时期的数学家秦九韶（约1202~1261）在他的著作《数书九章》中提出了下面的算法：
把一个n次多项式f(x)=anxn+an-1xn-1+…+a1x+a0改写成如下形式：
f(x)=anxn+an-1xn-1+…+a1x+a0
=（anxn-1+an-1xn-2+…+a1）x+ a0
=（（anxn-2+an-1xn-3+…+a2）x+a1)x+a0
第一章 算法初步1.3 算法案例
1．求两个正整数的最大公约数的算法
（1）辗转相除法
①定义：辗转相除法是用于求_____________的最大公约数的一种算法，这种算法是由欧几里得在公元前300年左右首先提出的，因而又叫欧几里得算法．就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成一对新数，继续上面的除法，直到余数为零，则这时较小的数就是原来两个数的最大公约数．
②算法步骤
用辗转相除法求两个正整数的最大公约数，其算法步骤如下：
第一步，给定两个正整数,mn．
第二步，计算m除以n所得的余数r．
第三步，,mnnr．
第四步，若0r，则,mn的最大公约数等于m；否则，返回第二步．
③程序框图如图所示：
④程序如下：
INPUT m，n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END 或 INPUT m，n
r=1
While r>0
r=m MOD n
m=n
n=r
WEND
PRINT m
END
（2）更相减损术
①定义：中国古代的数学专著《九章算术》中记载着“更相减损术”，即“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也．以等数约之．”
②算法步骤
第一步，任意给定两个正整数，判断它们是否都是偶数．若是，用2约简；若不是，执行第二步．
第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数．继续这个操作，直到所得的数相等为止，则这个数(等数)或这个数与约简的数的乘积就是所求的最大公约数．
③程序框图
④程序如下：
INPUT “a，b=”;a，b
WHILE a≠b
r=a−b
IF b>r THEN
a=b
b=r
ELSE
a=r
END IF
