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