Le plus grand diviseur commun d'un sous-ensemble du tableau appartient-il au tableau donné ?

Ici, nous verrons une question intéressante. Il existe un ensemble contenant N éléments. Nous devons générer un tableau tel que le GCD de tout sous-ensemble du tableau se trouve dans l'ensemble d'éléments donné. Une autre limitation est que le tableau résultant ne doit pas dépasser trois fois la longueur de la collection GCD. Par exemple, s'il y a 4 nombres {2, 4, 6, 12}, alors un tableau sera {2, 2, 4, 2, 6, 2, 12}

Pour résoudre ce problème, il faut d'abord faire le Triez, puis si le GCD est le même que le plus petit élément de la collection donnée, vous pouvez créer le tableau en plaçant simplement le GCD entre chaque élément. Sinon, le tableau ne peut pas être formé.

Algorithme

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

Exemple

#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);
}

Sortie

2 2 4 2 6 2 12

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!