詳解C語(yǔ)言求兩個(gè)數(shù)的最大公約數(shù)及最小公倍數(shù)的方法
更新時(shí)間：2016年03月15日 16:34:22 作者：wuzhekai1985
這篇文章主要介紹了C語(yǔ)言求兩個(gè)數(shù)的最大公約數(shù)及最小公倍數(shù)的方法,輾轉(zhuǎn)相除法和輾轉(zhuǎn)相減法在解決這種問題時(shí)最常用到,需要的朋友可以參考下
求兩個(gè)正整數(shù)的最大公約數(shù)
思路：這是一個(gè)很基本的問題，最常見的就是兩種方法，輾轉(zhuǎn)相除法和輾轉(zhuǎn)相減法。通式分別為 f(x, y) = f(y, x%y), f(x, y) = f(y, x - y) (x >=y > 0)。根據(jù)通式寫出算法不難，這里就不給出了。這里給出《編程之美》上的算法，主要是為了減少迭代的次數(shù)。
對(duì)于x和y，如果y = k * y1, x= k * x1，那么f(x, y) = k * f(x1, y1)。另外，如果x = p * x1，假設(shè)p為素?cái)?shù)，并且y % p != 0，那么f(x, y) = f(p * x1, y) = f(x1, y)。取p = 2。
參考代碼：
//函數(shù)功能: 求最大公約數(shù)
//函數(shù)參數(shù): x,y為兩個(gè)數(shù)
//返回值: 最大公約數(shù)
int gcd_solution1(int x, int y)
{
if(y == 0)
return x;
else if(x < y)
return gcd_solution1(y, x);
else
{
if(x&1) //x是奇數(shù)
{
if(y&1) //y是奇數(shù)
return gcd_solution1(y, x-y);
else //y是偶數(shù)
return gcd_solution1(x, y>>1);
}
else //x是偶數(shù)
{
if(y&1) //y是奇數(shù)
return gcd_solution1(x>>1, y);
else //y是偶數(shù)
return gcd_solution1(x>>1, y>>1) << 1;
}
}
}
求最小公倍數(shù)：
最常用的是輾轉(zhuǎn)相除法，有兩整數(shù)a和b：
① a%b得余數(shù)c
② 若c=0，則b即為兩數(shù)的最大公約數(shù)
③ 若c≠0，則a=b，b=c，再回去執(zhí)行①
下面非遞歸版本：
int gcd_solution2(int x, int y)
{
int result = 1;
while(y)
{
int t = x;
if(x&1)
{
if(y&1)
{
x = y;
y = t % y;
}
else
y >>= 1;
}
else
{
if(y&1)
x >>= 1;
else
{
x >>= 1;
y >>= 1;
result <<= 1;
}
}
}
return result * x;
}
相關(guān)文章
C語(yǔ)言fgetc和fputc函數(shù)用法詳解(以字符形式讀寫文件)
這篇文章主要介紹了C語(yǔ)言fgetc和fputc函數(shù)用法詳解(以字符形式讀寫文件)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)版通訊錄的代碼分享
這篇文章主要為大家詳細(xì)介紹了如何利用C語(yǔ)言實(shí)現(xiàn)一個(gè)簡(jiǎn)單的動(dòng)態(tài)版通訊錄，主要運(yùn)用了結(jié)構(gòu)體，一維數(shù)組，函數(shù)，分支與循環(huán)語(yǔ)句等等知識(shí)，需要的可以參考一下2023-01-01
這篇文章主要介紹了C++實(shí)現(xiàn)四叉樹效果(附源碼下載),非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2017-03-03
C語(yǔ)言開發(fā)實(shí)現(xiàn)掃雷游戲
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言開發(fā)實(shí)現(xiàn)掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-11-11
C++實(shí)現(xiàn)json形式的Socket傳輸圖片
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)json形式的Socket傳輸圖片，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-03-03
這篇文章主要為大家介紹了C/C++?extern關(guān)鍵字用法示例全面解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-01-01
C++字符數(shù)組、字符數(shù)組指針和string類
這篇文章主要介紹了C++字符數(shù)組、字符數(shù)組指針和string類，string是一個(gè)類而不是基本數(shù)據(jù)類型，數(shù)組不含有處理函數(shù)，下面更多詳細(xì)內(nèi)容，需要的小伙伴可以參考下面文章2022-03-03
本文介紹了QT定時(shí)器事件的概念和原理,闡述了其工作方式及實(shí)現(xiàn)方法,QT定時(shí)器事件可以用于在一定時(shí)間間隔內(nèi)執(zhí)行特定的任務(wù),從而實(shí)現(xiàn)定時(shí)操作和控制,具有一定的參考價(jià)值,感興趣的可以了解一下2023-08-08
C++ 實(shí)現(xiàn)優(yōu)先隊(duì)列的簡(jiǎn)單實(shí)例
這篇文章主要介紹了C++ 實(shí)現(xiàn)優(yōu)先隊(duì)列的簡(jiǎn)單實(shí)例的相關(guān)資料,希望通過本文能幫助大家實(shí)現(xiàn)優(yōu)先隊(duì)列，需要的朋友可以參考下2017-08-08
這篇文章主要介紹了如何利用Matlab實(shí)現(xiàn)繪制有趣的羅盤時(shí)鐘，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)Matlab有一定的幫助，需要的可以參考一下2023-01-01