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