Ein Programm in C/C++ schreiben, um die Anzahl der Binärzeichenfolgen ohne aufeinanderfolgende Einsen zu zählen?

Hier sehen wir eine interessante Frage. Angenommen, ein Wert n ist gegeben. Wir müssen alle Strings der Länge n finden, in denen es keine aufeinanderfolgenden Einsen gibt. Wenn n = 2, sind die Zahlen {00, 01, 10}, also ist die Ausgabe 3.

Wir können dynamische Programmierung verwenden, um es zu lösen. Angenommen, wir haben eine Tabelle „a“ und „b“. Dabei speichert arr[i] die Anzahl der Binärzeichenfolgen der Länge i, die keine aufeinanderfolgenden Einsen haben und mit 0 enden. Ebenso ist b gleich, endet aber mit 1. Wir können 0 oder 1 hinzufügen, wenn der letzte Wert 0 ist, aber nur 0 hinzufügen, wenn der letzte Wert 1 ist.

Schauen wir uns den Algorithmus an, um auf diese Idee zu kommen.

Algorithmus

noConsecutiveOnes(n) – Die chinesische Übersetzung von

Begin
   define array a and b of size n
   a[0] := 1
   b[0] := 1
   for i in range 1 to n, do
      a[i] := a[i-1] + b[i - 1]
      b[i] := a[i - 1]
   done
   return a[n-1] + b[n-1]
End

Example

ist:

Example

#include <iostream>
using namespace std;
int noConsecutiveOnes(int n) {
   int a[n], b[n];
   a[0] = 1;
   b[0] = 1;
   for (int i = 1; i < n; i++) {
      a[i] = a[i-1] + b[i-1];
      b[i] = a[i-1];
   }
   return a[n-1] + b[n-1];
}
int main() {
   cout << noConsecutiveOnes(4) << endl;
}

Output

8

Das obige ist der detaillierte Inhalt vonEin Programm in C/C++ schreiben, um die Anzahl der Binärzeichenfolgen ohne aufeinanderfolgende Einsen zu zählen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!