Purata bit yang ditetapkan dikira dalam rentetan binari yang diberikan selepas semua kemungkinan operasi K

Dalam masalah ini, kita perlu mencari purata kiraan bit yang ditetapkan selepas melakukan semua operasi K terpilih pada rentetan yang diberikan.

Kaedah brute force boleh digunakan untuk menyelesaikan masalah, tetapi kami akan menggunakan prinsip kebarangkalian untuk mengatasi kerumitan masa kaedah brute force.

Pernyataan Masalah - Kami diberi integer N, array arr[] yang mengandungi K integer positif dan rentetan binari panjang N yang mengandungi hanya set bit. Kita perlu mencari purata kiraan bit yang ditetapkan selepas melakukan semua kemungkinan operasi K. Dalam operasi ke-3, kita boleh menyelak mana-mana bit arr[i] dalam rentetan yang diberikan.

Contoh

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

Output– 1

Penerangan – Rentetan binari awal ialah 11.

• Dalam langkah pertama, kita boleh menyelak aksara pertama dan rentetannya ialah 01.

• Dalam operasi kedua, kita perlu menyelak mana-mana dua bit. Jadi rentetan akan menjadi 10.

• Pilihan kedua boleh bermula dengan membalikkan aksara kedua dari langkah pertama dan rentetannya ialah 10.

• Dalam langkah kedua operasi semasa, kita perlu membalikkan mana-mana 2 bit, rentetan boleh menjadi 01.

Jadi, kita ada dua pilihan, rentetan akhir boleh jadi 01 atau 10.

Jumlah pilihan = 2, jumlah set bit dalam rentetan akhir = 2, ans = 2/2 = 1.

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

Output– 1.6667

Penjelasan – Kami mempunyai rentetan awal iaitu 111.

• Dalam operasi pertama, kita boleh menyelak mana-mana 2 aksara. Jadi rentetan itu boleh menjadi 001, 100, 010.

• Dalam operasi kedua, kita boleh menyelak 2 bit dalam rentetan yang terhasil daripada operasi pertama.

• Apabila kita menyelak mana-mana dua bit 001, kita mendapat 111, 010 dan 100.

• Apabila kita menyelak mana-mana 2 digit 100, kita boleh mendapat 010, 111 dan 001.

• Apabila kita menyelak mana-mana dua bit 010, kita boleh mendapat 100, 001 dan 111.

Jadi, dalam operasi lepas, kami mendapat sejumlah 9 rentetan yang berbeza.

Jumlah set bilangan digit dalam 9 rentetan=15, jumlah bilangan operasi=9, answer=15/9=1.6667

Kaedah 1

Di sini, kami akan menggunakan prinsip kebarangkalian untuk menyelesaikan masalah ini. Katakan selepas menjalankan operasi i-1, nilai purata bit yang ditetapkan ialah p dan nilai purata bit yang tidak ditetapkan ialah q. Kita perlu mengira purata bit set dan bit tidak ditetapkan dalam operasi ke-i.

Jadi, nilai p yang dikemas kini boleh menjadi p + purata bilangan bit set baharu - purata bilangan bit baru.

Algoritma

• Inisialisasikan P ke N kerana kita pada mulanya mempunyai bit set N, dan mulakan Q kepada 0 kerana kita pada mulanya mempunyai 0 set bit.

• Lintas tatasusunan operasi.

• Mulakan prev_p dan prev_q dengan nilai P dan Q.

• Kemas kini nilai P menggunakan prev_p - prev_p * arr[i]/N + prev_q * arr[i]/N, yang akan menambah bit terbalik kepada bit set secara purata dan terbalikkan bit set secara purata kepada bit Unset

• Kemas kini nilai Q.

• Mengembalikan nilai P.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

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

Output

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

Kerumitan masa - O(K), dengan K ialah panjang tatasusunan.

Kerumitan Ruang - O(1) kerana kami tidak menggunakan sebarang ruang tambahan.

Dalam tutorial ini kami belajar mencari bit set purata selepas melakukan semua pilihan operasi K yang mungkin. Dalam pemilihan tunggal kita perlu melaksanakan semua operasi yang diberikan dalam tatasusunan.

Atas ialah kandungan terperinci Purata bit yang ditetapkan dikira dalam rentetan binari yang diberikan selepas semua kemungkinan operasi K. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!