辗转相除法和更相减损术.ppt

算法案例之辗转相除法与更相减损术“古 今 中 外”数学大风暴大同一中高一数学计琳自主学习成果检验分别用辗转相除法和更相减损术求470和282的最大公约数。更相减损术由于282和470都是偶数，则需用2约简得：141和235辗转相除法（1）辗转相除法，又叫欧几里得法，提出于公元前300年左右，是一种求两个正整数的最大公约数的古老而有效的算法。（2）辗转相除法是指对于给定的两个数，用大数除以小数，若余数不为零，则将余数和较小数构成新的一对数，继续上面的除法，直到大数被小数除尽，则这时小数就是原来两个数的最大公约数。更相减损术更相减损术是我国古代数学专著九章算术中介绍的一种求两个数的最大公约数的算法.提出于公元一世纪左右。“可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也，以等数约之”问题一：辗转相除法的关键步骤是做带余除法：被除数=除数商+余数。其中被除数、除数和除数、余数有相同的最大公约数，即：gcd（被除数，除数）=gcd（除数，余数）,为什么呢？gcd(470,282)=gcd(282,188)=gcd(188,94)=94已知，求证：下面说明c为最大公约数，即：与b互质令，则设，故c也为n和r的约数。与有公约数cd，且cdc。与产生矛盾（反证法）假设，则假设不成立，原结论成立问题二：两种算法中，带余除法和减法分别进行到什么时候为止？为什么？辗转相除法中，带余除法进行到余数为0为止；更相减损术中，减法进行到减数和差相等为止。由于若时，我们称n整除m，此时，n为m的约数或最大公约数。因此，在辗转相除过程中，若余数为0，则与的最大公约数是，依据问题一可知：也就是与的最大公约数；同样的理由，逐步推上去，可得：中西方数学文化大碰撞辗转相除法与更相减损术的区别与联系？（1）都是求最大公约数的方法，计算上辗转相除法以除法为主，更相减损术以减法为主，计算次数上辗转相除法计算次数相对较少，特别当两个数字大小区别较大时计算次数的区别较明显。比如求1996和228的最大公约数。（2）从结果体现形式来看，辗转相除法体现结果是余数为0则得到，而更相减损术则以差和减数相等而得到。62222634；6412；4220666422古今算法演变大风暴辗转相除法的算法步骤：1、给定两个正整数；2、计算m除以n所得的余数r；3、m=n，n=r；4、若r=0，则m，n的最大公约数等于m；否则返回第二步。更相减损术的算法步骤：1、任意给定两个正整数,判定它们是否都是偶数，若是，用2约简；若不是，执行第二步2、以较大的数减去较小的数，接着把所得的差与较小的数比较，并以大数减小数，继续这个操作，直到所得的数相等为止。则这个数（等数）或这个数与约简的数的乘积就是所求的最大公约数。2017年6月19日，在德国法兰克福全球超级计算大会上，中国“神威太湖之光”荣登全球超级计算机500强榜首。自2016年6月问世以来，这是它第三次获评“全球最快超级计算机”，由此实现“三连冠”。神威”到底有多快？它有三个“世界第一”指标：系统峰值性能每秒12.5亿亿次，持续性能每秒9.3亿亿次，性能功耗比每瓦特60.5亿次。据了解，其1分钟的计算能力，相当于全球72亿人同时用计算器不间断计算32年。开始输入m，n求m除以n的余数r输出m结束否是辗转相除法程序框图：程序直到型循环使用当型循环结构该如何制作程序框图及相应的程序？程序框图：开始输入m，n求m除以n的余数r输出m结束是否更相减损术程序框图输出开始输入m，n（mn）结束m，n均为偶数？否否否是是是更相减损术