Heim > Backend-Entwicklung > C++ > Gehört der größte gemeinsame Teiler einer Teilmenge des Arrays zum gegebenen Array?

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

WBOY
Freigeben: 2023-09-03 10:25:04
nach vorne
663 Leute haben es durchsucht

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
Nach dem Login kopieren

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);
}
Nach dem Login kopieren

Ausgabe

2 2 4 2 6 2 12
Nach dem Login kopieren

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!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage