C語言 擴展歐幾里得算法代碼
更新時間：2013年09月01日 15:03:01 作者：
這篇文章介紹了擴展歐幾里得算法的實現(xiàn)代碼，有需要的朋友可以參考一下
給定兩個正整數(shù)m和n,我們計算它們的最大公因子d和兩個整數(shù)a和b,使得a*m+b*n=d
算法流程
E1.置a'=b=1;a=b'=0;c=m,d=n;
E2.計算d和r,使得c=q*d+r;
E3.若r==0;則退出,當前已有a*m+b*n=d;
E4;c=d;d=r;t=a';a'=a;a=t-q*a;t=b';b'=b;b=t-q*b;返回E2.
證明
對于已有的m和n,假設m>n;如果刨除變量a,b,a',b';算法與歐幾里得算法完全一樣,為計算最大公約數(shù)的算法.
最終要求的為a*m+b*n=d=GCD(m,n);如果改式子成立由歐幾里得算法可推出a'*n+b'*(m%n)=GCD(n,m%n);
因為GCD(m,n)=GCD(n,m%n);
所以a*m+b*n=a'*n+b'*(m%n)
=a'*n+b'*(m-(m/n)*n)
=a'*n+b'*m-b'*(m/n)*n
=b'*m+(a'-b'*(m/n))*n
所以a=b';b=a'-b'*(m/n);
可以推出根據(jù)a‘、b'可以計算a、b。
代碼實現(xiàn)
復制代碼 代碼如下:
void EGCD(int m,int n)
{
int a,a1,b,b1,c,d,q,r,t;
a1=b=1,a=b1=0,c=m,d=n;
while(1)
{
q=c/d,r=c%d;
if(r==0)
{
printf("(%d)*%d+(%d)*%d=%d\n",a,m,b,n,d);
return;
}
c=d,d=r,t=a1,a1=a,a=t-q*a,t=b1,b1=b,b=t-q*b;
}
}
相關文章
C語言 超詳細介紹與實現(xiàn)線性表中的帶頭雙向循環(huán)鏈表
帶頭雙向循環(huán)鏈表：結構最復雜，一般用在單獨存儲數(shù)據(jù)。實際中使用的鏈表數(shù)據(jù)結構，都是帶頭雙向循環(huán)鏈表。另外這個結構雖然結構復雜，但是使用代碼實現(xiàn)以后會發(fā)現(xiàn)結構會帶來很多優(yōu)勢，實現(xiàn)反而簡單2022-03-03
Embarcadero?Dev-C++輸出中文亂碼問題圖文詳解
Dev-C++(或者叫做 Dev-Cpp)是Windows環(huán)境下的一個輕量級C/C++ 集成開發(fā)環(huán)境(IDE),下面這篇文章主要給大家介紹了關于Embarcadero?Dev-C++輸出中文亂碼問題的相關資料,需要的朋友可以參考下2023-01-01
這篇文章主要介紹了C語言常見的一些語義陷阱，梳理的比較全面，對我們做開發(fā)的過程中有一定幫助，感興趣的朋友快來看看吧2022-03-03
這篇文章主要介紹了C++遺傳算法的一個類文件,是學習遺傳算法的絕佳參考資料,需要的朋友可以參考下2014-08-08
本文主要介紹了C++17之std::any的具體使用，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-02-02
大家好，本篇文章主要講的是C語言遞歸思想實現(xiàn)漢諾塔詳解，感興趣的同學趕快來看一看吧，對你有幫助的話記得收藏一下2022-01-01
c語言合并兩個已排序數(shù)組的示例(c語言數(shù)組排序)
如何將兩個已排序數(shù)組合并成一個排序數(shù)組,下面我們給出使用c語言合并兩個已排序數(shù)組的示例,需要的朋友可以參考下2014-03-03
這篇文章主要利用Matlab實現(xiàn)繪制獨特的表白動圖，文中的示例代碼講解詳細，對我們學習Matlab有一定的幫助，感興趣的小伙伴可以了解一下2022-05-05
在C++中mutable關鍵字正如字面意思所示,表示「可變的」之意,一般在以下兩種情況中使用較多,一是修飾類中的變量,用來突破const的限制,二是在Lambda表達式中使用,用來捕獲修改表達式之外的變量值,下面我們就針對這兩種使用場景逐個介紹2023-10-10
C++11 新增了很多特性，lambda 表達式是其中之一，本文涉及到C++11這次更新中較為重要的lambda表達式。有需要的朋友們可以參考學習。2016-08-08