前言
本文主要介紹的是C語言常規的一道題,希望對於廣大讀者學習C語言有一些幫助。使用C語言求解a和b的最大公約數。該問題可以採用輾轉相除法去解決!
輾轉相除法
歐幾里德算法又稱輾轉相除法,歐幾里德算法是用來求兩個正整數最大公約數的算法。古希臘數學家歐幾里德在其著作《The Elements》中最早描述了這種算法,所以被命名為歐幾里德算法。擴展歐幾里德算法可用於RSA加密等領域。
假如需要求 1997 和 615 兩個正整數的最大公約數,用歐幾里德算法,是這樣進行的:
<code>1997 / 615 = 3 (餘 152)
615 / 152 = 4(餘7)
152 / 7 = 21(餘5)
7 / 5 = 1 (餘2)
5 / 2 = 2 (餘1)
2 / 1 = 2 (餘0)/<code>
至此,最大公約數為1
以除數和餘數反覆做除法運算,當餘數為 0 時,取當前算式除數為最大公約數,所以就得出了 1997 和 615 的最大公約數 1。
代碼描述--新手版本
這種寫法是非常簡單的思路
- 1.先求兩者中的最大值
- 2.再用循環描述輾轉相除即可
源碼:
<code>#include <stdio.h>
#include <stdlib.h>
int result(int m, int n)
{
\tint r;
\tif (m>n)
\t{
\t\tr = m, m = n, n = r;
\t}
\tr = n%m;
\twhile (r != 0)
\t{
\t\tn = m;
\t\tm = r;
\t\tr = n%m;
\t}
\treturn m;
}
int main()
{
\tprintf("result:%d\\n",result(12,9));
\tsystem("pause");
\treturn 0;
}/<stdlib.h>/<stdio.h>/<code>
代碼描述--大神版本
看到這個代碼,你的反應是不是黑人問號??輾轉相除法,還能這麼寫?你寫了幾十行的代碼,別人只用了簡單幾行的遞歸就實現的功能。有興趣的可以去嘗試下哦,源碼如下:
<code>#include <stdio.h>
#include <stdlib.h>
int result(int m, int n)
{
\treturn n ? result(n, m%n) : m;
}
int main()
{
\tprintf("result:%d\\n",result(12,9));
\tsystem("pause");
\treturn 0;
}/<stdlib.h>/<stdio.h>/<code>
尾言
文章都是手打原創,每天最淺顯的介紹C語言、C++,windows知識,喜歡我的文章就關注一波吧,每天帶你學習C/C++不同的知識,也可以看到最新更新和之前發表的文章哦。如果足下基礎比較差,不妨關注下人人都可以學習的視頻教程
通俗易懂,深入淺出,一個視頻只講一個知識點。視頻不深奧,不需要鑽研,在公交、在地鐵、在廁所都可以觀看,隨時隨地漲姿勢
閱讀更多 C語言基礎 的文章