必修三 中国古代算法案例.pptx

必修三 第一章 目 录 1.2 基本算法语句 1.1.2 程序框图 1. 1.1 算法概念 1.1.3 算法的三种基本逻辑结构和框图表示 1.3 算法案例 1.3中国古代算法案例 1.3 中国古代的算法案例. 一、更相减损之术 更相减损术如下:可半者半之,不可半者,副置分母·子之数 以少减多，更相减损，求其等也，以等数约之。 翻译出来为： 第一步：任意给出两个正数；判断它们是否都是偶数。 若是，用2约简；若不是，执行第二步。 第二步：以较大的数减去较小的数，接着把较小的数与 所得的差比较，并以大数减小数。继续这个操作 … 直到所得的数相等为止， 则这个数（等数）就是所求的最大公约数。 1.3 中国古代的算法案例. 一、更相减损之术 例题演练: 用更相减损术求98与63的最大公约数. 解：由于63不是偶数,把98和63以大数减小数,并辗转相减,即： 98－63＝35 63－35＝28 35－28＝7 28－7＝21 21－7＝14 14－7＝7 所以，98与63的最大公约数是7。 1.3 中国古代的算法案例. 一、更相减损之术 练习1.用更相减损术求两个正数84与72的最大公约数。 （答案：12） 例2.80和36最大公约数.(答案:4) 2.求324和135的最大公约数.（学案） 1.3 中国古代的算法案例. 二、辗转相除法. 例1 求两个正数8251和6105的最大公约数。 （分析：8251与6105两数都比较大，而且没有明显的公约数，如能把它们都变小一点， 根据已有的知识即可求出最大公约数） 解：8251＝6105×1＋2146 显然8251与6105的最大公约数也必是2146的约数， 同样6105与2146的最大公约数也必是8251的约数， 所以8251与6105的最大公约数也是6105与2146的最大公约数。 6105＝2146×2＋1813 2146＝1813×1＋333 1813＝333×5＋148 333＝148×2＋37 148＝37×4＋0 则37为8251与6105的最大公约数。 1.3 中国古代的算法案例. 二、辗转相除法步骤 第一步:用较大的数 m 除以较小的数 n 得到一个商q0和一个余数r0； 第二步:若r0＝0，则n为m，n的最大公约数； 若r0≠0，则用除数n除以余数r0得到一个商q1和一个余数r1 第三步:若r1＝0，则r1为m，n的最大公约数； 若r1≠0，则用除数r0除以余数r1得到一个商q2和一个余数r2 …… 依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公约数。 1.3 中国古代的算法案例. 二、辗转相除法步骤 第一步: m = n×q0+r0； 第二步: n = r0×q1+r1 第三步: r0 = r1×q2+r2 …… 第n步 : rn-3 = rn-2×qn-1+rn-1 第n+1步: rn-2 = rn-1×qn+0 依次计算直至rn＝0，此时所得到的rn－1即为所求的最大公约数。 1.3 中国古代的算法案例. 比较更相减损术与辗转相除法 （1）都是求最大公约数的方法，辗转相除法以除法为主， 更相减损术以减法为主，辗转相除法计算次数相对较少 （2）从结果体现形式来看，辗转相除法体现结果是以相除余数为0则得到， 而更相减损术则以减数与差相等而得到. 例1、写出用辗转相除法求123和48的最大公约数的算法步骤， 并画出程序框图，写出程序。  课中探究导学案 解：第一步:123 = 48×2+27； 第二步: 48 = 27×1+21 第三步: 27 = 21×1+6 第四步 : 21 = 6×3+ 3 第n+1步: 6 = 3×2+0 所以3为123和48最大公约数。 辗转相除法程序框图和程序. 否 输入正整数m ，n 是 是 m=input (“m=”); n=input( “n=”); If mn x=m; m=n; n=x; end r=m mod n; While r~=0 r=m mod n; m=n; n=r; end n 否 1.3 中国古代的算法案例. 【变式训练】 1.求1734,816,1343的最大公约数。 分析：可以先求其中两个数的最大公约数 m，再求m和第三个数的最大公约数. 2.用辗转相除法或者更相减损术求三个数324,243,135 的最大公约数. 1.3 中国古代的算法案例. 我国魏晋时期的数学家刘徽，他在《九章算术》中采取正多边形面积逐渐逼近圆面积的算法计算圆周率π，即作圆的内接正多边形，通过让边数逐步加倍，如用正六边形，正十二边形，正二十四边形