資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究C++ 中所有可能子陣列的最小 LCM 和 GCD
假設我們有一個大小為 N 的陣列 arr。它有 N 個正數。我們必須查詢所有可能子陣列的最小元素。假設陣列為 {2, 66, 14, 521}，則最小 LCM 為 2，GCD 為 1。
我們將使用貪婪演算法解決此問題。如果減少元素數量，則 LCM 將更小，如果增加陣列大小，GCD 將更小。我們需要在陣列中找到最小的元素，該元素是一個單一元素，它將是必需的 LCM。對於 GCD，它將是陣列所有元素的 GCD。
示例
#include <iostream>
#include <algorithm>
using namespace std;
int minimum_gcd(int arr[], int n) {
int GCD = 0;
for (int i = 0; i < n; i++)
GCD = __gcd(GCD, arr[i]);
return GCD;
}
int minimum_lcm(int arr[], int n) {
int LCM = arr[0];
for (int i = 1; i < n; i++)
LCM = min(LCM, arr[i]);
return LCM;
}
int main() {
int arr[] = { 2, 66, 14, 521 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "LCM: " << minimum_lcm(arr, n) << ", GCD: " << minimum_gcd(arr, n);
}輸出
LCM: 2, GCD: 1
更新於：21-Oct-2019
191 瀏覽
廣告