PHP-Programm zum Zählen der Anzahl von Binärzeichenfolgen, die keine aufeinanderfolgenden Einsen enthalten

Wie viele Binärzeichenfolgen ohne aufeinanderfolgende Einsen zählen?

Betrachten wir ein Beispiel, um das Konzept des Zählens einer Binärzeichenfolge ohne aufeinanderfolgende Einsen zu erklären.

Beispiel

Angenommen, wir möchten die Anzahl der Binärzeichenfolgen der Länge 3 zählen, die keine aufeinanderfolgenden Einsen enthalten. Eine Binärzeichenfolge ist eine Zeichenfolge, die nur aus Nullen und Einsen besteht.

Mögliche Binärzeichenfolgen der Länge 3 sind: 000, 001, 010, 011, 100, 101, 110 und 111.

Wir müssen jedoch nur die Binärzeichenfolgen zählen, die keine aufeinanderfolgenden Zeichenfolgen haben. Daher müssen wir die Zeichenfolgen 011, 101 und 111 von der Zählung ausschließen.

Lassen Sie uns die verbleibende Binärzeichenfolge analysieren:

• 000: Dies ist eine gültige Zeichenfolge, da sie keine aufeinanderfolgenden Einsen enthält.

• 001: Dies ist eine gültige Zeichenfolge, da sie keine aufeinanderfolgenden Einsen enthält.

• 010: Dies ist eine gültige Zeichenfolge, da sie keine aufeinanderfolgenden Einsen enthält.

• 100: Dies ist eine gültige Zeichenfolge, da sie keine aufeinanderfolgenden Zeichenfolgen enthält.

• 110: Dies ist eine ungültige Zeichenfolge, da sie aufeinanderfolgende Einsen enthält.

Wie aus der obigen Analyse ersichtlich ist, gibt es 4 gültige Binärzeichenfolgen der Länge 3 und keine aufeinanderfolgenden Einsen.

PHP-Programm zum Zählen der Anzahl von Binärzeichenfolgen ohne aufeinanderfolgende Einsen

Methode 1 – Verwenden Sie dynamische Programmierung

Beispiel

<?php
function countBinaryStrings($n) {
   $dp = array();
   $dp[0] = 1;
   $dp[1] = 2;

   for ($i = 2; $i <= $n; $i++) {
      $dp[$i] = $dp[$i - 1] + $dp[$i - 2];
   }

   return $dp[$n];
}

$n = 5; // Number of digits in the binary string
$count = countBinaryStrings($n);
echo "Number of binary strings without consecutive 1's: " . $count;

?>

Ausgabe

Number of binary strings without consecutive 1's: 13

Codebeschreibung

Dieser PHP-Code definiert eine Funktion namens countBinaryStrings, die mithilfe dynamischer Programmierung die Anzahl der Binärzeichenfolgen der Länge $n zählt, die keine aufeinanderfolgenden Zeichenfolgen enthalten. Es initialisiert das Array $dp unter Verwendung der Basisfälle $dp[0] = 1 und $dp[1] = 2, die Zählungen für Zeichenfolgen der Länge 0 bzw. 1 darstellen. Anschließend wird eine Schleife verwendet, um die verbleibenden Anzahlen der Längen 2 bis $n aufzufüllen, indem die Anzahlen der Längen $i - 1 und $ summiert werden. >i - 2. Schließlich wird die Anzahl der Länge $n zurückgegeben und gedruckt. In diesem speziellen Beispiel zählt der Code die Anzahl der Binärzeichenfolgen der Länge 5, die keine aufeinanderfolgenden Einsen haben, und zeigt das Ergebnis an.

Methode 2

<?php
// PHP program to count all distinct
// binary stringswithout two
// consecutive 1's

function countStrings($n)
{
	$a[$n] = 0;
	$b[$n] = 0;
	$a[0] = $b[0] = 1;
	for ($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];
}

	// Driver Code
	echo "Number of binary strings without consecutive 1's: " . countStrings(5) ;

?>

Ausgabe

Number of binary strings without consecutive 1's: 13

Codebeschreibung

Dieser PHP-Code zählt die Anzahl unterschiedlicher Binärzeichenfolgen der Länge $n, die nicht zwei aufeinanderfolgende Einsen enthalten. Es definiert zwei Arrays, $a und $b, um die Zählungen zu speichern. Der Basisfall ist auf $a[0] = $b[0] = 1 gesetzt. Verwenden Sie dann eine Schleife, um die Längen 1 bis $n-1 zu berechnen. Die Anzahl der Längen $i wird erhalten, indem die Anzahl der Längen $i-1 zur Anzahl der Längen a im Array $a addiert wird. >$i-1 kommt aus Array $b. Zusätzlich wird die Anzahl der Länge $i in Array $b aus der Anzahl der Länge $i-1 in Array $a ermittelt. Schließlich gibt der Code die Summe der Anzahl der Längen $n-1 in Array $a und der Anzahl der Längen $n-1 aus Array $b zurück, was die Gesamtzahl der Binärzeichenfolgen ohne darstellt aufeinanderfolgende. In diesem speziellen Beispiel berechnet der Code eine Anzahl der Länge 5 und zeigt das Ergebnis an.

Fazit

Zusammenfassend lässt sich sagen, dass der erste Ansatz dynamische Programmierung nutzt, das Array mit dem Basisfall initialisiert und die Anzahl für größere Längen iterativ berechnet. Das Ergebnis wird effizient berechnet, indem die Anzahl der ersten beiden Längen addiert wird. Der zweite Ansatz verfolgt einen einfacheren Ansatz und verwendet zwei Arrays zum Speichern der Zählwerte und aktualisiert sie iterativ basierend auf den Zählwerten der vorherigen Länge. Es berechnet die Gesamtzahl direkt, ohne dass die beiden Arrays separat summiert werden müssen. Beide Methoden ermöglichen eine genaue Zählung binärer Zeichenfolgen ohne aufeinanderfolgende Zeichenfolgen, und die Wahl zwischen ihnen kann von spezifischen Anforderungen und Leistungsaspekten abhängen.

Das obige ist der detaillierte Inhalt vonPHP-Programm zum Zählen der Anzahl von Binärzeichenfolgen, die keine aufeinanderfolgenden Einsen enthalten. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!