Berechnen Sie binäre Zeichenfolgen der Länge N, die wiederholte Verkettungen von Teilzeichenfolgen sind

Der Zweck dieses Artikels besteht darin, ein Programm zu implementieren, das die Anzahl der binären Zeichenfolgen der Länge N zählt, die durch wiederholte Verkettung einer Teilzeichenfolge gebildet werden.

Das Ziel besteht darin, zu bestimmen, wie viele Binärzeichenfolgen der Länge N durch wiederholtes Verketten einzelner Teilzeichenfolgen des gegebenen Textes erstellt werden können, wobei N eine positive ganze Zahl ist.

Problemstellung

Implementieren Sie ein Programm, das die Anzahl der Binärzeichenfolgen der Länge N zählt, die wiederholt Teilzeichenfolgen verketten.

Beispiel Beispiel 1

Let us take the Input, N = 3

Output: 2

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Nachfolgend sind mögliche binäre Zeichenfolgen der Länge N=3 aufgeführt, bei denen eine Teilzeichenfolge wiederholt verkettet wird.

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

Wenn wir also die Gesamtzahl all dieser Zeichenfolgen zählen, erhalten wir eine Summe von 2. Daher ist die Ausgabe 2.

Beispiel Beispiel 2

Let us take the Input, N = 8

Output: 16

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Nachfolgend sind mögliche Binärzeichenfolgen der Länge N=8 aufgeführt, die eine wiederholte Verkettung von Teilzeichenfolgen enthalten.

“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.

Wenn wir also die Gesamtzahl aller dieser Zeichenfolgen addieren, erhalten wir eine Summe von 16. Daher beträgt die Ausgabe 16.

Methode

Um die Anzahl der binären Zeichenfolgen der Länge N zu zählen, die durch wiederholte Verkettung von Teilzeichenfolgen gebildet werden, verwenden wir die folgende Methode.

Eine Möglichkeit, dieses Problem zu lösen und die Anzahl der Binärzeichenfolgen der Länge N durch wiederholtes Verketten von Teilzeichenfolgen zu zählen.

Das obige Problem kann auf der Grundlage der Tatsache gelöst werden, dass jede mögliche Zeichenfolge eine wiederholte Teilzeichenfolge enthält, die C-mal verkettet ist. Daher muss die bereitgestellte Stringlänge N durch C teilbar sein, um alle aufeinanderfolgenden Strings zu generieren.

Ermitteln Sie also zunächst alle Teiler von N und ermitteln Sie dann für jeden möglichen Teiler C die Gesamtzahl aller potenziellen Zeichenfolgen, die durch Verkettung erstellt werden können. Diese Zahl kann mithilfe von 2C ermittelt werden. Um die Gesamtzahl für jeden rekursiven Aufruf zu ermitteln, wenden Sie dieselbe Technik auf den Divisor C an und subtrahieren ihn von 2C. Dabei wird auch die Anzahl der zwischen ihnen vorhandenen doppelten Zeichenfolgen berücksichtigt.

Algorithmus

Algorithmus zur Berechnung einer Binärzeichenfolge der Länge N durch wiederholte Verkettung der unten angegebenen Teilzeichenfolgen.

• Erster Schritt − Start

• Schritt 2 − Definieren Sie eine Funktion, um die Anzahl der Zeichenfolgen der Länge N zu zählen, sodass sie die Verkettung ihrer Teilzeichenfolgen darstellen.

• Schritt 3 – Überprüfen Sie, ob der Status berechnet wurde

• Schritt 4 – Speichern Sie das Ergebnis des aktuellen rekursiven Aufrufs oder den Wert der Zählung

• Schritt 5 – Iterieren Sie über alle Teiler

• Schritt 6 – Geben Sie die erhaltenen Ergebnisse zurück

• Schritt 7 − Stopp

Beispiel: C++-Programm

Dies ist eine C-Programmimplementierung des obigen Algorithmus zum Zählen der Anzahl von binären Zeichenfolgen der Länge N, die durch wiederholte Verkettung von Teilzeichenfolgen gebildet werden.

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

Ausgabe

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

Fazit

Ähnlich können wir binäre Strings der Länge N berechnen, die wiederholte Verkettungen von Teilstrings sind.

In diesem Artikel wird die Herausforderung angesprochen, die Anzahl einer binären Zeichenfolge der Länge N zu ermitteln, die durch wiederholte Verkettung von Teilzeichenfolgen gebildet wird.

C++-Programmiercode wird hier zusammen mit dem Algorithmus zur Berechnung von Binärzeichenfolgen der Länge N aus wiederholt verketteten Teilzeichenfolgen bereitgestellt.

Das obige ist der detaillierte Inhalt vonBerechnen Sie binäre Zeichenfolgen der Länge N, die wiederholte Verkettungen von Teilzeichenfolgen sind. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!