(
课件网) 基本结构 程序框图 顺序结构 变量与赋值 循环结构 基本语句 循环语句 条件语句 WHILE语句 UNTIL语句 IF-THEN语句 语句适用结构 算法 条件结构 我们这节课就利用基本的算法程序来解决一些实际问题，进一步体会算法的程序思想。 案例1.辗转相除法与更相减损术 在初中，我们已经学过求最大公约数的知识，你能求出18与30的最大公约数吗？ 2 30 3 9 15 3 5 所以，18和30的最大公约数是：2×3＝6 互质 因数 但是，当我们处理较大数（如：8251与6105）的最大公因数时，如果利用这种方法可能计算量比较大，步骤比较多。下面我们介绍一种古老而有效的算法———辗转相除法 这种算法是欧几里得公元前300年左右首先提出的，因此又叫欧几里得算法 例1 求两个正数8251和6105的最大公约数。 分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点，根据已有的知识即可求出最大公约数 解 8251＝6105×1＋2146 显然8251和6105的最大公约数也必是2146的约数，同样6105与2146的公约数也必是8251的约数，所以8251与6105的最大公约数也是6105与2146的最大公约数 继续下去，我们得到： 欧几里得（公元前330-公元前275）：古希腊数学家，雅典人 欧几里得是柏拉图的学生，长期在亚历山大里亚教书。 公元前300年左右，代表作《几何原本》13卷问世，创立了著名的欧氏几何，至今仍为中学生必学的一门基础知识。欧几里得对光学也有一定研究。 6105＝2146×2＋1813 2146＝1813×1＋333 1813＝333×5＋148 333＝148×2＋37 148＝37×4＋0 则37为8251与6105的最大公约数 这就是辗转相除法，有除法的性质可以知道，对于任意两个正整数，上述除法步骤总可以在有限步骤之后完成 利用辗转相除法求最大公约数的步骤如下： 第一步：给定两个正整数m,n. 第二步：计算m除以n的余数. 第三步：m=n,n=r. 第四步：若r＝0,则m,n的最大公约数等于m;否则,返回第二步. r= m MOD n m=n n=r r=o 否 是 程序图框 带余除法 INPUT “请输入m，n的值”；m，n DO r=m MOD N m=n n=r LOOP UNTIL r=0 PRINT m END 为什么要用直到型循环结构？ 1.利用辗转相除法求两数4081与20723的最大公约数 ，写出它的流程框图和BASIC程序 更相减损术 我国早期也有解决求最大公约数问题的算法 《九章算术》（公元50年～100年或更早 ）是中国古代数学专著，承先秦数学发展的源流，进入汉朝后又经许多学者的删补才最后成书，这大约是公元一世纪的下半叶。它的出现，标志着中国古代数学体系的形成。 历代数学家把它尊为“算经之首”．这是世界上最早的印刷本数学书。 《九章算术》共收有 246个数学问题，分为九章。分别是：方田、栗米、衰分、少广、商功、均输、盈不足、方程、勾股。 《九章算术》是世界上最早系统叙述了分数运算的著作；其中盈不足的算法更是一项令人惊奇的创造；“方程”章还在世界数学史上首次阐述了负数及其加减运算法则。 更相减损术求最大公约数的步骤如下：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之。 翻译出来为： 第一步：任意给出两个正数；判断它们是否都是偶数。若是，用2约简；若不是，执行第二步。 第二步：以较大的数减去较小的数，接着把较小的数与所得的差比较，并以大数减小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数 例1 用更相减损术求98与63的最大公约数. 解 由于63不是偶数，把98和63以大数减小数，并辗转相减 98-63＝35 63-35＝28 35-28＝7 28-7＝14 14-7＝7 所以，98与63的最大公约数是7 比较辗转相除法与更相减损术的区别 （1）都是求最大公约数的方法，计算上辗转相除法以除 ... ...
