詳解C語言求兩個(gè)數(shù)的最大公約數(shù)及最小公倍數(shù)的方法
更新時(shí)間：2016年03月15日 16:34:22 作者：wuzhekai1985
這篇文章主要介紹了C語言求兩個(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ù)。
對于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語言中g(shù)etchar()與putchar()函數(shù)詳解
本文主要介紹了C語言中g(shù)etchar()與putchar()函數(shù)詳解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01
windows自帶的游戲《掃雷》是陪伴了無數(shù)人的經(jīng)典游戲，本文將利用C語言實(shí)現(xiàn)這一經(jīng)典的游戲，文中的示例代碼講解詳細(xì)，感興趣的可以學(xué)習(xí)一下2022-05-05
這篇文章主要為大家詳細(xì)介紹了Qt簡單實(shí)現(xiàn)密碼器控件，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
生成隨機(jī)數(shù)rand函數(shù)的用法詳解
本篇文章是對生成隨機(jī)數(shù)rand函數(shù)的用法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C++常見編程問題解決方案,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07
這篇文章主要為大家介紹了C++實(shí)現(xiàn)Linux框架示例代碼詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-12-12
這篇文章主要為大家詳細(xì)介紹了C語言基于圖形庫實(shí)現(xiàn)雙人貪吃蛇，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-05-05
C/C++ Qt 基本文件讀寫的基本使用(2種實(shí)現(xiàn))
文件的讀寫是很多應(yīng)用程序具有的功能，本文主要介紹了兩種實(shí)現(xiàn)方法，第一種使用QFile類的IODevice讀寫功能直接讀寫，第二種是利用 QFile和QTextStream結(jié)合起來，用流的方式進(jìn)行文件讀寫2021-11-11
為了讓程序盡快響應(yīng)用戶操作，在開發(fā)應(yīng)用程序時(shí)經(jīng)常會使用到線程。這篇文章就來和大家介紹一下Qt中線程的實(shí)際應(yīng)用，感興趣的小伙伴可以了解一下2023-03-03
C++運(yùn)行時(shí)類型識別與轉(zhuǎn)換實(shí)現(xiàn)方法
運(yùn)行時(shí)類型識別可能被認(rèn)為是C++中一個(gè)”次要“的特征，當(dāng)程序員在編程過程中陷入非常困難的境地時(shí)，實(shí)用主義將會幫助他走出困境2022-10-10