C/C++-Programm: Anzahl der Binärzeichenfolgen ohne aufeinanderfolgende Einsen zählen?

Binärzahlen sind Zahlen, die nur zwei Ziffern enthalten, nur 0 und 1. Jede Binärzahl ist ein Strom binärer Bits, den wir uns als binäre Zeichenfolge vorstellen. Für diese Zeichenfolge müssen wir die Anzahl der binären Zeichenfolgen der Länge N ermitteln, die keine aufeinanderfolgenden Einsen enthalten.

Beispielsweise ist für N=5 die Binärzeichenfolge, die die gegebene Bedingung erfüllt, 00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101.

Eine Möglichkeit besteht darin, alle N-stelligen Zeichenfolgen zu generieren und nur die Zeichenfolgen auszugeben, die die gegebene Bedingung erfüllen. Dieser Ansatz ist jedoch bei Großoperationen nicht effizient.

Eine andere Möglichkeit ist die Rekursion. Bei jedem Schritt der Rekursion hängen wir 0 und 1 an die teilweise gebildete Zahl an und rekursieren mit einer Zahl weniger. Der Schlüssel ist, dass wir nur dann 1 anhängen und eine Rekursion durchführen, wenn die letzte Ziffer der teilweise gebildeten Zahl 0 ist. Auf diese Weise enthält die Ausgabezeichenfolge keine aufeinanderfolgenden Einsen.

Input: n = 5
Output: Number of 5-digit binary strings without any consecutive 1's are 13

Beispiel

#include <iostream>
#include <string>
using namespace std;
int countStrings(int n, int last_digit) {
   if (n == 0)
      return 0;
   if (n == 1) {
      if (last_digit)
         return 1;
      else
         return 2;
   }
   if (last_digit == 0)
      return countStrings(n - 1, 0) + countStrings(n - 1, 1);
   else
      return countStrings(n - 1, 0);
}
int main() {
   int n = 5;
   cout << "Number of " << n << "-digit binary strings without any "
   "consecutive 1&#39;s are " << countStrings(n, 0);
   return 0;
}

Das obige ist der detaillierte Inhalt vonC/C++-Programm: Anzahl der Binärzeichenfolgen ohne aufeinanderfolgende Einsen zählen?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!