資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告