當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

递归方法实现最大公约数

發(fā)布時間：2023/12/14 编程问答 28 豆豆

生活随笔收集整理的這篇文章主要介紹了递归方法实现最大公约数小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.

最大公約數(shù)

最大公因數(shù)，也稱最大公約數(shù)、最大公因子，指兩個或多個整數(shù)共有約數(shù)中最大的一個

求最大公約數(shù)的方法有很多：質(zhì)因數(shù)分解法、短除法、輾轉(zhuǎn)相除法、更相減損法等

接下來我們以輾轉(zhuǎn)相除法為例子來求兩個數(shù)的最大公約數(shù)

輾轉(zhuǎn)相除法

輾轉(zhuǎn)相除法：輾轉(zhuǎn)相除法是求兩個自然數(shù)的最大公約數(shù)的一種方法，也叫歐幾里德算法。
例如：

求（319，377）：
∵ 319÷377=0（余319）
∴（319，377）=（377，319）；
∵ 377÷319=1（余58）
∴（377，319）=（319，58）；
∵ 319÷58=5（余29）
∴ （319，58）=（58，29）；
∵ 58÷29=2（余0）
∴ （58，29）= 29；
∴ （319，377）=29。

用輾轉(zhuǎn)相除法求幾個數(shù)的最大公約數(shù)，可以先求出其中任意兩個數(shù)的最大公約數(shù)，再求這個最大公約數(shù)與第三個數(shù)的最大公約數(shù)，依次求下去，直到最后一個數(shù)為止。最后所得的那個最大公約數(shù)，就是所有這些數(shù)的最大公約數(shù)。

數(shù)據(jù)分析

由上文所述，可以使用輾轉(zhuǎn)相除法（歐幾里德算法）來求最大公約數(shù)，那么我們可以將319，377這兩個具體的數(shù)值用函數(shù)的參數(shù)來代替。接下來尋找他的規(guī)律

第一輪

將（319，377）看作是（a，b）；

那么

319÷377=0（余319）可以看作是 a%b=x (余n);

n為余數(shù)

（319，377）=（377，319）；類似于（a，b）= （b，n）；
（即b=377，n=319）

注意：第二319不是一開始a=319的數(shù)，而是a%b得到的余數(shù)

第二輪

377÷319=1（余58）可以看作 a=377,b=319,a%b=x(余n);

（377，319）=（319，58）；類似于（a，b）= （b，n）；

和上一輪對比可知，我們可以將上一輪的b，n的值賦給第二輪的a，b，直到余數(shù)為0時，b為最大公約數(shù)，
這里可以使用遞歸方法實現(xiàn)

完成代碼

<!DOCTYPE html> <html lang="en"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0"><title>Document</title> </head><body><script>//輾轉(zhuǎn)相除法function measure(a, b) {var n = a % b //取余數(shù)if (n == 0) { //判斷余數(shù)是否為0，為0輸出b為最大公約數(shù)return b;} else {a = b; //將上一輪的b的值給ab = n; //將上一輪的n的值給breturn measure(a, b); //遞歸繼續(xù)調(diào)用函數(shù)直到余數(shù)n為0}}console.log(measure(319, 377));;// 29</script> </body></html>

好運藏在努力里~ 加油！💖

總結(jié)

以上是生活随笔為你收集整理的递归方法实现最大公约数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。

上一篇： Riak - 使用篇（1）
下一篇：举个栗子！Tableau 技巧（107）