C++-Programm: Finden Sie die größte teilbare Teilmenge in einem Array

In diesem Tutorial wird ein Problem besprochen, bei dem ein anderes Array positiver Ganzzahlen angegeben wird. Wir müssen die größte Teilmenge finden, sodass beispielsweise jedes Paar größerer Elemente durch das kleinere Element geteilt wird –

Input: nums[ ] = { 1, 4, 2, 6, 7}
Output: 1 2 4
Explanation:
All Divisible subsets are: (1, 2, 4), (1, 2, 6), (1, 7), etc
We have 2 subsets of length 3 in which all the pairs satisfy the condition.

Input: nums[ ] = { 1, 2, 3, 6 }
Output: 6 2 1

Möglichkeiten, die Lösung zu finden

Wir werden in diesem Tutorial zwei verschiedene Methoden erklären.

Einfache Methode

Bei der einfachen Methode können wir eine Rekursion anwenden, um dieses Problem zu lösen. Wir erhalten jedes Element und prüfen, ob es in die Teilmenge aufgenommen werden sollte. Nehmen wir an, wir beginnen mit dem ersten Element. Wir haben zwei Möglichkeiten, entweder in die Teilmenge aufgenommen zu werden oder nicht in das erste Element aufgenommen zu werden. Fügen wir das erste Element hinzu. Damit das zweite Element in die Teilmenge aufgenommen werden kann, muss es dann teilbar oder durch die Elemente in der Teilzeichenfolge (d. h. dem ersten Element) dividierbar sein. So iterieren wir über das Array. Daher gibt es 2^n mögliche Pfade mit einer Zeitkomplexität von O(2^n). Schauen wir uns mögliche Lösungen für dieses Problem an.

Effektive Methode

kann durch dynamische Programmierung gelöst werden.

• Sortieren Sie das Array so, dass das linke Element durch das richtige Element teilbar ist. Wir müssen einmal die Teilbarkeit prüfen.

• Wir werden die am längsten wachsende Teilsequenz, unser dp[ ]-Array, verwenden, um die größte teilbare Teilmenge bis zum i-ten Index zu speichern. Wir werden jeden Index mit 1 initialisieren, da sich jedes Element selbst teilt.

• Jetzt iterieren wir ausgehend vom zweiten Index und prüfen für jedes Element, ob es eine maximal teilbare Teilmenge gibt, die beim aktuellen Index endet. Auf diese Weise finden wir die größte Teilmenge für jeden Index.

• Jetzt durchlaufen Sie das Array und finden für jedes Element den Teiler mit der größten Teilbarkeit. Und ändert den teilbaren Zählwert des aktuellen Index in den teilbaren Zählwert dieses Elements + 1.

Beispiel: C++-Code für die obige Methode Teilmenge. Wir haben einen rekursiven Ansatz besprochen, der zu exponentieller Zeitkomplexität führt, also haben wir dynamische Programmierlösungen besprochen. Wir haben auch C++-Programme zur Lösung dieses Problems besprochen, die wir mithilfe von Programmiersprachen wie C, Java, Python usw. implementieren können. Wir hoffen, dass Sie dieses Tutorial hilfreich fanden.

Das obige ist der detaillierte Inhalt vonC++-Programm: Finden Sie die größte teilbare Teilmenge in einem Array. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!