更相减损术与辗转相除法的比较的教学设计.doc

更相减损术与辗转相除法的比较的教学设计摘要：现代计算机科学是算法的科学，它需要机械的算法，始于我国的数学机械化思想，在经过明代以来几百年的相对消沉后，势将重新登上历史舞台。“更相减损术”是中国古代算法中 .关键词：计算机,算法类别：专题技术来源：牛档搜索（Niudown.COM）本文系牛档搜索（Niudown.COM）根据用户的指令自动搜索的结果，文中内涉及到的资料均来自互联网，用于学习交流经验，作品其著作权归原作者所有。不代表牛档搜索（Niudown.COM）赞成本文的内容或立场，牛档搜索（Niudown.COM）不对其付相应的法律责任！对“更相减损术与辗转相除法”的教学思考梁常东1 蒋晓云2（1钦州师专数学与计算机科学系 广西 钦州 535000 2桂林师专数学与计算机科学系 广西 桂林 541001）算法是普通高中数学课程标准（实验稿）引入的新内容之一，作为高中数学必修内容，并提出“通过阅读中国古代数学中的算法案例，体会中国古代数学对世界数学发展的贡献”的要求。人民教育出版社出版的普通高中课程标准实验教科书数学（必修）（以下简称课本）第一章“算法初步”中就介绍古希腊欧几里得的“辗转相除法”和我国古代数学名著九章算术中的“更相减损术”。下面是笔者在工作和学习中对“更相减损术与辗转相除法”的教学思考。1 问题的提出在小学学习分数时，一定遇到过将分数写成“最简分数”的问题。当时老师说你不能写成6/15，因为3是分子和分母的公约数，应当约去，所以应写成2/5。如果你写出6105/8251，老师可能不会追究的，尽管该分数并不是最简形式（既约分数），6105和8251的最大公约数是37，约去它之后该分数应该为165/223，因为用小学数学方法发现这一点比较困难，那我们怎样才能知道这一点呢？将分数化为既约分数问题，我国古代数学家给出了一个极为优美的解法，即“更相减损术”。2 阅读古代名著九章算术“方田”章的第六题：又有九十一分之四十九。问：约之，得几何？答曰：十三分之七。约分术曰：可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。 九章算术是以算筹为算具的数学书，现将上述算题作筹算图式，以帮助我们领会“更相减损术”术文的真实含义。上述演算过程表为现代形式为：49914942742735以少减多7287211714777713以等数约 之 由此可见，“更相减损术”是一个分数化简为既约分数的算法。翻译为现代语言如下。第一步：任意给定分数（m, n为两个正整数）；判断m, n是否都是偶数。若是，用2约简；若不是，才执行第二步。第二步：对分子和分母辗转相减，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减去小数。继续这个操作，直到所得的数相等为止。第三步：以等数约之，可得到（最简）既约分数。 我们来看课本中对“更相减损术”表述，课本认为“更相减损术”是求两个数的最大公约数的算法，我们用课本的步骤来做一个计算例子：例1 用课本算法求18与12的最大公约数。解：第一步：由于18与12均为偶数，用2约简得到9和6。1812963633用2约简9-6=36-3=3 第二步：把9和6以大数减去小数，并辗转相减，直到所得到的数相等为止。过程如下图所示。 所以，18与12的最大公约数为3（等数）。这显然是一个错误的结果。这一例子说明课本对“更相减损术”术文的理解是错误的。讨论：课本的解释错在哪？分数化简与最大公约数是紧密关联的，能否将“更相减损术”可以适当改造后用于求最大公约数？3 “更相减损术”与“辗转相减法”其实“更相减损术”中“副置分母、子之数，以少减多，更相减损，求其等也”就是求最大公约数的。我们不妨称之为辗转相减法。翻译为现代语言如下：任意给定两个正整数，以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减去小数。继续这个操作，直到所得的数相等为止，则这个数（等数）就是所求的最大公约数。例2 求18与12的最大公约数。解：由下述辗转相减过程可得18与12的最大公约数为612=612-6=6例2 用辗转相减法（更相减损术）求98与63的最大公约数。解：我们类似九章算术的筹算推演过程来表述辗转相减法的操作步骤98633563352872898-63简63-3535-2872128-7714121-77714-7所以，98与63的最大公约数等于7。我们看出，“辗转相减法（更相减损术）”求两个正整数的最大公因数是非常机械的，数学机械化思想正是我国古代数学的精髓。现代计算机科学是算法的科学，它需要机械的算法，始于我国的数学机械化思想，在经过明代以来几百年的相对消沉后，势将重新登上历史舞台。“更相减损术”是中国古代算法中的瑰宝，要让它放射出光辉必须与现代计算机程序结合。如何编写“辗转相减法（更相减损术）”的计算机程序呢？m=m-n是否是开 始输入m,nmn?输出m结 束mn？否n=n-m我们用变量m和n来表示两个整数，辗转相减法的过程，就是一个机械重复执行较大数减去较小数；直到所得的两数相等为止，我们可以把它看作一个循环结构，先用程序框图把这个结构表示出来（见右图）。然后编写一个计算机程序。（注：由于广西的中学信息技术课程的“程序设计方法”模块选用PASCAL语言，因此本文使用PASCAL语言编写程序，在Turbo PASCAL环境中运行，读者很容易将它移植到课本介绍的BASIC语言环境中）。PROGRAM example(input,output);VAR m,n,t:integer;BEGIN read(m,n); WHILE mn DO IF mn THEN m:=m-n ELSE n:=n-m; writeln(gcd=,m);END.4 辗转相除法我们写出用辗转相减法（更相减损术）求8251与6105的最大公约数的筹算推演过程，发现书写很复杂，能不能简化？按减去相同的数的步骤合并书写可得简洁一些的表示形式：37373782516105214618133331813大减去小1次3331483714821466105大减去小2次大减去小1次大减去小5次大减去小2次大减去小3次我们不妨将上述过程用等式表示：8251-61051=2146 即8251=61051+21466105-21462=1813 即6105=21462+18132146-18131+333 即2146=18131+3331813-3335=148 即1813=3335+148333-1482=37 即333=1482+37148-373=37 即148=373+37（带余除法要求写为 148=374+0）观察右边一系列等式，你得到了什么规律？开 始输入m,nr = m MOD nm=nn=rr=o?输出m结 束是否我们首先是用8251和6105中的较小数除较大数，得商为1，余数为2146；然后将前一步骤的除数作为被除数，余数作为除数，再作带余除法求余数；继续重复上述步骤，直到余数等于零为止，最后一式的除数就是“辗转相减法（更相减损术）”的“等数”，即两个数的最大公约数。这种求两个数的最大公约数的方法就是古希腊欧几里得在公元前300的左右首先提出“辗转相除法”。用m表示被除数，n表示除数，我们很容易画出“辗转相除法”的程序框图并写出程序。PROGRAM example (input,output);VAR m,n,r:integer;BEGIN read(m,n); REPEAT r:=m MOD n; m:=n; n:=r; UNTIL r=0; Writeln (gcd=,m);END.比较“辗转相减法（更相减损术）”和“辗转相除法”，古希腊的“辗转相除法”是中国古代“辗转相减法（更相减损术）”的一个简洁表示的形式，它们在理论上是一致的。简洁是数学家追求的理想目标，“辗转相除法”因其简洁美而成为世界数学工作者公认求最大公约数的重要算法，并被推广到求多项式的最大公因式，复整数的最大公因数以及现代数学的其它一些代数结构上。而古代中国的“辗转相减法（更相减损术）”遗憾地失去了耀人的光辉。5 几点教学体会（1）本节课突出介绍了中国古代数学的瑰宝“更相减损术”，让学生通过阅读原文、分析算法，从中可感悟到中国数学的机械化的算法思想及其对数学发展的贡献。领略到中国古代算法对现代计算机算法的影响。 （2）如果我国古代数学家“再进一步”，“更相减损术”也不会成为中国数学史上的憾事，它将与古希腊的“辗转相除法”同台放射出耀眼的光辉。让学生体会到数学问题解决后的“再进一步”反思有助于寻找更美的数学解答，养成学习数学的良好习惯。 （3）从教材和古代数学瑰宝中寻找缺憾，鼓励学生忌随大流思考权威教材、权威人物作出的结论，教会学生批判性地思考是创新教育的一个重要环节。参考文献：1 刘绍学，张淑梅等. 普通高中课程标准实验教科书数学（必修）J. 人民教育出版社,2004.作者: 梁常东1 蒋晓云2联系电话：13813952442（南京）13788562215（桂林）Email: 或通讯地址：江苏省南京市宁海路122号南京师范大学研究生公寓1910号（邮编210097）作者: 梁常东1 蒋晓云2联系电话：13813952442（南京）13788562215（桂林）Email: 或通讯地址：江苏省南京市宁海路122号南京师范大学研究生公寓1910号（邮编210097）作者: 梁常东1 蒋晓云2联系电话：13813952442（南京）13788562215（桂林）Email: