Maison > développement back-end > C++ > le corps du texte

Écrire un programme en C/C++ pour compter le nombre de chaînes binaires sans 1 consécutifs ?

WBOY
Libérer: 2023-08-25 22:05:13
avant
636 Les gens l'ont consulté

Écrire un programme en C/C++ pour compter le nombre de chaînes binaires sans 1 consécutifs ?

Ici, nous verrons une question intéressante. Supposons qu'une valeur n soit donnée. Nous devons trouver toutes les chaînes de longueur n dans lesquelles il n’y a pas de 1 consécutifs. Si n = 2, les nombres sont {00, 01, 10}, donc le résultat est 3.

Nous pouvons utiliser la programmation dynamique pour le résoudre. Supposons que nous ayons une table « a » et « b ». où arr[i] stocke le nombre de chaînes binaires de longueur i qui n'ont pas de 1 consécutifs et se terminent par 0. De même, b est identique mais se termine par 1. On peut ajouter 0 ou 1 si le dernier est 0, mais seulement ajouter 0 si le dernier est 1.

Regardons l'algorithme pour avoir cette idée.

Algorithm

noConsecutiveOnes(n) - La traduction chinoise de

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
Copier après la connexion

Example

est :

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;
}
Copier après la connexion

Output

8
Copier après la connexion

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!

Étiquettes associées:
source:tutorialspoint.com
Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal