数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究在C++中，从给定数组中连续元素的最大公约数构造一个数组
假设我们有一个包含n个元素的数组A[]。我们必须找到另一个大小为n+1的数组B[]，使得B[i]和B[i+1]的最大公约数为A[i]。如果有多个解，则打印其中数组和最小的一个。因此，如果A = [1, 2, 3]，则输出为[1, 2, 6, 3]
当A只有一个元素K时，则B = [K, K]。所以B[0]将是A[0]。现在考虑我们已经处理到索引i，所以我们已经处理了索引i，并计算了B[i+1]。现在B[i+1]和B[i+2]的最大公约数= A[i+1]，则B[i+2]和B[i+3]的最大公约数= A[i+2]。所以B[i+2] >= A[i+1]和A[i+2]的最小公倍数。因为我们想要最小和，所以我们想要得到B[i+2]的最小值，所以B[i+2] – A[i+2]和A[i+3]的最小公倍数
示例
#include <iostream>
#include <algorithm>
using namespace std;
int getLCM(int a, int b) {
return (a * b) / __gcd(a, b);
}
void gcdArray(int A[], int n) {
cout << A[0] << " ";
for (int i = 0; i < n - 1; i++)
cout << getLCM(A[i], A[i + 1]) << " ";
cout << A[n - 1];
}
int main() {
int A[] = { 1, 2, 3 };
int n = sizeof(A) / sizeof(A[0]);
cout << "Constructed array: ";
gcdArray(A, n);
}输出
Constructed array: 1 2 6 3
更新于：2019年12月30日
150 次浏览
广告