ruize
忻州二中高一数学学科学案
（必修三）第一章 算法初步 第三节 算法案例
辗转相除法与更相减损术
（ 主编：翟全福 审核：朱爱荣 终审：杜慧兰 编号：12041 启用： ）
【学习目标】1.知道辗转相除法与更相减损术的含义,并了解其过程.
2.进一步体会算法的基本思想.
【文本研读】研读要求：
阅读课本第34页------第37页完成以下几个问题：
1.辗转相除法的算法思想是什么？你能阐述一下其算法步骤吗？
2.你能写出辗转相除法的程序框图及程序吗？
3.更相减损术的算法思想是什么？你能阐述一下其算法步骤吗？
4.你能写出更相减损术的程序框图及程序吗？
【思维导图】
【尝试探究】
DC复述识记题：
1.复述辗转相除法求最大公约数的步骤
2. .复述更相减损术求最大公约数的步骤
DC阅读思考：
课本第36页的例1。
ruize
DC针对练习题：
1.下列说法中正确的个数为
A. 辗转相除法也叫欧几里得算法;
B. 辗转相除法的基本步骤是用较大的数除以较小的数;
C. 求最大公约数的方法,除辗转相除法外,没有其他的方法;
D. 编写辗转相除法的程序时,要用到循环语句.
2..用辗转相除法求840和1785的最大公约数.
BA典型强化题：
1.用更相减损术求295和85的最大公约数.
2.用辗转相除法求1743和816的最大公约数.
BA自主设计：
ruize
【学习总结】课前疑惑：
课间得失：
课后反思：
学程考评 课前学案完成情况：
课间学案充实情况：
学习成果汇报展示情况 学组 次 学班 次
其中：质疑 答疑 评价 语示 板示 电示
研卷知古今；藏书教子孙。
高一数学必修3 编号_5_ 时间________班级___ 组别___ 姓名___
【学习目标】
1．理解辗转相除法与更相减损法的含义，了解其过程.
2．掌握秦九韶算法的计算过程，并了解它提高计算效率的实质.
3．进一步体会算法的基本思想.
【重点、难点】
1． 理解辗转相除法与更相减损法的含义
2． 掌握秦九韶算法的计算过程，并了解它提高计算效率的实质.
自主学习案
【知识梳理】
一．“求两个正整数的最大公约数”的两种方法.
1. 辗转相除法，就是对于给定的两个正整数，用较大的数除以较小的数，若余数不为零，则将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽为止，这时的较小的数即为原来两个数的最大公约数.
2. 更相减损术，就是对于给定的两个正整数，用较大的数减去较小的数，然后将差和较小的数构成新的一对数，继续上面的减法，直到差和较小的数相等，此时相等的两数即为原来两个数的最大公约数.
二．秦九韶算法
_________)__________(_________...)...(...)(012110111axaxaxaaxaxaxaxfnnnnnnnn
从括号最内层开始，由内项外逐层计算：
________,....,,________,,32321210nnnnvaxvvaxvvvav
这样，求n次多项式)(xf的值就转化为求_______________的值.
特点：通过一次式的反复计算，逐步得出高次多项式的值，对于一个n次多项式，只需做n次乘法和n次加法即可。
【预习自测】
1. 用辗转相除法求35和134的最大公约数，第一步是 ( )
A. 134-35=99 B. 134=35*3+29 C. 先除以2，得到18和67 D.
35=25*1+10
2. 用更相减损法求35和134的最大公约数，第一步是 ( ) 研卷知古今；藏书教子孙。
1
算法案例（讲义）
➢ 知识点睛
典型算法举例：
1. 辗转相除法
①方法概述：两数相除，较大数除以较小数，得商和余数，继而较小数除以余数，重复操作，直至除尽，此时除数即为最大公约数．
②原理：在a=bq+r中，除数b和余数r能被同一个数整除，那么被除数a也能被这个数整除．或者说，除数与余数的最大公约数，就是被除数与除数的最大公约数．
2. 秦九韶算法
把一个n次多项式改写成如下形式：
1110121102312101210()()(())((()))nnnnnnnnnnnnnnnfxaxaxaxaaxaxaxaaxaxaxaxaaxaxaxaxa………………
记0nva，11nnvaxa，…，10nnvvxa．
求多项式的值时，首先计算最内层括号内一次多项式的值，即v1，然后由内向外逐层计算．
3. 进位制
①k进制：若k是一个大于1的整数，那么以k为基数的k进制数可以表示为一串数字连写在一起的形式．
110()nnkaaaa…
11011000nnnnaaaaNakaaak≤（，，…，，，，，…，，）
②进位制数相互转化：
k进制转十进制，计算k进制数a的右数第i位数字ia与1ik的乘积1iiak，再将其累加，重复操作求和．
十进制数转k进制数（除k取余法）：
如右图，十进制数化为二进制数，
89=1011001（2）．
➢ 精讲精练
1. 用“辗转相除法”求下列数的最大公约数：
（1）459和357的最大公约数是____________；
余数10011012222222012511224489
2
（2）三个数324243135，，的最大公约数是____________．
2. 用秦九韶算法求多项式的值：
（1）计算多项式xxxxxxxf876543)(23456在
高一数学学案 序号___067__ 高一 年级 _1、6___ 班 教师 张杰 学生 _____
课 题 1.3 算法案例————辗转相除法、更相减损术与秦九韶算法
一、学习目的
1.理解辗转相除法与更相减损术中蕴含的数学原理，并能根据这些原理进行算法分析。
2．了解秦九韶算法的计算过程，并理解利用秦九韶算法可以减少计算次数提高计算效率的实质。
3.基本能根据算法语句与程序框图的知识设计完整的程序框图并写出算法程序。
二、学习重点、难点
重点：理解辗转相除法与更相减损术求最大公约数的方法。理解秦九韶算法的思想。
难点：把辗转相除法与更相减损术、秦九韶算法的方法转换成程序框图与程序语言。
三、学习过程
复习回顾
直到型循环与当型循环的程序语言分别是什么？
知识探究（一）:辗转相除法
思考1:18与30的最大公约数是多少？你是怎样得到的？
思考2:对于8251与6105这两个数，由于其公有的质因数较大，利用上述方法求最大公约数就比较困难.注意到8251=6105×1+2146，那么8251与6105这两个数的公约数和6105与2146的公约数有什么关系？
思考3:又6105=2146×2+1813，同理，6105与2146的公约数和2146与1813的公约数相等.重复上述操作，你能得到8251与6105这两个数的最大公约数吗？
例1：用辗转相除法求225和135的最大公约数
练习：利用辗转相除法求两数4081与20723的最大公约数.
思考4:上述求两个正整数的最大公约数的方法称为辗转相除法或欧几里得算法.一般地，用辗转相除法求两个正整数m，n的最大公约数，可以用什么逻辑结构来构造算法？其算法步骤如何设计？
第一步，给定两个正整数m，n(m>n).
第二步，
第三步，
第四步，
第五步，
思考5:该算法的程序框图如何表示？ 思考6:该程序框图对应的程序如何表述？
