高中数学新课程----算法案例教案

高中数学新课程----算法案例
一．【课标要求】
通过阅读中国古代数学中的算法案例，体会中国古代数学对
世界数学发展的贡献。
二．【命题走向】
算法是高中数学新课程中的新增内容，本讲的重点是几种重
要的算 法案例思想，复习时重算法的思想轻算法和程序的构造。
预测2020年高考队本讲的考察是：以选择 题或填空题的形
式出现，分值在5分左右，考察的热点是算法实例和传统数学知
识的结合题目
三．【要点精讲】
1．求最大公约数
（1）短除法
求两个正整数的最大 公约数的步骤：先用两个数公有的质因
数连续去除，一直除到所得的商是两个互质数为止，然后把所有< br>的除数连乘起来
（2）穷举法（也叫枚举法）
穷举法求两个正整数的最大公约数的解 题步骤：从两个数中
较小数开始由大到小列举，直到找到公约数立即中断列举，得到
的公约数便 是最大公约数
（3）辗转相除法
辗转相除法求两个数的最大公约数，其算法可以描述如下：
①输入两个正整数m和n；
②求余数r：计算m除以n，将所得余数存放到变量r中；
③更新被除数和余数：m=n，n=r；
④判断余数r是否为0。若余数为0，则输出结果；否则转
向第②步继续循环执行
如此循环，直到得到结果为止。
（4）更相减损术
我国早期也有解决求最大公约数 问题的算法，就是更相减损
术。在《九章算术》中记载了更相减损术求最大公约数的步骤：
可半 者半之，不可半者，副置分母?子之数，以少减多，更相减
损，求其等也，以等数约之
步骤：
Ⅰ．任意给出两个正数；判断它们是否都是偶数。若是，用

1

2约简；若不是，执行第二步。
Ⅱ．以较大的数减去较小的数，接着把较小的 数与所得的差
比较，并以大数减小数。继续这操作，直到所得的数相等为止，
则这个数（等数） 就是所求的最大公约数。
2．秦九韶算法
秦九韶算法的一般规则：
nn-1秦九韶算法适用一般的多项式f(x)=a
n
x+a
n-1
x+….+a
1
x+a
0
的求值问题。用秦九韶算法求一般多项式
nn-1
f(x)=a
n
x+a
n-1
x+….+a
1
x+a0
当x=x
0
时的函数值，可把n次多项
式的求值问题转化成求n个一次 多项式的值的问题，即求
v
0
=a
n

v
1
=a
n
x+a
n－1

v
2
=v
1
x+a
n－2
v
3
=v
2
x+a
n－3

……..
v
n
=v
n－1
x+a
0

观察秦九韶算 法的数学模型，计算v
k
时要用到v
k－1
的值，若
令v
0
=a
n
。
我们可以得到下面的递推公式：
v
0
=a
n

v
k
=v
k－1
+a
n－k
(k=1,2,…n)
这是一个在秦九韶算法中反复执行的步骤，可以用循环结构
来实现
3．进位制
（1）概念
进位制是一种记数方式，用有限的数字在不同的位置表示不
同的数值。可 使用数字符号的个数称为基数，基数为n，即可称
n进位制，简称n进制。现在最常用的是十进制，通常 使用10
个阿拉伯数字0—9进行记数。
对于任何一个数，我们可以用不同的进位制来表示。 比如：
十进数57，可以用二进制表示为111001，也可以用八进制表示
为71、用十六进 制表示为39，它们所代表的数值都是一样的。
一般地，若k是一个大于一的整数，那么以k为基数的k进
制可以表示为：
a
n
a
n?1
...a
1
a
0(k)
(0?an
?k,0?a
n?1
,...,a
1
,a
0
?k)
，

2

而表示各种进位制数一般在数字右下脚加注 来表示,如
111001
(2)
表示二进制数,34
(5)
表示5进 制数。
（2）进位制间的转换
关于进位制的转换，教科书上以十进制和二进制之间的转换< br>为例讲解，并推广到十进制和其它进制之间的转换。这样做的原
因是，计算机是以二进制的形式进 行存储和计算数据的，而一般
我们传输给计算机的数据是十进制数据，因此计算机必须先将十
进 制数转换为二进制数，再处理，显然运算后首次得到的结果为
二进制数，同时计算机又把运算结果由二进 制数转换成十进制数
输出。
非十进制数转换为十进制数比较简单，只要计算下面的式子
值即可：
a
n< br>a
n?1
.....a
1
a
0
(k)?a
n
?k
n
?a
n?1
?k
n?1
?........ .?a
1
?k?a
0
第一步：从左到右依次取出k进制数
a
n
a
n?1
.....a
1
a
0
(k)
各 位上的
数字，乘以相应的k的幂，k的幂从n开始取值，每次递减1，
递减到0，即；
第二步：把所得到的乘积加起来，所得的结果就是相应的十
进制数。
十进制数转换成非十进制数
把十进制数转换为二进制数，教科书上提供了“除2取余
法”，我们可以类比得到十进制数转换成k进制数的算法“除k
取余法”。
非十进制之间的转换
一个自然的想法是利用十进制作为桥梁。教科书上提供了一
个二 进制数据与16进制数据之间的互化的方法，也就是先有二
进制数转化为十进制数，再由十进制数转化成 为16进制数。
四．【典例解析】
题型1：求最大公约数
例1．（1）用辗转相除法求123和48的最大公约数？
（2）用更相减损来求80和36的最大公约数？
解析：（1）辗转相除法求最大公约数的过程如下：（建立
带余除式）
123＝2×48＋27
48＝1×27＋21
27＝1×21＋6

3

a
n
?k
n
,a
n?1
? k
n?1
,.........,a
1
?k,a
0
?k0

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
2
可得80和36的最大公约数为2×1=4。
点评：对比两 种方法控制好算法的结束，辗转相除法是到达
余数为0，更相减损术是到达减数和差相等。
例2．设计一个算法，求出840与1764的最大公因数。
解析：我们已经学习过了对自然数的素因数分解的方法，下
面的算法就是在此基础上设计的。
解题思路如下：
首先对两个数进行素因数分解：
3222
840=2×3×5×7，1764=2×3×7
，
其次，确定两个数的公共素因数：2，3，7。
接着确定公共素因数的指数：对于公共素因数 2，840中为
322
2，1764中为2，应取较少的一个2，同理可得下面的因数为3和7。
算法步骤：
3
第一步：将840进行素数分解2×3×5×7；
222
第二步：将1764进行素数分解2×3×7；

4

第三步：确定它们的公共素因数：2，3，7；
第四步：确定公共素因数2，3，7的指数分别是：2，1，1；
211
第五步：最大公因数为2×3×7=84。
点评：质数是除１以外只能被１和 本身整除的正整数，它应
该是无限多个，但是目前没有一个规律来确定所有的质数
题型2：秦九韶算法
例3．（2009福州模拟）如果执行右面的程
序框图，那么输出的
S?
（ ）

A．22 B．46 C．
94
D．190
答案C
2、（2009浙江卷理）某程序框图如图所示，
该程序运行后输出的
k
的
值是 （）
A．
4
B．
5
C．
6
D．
7
< br>【解析】对于
k?0,s?1,?k?1
，而对于
k?1,s?3,?k?2< br>，则
k?2,s?3?8,?k?3
，后面是
k?3,s?3?8?2
11
,?k?4
，不
符合条件时输出的
k?4
．
答案A
3、（2009天津卷理）阅读上（右）图的程序框图，
则输出的S=()
A26B35C40D57
【解析】当
i?1
时，
T?2,S?2
；当
i?2
时，
T?5,S?7
；当
i?3
T?8,S?15
；
T?11,S?26
；时，当
i?4
时，当
i?5
时，
T?14,S?40
；当
i?6
时，
T?17,S?57
，故选择C。
答案 Ｃ
4（2009安徽卷文）程序框图上 （右）（即算法流
程图）如图所示，其输入结果是_______。
【解析】根据流程图可得
a
的取值依次为1、3、7、15、31、
63……
答案127
点评：秦九韶算法适用一般的多项式

5

f(x)=a
n
x+a
n-1
x+….+a
1
x+a< br>0
的求值问题。直接法乘法运算的次数
n次。秦九韶算法通过转化把乘法
运算的 次数减少到最多n次，加法最多n次。
5432
例4．已知多项式函数f(x)=2x－5x －4x+3x－6x+7，求当
x=5时的函数的值。
5432
解析：把多项式变形为：f(x)=2x－5x－4x+3x－6x+7
=((((2x－5)x－4)x+3)x－6)x+7
计算的过程可以列表表示为：
多项式x系－－－运
2 3 7
数 5 4 6 算
运算所得的12152

+
值 0 5 05 40 670
变形后x的2152*
2 5
系数1 08 34 677 5
最后的系数2677即为所求的值
算法过程：
v
0
=2
v
1
=2×5－5=5
v
2
=5×5－4=21

v
3
=21×5+3=108
v
4
=108×5－6=534
v
5
=534×5+7=2677
点评：如果多项式函数中有缺项的话，要以系数为0的项补
齐后再计算。
题型3：进位值
例5．把十进制数89化为三进制数，并写出程序语句.
解析：具体的计算方法如下：
89=3×29+2
29=3×9+2
9=3×3+0
3=3×1+0
1=3×0+1
所以:89
（10）
=1011001
(3)
。
点评：根 据三进制数满三进一的原则，可以用3连续去除
nn-1
(n?1)n
最多可到达2
，加法最多

6

89及其所的得的商，然后按倒序的先后顺序取出余数组成数据
即可。
例6．将8进制数314706
（8）
化为十进制数，并编写出一个
实现算法的程序 。
解析：3147068
5
+1×8
4
+4×8
3
+7×8
2
（8）
=3×+0×
8
1
+6×8
0
=104902。
所以，化为十进制数是104902。
点评：利用把k进制数转 化为十进制数的一般
方法就可以把8进制数314706
（8）
化为十进制数，然后根据该算法，利用GET函数，应用循环结构可以
设计程序。
五．【思维总结】
1．求最大公约数
（1）辗转相除法
程序框图与程序语句
程序：
INPUT“m，n=”;m,n
DO
r=mMODn
m=n
n=r
LOOPUNTILr=0
PRINT
END
（2）更相减损术
更相减损术程序：
INPUT“请输入两个不相等的正整数”；a，b
i=0
WHILEaMOD2=0ANDbMOD2=0
a=a2
b=b2
i=i+1
WEND
DO
IFb
7
开始
输入：m,n
r=m MOD n
m=n
n=r
N
r=0?
Y
输出：
开始

t=a
a=b
b=t
ENDIF
c=a－b
a=b
b=c
LOOPUNTILa=b
PRINTa^i
END
对于两个正整数如何选择合适的方法求他们的最大公约数
方适用范围及特点
法
短适合两个较小的正整数或两个质因数较少的正整
除法 数，简便易操作。
穷适合计算机操作，但一一验证过于繁琐。
举法
辗适用于两个较大的正整数，以除 法为主，辗转相
转相除除法计算次数相对较少，特别当两个数字大小差别较
法 大时计算次数较明显。
更适用于两个较大的正整数，更相减损术以减法为
相减损主，计算次数 上相对于辗转相处法较多。
术
2．我们以这个5次多项式函数为例加以说明，设：
5432
f（x）=a
5
x+a
4
x+a
3
x+ a
2
x+a
1
x+a
0

首先，让我们以5次多项式一步步地进行改写：
432
f（x）=（a
5< br>x+a
4
x+a
3
x+a
2
x+a
1
）x+a
0
32
=（（a
5
x+a
4
x+a< br>3
x+a
2
）x+a
1
）x+a
0

2
=（（（a
5
x+a
4
x+a
3
）x+a2
）x+a
1
）x+a
0

=（（（（a
5< br>x+a
4
）x+a
3
）x+a
2
）x+a
1
）x+a
0

上面的分层计算。只用了小括号，计算时，首先计算最内层的括号，然后由里向外逐层计算，直到最外层的括号，然后加上
常数项即可。


8