基于歐幾里德算法的使用
更新時間：2013年05月02日 11:49:02 作者：
本篇文章介紹了，基于歐幾里德算法的使用。需要的朋友參考下
歐幾里德算法稱為輾轉(zhuǎn)相除法，用來求已知m、n兩個自然數(shù)的公因數(shù)。結(jié)合程序說明一下輾轉(zhuǎn)相除的具體情況。
首先看遞歸實現(xiàn)：
復(fù)制代碼 代碼如下:
int getcd(int m,int n)
{
if (m < 0 || n <0) {
return 0;
}
if(m < n)
{
int t = m;
m = n;
n = t;
}
if(m % n)
{
return getcd(n,(m % n));
}
else
{
return n;
}
}
主要計算過程分為三個步驟：
1、對輸入的兩個自然數(shù)m > n取余數(shù)r，使得0<= r < n
2、如果r為0，n即為所求結(jié)果，直接返回
3、r不為0，則賦值m=n,n=r從步驟1開始重新執(zhí)行
兩自然數(shù)的公因數(shù)的定義說明了計算結(jié)果產(chǎn)生的條件。如果步驟1中計算出的余數(shù)r = 0，則較小的數(shù)為公因數(shù)。如果r!=0則自然數(shù)m、n的關(guān)系可表示為：m = kn + r（其中k為自然數(shù)），等式可以證明能整除m的任何數(shù)必定能整除n和r；等式進(jìn)一步可變形為：r = m - kn，說明同時整除m、n的任何數(shù)也必定能整除r。也就是說，能整除m、n的數(shù)的集合與整除n、r的數(shù)的集合相等。所以輾轉(zhuǎn)相除的方法成立。
再發(fā)布一個循環(huán)實現(xiàn)歐幾里德算法的版本。
復(fù)制代碼 代碼如下:
int getcd2(int m,int n)
{
if (m < 0 || n <0) {
return 0;
}
if(m<n)
{
int t=m;
m=n;
n=t;
}
int cd = 1;
while(1){
int r = m % n;
if(0==r)
{
cd = n;
break;
}
else {
m=n;
n=r;
}
}
return cd;
}
相關(guān)文章
C++ 提供了異常機(jī)制，讓我們能夠捕獲運行時錯誤，本文就詳細(xì)的介紹了C++異常處理入門，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
這篇文章主要為大家詳細(xì)介紹了C語言三個函數(shù)的模擬實現(xiàn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03![深入理解char *a與char a[]的區(qū)別](http://img.jbzj.com/images/xgimg/bcimg2.png)
很多人可能或多或少知道char *a與char a[]的一些區(qū)別，但如果詳細(xì)的說出來卻不知如何說去，下面這篇文章就給大家詳細(xì)介紹了關(guān)于C語言中char *a與char a[]的區(qū)別，有需要的朋友們可以參考借鑒，下面來一起學(xué)習(xí)學(xué)習(xí)吧。2016-12-12
這篇文章主要介紹了c++ decltype關(guān)鍵字的用法，幫助大家更好的理解和學(xué)習(xí)c++，感興趣的朋友可以了解下2020-10-10
這篇文章主要介紹了C語言字符串轉(zhuǎn)換為Python字符串的方法，文中講解非常細(xì)致，代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下2020-07-07
C++ 提供了異常機(jī)制，讓我們能夠捕獲運行時錯誤，本文就詳細(xì)的介紹了C++異常處理入門，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
C++ xxx_cast實現(xiàn)轉(zhuǎn)換代碼實例解析
這篇文章主要介紹了C++xxx_cast轉(zhuǎn)換代碼實例解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-07-07
這篇文章主要介紹了C語言實現(xiàn)的循環(huán)單鏈表功能,結(jié)合實例形式分析了基于C語言實現(xiàn)的循環(huán)單鏈表定義、創(chuàng)建、添加、刪除、打印、排序等相關(guān)操作技巧,需要的朋友可以參考下2018-04-04
Qt添加MSVC2017編譯器是開發(fā)者在Windows平臺上進(jìn)行Qt應(yīng)用程序開發(fā)的重要步驟,本文詳細(xì)介紹了如何為Qt配置MSVC2017編譯器的具體步驟,感興趣的可以了解一下2023-09-09
C語言判斷數(shù)是否為素數(shù)與素數(shù)輸出
大家好，本篇文章主要講的是C語言判斷數(shù)是否為素數(shù)與素數(shù)輸出，感興趣的同學(xué)趕快來看一看吧，對你有幫助的話記得收藏一下，方便下次瀏覽2021-12-12