C語言如何求最大公約數(shù)？錯覺？C語言兩行代碼描述輾轉(zhuǎn)相除法

前言

本文主要介紹的是C語言常規(guī)的一道題，希望對于廣大讀者學(xué)習(xí)C語言有一些幫助。使用C語言求解a和b的最大公約數(shù)。該問題可以采用輾轉(zhuǎn)相除法去解決!

輾轉(zhuǎn)相除法

歐幾里德算法又稱輾轉(zhuǎn)相除法,歐幾里德算法是用來求兩個正整數(shù)最大公約數(shù)的算法。古希臘數(shù)學(xué)家歐幾里德在其著作《The Elements》中最早描述了這種算法,所以被命名為歐幾里德算法。擴(kuò)展歐幾里德算法可用于RSA加密等領(lǐng)域。

假如需要求 1997 和 615 兩個正整數(shù)的最大公約數(shù),用歐幾里德算法，是這樣進(jìn)行的：

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 /?1?= 2 (余0)

至此，最大公約數(shù)為1

以除數(shù)和余數(shù)反復(fù)做除法運(yùn)算，當(dāng)余數(shù)為 0 時，取當(dāng)前算式除數(shù)為最大公約數(shù)，所以就得出了 1997 和 615 的最大公約數(shù) 1。

代碼描述--新手版本

這種寫法是非常簡單的思路

1. 1.先求兩者中的最大值

2. 2.再用循環(huán)描述輾轉(zhuǎn)相除即可

源碼:

#include <stdio.h>
#include <stdlib.h>
int result(int m, int n)
{
int r;
if (m>n)
{
r = m, m = n, n = r;
}
r = n%m;
while (r != 0)
{
n = m;
m = r;
r = n%m;
}
return m;
}
int main()
{
printf("result:%d\n",result(12,9));
system("pause");
return 0;
}

代碼描述--大神版本

看到這個代碼，你的反應(yīng)是不是黑人問號？？輾轉(zhuǎn)相除法，還能這么寫？你寫了幾十行的代碼，別人只用了簡單幾行的遞歸就實現(xiàn)的功能。有興趣的可以去嘗試下哦，源碼如下:

#include <stdio.h>
#include <stdlib.h>
int result(int m, int n)
{
return n ? result(n, m%n) : m;
}
int main()
{
printf("result:%d\n",result(12,9));
system("pause");
return 0;
}

尾言

文章都是手打原創(chuàng)，每天最淺顯的介紹C語言、C++，windows知識，喜歡我的文章就關(guān)注一波吧，每天帶你學(xué)習(xí)C/C++不同的知識，也可以看到最新更新和之前發(fā)表的文章哦。如果足下基礎(chǔ)比較差，不妨關(guān)注下人人都可以學(xué)習(xí)的視頻教程通俗易懂，深入淺出，一個視頻只講一個知識點(diǎn)。視頻不深奧，不需要鉆研，在公交、在地鐵、在廁所都可以觀看，隨時隨地漲姿勢