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.
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
#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; }
8
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!