資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究任意子集的 GCD 都屬於給定陣列的陣列？
下面我們來看看一個有意思的問題。有一組 N 個元素。我們必須生成這樣一個數組，其 GCD 的任何子集都位於給定元素組中。另一個限制是，生成的陣列長度不應超過 GCD 組長度的三倍。比如，如果有 4 個數字 {2, 4, 6, 12}，那麼一個數組將為 {2, 2, 4, 2, 6, 2, 12}
要解決這個問題，我們首先必須對列表進行排序，然後如果 GCD 與給定組中的最小元素相同，那麼僅在每個元素之間放入 GCD 就可建立陣列。否則，無法形成任何陣列。
演算法
generateArray(arr, n)
Begin answer := empty array gcd := gcd of array arr if gcd is same as the min element of arr, then for each element e in arr, do append gcd into answer append e into answer done display answer else array cannot be formed end if End
示例
#include<iostream>
#include<vector>
#include<set>
using namespace std;
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
int getGCDofArray(vector<int> arr) {
int result = arr[0];
for (int i = 1; i < arr.size(); i++)
result = gcd(arr[i], result);
return result;
}
void generateArray(vector<int> arr) {
vector<int> answer;
int GCD_of_array = getGCDofArray(arr);
if(GCD_of_array == arr[0]) { //if gcd is same as minimum element
answer.push_back(arr[0]);
for(int i = 1; i < arr.size(); i++) { //push min before each
element
answer.push_back(arr[0]);
answer.push_back(arr[i]);
}
for (int i = 0; i < answer.size(); i++)
cout << answer[i] << " ";
}
else
cout << "No array can be build";
}
int main() {
int n = 4;
int data[]= {2, 4, 6, 12};
set<int> GCD(data, data + n);
vector<int> arr;
set<int>::iterator it;
for(it = GCD.begin(); it!= GCD.end(); ++it)
arr.push_back(*it);
generateArray(arr);
}輸出
2 2 4 2 6 2 12
更新於: 2019 年 8 月 1 日
97 次瀏覽
廣告