2024年5月20日发(作者：集品韵)
几种常见的算法案例分析
算法不仅是数学及其应用的重要的组成局部，也是计算机科学的重要根底，其中算法
的重要思想在几种常见的算法例案中得以较好的表达。本文从几种常见算法案例出发，来探
究一下算法的内涵。
一、辗转相除法
所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数，假设余数不为零，
那么将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，那么这时
的较小的数就是原来两个数的最大公约数。
例1． 写出求两个正数
a,b(ab)
的最大公约数的一个算法。
算法设计：第一步：输入两个正整数
a,b(ab)
；
第二步：把
ab
的余数赋予
r
；
第三步：如果
r0
，那么把
b
赋予
a
，把
r
赋予
b
，转到第二步；否那么
转到第四步；
第四步：输入最大公约数
b
。
程序框图下列图所示：
开始
输入
a,b
r=mod(a,b)
a=b
b=r
N
r=0
Y
输出
b
结束
用伪代码表示：input“a=,b=〞；a,b
do r=mod(a,b)
a=b
b=r
loop until r=0
print b
end
二、更相减损术
所谓更相减术，就是对于给定的两个数，以其中较大的数减去较小的数，然后将差和
较小的数构成一对新数，再用较大的数减去较小的数，反复执行此步骤，直到差数和较小的
数相等，此时相等的两个数就是原两个数的最大公约数。在我国古代的<<九章算术>>中有
这样的描述“约分术曰：可半者半之，不可半者会置分母分子之数，以少减多，更相损减，
求其等也，以等数约之。〞意思是说如果分母、分子都是偶数，那么先除以2；如果不全是
偶数，便将分子与分母互减，以少减多，直到得出最大公约数为止，用最大公约数约分子与
分母，便可使分数最简。如果两个数都是偶数，也不除以2，直接求最大公约数。这是一种
多么奇妙的方法啊，我们古代人在许多方面都比西方先进，这是值得我们自豪的。
以上题为例，算法可以这样来设计：
第一步：输入两个正整数
a,b(ab)
；
第二步：假设
a
不等于
b
，那么执行第三步；否那么执行第五步；
第三步：把
ab
的差赋予
r
；
第四步：如果
br
，那么把
b
的值赋予
a
，否那么把
r
的值赋予
a
，执行第二步；
第五步：输出最大公约数
b
。
程序框图如图(2)所示：
用伪代码表示：
input a,b
while a<>b
r=a-b
if b>r then
a=b
b=r
else a=r
end if
wend
print b
end
三、秦九韶算法
例2、写出
x23
，求多项式
7x3x5x11
的值的一个算法。
算法1：input “x〞；x
p=
7x3x5x11
print “p〞；p
end
算法2：input “x〞；x
32
32
p=
((7x3)x5)x11
print “p〞；p
end
比拟上述两种算法，我们可以看出算法2是较为方便的，这种算法就是“秦九韶算法〞。其
特点是：通过一次式的反复计算，逐步得出高次多项式的值，对于一个
n
次多项式，只要做
n
次乘法和
n
次加法即可。
例3、试描述给定
x
的值，求多项式
p(x)a
0
a
1
xa
2
x
2
a
n
x
n
值的算法。
a
5
x
5
函数值的分析：我们先看给定一个定值
x
，求5次多项式
p(x)a
0
a
1
xa
2
x
2
例子。首先可以把多项式一步一步的改写：
p(x)(a
5
x
4
a
4
x
3
a
3
x
2
a
2
xa
1
)xa
0
((a
5
x
3
a
4
x
2
a
3
xa
2
)xa
1
)xa
0
(((a
5
x
2
a
4
xa
3
)xa
2
)xa
1
)xa
0
((((a
5
xa
4
)xa
3
)xa
2
)xa
1
)xa
0
上面分层计算：
第一步：计算最内层
a
5
xa
4
的值，把
a
5
xa
4
的值赋给一个变量
v
1
；
第二步：计算
(a
5
xa
4
)xa
3
的值，可以改写为
v
1
xa
3
四、直接插入排序法
五、冒泡排序法
希望同学们通过对上述算法案例的模仿、操作和探索的过程中，学习用数学语言描述算
法 ，了解计算机科学与现实世界的联系，学会欣赏数学，提高自己学习数学的兴趣。
2024年5月20日发(作者：集品韵)
几种常见的算法案例分析
算法不仅是数学及其应用的重要的组成局部，也是计算机科学的重要根底，其中算法
的重要思想在几种常见的算法例案中得以较好的表达。本文从几种常见算法案例出发，来探
究一下算法的内涵。
一、辗转相除法
所谓辗转相除法，就是对于给定的两个数，用较大的数除以较小的数，假设余数不为零，
那么将余数和较小的数构成新的一对数，继续上面的除法，直到大数被小数除尽，那么这时
的较小的数就是原来两个数的最大公约数。
例1． 写出求两个正数
a,b(ab)
的最大公约数的一个算法。
算法设计：第一步：输入两个正整数
a,b(ab)
；
第二步：把
ab
的余数赋予
r
；
第三步：如果
r0
，那么把
b
赋予
a
，把
r
赋予
b
，转到第二步；否那么
转到第四步；
第四步：输入最大公约数
b
。
程序框图下列图所示：
开始
输入
a,b
r=mod(a,b)
a=b
b=r
N
r=0
Y
输出
b
结束
用伪代码表示：input“a=,b=〞；a,b
do r=mod(a,b)
a=b
b=r
loop until r=0
print b
end
二、更相减损术
所谓更相减术，就是对于给定的两个数，以其中较大的数减去较小的数，然后将差和
较小的数构成一对新数，再用较大的数减去较小的数，反复执行此步骤，直到差数和较小的
数相等，此时相等的两个数就是原两个数的最大公约数。在我国古代的<<九章算术>>中有
这样的描述“约分术曰：可半者半之，不可半者会置分母分子之数，以少减多，更相损减，
求其等也，以等数约之。〞意思是说如果分母、分子都是偶数，那么先除以2；如果不全是
偶数，便将分子与分母互减，以少减多，直到得出最大公约数为止，用最大公约数约分子与
分母，便可使分数最简。如果两个数都是偶数，也不除以2，直接求最大公约数。这是一种
多么奇妙的方法啊，我们古代人在许多方面都比西方先进，这是值得我们自豪的。
以上题为例，算法可以这样来设计：
第一步：输入两个正整数
a,b(ab)
；
第二步：假设
a
不等于
b
，那么执行第三步；否那么执行第五步；
第三步：把
ab
的差赋予
r
；
第四步：如果
br
，那么把
b
的值赋予
a
，否那么把
r
的值赋予
a
，执行第二步；
第五步：输出最大公约数
b
。
程序框图如图(2)所示：
用伪代码表示：
input a,b
while a<>b
r=a-b
if b>r then
a=b
b=r
else a=r
end if
wend
print b
end
三、秦九韶算法
例2、写出
x23
，求多项式
7x3x5x11
的值的一个算法。
算法1：input “x〞；x
p=
7x3x5x11
print “p〞；p
end
算法2：input “x〞；x
32
32
p=
((7x3)x5)x11
print “p〞；p
end
比拟上述两种算法，我们可以看出算法2是较为方便的，这种算法就是“秦九韶算法〞。其
特点是：通过一次式的反复计算，逐步得出高次多项式的值，对于一个
n
次多项式，只要做
n
次乘法和
n
次加法即可。
例3、试描述给定
x
的值，求多项式
p(x)a
0
a
1
xa
2
x
2
a
n
x
n
值的算法。
a
5
x
5
函数值的分析：我们先看给定一个定值
x
，求5次多项式
p(x)a
0
a
1
xa
2
x
2
例子。首先可以把多项式一步一步的改写：
p(x)(a
5
x
4
a
4
x
3
a
3
x
2
a
2
xa
1
)xa
0
((a
5
x
3
a
4
x
2
a
3
xa
2
)xa
1
)xa
0
(((a
5
x
2
a
4
xa
3
)xa
2
)xa
1
)xa
0
((((a
5
xa
4
)xa
3
)xa
2
)xa
1
)xa
0
上面分层计算：
第一步：计算最内层
a
5
xa
4
的值，把
a
5
xa
4
的值赋给一个变量
v
1
；
第二步：计算
(a
5
xa
4
)xa
3
的值，可以改写为
v
1
xa
3
四、直接插入排序法
五、冒泡排序法
希望同学们通过对上述算法案例的模仿、操作和探索的过程中，学习用数学语言描述算
法 ，了解计算机科学与现实世界的联系，学会欣赏数学，提高自己学习数学的兴趣。