当前位置: 首页>编程笔记>正文

輾轉相除法求最小公倍數的方法,如何求出兩個整數的最大公約數

輾轉相除法求最小公倍數的方法,如何求出兩個整數的最大公約數

目錄

前言

1.暴力枚舉法

2.輾轉相除法

3.更相減損術

4.更相減損術與移位相結合


前言

????????幾個整數中公有的約數,叫做這幾個數的公約數;其中最大的一個,叫做這幾個數的最大公約數。例如:12、16的公約數有1、2、4,其中最大的一個是4,4是12與16的最大公約數,一般記為(12,16)=4。12、15、18的最大公約數是3,記為(12,15,18)=3。

1.暴力枚舉法

int get_greatest_common_divisorV1(int a, int b) {int big = a>b ? a : b;int small = a<b ? a : b;if (big % small == 0) {return small;}int i = 0;for (i = small / 2; i > 1; i--) {if (small % i == 0 && big % i == 0) {return i;}}return 1;
}

????????該法思路特別簡單,從較小整數的一半開始,試圖找到一個合適的整數i,看看這個整數能否被a和b同時整除。雖然這個方法實現了所要求的功能,但是效率十分的低,比如輸入的整數是10000和10001,用該法就需要循環10000/2-1=4999次。

該法的時間復雜度是O(min(a,b))。

2.輾轉相除法

輾轉相除法求最小公倍數的方法?定理:兩個正整數a和b(a>b),它們的最大公約數等于a除以b的余數c和b之間的最大公約數。

? ? ? ? 例如10和25,25除以10商2余5,那么10和25的最大公約數,等同于10和5的最大公約數。

int get_greatest_common_divisorV2(int a, int b) {int big = a>b ? a : b;int small = a<b ? a : b;if (big % small == 0) {return small;}return get_greatest_common_divisorV2(big % small, small);
}

? ? ? ? 該法可以使用遞歸的方法把問題逐步簡化,逐漸把兩個較大的整數之間的運算簡化為成兩個較小的整數之間的運算,直到兩個數可以整除,或者其中一個數減小到1為止。不過該法仍有一個問題所在,當兩個整數較大時,做a%b取模運算的性能會比較差。

該法的時間復雜度是O(log(max(a,b)))。

3.更相減損術

最大公因數什么意思?原理:兩個正整數a和b(a>b),它們的最大公約數等于a-b的差值c和較小數b的最大公約數。

? ? ? ??例如10和25,25減10的差是15,那么10和25的最大公約數,等同于10和15的最大公約數。

int get_greatest_common_divisorV3(int a, int b) {if (a == b) {return a;}int big = a>b ? a : b;int small = a<b ? a : b;return get_greatest_common_divisorV3(big - small, small);
}

? ? ? ? 逐漸把兩個較大的整數之間的運算簡化成兩個較小整數之間的運算,直到兩個數可以相等為止,最大公約數就是最終相等的這兩個數的值。但是更相減損術是不穩定的是算法,當兩數相差懸殊時,如計算10000和1的最大公約數,就要遞歸9999次。

該法的時間復雜度為O(max(a,b))。

4.更相減損術與移位相結合

最大公因數的定義、????????總所周知,移位運算的性能非常好。

int get_greatest_common_divisorV4(int a, int b) {if (a == b) {return a;}if ((a&1) == 0 && (b&1) == 0) {return get_greatest_common_divisorV4(a >> 1, b >> 1) << 1;} else if ((a&1) == 0 && (b&1) != 0) {return get_greatest_common_divisorV4(a >> 1, b);} else if ((a&1) != 0 && (b&1) == 0) {return get_greatest_common_divisorV4(a, b >> 1);} else {int big = a>b ? a : b;int small = a<b ? a : b;return get_greatest_common_divisorV4(big - small, small);}
}

(獲取最大公約數的方法get_greatest_common_divisor簡稱為gcd)

當a和b均為偶數的時,?gcd(a,b)=2×gcd(a/2,b/2)=2×gcd(a>>1,b>>1)。

當a為偶數,b為奇數時,gcd(a,b)=gcd(a/2,b)=gcd(a>>1,b)。

兩個整數的最大公約數,當a為奇數,b為偶數時,gcd(a,b)=gcd(a,b/2)=gcd(a,b>>1)。

當a和b均為奇數時,可以先利用更相減損術運算一次,gcd(a,b)=gcd(b,a-b),此時a-b必然是偶數,然后又可以繼續進行移位運算。

?例如計算10和25的最大公約數的步驟如下:

  1. 整數10通過移位,可以轉化成5和25的最大公約數。
  2. 利用更相減損術,計算出25-20=20,轉化成求5和20的最大公約數。
  3. 整數20通過移位,可以轉換為求5和10的最大公約數。
  4. 整數10通過移位,可以轉化成求5和5的最大公約數。
  5. 利用更相減損術,因為兩數相等,所以最大公約數是5。

????????這種方式在兩數較小時可能看不出計算次數的優勢,但當兩數越大時,計算次數的減少就會越明顯。

編程求兩個整數的最大公約數?該法的時間復雜度為O(log(max(a,b)))。

參考書籍《漫畫算法:小灰的算法之旅》

https://www.nshth.com/bcbj/338802.html
>

相关文章:

  • 輾轉相除法求最小公倍數的方法
  • 最大公因數什么意思
  • 最大公因數的定義
  • 兩個整數的最大公約數
  • 編程求兩個整數的最大公約數
  • 兩個質數有沒有最大的公因數
  • 輸入兩個整數求最大公約數
  • 怎么求兩個數的最大公約數
  • pdf翻譯網站,1 Trillion Dollar Refund – How To Spoof PDF Signatures——欺騙PDF簽名
  • 如何創建一個抽象類,創建具體的產品,并繼承產品抽象類
  • 主從庫理論知識-主從同步如何實現?
  • Tomcat環境變量配置,Mybatis的配置文件參數詳解
  • I Am You,POJ 3130 How I Mathematician Wonder What You Are! 半平面交
  • 要學vue需要學什么基礎知識,第一章 Vue基礎入門
  • win7下安裝win10,win10下安裝Ubuntu18.10雙系統
  • vmplayer怎么使用烏邦圖,烏邦圖環境安裝
  • 計算機專業要不要考研——寫的很棒
  • redisson看門狗原理,記錄一次redis漏洞攻擊
  • 任意波形發生器,基于單片機信號波形發生器系統設計-畢設課設
  • 嵌入式驅動,嵌入式Linux驅動大全問世,十年磨一劍,視頻!服務!新老客戶都有大折扣!
  • socket連接器v2下載,Netty(一)基礎socketchannel,Buffer,selector黏包 半包解決 實戰
  • 大一c語言程序設計筆記,吉林大學2013級大一下學期程序設計作業:同學通訊錄系統
  • 暑期小學生計算機培訓班,青島小學生學習編程暑假
  • 熊貓毛小喵喵去哪里了,小西貝、何小喵看熊貓之觀察者設計模式
  • 如何用c語言比較兩個數的大小,如何用C語言求兩個數的較大值
  • 輾轉相除法求最小公倍數的方法,更相減損術--最大公約數
  • 輾轉相除法求最小公倍數的方法,如何求出兩個整數的最大公約數
  • 李新義的書畫藝術,中國現代書畫家——譚奇中、李義象、高俊鵬等
  • 海底撈張勇名言,致張勇先生一封信:海底撈的“七宗罪”!
  • WPF學習(12)動畫
  • ui自動化測試工具,移動端UI自動化之appium的使用(二)
  • 爬蟲網站,Search For Free —— 新聞爬蟲及爬取結果的查詢網站
  • tenda騰達無線設置,騰達F6路由器無線中繼功能設置
  • 斐波那契數列、小青蛙跳臺階
  • OJ每日一練——小青蛙上臺階
  • 小青蛙貝葉斯
  • 小青蛙走臺階問題
  • MySQL數據庫下載,NAVICAT FOR MYSQL存儲過程