Wie mache ich die Sequenz zu einer nicht-abnehmenden Sequenz mit der minimalen Anzahl von Schritten?

Ich habe Arbeitscode in C # bereitgestellt. Es kann leicht auf Sprache Ihrer Wahl portiert werden. Die Zeitkomplexität liegt bei n2. Es kann in der Methode GenerateSequenceForEveryIndex () optimiert werden, wenn count mehr als minimumValue ist.

Erklärung des Algorithmus Jeder Elementwert kann als Pivot-Wert fungieren. Das bedeutet, dass die Werte auf der linken Seite gleich dem eigenen Wert und die Werte auf der rechten Seite größer oder gleich dem eigenen Wert sein müssen. Nachdem gesagt wurde, dass es ein Maximum von "n" eindeutigen nicht-absteigenden Sequenzen geben kann. Nun nimmt der Algorithmus jeweils den Wert an (siehe Methode GenerateSequenceForEveryIndex) und erzeugt eine neue nicht-absteigende Sequenz.

Innerhalb von GenerateSequenceForCurrentIndex () wird sichergestellt, dass Werte auf der linken Seite des Index gleich array [index] sind. Wir müssen uns um weniger Sorgen machen, als dies bereits durch verschiedene Sequenzen (bei Index & lt; aktueller Index) möglich ist. Werte auf der rechten Seite sind garantiert größer oder gleich dem aktuellen Wert. Jede Differenz wird als zusätzliche Bewegung (absoluter Wert) betrachtet

Schließlich zeigt DisplaySequence () nur die Werte aus der Sequenz an.

Nun, das Problem besagt, dass Sie nach der minimalen Anzahl von Änderungen streben sollten. Sagen wir, dass die letzte Zahl -1000000 ist. Wenn Sie die Sequenz sequenziell durchlaufen, müssen Sie am Ende 1000002 zum letzten Element hinzufügen, um eine nicht abnehmende Sequenz zu erhalten, aber die Lösung würde nicht die Anforderung erfüllen, die minimale Anzahl an Schritten zu verwenden. Daher kann es sinnvoll sein, die Sequenz einmal zu durchlaufen und die Unterschiede zwischen den Elementen zu erfassen. Ich hoffe, du verstehst mich. (Ich bin nicht so klar im Schreiben, wie meine Gedanken mir selbst erscheinen:)

Wenn Sie sich Bubble-Sortierung ansehen, wird im ersten Durchlauf der äußeren Schleife das Element an die richtige Stelle gesetzt. Ich versuche, dieses Konzept zu verwenden. Wenn Sie die Position für den ersten Durchlauf gefunden haben, verwenden Sie sie als Referenz und passen Sie alle Elemente in der Sequenz in Bezug auf dieses Element an.

Die Lösung finden Sie unter - Ссылка

Es sagt -

Beachten Sie, dass es eine nicht-abnehmende Sequenz gibt, die aus der gegebenen Sequenz mit einer minimalen Anzahl von Zügen erhalten werden kann und in der alle Elemente gleich einem Element aus der ursprünglichen Sequenz sind (dh die nur aus den Zahlen von besteht) die Anfangssequenz).

BEWEIS -

Angenommen, es gibt keine optimale Sequenz, in der jedes Element einem Element aus der ursprünglichen Sequenz entspricht. Dann gibt es ein Element i, das keinem der Elemente von {ai} gleicht. Wenn die Elemente mit den Zahlen i-1 und i + 1 nicht gleich dem Element i sind, können wir sie näher an ai bewegen und die Antwort wird abnehmen. Es gibt also einen Block von gleichen Elementen, und alle sind nicht gleich einem der Elemente der ursprünglichen Sequenz. Beachten Sie, dass wir alle Blöcke um 1 erhöhen oder um 1 verringern können und eine dieser Aktionen die Antwort nicht erhöht, sodass wir diesen Block nach oben oder unten verschieben können, bis alle Elemente gleich einem Element der ursprünglichen Sequenz sind.

ALGORITHMUS -

Angenommen, {ai} ist die Anfangssequenz, {bi} ist die gleiche Sequenz, in der jedoch alle Elemente verschieden sind und vom kleinsten zum größten sortiert sind. Sei f (i, j) die minimale Anzahl von Zügen, die erforderlich sind, um die Folge zu erhalten, in der die ersten i Elemente nicht abnehmen und das i-te Element höchstens bj ist. In diesem Fall ist die Antwort auf das Problem gleich f (n, k), wobei n die Länge von {ai} und k die Länge von {bi} ist. Wir berechnen f (i, j) unter Verwendung der folgenden Wiederholungen:

Die Komplexität ist O (N2). Um das Speicherlimit zu vermeiden, sollte man beachten, dass man zur Berechnung von f (i, ) nur f (i-1, ) und den Teil der i-ten Zeile, der bereits berechnet ist, kennen muss.

Ich habe folgende Idee:

1. Erstellen Sie Gruppen von nicht abnehmenden Sequenzen (in Ihrem Beispiel {3} {2} {-1 2 11})
2. Zwei Gruppen zusammenführen, dadurch wird die Anzahl der Gruppen um eins oder zwei reduziert.
3. Wenn es nur eine Gruppe gibt, wird eine nicht abnehmende Lösung gefunden. Wenn nicht, gehe zurück zu Schritt 2.

Zusammenführen: Es gibt immer zwei Möglichkeiten, zwei Gruppen zusammenzuführen, anzupassen die linke Gruppe oder passen Sie die richtige Gruppe an. Ich werde dies an Beispielen zeigen, Die Idee sollte klar sein.

Passen Sie die richtige Gruppe an:

Passen Sie die linke Gruppe an:

Weil es immer zwei Wege gibt (rechts anpassen / linke Gruppe anpassen) Sie können die Schritte in einem Backtracking-Algorithmus verwenden (der sich am besten erinnert Lösung gefunden bis jetzt).

Demonstration:

Lösungen: