Der Durchschnitt der gesetzten Bitanzahlen in einer bestimmten Binärzeichenfolge nach allen möglichen K Operationen

Bei diesem Problem müssen wir den Durchschnitt der eingestellten Bitanzahl ermitteln, nachdem wir alle ausgewählten K-Operationen für die gegebene Zeichenfolge ausgeführt haben.

Brute-Force-Methoden können zur Lösung des Problems verwendet werden, wir werden jedoch Wahrscheinlichkeitsprinzipien verwenden, um die zeitliche Komplexität von Brute-Force-Methoden zu überwinden.

Problemstellung – Wir erhalten eine Ganzzahl N, ein Array arr[] mit K positiven Ganzzahlen und eine Binärzeichenfolge der Länge N, die nur gesetzte Bits enthält. Wir müssen den Durchschnitt der eingestellten Bitanzahl ermitteln, nachdem wir alle möglichen K-Operationen ausgeführt haben. In der i-ten Operation können wir jedes arr[i]-Bit in der angegebenen Zeichenfolge umdrehen.

Beispiel

Eingabe– N = 2, arr[] = {1, 2}

Ausgabe– 1

Beschreibung – Die anfängliche Binärzeichenfolge ist 11.

• Im ersten Schritt können wir das erste Zeichen umdrehen und die Zeichenfolge lautet 01.

• In der zweiten Operation müssen wir zwei beliebige Bits umdrehen. Die Zeichenfolge wird also 10.

• Die zweite Auswahl kann durch Umdrehen des zweiten Zeichens aus dem ersten Schritt beginnen und die Zeichenfolge lautet 10.

• Im zweiten Schritt der aktuellen Operation müssen wir zwei beliebige Bits umdrehen, die Zeichenfolge kann 01 sein.

Wir haben also zwei Möglichkeiten: Die letzte Zeichenfolge kann 01 oder 10 sein.

Gesamtauswahlen = 2, insgesamt gesetzte Bits in der letzten Zeichenfolge = 2, ans = 2/2 = 1.

Eingabe– N = 3, arr[] = {2, 2}

Ausgabe– 1,6667

Erklärung – Wir haben eine Anfangszeichenfolge, die 111 ist.

• Im ersten Vorgang können wir zwei beliebige Zeichen umdrehen. Die Zeichenfolge könnte also 001, 100, 010 sein.

• In der zweiten Operation können wir 2 Bits in der resultierenden Zeichenfolge aus der ersten Operation umdrehen.

• Wenn wir zwei beliebige Bits von 001 umdrehen, erhalten wir 111, 010 und 100.

• Wenn wir zwei beliebige Ziffern von 100 umdrehen, erhalten wir 010, 111 und 001.

• Wenn wir zwei beliebige Bits von 010 umdrehen, können wir 100, 001 und 111 erhalten.

Also, bei der letzten Operation haben wir insgesamt 9 verschiedene Saiten bekommen.

Gesamtzahl der Ziffern in 9 Zeichenfolgen = 15, Gesamtzahl der Operationen = 9, Antwort = 15/9 = 1,6667

Methode 1

Hier verwenden wir das Wahrscheinlichkeitsprinzip, um dieses Problem zu lösen. Nehmen wir an, dass nach der Durchführung von i-1 Operationen der Durchschnittswert der gesetzten Bits p und der Durchschnittswert der nicht gesetzten Bits q ist. Wir müssen den Durchschnitt der gesetzten und nicht gesetzten Bits in der i-ten Operation berechnen.

Der aktualisierte Wert von p kann also p + die durchschnittliche Anzahl neu gesetzter Bits sein – die durchschnittliche Anzahl neuer Off-Bits.

Algorithmus

• Initialisieren Sie P auf N, weil wir anfänglich N gesetzte Bits haben, und initialisieren Sie Q auf 0, weil wir anfänglich 0 gesetzte Bits haben.

• Durchlaufen Sie das Operationsarray.

• Prev_p und prev_q mit P- und Q-Werten initialisieren.

• Aktualisieren Sie den P-Wert mit prev_p - prev_p * arr[i]/N + prev_q * arr[i]/N, wodurch die invertierten Bits im Durchschnitt zu den gesetzten Bits addiert werden und die gesetzten Bits im Durchschnitt in nicht gesetzte Bits invertiert werden

• Q-Wert aktualisieren.

• Gibt den P-Wert zurück.

Beispiel

Beispiel

#include <bits/stdc++.h>
using namespace std;

double getAverageBits(int len, int K, int array[]) {
   // to store the average '1's in the binary string
   double P = len;
   // to store the average '0's in the binary string
   double Q = 0;
   // Traverse the array array[]
   for (int i = 0; i < K; i++) {
      // Initialize the prev_p and prev_q with P and Q, which we got from the previous iteration
      double prev_p = P, prev_q = Q;
      // Update the average '1's
      P = prev_p - prev_p * array[i] / len + prev_q * array[i] / len;
      // Update the average '0's
      Q = prev_q - prev_q * array[i] / len + prev_p * array[i] / len;
   }
   return P;
}
int main() {
   int N = 2;
   int array[] = {1};
   int K = sizeof(array) / sizeof(array[0]);
   cout << "The average number of set bits after performing the operations is " << getAverageBits(N, K, array);
   return 0;
}

Ausgabe

The average number of set bits after performing the operations is 1

Zeitkomplexität – O(K), wobei K die Länge des Arrays ist.

Raumkomplexität – O(1), da wir keinen zusätzlichen Raum nutzen.

In diesem Tutorial haben wir gelernt, das durchschnittlich gesetzte Bit zu ermitteln, nachdem wir alle möglichen K-Operationen durchgeführt haben. Bei der Einzelauswahl müssen wir alle im Array angegebenen Operationen ausführen.

Das obige ist der detaillierte Inhalt vonDer Durchschnitt der gesetzten Bitanzahlen in einer bestimmten Binärzeichenfolge nach allen möglichen K Operationen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!