Hitung rentetan perduaan panjang N yang merupakan gabungan berulang subrentetan

Tujuan artikel ini adalah untuk melaksanakan program yang mengira bilangan rentetan binari panjang N yang dibentuk oleh penggabungan berulang subrentetan.

Matlamatnya adalah untuk menentukan bilangan rentetan perduaan panjang N yang boleh dibuat dengan menggabungkan berulang kali subrentetan individu bagi teks yang diberikan, dengan N ialah integer positif.

Pernyataan Masalah

Laksanakan atur cara yang mengira bilangan rentetan binari panjang N yang berulang kali menggabungkan subrentetan.

Contoh Contoh 1

Let us take the Input, N = 3

Output: 2

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Disenaraikan di bawah adalah rentetan binari yang boleh dilaksanakan dengan panjang N=3, dengan subrentetan berulang kali digabungkan.

"000":The substring "0" is repeatedly concatenated to form this string.
"111":The substring "1" is repeatedly concatenated to form this string.

Jadi apabila kita mengira jumlah bilangan semua rentetan ini, jumlah yang kita dapat ialah 2. Oleh itu, keluarannya ialah 2.

Contoh Contoh 2

Let us take the Input, N = 8

Output: 16

Terjemahan bahasa Cina bagi

Penjelasan

ialah:

Penjelasan

Disenaraikan di bawah adalah rentetan binari yang boleh dilaksanakan dengan panjang N=8 yang mengandungi penyambungan subrentetan berulang.

“00000000”: The substring "0" is repeatedly concatenated to form this string.
“11111111”: The substring "1" is repeatedly concatenated to form this string.
“01010101”: The substring "01" is repeatedly concatenated to form this string.
“10101010”: The substring "10" is repeatedly concatenated to form this string.
"00110011”: The substring "0011" is repeatedly concatenated to form this string.
"11001100”: The substring "1100" is repeatedly concatenated to form this string.
"11011101”: The substring "1101" is repeatedly concatenated to form this string.
"00100010”: The substring "0010" is repeatedly concatenated to form this string.
"10111011”: The substring "1011" is repeatedly concatenated to form this string.
"01000100”: The substring "0100" is repeatedly concatenated to form this string.
"10001000”: The substring "1000" is repeatedly concatenated to form this string.
"00010001”: The substring "0001" is repeatedly concatenated to form this string.
"11101110”: The substring "1110" is repeatedly concatenated to form this string.
"01110111”: The substring "0111" is repeatedly concatenated to form this string.
"01100110”: The substring "0110" is repeatedly concatenated to form this string.
"10011001”: The substring "1001" is repeatedly concatenated to form this string.

Jadi apabila kita menjumlahkan jumlah semua rentetan ini, kita mendapat jumlah 16. Oleh itu, keluarannya ialah 16.

Kaedah

Untuk mengira bilangan rentetan perduaan panjang-N yang dibentuk oleh penyambungan subrentetan berulang, kami menggunakan kaedah berikut.

Satu cara untuk menyelesaikan masalah ini dan mengira bilangan rentetan binari N-panjang dengan menggabungkan subrentetan berulang kali.

Masalah di atas boleh diselesaikan berdasarkan fakta bahawa setiap rentetan yang boleh dilaksanakan mengandungi subrentetan berulang yang digabungkan C kali. Oleh itu, panjang rentetan N yang disediakan perlu dibahagikan dengan C untuk menjana semua rentetan berturut-turut.

Jadi, mula-mula cari semua pembahagi N, dan kemudian bagi setiap pembahagi C yang mungkin, cari jumlah bilangan semua rentetan berpotensi yang boleh dibuat dengan menggabungkan nombor ini boleh ditentukan menggunakan 2C. Untuk menentukan jumlah kiraan bagi setiap panggilan rekursif, gunakan teknik yang sama pada pembahagi C dan tolakkannya daripada 2C. Ini juga akan mengambil kira bilangan rentetan pendua yang terdapat di antara mereka.

Algoritma

Algoritma untuk mengira rentetan binari panjang N dengan penyatuan berulang subrentetan yang diberikan di bawah.

• Langkah pertama − Mulakan

• Langkah 2 − Takrifkan fungsi untuk mengira bilangan rentetan panjang N supaya ia adalah gabungan subrentetannya.

• Langkah 3 - Semak sama ada status telah dikira

• Langkah 4 - Simpan hasil panggilan rekursif semasa atau nilai kiraan

• Langkah 5 - Ulangi semua pembahagi

• Langkah 6 - Kembalikan keputusan yang diperoleh

• Langkah 7 − Berhenti

Contoh: program C++

Ini ialah pelaksanaan program C bagi algoritma di atas untuk mengira bilangan rentetan binari N-panjang yang dibentuk oleh penyambungan subrentetan berulang.

// C++ program for the above approach
#include<bits/stdc++.h>
using namespace std;

// Storing all the states of recurring recursive 
map<int, int> dp;

// Function for counting the number of strings of length n wherein thatstring is a  concatenation of its substrings
int countTheStrings(int n){

   //the single character cannot be repeated
   if (n == 1)
      return 0;
      
   // Checking whether the state is calculated already or not
   if (dp.find(n) != dp.end())
      return dp[n];
      
      // Storing those value of the result or the count for the present recursive call
   int res = 0;
   
   // Iterate through all of the divisors
   for(int d= 1; d <= sqrt(n); d++){
      if (n % d== 0){
         res += (1 << d) -  countTheStrings(d);
         int div1 = n/d;
         if (div1 != d and d!= 1)
         
            // Non-Rep = Total - Rep
            res += (1 << div1) -  countTheStrings(div1);
      }
   }
   
   // Storing the result of the above calculations
   dp[n] = res; 
   
   // Returning the obtained result
   return res;
}
int main(){
   int n = 8;
   cout<< "Count of 8-length binary strings that are repeated concatenation of a substring: "<< endl;
   cout << countTheStrings(n) << endl;
}

Output

Count of 8-length binary strings that are repeated concatenation of a substring −
16

Kesimpulan

Begitu juga, kita boleh mengira rentetan binari panjang N, yang merupakan gabungan berulang subrentetan.

Dalam artikel ini, cabaran untuk mendapatkan kiraan rentetan perduaan panjang N yang dibentuk oleh penyatuan subrentetan berulang ditangani.

Kod pengaturcaraan C++ disediakan di sini bersama-sama dengan algoritma untuk mengira rentetan binari N-panjang dengan menggabungkan subrentetan berulang kali.

Atas ialah kandungan terperinci Hitung rentetan perduaan panjang N yang merupakan gabungan berulang subrentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!