1.3算法案例教案

03算法案例
1.算法案例
一、辗转相除法（欧几里得算法）
（1）算法步骤
第一步，给定两个正整数m，n.
第二步，计算m除以n所得的余数r.
第三步， HYPERLINK "http://www.21cnjy.com" .
第四步，若 HYPERLINK "http://www.21cnjy.com" ,则m，n的最大公约数等于m；否则，
返回第二步。
（2）程序语句
INPUT m,n
DO
r=m MOD n
m=n
n=r
LOOP UNTIL r=0
PRINT m
END
2.更相减损术
步骤：第一步，任意给定两个正整数，判断它们是否都是偶数，若是，用2约简；若不是，执行第二步。
第二步，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止，则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数。
二、秦九韶算法
秦九韶算法是关于求高次多项式的函数值的一个算法，其过程如下：
把一个n次多项式 HYPERLINK "http://www.21cnjy.com" 改写成如下形式：
HYPERLINK "http://www.21cnjy.com"
HYPERLINK "http://www.21cnjy.com"
HYPERLINK "http://www.21cnjy.com"
HYPERLINK "http://www.21cnjy.com"
HYPERLINK "http://www.21cnjy.com"
求多项式的值时，首先计算最内层括号内一次多项式的值，即 HYPERLINK "http://www.21cnjy.com"
然后由内向外逐层计算一次多项式的值，即
HYPERLINK "http://www.21cnjy.com" ；
HYPERLINK "http://www.21cnjy.com" ；
HYPERLINK "http://www.21cnjy.com"
HYPERLINK "http://www.21cnjy.com"
这样，求n次多项式 HYPERLINK "http://www.21cnjy.com" 的值就转化为求n个一次多项式的值，上述方法称为秦九韶算法。
（1）算法步骤
第一步，输入多项式次数n、最高次项的系数 HYPERLINK "http://www.21cnjy.com" 和x的值。
第二步 HYPERLINK "http://www.21cnjy.com" 的值初始化为 HYPERLINK "http://www.21cnjy.com" ，将i的值初始化为n-1.
第三步，输入i次项的系数 HYPERLINK "http://www.21cnjy.com" .
第四步： HYPERLINK "http://www.21cnjy.com"
第五步，判断i是否大于或等于0.若是，则返回第三步；否则输出多项式的值v.
(2)程序语句
INPUT “n=”；n
INPUT “an=”；a
INPUT “x=”；x
v=a
i=n-1
WHILE i＞=0
PRINT “i=”；i
INPUT “ai=”；a
v=v*x+a
i=i-1
WEND
PRINT v
END
详解：
无
2.进位制
（1）进位制是人们为了计算和运算方便而约定的记数系统，约定满二进一，就是二进制；满十进一，就是十进制；满十二进一，就是十二进制；等等。也就是说，“满几进一”就是几进制，几进制的基数就是几。
（2）一般地，若k是一个大于1的整数，那么以k为基数的k进制数可以表示为一串数字连写在一起的形式
HYPERLINK "http://www.21cnjy.com"
（3）将k进制数转换为十进制数的方法
HYPERLINK "http://www.21cnjy.com"
只要将上式等号右面边的值计算出来，就得到相应的十进制数。
（4）将十进制数转换为k进制数一般用除k取余法，其方法是用k连续去除这个数或所得的商，一直到商为0止，然后把每次所得的余数倒过来排成一个数，就是相应的k进制数。
详解：
无