人教必修三1.3算法案例

学习目标1.了解辗转相除法、更相减损术，理解其中所包含 的算法思想； 2.通过模仿、操作、探索经历算法设计的全过程， 进一步体会算法的基本思想，感受算法在解决实 际问题中的重要作用； 3.学会提炼算法中的关键步骤，并转化为自然语言、 程序框图、程序语言； 4.发展有条理的思考与表达能力，提高逻辑思维能 力；

5.体会小组合作过程，培养探究精神.

回顾与思考1.什么叫算法？算法有哪些描述方法？

按照一定规则解决某一类问题的明确和有限的步骤.算法步骤、程序框图、程序. 2.在程序框图中算法的基本逻辑结构有哪些？ 顺序结构、条件结构、循环结构 3.在程序设计中基本的算法语句有哪些？ 输入语句、输出语句、赋值语句、条件语句、循环语句

情境引入问题一：在小学，我们已学过求最大公约数的知 识，你能求出18与30的最大公约数吗？

方法：先用两个数公有的质 因数连续去除,一直除到所得 的商是互质数为止,然后把所 ∴18和30的最大公约数 有的除数连乘起来. 是2×3=6.

2 18 30 3 9 15 3 5

问题二：你能求出8251与6105的最大公约数吗？

人教版 高一数学必修三第一章

算法初步

1.3.算法案例(一)——辗转相除法与更相减损术

小组活动探究1请仔细阅读课本34页的辗转相除法.模仿、操作、 探究以下问题：1.模仿课本中利用辗转相除法求8251与6105的最大 公约数的方法，求18与30的最大公约数. 2.尽量用自己的语言描述辗转相除法求两个正整数 最大公约数的过程. 3.试着说明辗转相除法求最大公约数的原理.

4.再次模仿课本，求153与119的最大公约数，并体 会辗转相除法的步骤和原理.5.你能把辗转相除法编成一个程序吗？

辗转相除法求8251和6105的最大公约数8251=6105×1+2146 6105=2146×2+1813 2146=1813×1+333

求m和n的最大公约数S1:给定两个正整数m,n S2:计算m除以n所得余数r S3:除数赋给被除数，余数赋给除数 S4:若r=0,则得到m、n的最大公 约数；否则返回S2.

1813=333×5+148 333=148×2+37148=37×4+0

r =m MOD nm=n n=r r=0

显然37是148和37的最大公 约数，也就是8251和6105的 最大公约数

辗转相除法求m和n的最大公约数S1:给定两个正整数m,n S2:计算m除以n所得余数r S3:除数赋给被除数，余数赋给除数 S4:若r=0,则得到m、n的最

用程序框图表示开始 输入m,n r=m MOD n m=n n=r r=0? 是 输出m 结束 否

大公约数；否则返回S2.

r =m MOD n

m=n n=r r=0

辗转相除法求m和n的最大公约数S1:给定两个正整数m,n S2:计算m除以n所得余数r S3:除数赋给被除数，余数赋给除数 S4:若r=0,则得到m、n的最大公 约数；否则返回S2.

用程序框图表示开始 输入m,n r=m MOD n

m=n

r =m MOD n

n=r r=0? 是 输出m 结束 否

m=n n=r r=0

小组活动探究2请类比辗转相除法的探究方法，仔细阅读课本36 页的更相减损术.模仿、操作、探究以下问题：1.模仿课本中利用更相减损术求98与63的最大公约 数的方法，求30与18的最大公约数. 2.尽量用自己的语言描述更相减损术求两个正整数 最大公约数的过程. 3.试着说明更相减损术求最大公约数的原理.

4.再次模仿课本，求72与84的最大公约数，并体会 更相减损术的步骤和原理.思考：你能把更相减损术编成一个程序吗？

请类比辗转相除法的探究方法，仔细阅读课本36 页的更相减损术.模仿、操作、探究以下问题：1.模仿课本中利用更相减损术求98与63的最大公约 数的方法，求30与18的最大公约数. 2.尽量用自己的语言描述更相减损术求两个正整数 最大公约数的过程. 3.试着说明更相减损术求最大公约数的原理.

4.再次模仿课本，求72与84的最大公约数，并体会 更相减损术的步骤和原理.思考：你能把更相减损术编成一个程序吗？

更相减损术算理：可半者半之，不可半者，副置分母、子之数， 以少减多，更相减损，求其等也，以等数约之. ——《九章算术》

S1:任意给定两个正整数m,n;判断他们是否都是 偶数。若是，则用2约简；若不是则执行S2. S2:以较大的数减较小的数，接着把所得的差与较 小的数比较，并以大数减小数。继续这个操作，直 到所得的减数和差相等为止，则这个等数就是所求 的最大公约数.

小结 1、体会算法的基本思想 2、比较辗转相除法与更相减损术的区别区别：

(1)都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数 上辗转相除法计算次数相对较少，特别当两个数字 大小区别较大时计算次数的区别较明显。 (2)从结果体现形式来看，辗转相除法体现结果

是以相除余数为0则得到，而更相减损术则以减数与差相等而得到。

达标检测 用辗转相除法求225和135的最大公约数，并用 更相减损术检验你的结果。 辗转相除法： 225=135×1+90; 135=90×1+45; 90=45×2+0. 因此45为225和135的 最大公约数 更相减损术： 225-135=90; 135-90=45; 90-45=45. 因此45为225和135的 最大公约数

思考：如何求225和135的最小公倍数？你会设计此 算法的程序么？

更相减损术用程序框图表示开始 输入m,n m<n? 否 k=0 k=k+1 m=m/2 n=n/2 m,n均为偶数? 是 否 d<>n? 否 输出2k*d 是 d = m-n

1d = m-n

a=m m=n n=am=n n=d 否 d>n? 是 是 m=d

1结束

INPUT a,b K=0 WHILE a MOD 2=0 AND b MOD 2=0 k=k+1 a=a\2 b=b\2 WEND WHILE a<>b IF a>b THEN a=a-b ELSE b=b-a END IF WEND PRINT b*2^n END

作业 1、阅读课本34~36

页，复习巩固； 2、课本45页练习1、48页习题1; 3、类比本课学习方法，预习秦九韶算法和 进位制；

4、上网搜索有关古代算法案例，互相交流.