|
3.歐幾里得算法,即gcd(m,n) = gcd (n,m mod n);gcd是greatest common diviso（最大公約數(shù)）的縮寫(xiě)，gcd(m ,n ) 表示m和n的最大公約m mod
n代表m除以n后的余數(shù).重復(fù)以上等式直到m mod n=0；因?yàn)間cd(m,0) =
m,m最后的取值就是m和n的初值的最大公約數(shù)。 （也有人叫這輾轉(zhuǎn)相除法） 偽代碼描述如下: Euclid(m,n) //使用歐幾里得算法計(jì)算gcd(m,n) while n != 0 do return m 4.stein算法 Stein算法由J. Stein 1961年提出，這個(gè)方法也是計(jì)算兩個(gè)數(shù)的最大公約數(shù)。和歐幾里德算法不同的是，Stein算法只有整數(shù)的移位和加減法，這對(duì)于程序設(shè)計(jì)者是一個(gè)福音。 首先需要了解的是：一個(gè)奇數(shù)的所有約數(shù)都是奇數(shù)。我們來(lái)研究一下最大公約數(shù)的性質(zhì)，我們發(fā)現(xiàn)有 gcd( k*m,k*n ) = k*gcd( m,n) 這么一個(gè)非常好的性質(zhì)（證明就省去了）。說(shuō)他好是因?yàn)樗浅７衔覀兓〉乃枷?。我們?cè)嚾?k=2 ，則有 gcd( 2m,2n ) = 2 * gcd(m,n)。這使我們很快聯(lián)想到將兩個(gè)偶數(shù)化小的方法。那么一奇一個(gè)偶以及兩個(gè)奇數(shù)的情況我們?nèi)绾位∧兀?/p> 我們來(lái)看看一奇一偶的情況：設(shè)有2x和y兩個(gè)數(shù)，其中y為奇數(shù)。因?yàn)閥的所有約數(shù)都是奇數(shù)，所以 a = gcd( 2m,n) 是奇數(shù)。根據(jù)2x是個(gè)偶數(shù)不難聯(lián)想到，a應(yīng)該是x的約數(shù)。我們來(lái)證明一下：(2m)%a=0，設(shè)2m=n*a，因?yàn)閍是奇數(shù)，2x是偶數(shù)，則必有n是偶數(shù)。又因?yàn)?m=(n/2)*a，所以 m%a=0，即a是m的約數(shù)。因?yàn)閍也是n的約數(shù)，所以a是m和n的公約數(shù)，有 gcd(2m,n ) <= gcd(m,n)。因?yàn)間cd(m,n)明顯是2m和n的公約數(shù)，又有g(shù)cd(m,n) <= gcd(2m,n)，所以 gcd(2m,n) = gcd(m,n)。至此，我們得出了一奇一偶時(shí)化小的方法。
再來(lái)看看兩個(gè)奇數(shù)的情況：設(shè)有兩個(gè)奇數(shù)m和n，似乎m和n直接向小轉(zhuǎn)化沒(méi)有什么太好的辦法，我們可以繞個(gè)道，把m和n向偶數(shù)靠攏去化小。設(shè)m>n，我們注意到m+n和m-n是兩個(gè)偶數(shù)，則有
gcd( m+n,m-n) = 2 * gcd( (m+n)/2,(m-n)/2 )，那么 gcd(m,n) 與
gcd(m+n,m-n) 以及 gcd( (m+n)/2,(m-n)/2 )
之間是不是有某種聯(lián)系呢？為了方便設(shè) x=(m+n)/2 ，y=(m-n)/2 ，容易發(fā)現(xiàn)
x+y=m ，x-y=n 。設(shè) a = gcd(x,y)，則 x%a=0,y%a=0 ，所以
(x+y)%a=0，(x-y)%a=0 ，即m%a=0 ，n%a=0 ，所以a是m和n的公約數(shù)，有
gcd(m,n)<= gcd(m,n)。再設(shè) b = gcd(m,n)肯定為奇數(shù)，則 m%b=0,n%b=0
，所以 (m+n)%b=0 ，(m-n)%b=0
，又因?yàn)閙+n和m-n都是偶數(shù)，跟前面一奇一偶時(shí)證明a是m的約數(shù)的方法相同，有
((m+n)/2)%b=0,((m-n)/2)%b=0 ，即 x%b=0 ，y%b=0
，所以b是x和y的公約數(shù)，有 gcd(m,n) <= gcd(x,y)。所以 gcd(m,n) =
gcd(x,y) = gcd( (m+n)/2,(m-n)/2 )。 現(xiàn)在我們已經(jīng)有了遞歸式，還需要再找出一個(gè)退化情況。我們用這個(gè)： gcd(m,m) = m。 最小公倍數(shù)的求法有二： 1.適合數(shù)不太大時(shí)直接求最小倍數(shù)的題。其實(shí)和二是一樣的道理。
已知m,n均為正整數(shù)，試用C語(yǔ)言寫(xiě)出求m與n的最小公倍數(shù)的算法，算法的步驟為：
2.lcm(m,n) =
m*n/gcd(m,n),即兩個(gè)數(shù)的積除以它們的最大公約數(shù)。這個(gè)適合已知最大公約數(shù)時(shí)。（1） 計(jì)算m*n的積，送臨時(shí)變量r。 （2） 若m等于n，則輸出最小公倍數(shù)r/m，算法結(jié)束。 （3） 若m大于n，計(jì)算m-n，結(jié)果送m，否則，計(jì)算n-m，結(jié)果送n。(即max = max - min) （4） 轉(zhuǎn)到（2）或者（3）。 以上是兩個(gè)數(shù)的最大公約數(shù)和最小公倍數(shù)的算法，其實(shí)n個(gè)數(shù)的算法也是類(lèi)似的，只需要類(lèi)推就是了： int gcd(int, int); //兩個(gè)數(shù)的最大公約數(shù) int ngcd(int *, int) //N個(gè)數(shù)的最大公約數(shù) int lcm(int, int) //兩個(gè)數(shù)的最小公倍數(shù) int nlcm(int *, int) //N個(gè)數(shù)的最小公倍數(shù) int gcd(int a, int b) { if(a < b) //swap(a,b) { a = a ^ b; b = a ^ b; a = a ^ b; } int c; while((c = a % b) != 0) //輾轉(zhuǎn)相除 { a = b; b = c; } return b; } int ngcd(int * pa, int n) { if(n == 1) return *pa; return (gcd(pa[n-1], ngcd(pa, n-1))); } int lcm(int a, int b) //最大公倍數(shù) ＝ 兩數(shù)乘積 / 最大公約數(shù) { return a*b/gcd(a, b); } int nlcm(int * pa, int n) { if(n == 1) return *pa; return lcm(pa[n-1], nlcm(pa, n-1)); } |
|
|
