資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 程式用於求多個數字（或陣列）的最大公約數？
在這裡，我們將看到如何獲取多個數字的最大公約數。求兩個數字的最大公約數很容易。當我們想要求多個數字的最大公約數時，我們必須遵循最大公約數的結合律。例如，如果我們想求 {w, x, y, z} 的最大公約數，那麼它將是 {gcd(w,x), y, z}，然後是 {gcd(gcd(w,x), y), z}，最後是 {gcd(gcd(gcd(w,x), y), z)}。使用陣列可以很輕鬆地完成此操作。
演算法
gcd(a, b)
begin if a is 0, then return b end if return gcd(b mod a, a) end
getArrayGcd(arr, n)
begin res := arr[0] for i in range 1 to n-1, do res := gcd(arr[i], res) done return res; end
範例
#include<iostream>
using namespace std;
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b%a, a);
}
int getArrayGcd(int arr[], int n) {
int res = arr[0];
for(int i = 1; i < n; i++) {
res = gcd(arr[i], res);
}
return res;
}
main() {
int arr[] = {4, 8, 16, 24};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "GCD of array elements: " << getArrayGcd(arr, n);
}輸出結果
GCD of array elements: 4
更新於：2019 年 7 月 30 日
136 次瀏覽
廣告