La moyenne du nombre de bits définis dans une chaîne binaire donnée après toutes les K opérations possibles

Dans ce problème, nous devons trouver la moyenne du nombre de bits défini après avoir effectué toutes les opérations K sélectionnées sur la chaîne donnée.

Les méthodes de force brute peuvent être utilisées pour résoudre le problème, mais nous utiliserons des principes de probabilité pour surmonter la complexité temporelle des méthodes de force brute.

Énoncé du problème - On nous donne un entier N, un tableau arr[] contenant K entiers positifs et une chaîne binaire de longueur N contenant uniquement des bits définis. Nous devons trouver la moyenne du nombre de bits défini après avoir effectué toutes les K opérations possibles. Dans la ième opération, nous pouvons inverser n’importe quel bit arr[i] dans la chaîne donnée.

Exemple

Entrée– N = 2, arr[] = {1, 2}

Sortie– 1

Description – La chaîne binaire initiale est 11.

• Dans la première étape, nous pouvons retourner le premier caractère et la chaîne sera 01.

• Dans la deuxième opération, nous devons retourner deux bits quelconques. La chaîne deviendra donc 10.

• La deuxième sélection peut commencer en retournant le deuxième caractère de la première étape et la chaîne sera 10.

• Dans la deuxième étape de l'opération en cours, nous devons inverser 2 bits, la chaîne peut être 01.

Nous avons donc deux choix, la chaîne finale peut être 01 ou 10.

Total des sélections = 2, total des bits définis dans la chaîne finale = 2, ans = 2/2 = 1.

Entrée– N = 3, arr[] = {2, 2}

Sortie– 1,6667

Explication – Nous avons une chaîne initiale qui est 111.

• Dans la première opération, nous pouvons retourner 2 personnages quelconques. La chaîne pourrait donc être 001, 100, 010.

• Dans la deuxième opération, nous pouvons inverser 2 bits dans la chaîne résultante de la première opération.

• Lorsque nous retournons deux bits de 001, nous obtenons 111, 010 et 100.

• Lorsque nous retournons 2 chiffres de 100, nous pouvons obtenir 010, 111 et 001.

• Lorsque nous retournons deux bits de 010, nous pouvons obtenir 100, 001 et 111.

Donc, lors de la dernière opération, nous avons obtenu un total de 9 chaînes différentes.

Nombre total de chiffres dans 9 chaînes = 15, nombre total d'opérations = 9, réponse = 15/9 = 1,6667

Méthode 1

Ici, nous utiliserons le principe de probabilité pour résoudre ce problème. Supposons qu'après avoir effectué i-1 opérations, la valeur moyenne des bits définis est p et la valeur moyenne des bits non définis est q. Nous devons calculer la moyenne des bits activés et non activés dans la ième opération.

Ainsi, la valeur mise à jour de p peut être p + le nombre moyen de nouveaux bits définis - le nombre moyen de nouveaux bits désactivés.

Algorithme

• Initialisez P à N car nous avons initialement N bits définis, et initialisons Q à 0 car nous avons initialement 0 bits définis.

• Traversez le tableau d'opérations.

• Initialisez prev_p et prev_q avec les valeurs P et Q.

• Mettez à jour la valeur P en utilisant prev_p - prev_p * arr[i]/N + prev_q * arr[i]/N, ce qui ajoutera les bits inversés aux bits définis en moyenne et inversera les bits définis en moyenne en bits non définis

• Mettre à jour la valeur Q.

• Renvoie la valeur P.

La traduction chinoise de

Exemple

est :

Exemple

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

Sortie

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

Complexité temporelle - O(K), où K est la longueur du tableau.

Complexité spatiale - O(1) puisque nous n'utilisons aucun espace supplémentaire.

Dans ce tutoriel, nous avons appris à trouver le bit moyen après avoir effectué tous les choix possibles d'opérations K. En sélection unique, nous devons effectuer toutes les opérations données dans le tableau.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!