Kedudukan leksikografi rentetan binari

Dalam artikel ini, kami akan meneroka masalah menarik yang melibatkan rentetan binari dan susunan leksikografi. Tugas kami adalah untuk mencari kedudukan leksikografi rentetan binari yang diberikan. Kami akan menunjukkan penyelesaian kami menggunakan C++, bahasa pengaturcaraan popular yang terkenal dengan kecekapan dan fleksibilitinya.

Fahami susunan kamus

Susunan kamus (juga dipanggil susunan abjad atau susunan kamus) ialah susunan perkataan dalam susunan abjad mengikut huruf konstituennya.

Pernyataan Masalah

Memandangkan rentetan binari, kita perlu menentukan kedudukan leksikografinya antara semua pilihatur. Kedudukan leksikografi rentetan ialah kedudukannya dalam set semua pilihatur apabila ia disenaraikan secara leksikografi.

Kaedah penyelesaian

Pendekatan kami merangkumi langkah utama berikut−

• Initialize Count − Mulakan pembilang untuk menyimpan nombor '1' dalam rentetan binari.

• Pengiraan kedudukan − Merentasi rentetan binari secara berulang dari kiri ke kanan. Jika aksara semasa ialah '1', hitung kedudukannya menggunakan formula gabungan dan kurangkan pembilang untuk setiap '1' berikutnya.

• Keputusan Pulangan− Hasilnya ialah susunan leksikografi rentetan binari.

Pelaksanaan C++

Contoh

Kod C++ di bawah menggariskan penyelesaian kami−

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

// Function to calculate factorial
int fact(int n) {
   int res = 1;
   for (int i = 1; i <= n; i++)
      res *= i;
   return res;
}

// Function to find lexicographic rank of a binary string
int lexRank(string str) {
   int rank = 1;
   int onesCount = count(str.begin(), str.end(), '1');
   
   for (char c : str) {
      if (c == '1') {
         onesCount--;
         rank += fact(onesCount);
      }
   }
   
   return rank;
}

int main() {
   string str = "110";
   
   int result = lexRank(str);
   cout << "Lexicographic rank of the binary string: " << result << endl;
   
   return 0;
}

Output

Lexicographic rank of the binary string: 3

Penjelasan

Penjelasan

Pertimbangkan rentetan binari −

str = "110"

Permutasi dan gabungan rentetan binari ini ialah: "011", "101", "110". Dalam susunan leksikografi, pilih atur ini ialah: "011", "101", "110".

Rentetan binari "110" mempunyai pangkat 3 dan ini adalah output program kami.

Kesimpulan

Masalah mencari kedudukan leksikografi rentetan binari adalah masalah yang sangat menarik yang berdasarkan pemahaman kami tentang rentetan binari, pilih atur dan susunan leksikografi. Penyelesaian yang dilaksanakan dalam C++ ini menunjukkan cara kita boleh menggunakan binaan pengaturcaraan asas untuk menyelesaikan masalah ini dengan cekap.

Atas ialah kandungan terperinci Kedudukan leksikografi rentetan binari. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!