数据结构
网络
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 浏览
广告