基于歐幾里德算法的使用
更新時間：2013年05月02日 11:49:02 作者：
本篇文章介紹了，基于歐幾里德算法的使用。需要的朋友參考下
歐幾里德算法稱為輾轉相除法，用來求已知m、n兩個自然數(shù)的公因數(shù)。結合程序說明一下輾轉相除的具體情況。
首先看遞歸實現(xiàn)：
復制代碼 代碼如下:
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即為所求結果，直接返回
3、r不為0，則賦值m=n,n=r從步驟1開始重新執(zhí)行
兩自然數(shù)的公因數(shù)的定義說明了計算結果產(chǎn)生的條件。如果步驟1中計算出的余數(shù)r = 0，則較小的數(shù)為公因數(shù)。如果r!=0則自然數(shù)m、n的關系可表示為：m = kn + r（其中k為自然數(shù)），等式可以證明能整除m的任何數(shù)必定能整除n和r；等式進一步可變形為：r = m - kn，說明同時整除m、n的任何數(shù)也必定能整除r。也就是說，能整除m、n的數(shù)的集合與整除n、r的數(shù)的集合相等。所以輾轉相除的方法成立。
再發(fā)布一個循環(huán)實現(xiàn)歐幾里德算法的版本。
復制代碼 代碼如下:
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;
}
相關文章
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡易版掃雷，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-02-02
這篇文章主要介紹了C++中形參和實參的區(qū)別及說明，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要為大家分享下本人在閱讀《C++ Primer》函數(shù)一章時的讀書總結,需要的朋友可以參考下2014-02-02
這篇文章主要給大家介紹了關于C++中對象&類的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-05-05
這篇文章主要介紹了詳解C語言-二級指針三種內存模型的相關知識，文中代碼非常詳細，供大家參考和學習，感興趣的朋友可以了解下2020-06-06
這篇文章主要介紹了C++求兩數(shù)之和并返回下標題目的代碼詳解，本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-08-08
在C++中實現(xiàn)aligned_malloc的方法
這篇文章主要介紹了在C++中實現(xiàn)aligned_malloc的方法，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-03-03
C++指針和數(shù)組：字符和字符串、字符數(shù)組的關聯(lián)和區(qū)別
字符串是一種重要的數(shù)據(jù)類型，但是c語言并沒有顯示的字符串數(shù)據(jù)類型，因為字符串以字符串常量的形式出現(xiàn)或者存儲于字符數(shù)組中。在C++標準模板庫（STL）中提供了string類，實現(xiàn)了對字符串的封裝。2022-12-12
C++是一種面向對象編程語言，但它也可以作為C語言的擴展語言。在C++中，我們可以使用非面向對象方面的特性來擴展C語言。在本文中，我們將討論C++在非面向對象方面對C語言的擴充2023-05-05
這篇文章主要為大家詳細介紹了C++ Clock類模擬實現(xiàn)鬧鐘運行，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03