【C語言】聊聊輾轉相除法 - IT人

輾轉相除法，又名歐幾里德演算法。

用於計算兩數最大公約數（gcd） 主要思想是：gcd（a，b）=gcd（b，a%b） （a>=b) 原理證明也很簡單： 先不妨 ... Togglenavigation IT人 IT人 【C語言】聊聊輾轉相除法 xVIX發表於 2020-12-13 輾轉相除法，又名歐幾里德演算法。

用於計算兩數最大公約數（gcd） 主要思想是：gcd（a，b）=gcd（b，a%b）（a>=b) 原理證明也很簡單：先不妨設a=kb+r，a=cx，b=cy（c為最大公約數，也即x和y已無公因式） r=a-kb=c（x-ky）=>說明c是約數，那麼只需證明c是最大的公約數，也即x-ky和y無公因式即可 這裡的證明採用反證法假設x-ky=md，y=nd(d>1)則x=md+ky=md+knd=d(m+kn)a=cx=(m+kn)cd，b=cy=ncd=>a與b存在一個公約數cd>c與c是a與b的最大公約數矛盾也即結論錯誤，二者無公因式 QED 那麼清楚原理後，程式碼實現就很簡單了 你可以寫成遞迴的 intgcd(inta,intb) { returna%b？gcd(b,a%b):b; } 也可以寫成迴圈的 intgcd(inta,intb) { while(b!=0) { intr=a%b; a=b; b=r; } returna; } 相關文章 【C語言練習題】小球反彈問題 2020-12-11 C語言程式設計-現代方法第二版第4.1小節計算通用產品程式碼的校驗位 2020-12-12 C語言程式設計-現代方法第二版第2.5小節程式碼計算箱子的空間重量改進版 2020-12-12 C語言程式設計-現代方法第二版第2.6小節華氏溫度轉化為攝氏溫度 2020-12-12 C語言程式設計-現代方法第二版第5.2.3小節計算股票經紀人的佣金 2020-12-12 C語言程式設計-現代方法第二版2.1小節顯示雙關語 2020-12-12 C語言程式設計-現代方法第二版第6.1小節顯示平方表 2020-12-12 C語言程式設計-現代方法第二版第2.4.4小節計算箱子的空間重量 2020-12-12 C語言程式設計-現代方法第二版第3.1小節用printf函式格式化數 2020-12-12 whyelmlang:最簡最安全的fullolastack的終身webappdev語言選型 2020-12-12 50.C++物件模型的分析(上)(C語言實現物件導向特性) 2020-12-12 C++物件導向 各個程式語言語言的檔案/函式/變數的命名方法 2020-12-12 程式語言 資料結構——單連結串列介面實現(C語言) 2020-12-12 資料結構 Linux下C語言驗證多程式 2020-12-13 Linux SQL語言與資料庫完整性和安全性 2020-12-13 資料庫SQL c語言筆記：楊輝三角 2020-12-13 Luogu1196銀河英雄傳說+Python函式的定義與呼叫（C++/Python雙語言實現） 2020-12-13 PythonC++ c語言：定義一個含10個整型元素的一維陣列,從鍵盤上輸入10個元素值,求去掉最大值和最小值之後的元素平均值 2020-12-13 安全宣告標記語言SAML2.0初探 2020-12-13 【作業系統】頁面置換演算法（最佳置換演算法）（C語言實現） 2020-12-13 演算法 最新文章 「Vue原始碼學習」你真的知道插槽Slot是怎麼“插”的嗎 Android隱私合規靜態檢查實現(二) 分享2個超實用的線性迴歸分析操作教程，有手就會！ 追熱點不僅姿勢要對，工具也要對 Python英語單詞本 RPA榮譽：實在智慧獲評「2021年數字化服務創新潛力企業」 微信智慧經營是什麼，如何增加收入？ SpringBoot分片上傳檔案 五年推出僅兩代產品，雲鯨卻在智慧掃地機器人排名靠前！ 怎樣查詢兩組專案檔案的不同之處？推薦使用Kaleidoscope開發者檔案比較工具！ Amazing！！CSS也能實現煙霧效果？ 警惕！PHP、Node、Ruby和Python應用，漏洞還沒結束！