去年某个时候总结的东西，这次做省赛题目时候就有一个“更相减损术”的题目，感觉这些细小的知识还是不能忽略，贴出来分享一下～
辗转相除法
辗转相除法,又称欧几里德(Euclid)算法,是欧几里德在约公元前300年提出的.
用辗转相除法求两个数的最大公约数的步骤如下：
先用小的一个数除大的一个数，得第一个余数；
再用第一个余数除小的一个数，得第二个余数；
又用第二个余数除第一个余数，得第三个余数；
这样逐次用后一个数去除前一个余数，直到余数是0为止。那么，最后一个除数就是所求的最大公约数（如果最后的除数是1，那么原来的两个数是互质数）。
辗转相除法是求两个数的最大公约数的方法。如果求几个数的最大公约数，可以先求两个数的最大公约数，再求这个最大公约数与第三个数的最大公约数。这样依次下去，直到最后一个数为止。最后所得的一个最大公约数，就是所求的几个数的最大公约数。
这个思想的一般数学公式可以表示为:
gcd(a,b)=gcd(b,a mod b)
注: 函数gcd(x,y)表示x和y的最大公约数,(Greatest Common Diviser);
运算x mod y表示x除y的余数,在C语言中可以表示为x % y;
简单地描述为:a,b地最大公约数,等于b与a除b的余数的最大公约数
分享一个很精炼的函数
int gcd(int a,int b){
while(a>b?(a=a%b):(b=b%a));
return a+b;
}
在收集资料的过程中,我还发现一些有意思的东西~~
最小公倍数
公式可以描述为:
lcm(a,b)*gcd(a,b)=a*b
注:函数LCM(x,y)表示x,y的最小公倍数(Least Common Multiply);
函数gcd(x,y)表示x,y的最大公约数;
通过这个公式我们知道,要求a,b的最小公倍数,只需求出a,b的最大公约数,然后套用公式,即可求出最小公倍数
这个公式稍微想一下是很好理解的
更相减损术
我国早期也有求最大公约数的算法,就是"更相减损术".在<九章算术>中有更相减损术的步骤:
可半者半之,不可半者副置分母`子之数,以少减多,更相减损,求其等也,以等数约之.
翻译:1.任意给出两个正整数;
判断它们是否都是偶数.若是,用2约简;
若不是,执行第二步.
2.以较大的数减去较小的数,接着把较小的数与所得的差比较,并以大数减小数.继续这个操作,直到所得的数相等为止,则这个数(等数)就是所求的最大公约数.
我曾经看到过一个练习题就是用更相减损术描述的,大意是这样:
Q博士在实验室培养一批细菌.他发现他的细菌中有两种相互制约的细菌A和B.于是他培养这两种细菌,在试验中他发现细菌A,B有如下规律:当AB细菌共存时,细菌A,B中数量少的那一方每天会吞噬掉数量多的一方的部分个体,吞噬的数量等于数量少一方的个体数量;
这样培养下去,直到A,B细菌数量相等时,便不再相互吞噬.
程序要求任意输入两个数a,b分别代表细菌A,B的数量;
程序要求输出AB细菌数量达到稳定后的总个数.
这个题实质上就是要求两个数的最大公倍数,但是它用了更相减损术来描述,如果对更相减损术不了解的话第一思路只能模拟题目的描述;
一旦我们看出是求最大公约数,我们便可以用辗转相除法来求解,大大提高解题效率!
辗转相除法和更相减损术在数学本质上是相同的,只是一个用的减法描述,另一个用的除法描述.显然,辗转相除法的逼近速率要快得多.
【最大公约数相关原理】
