辗转相除法是一种求最大公因数的计算方法。
这种方法在编程中很常用,在数学计算中也可以用来求很复杂的最大公因数问题。
如何使用
题目:求最大公因数(36,14)
我们如何用辗转相除法做这道题呢? $$ \displaylines{ 反复用除数除以余数直到除尽\ 36{\div}14=2\dots8\ 14{\div}8=1\dots6\ 8{\div}6=1\dots2\ 6{\div}2=3\ 最后一个除数就是最大公约数,也就是2 } $$ 我们算出最大公约数(36,14)=2
到这里,我们就知道如何使用辗转相除法了。
但是,鲁迅曾说过“我们学公式必须得懂得原理”,我们明白了原理才能灵活运用
原理
求最大公因数(a,b)
首先我们推出这几条式子 $$ \displaylines{ a{\div}b=q\dots r \ a=bq+r \ r=a-bq } $$ 这是我们辗转法的原理 $$ \displaylines{ (a,b)=(b,r) \a和b的最大公约数就等于b和r的最大公约数 } $$ 接下来让我们证明这条公式 $$ \displaylines{ (1)设(a,b)=d\ 那么a=dm,b=dn\ 然后我们将其带入r=a-bq\ 得r=d(m-nq)\ 因为m,n,q都是整数,所以r是d的倍数,d是r的因数\ 所以:只要是a,b的因数,就一定是d,r的约数\ } $$
$$ \displaylines{ (2)设(b,r)=d\ 和之前一样,那么b=dx,r=dy\ 然后将其代入a=bq+r\ 得a=d(xq+y)\ 因为x,q,y都是整数,所以a是d的倍数,d是a的因数\ 所以:只要是d,r的因数,就一定是a的因数\ } $$
这样,我们就得出(a,b)的因数和(b,r)的因数相同,它们的因数都相同,那么它们的最大公因数也就相同。
所以我们要求(a,b)的最大公因数,我们就通过可以求(b,r)的最大公因数来得到。
现在我们再来看看开头的题
题目:求最大公因数(36,14)
反复用(a,b)=(b,r)的方法
(36,14)=(14,8)=(8,6)=(6,2)
最后得到(6,2),显而易见最大公约数是2
写gcd函数
接下来看看我们如何在C++中用辗转相除法写gcd函数
gcd函数就是用来求最大公因数的函数
|
|
当然也可以直接用algorithm头文件中的gcd函数,
我们学会自己写是为了理解原理,提升思维,
自己写还可以在有特殊需求的时候更自定义化。