C語言如何利用輾轉(zhuǎn)相除法求最大公約數(shù)
C語言利用輾轉(zhuǎn)相除法求最大公約數(shù)
1. 首先要明確幾個概念
最大公約數(shù): 也叫最大公因數(shù),是指倆個或多個整數(shù)公有約數(shù)中最大的一個。
例如,18 和 24的最大公約數(shù)是 6
最小公倍數(shù):除0以外最小的一個公倍數(shù)就叫作這幾個整數(shù)的最小公倍數(shù)
例如,18 和 24的最小公倍數(shù)是 72
2. 輾轉(zhuǎn)相除法
用除數(shù)和余數(shù)反復(fù)做除法運算,當(dāng)余數(shù)為0時,取當(dāng)前算式除數(shù)為最大公約數(shù)
例如:求 1997 和 615 倆個正整數(shù)的最大公約數(shù)
因為:
1997 % 615 = 152 615 % 152 = 7 152 % 7 = 5 7 % 5 = 2 5 % 2 = 1 2 % 1 = 0
所以,1997 和 615 的最大公約數(shù)為 1
3. C語言代碼實現(xiàn)
#include <stdio.h> int main() { ?? ?int data1 = 0, data2 = 0; ?? ?int m = 0; ? ? //該變量是中間變量,不能放在while函數(shù)的內(nèi)部 ?? ?scanf_s("%d %d", &data1, &data2); ?? ?while ((m = data1 % data2) != 0) ?? ?{ ?? ??? ?data1 = data2; ?? ??? ?data2 = m; ?? ?} ?? ?printf("最大公約數(shù)為%d\n", data2); ?? ?return 0; }
注意點:
對于求模運算符%,若是分?jǐn)?shù)形式求余數(shù)的話,如果分子小于分母,則分子就是余數(shù)。
例如:2 % 5 = 0
而當(dāng)不是分?jǐn)?shù)形式求余數(shù)的話,即例如:18 % 24 時,可將 % 左邊的內(nèi)容看成是分子,而 % 右邊的內(nèi)容看成是分母。所以 18 % 24 = 18
這里有一個誤區(qū),不能將18 與 24 在都約去 6 的情況下去求它們的余數(shù),所以 18 % 24(3 % 8)= 3 是錯誤的
而不管是 18 % 24 ,還是24 % 18 。它們的余數(shù)均不會成為0
如果知道了倆個數(shù)的最大公約數(shù),那么其最小公倍數(shù)可以根據(jù)公式來確定
即最小公倍數(shù) = 倆個數(shù)的乘積 / 最大公約數(shù)
C語言求最大公約數(shù)常見思路
輾轉(zhuǎn)相除法
輾轉(zhuǎn)相除法又稱為歐幾里得算法,用于求兩數(shù)的最大公約數(shù)gcd(全稱為greatest common divisor)
注意兩數(shù)必須為非負(fù)整數(shù)a,b。用法為:用兩數(shù)中較大的數(shù)(a1)除以較小的數(shù)(b1),得到余數(shù)(r1),再用b1除以r1得到余數(shù)r2,之后再用r1除以r2,反復(fù)進行,直到最后余數(shù)是0為止。最大公約數(shù)就是最后式子中的除數(shù)。
請看如下舉例:
若用函數(shù)gcd(a,b)來表示,即gcd(a,b)=gcd(b,a%b),我們可以這樣理解:3887 2231和2231 1656的最大公約數(shù)是相等的,依次類推、重復(fù)操作。
用表達式可以這樣來表示:gcd(3887,2231)=gcd(2231,1656)=gcd(1656,575),直到最后到底gcd(a,b)=gcd(c,0),即gcd(3887,2231)=gcd(23,0)。
這里的c為a和b的最大公約數(shù)。
下面來看輾轉(zhuǎn)相除法的圖像說明
下面看算法實現(xiàn):
算法實現(xiàn)一
代碼中的a就相當(dāng)于上述gcd(a,b)=gcd(c,0)中的c。當(dāng)然還有利用此原理的其他寫法,不過是大同小異,這里就不一一列舉了。這里的if語句其實是多余的,因為通過輾轉(zhuǎn)相除完全可以實現(xiàn)兩數(shù)之間的互換。
算法實現(xiàn)二(函數(shù)遞歸法)
對輾轉(zhuǎn)相除足夠熟悉后,可以采用遞歸的方式,如算法實現(xiàn)三
算法實現(xiàn)三(遞歸思想)
總之一句話:除數(shù)除以余數(shù),直到余數(shù)為0為止。
更相減損之術(shù)
更相減損之術(shù)出自我國《九章算術(shù)》,原文是這樣的:
可半者半之,不可半者,副置分母、子之?dāng)?shù),以少減多,更相減損,求其等也。以等數(shù)約之。
算法過程:大數(shù)減小數(shù),得到的差用來替換之前的大數(shù),如此反復(fù),直到得出來的差與上次的減數(shù)相等。此時的這個差就是兩者的最大公約數(shù)。
以 36 24為例(如下圖):
可以這樣表示:gcd(36,24)=gcd(24,12),即36 24和24 12的最大公約數(shù)是相等的。
下面來看代碼實現(xiàn)
總歸一句話:用大數(shù)減去小數(shù),知道減數(shù)和差相等。
最后,當(dāng)處理較大的數(shù)時,輾轉(zhuǎn)相除法雖然在時間上有明顯優(yōu)勢。但是,即使是這樣,輾轉(zhuǎn)相除法也同樣存在缺陷,其在處理較大的素因數(shù)(也叫質(zhì)因數(shù),就是說一個數(shù)是另一個數(shù)的因數(shù),本身又是質(zhì)數(shù),就叫做另一個數(shù)的素因數(shù))時,缺陷就會顯現(xiàn)出來。
當(dāng)然,實現(xiàn)求取最大公約數(shù)還有很多其他方法,這里只進行了常見思路的講解。
總結(jié)
以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。
相關(guān)文章
C++實現(xiàn)LeetCode(67.二進制數(shù)相加)
這篇文章主要介紹了C++實現(xiàn)LeetCode(67.二進制數(shù)相加),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07C語言調(diào)用攝像頭實現(xiàn)生成yuv未壓縮圖片
這篇文章主要為大家詳細(xì)介紹了C語言如何調(diào)用攝像頭實現(xiàn)生成yuv未壓縮圖片,文中的示例代碼講解詳細(xì),具有一定的學(xué)習(xí)價值,感興趣的小伙伴可以參考一下2023-11-11NDK 數(shù)據(jù)結(jié)構(gòu)之隊列與棧等的實現(xiàn)
這篇文章主要介紹了NDK 數(shù)據(jù)結(jié)構(gòu)之隊列與棧等的實現(xiàn)的相關(guān)資料,希望通過本文大家能理解掌握這部分內(nèi)容,需要的朋友可以參考下2017-10-10