Gehört der größte gemeinsame Teiler einer Teilmenge des Arrays zum gegebenen Array?

Hier sehen wir eine interessante Frage. Es gibt eine Menge mit N Elementen. Wir müssen ein Array so generieren, dass der GCD jeder Teilmenge des Arrays innerhalb der gegebenen Menge von Elementen liegt. Eine weitere Einschränkung besteht darin, dass das resultierende Array die dreifache Länge der GCD-Sammlung nicht überschreiten darf. Wenn es zum Beispiel 4 Zahlen {2, 4, 6, 12} gibt, dann ist ein Array {2, 2, 4, 2, 6, 2, 12}

Um dieses Problem zu lösen, müssen wir zuerst Folgendes tun Sortieren: Wenn der GCD mit dem kleinsten Element der angegebenen Sammlung übereinstimmt, können Sie das Array erstellen, indem Sie einfach den GCD zwischen den einzelnen Elementen platzieren. Andernfalls kann das Array nicht gebildet werden.

Algorithmus

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

Beispiel

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

Ausgabe

2 2 4 2 6 2 12

Das obige ist der detaillierte Inhalt vonGehört der größte gemeinsame Teiler einer Teilmenge des Arrays zum gegebenen Array?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!