发布时间 : 星期一 文章服务类第1章算法与程序框图更新完毕开始阅读ea6785447ed5360cba1aa8114431b90d6c8589ad
说明 求两个正整数的最大公约数的方法很多，例如:可以将上面的“更相减损之术”改进，得到“转辗相除法”，再如：可以先将每个正整数分解质因数，然后求最大公约数等等，有兴趣的话，可以查阅相关资料，得到相应的算法和程序框图。
想一想，用“更相减损之术”求最大公约数的数学道理是什么？
例2 （秦九韶算法）已知n次多项式f(x)?anxn?an?1xn?1???a1x?a0，设计一个算法，求当x?x0时，多项式f(x)的值，并画出算法的程序框图。 分析 在求多项式的值时，我们可以直接计算：
f(x0)?anx0?an?1x0nn?1???a1x0?a0
但是，这种做法的计算量比较大，为了减少计算量，我们常用我国宋代数学家秦九韶的方法，这种算法被称为“秦九韶算法”，其做法是将多项式恒等变形：
f(x)?anxn?an?1xn?1???a1x?a0 ?(anxn?1?an?1xn?2???a1)x?a0 ?((anxn?2?an?1xn?3???a2)x?a1)x?a0 ??
?(?(((anx?an?1)x?an?2)x???a2)x?a1)x?a0，
所以，只要逐步计算：
y1?anx?an?1，
y2?y1x?an?2， y3?y2x?an?3，
?，
yn?yn?1x?a0
则yn就是所求的多项式的值。 解 算法的程序框图为：
开始 输入n,an,x y?an i=n-1 否 i?0
是
输入ai y?yx?ai i=i-1
输出y
结束
秦九韶算法是多项式求值的一种比较好的算法，其实质是将n次多项式的求值转化为求n个一次多项式的值，所以，这种算法只要进行n次乘法运算和n次加法运算，n越大，这种算法越体现出它的优越性。
随堂练习
1.设计一个算法，任意输入一个正整数，判断这个数是否为质数，请画出算法的程序框图。 2. 设计一个算法，任意输入一个正整数，计算这个正整数的各位数字之和，请画出算法的程序框图。
例1 某城市对居民的生活用水实行阶梯式收费，标准为：每月每户生活用水20立方米以内(含20立方米)为第一级，按居民生活用水的供水价格收费；每月每户超过20立方米且低于或等于30立方米为第二级，超出部分按供水价格1.5倍收费；每月每户超过30立方米为第三级，超出部分按供水价格2倍收费。如果该市居民生活用水的供水价格为每立方米1.86元，且每立方米水另外还要加收城市附加费0.06元，污水处理费1.3元，水资源费0.2元。 “阶梯水价”的基本特点是用水越多，水价越贵,充分发挥市场、价格因素在水资源配置、水需求调节等方面的作用，增强居民的节水意识，避免了水资源的浪费。
请设计一个算法，输入某居民某个月的用水量，输出这个月该居民所要缴纳的水费。 分析 这实际上是一个分段函数的求值问题。设居民这个月的用水量为x立方米，所要缴纳的水费为y元，则
当0?x?20时，y?(1.24?0.06?1.3?0.2)x?2.8x； 当20?x?30时，
y?20?2.8?(1.24?1.5?0.06?1.3?0.2)(x?20)?3.42x?12.4；
当x?30时，
y?20?2.8?10?3.42?(1.24?2?0.06?1.3?0.2)(x?30)?4.04x?31.
解 算法的程序框图为:
y
开始 输入x x?20 否 是 是 20?x?30 否 ?4.04x?31 y?3.42x?12.4 y?2.8x 输出y 结束 上例中，条件选择的分支有3个，所以，用一个条件判断结构无法表示这种情形，这时，我们在一层条件判断结构中再包含一层条件判断结构。像这样在一层条件判断结构中再包含一层或多层条件判断结构的情形，称为条件判断结构的嵌套，它用于表示条件选择的分支在2个以上的情形。
例4 圆周长和直径的比值称为圆周率（π），它是一个常数，也是一个超越数。在历史上，有不少数学家都对圆周率作出过研究。到了现代，由于算法的改进和计算机科学的发展，π值计算精度也迅速提高。例如，利用莱布尼茨公式：
?11111?1??????? 4357911就可以计算π的近似值。
设计一个算法，利用上面的公式，计算π的近似值，请画出算法的程序框图。 解 算法的程序框图为： 开始
n=1，S=0，a=0
b=a
1 S?S?(?1)n?1 2n?1
n=n+1 a=4S 否
?5 ?10|a-b|
是 输入a 结束