Cuente el número de strings binarias sin 1 consecutivos

Dado un entero positivo N, cuente todas las posibles strings binarias distintas de longitud N de modo que no haya unos consecutivos.

Ejemplos: 

Input:  N = 2
Output: 3
// The 3 strings are 00, 01, 10

Input: N = 3
Output: 5
// The 5 strings are 000, 001, 010, 100, 101

Este problema se puede resolver usando Programación Dinámica. Sea a[i] el número de strings binarias de longitud i que no contienen dos 1 consecutivos y que terminan en 0. De manera similar, sea b[i] el número de tales strings que terminan en 1. Podemos agregar 0 o 1 a una string que termina en 0, pero solo podemos agregar 0 a una string que termina en 1. Esto produce la relación de recurrencia: 

a[i] = a[i - 1] + b[i - 1]
b[i] = a[i - 1] 

Los casos base de la recurrencia anterior son a[1] = b[1] = 1. El número total de strings de longitud i es solo a[i] + b[i].
A continuación se muestra la implementación de la solución anterior. En la siguiente implementación, los índices comienzan desde 0. Por lo tanto, a[i] representa el número de strings binarias para la longitud de entrada i+1. De manera similar, b[i] representa strings binarias para la longitud de entrada i+1.

Implementación:

// C++ program to count all distinct binary strings
// without two consecutive 1's
#include <iostream>
using namespace std;
 
int countStrings(int n)
{
    int a[n], b[n];
    a[0] = 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];
}
 
 
// Driver program to test above functions
int main()
{
    cout << countStrings(3) << endl;
    return 0;
}

class Subset_sum
{
    static  int countStrings(int n)
    {
        int a[] = new int [n];
        int b[] = new int [n];
        a[0] = 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];
    }
    /* Driver program to test above function */
    public static void main (String args[])
    {
          System.out.println(countStrings(3));
    }
}/* This code is contributed by Rajat Mishra */

# Python program to count
# all distinct binary strings
# without two consecutive 1's
 
def countStrings(n):
 
    a=[0 for i in range(n)]
    b=[0 for i in range(n)]
    a[0] = b[0] = 1
    for i in range(1,n):
        a[i] = a[i-1] + b[i-1]
        b[i] = a[i-1]
     
    return a[n-1] + b[n-1]
 
# Driver program to test
# above functions
 
print(countStrings(3))
 
# This code is contributed
# by Anant Agarwal.

// C# program to count all distinct binary
// strings without two consecutive 1's
using System;
 
class Subset_sum
{
    static int countStrings(int n)
    {
        int []a = new int [n];
        int []b = new int [n];
        a[0] = 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];
    }
     
    // Driver Code
    public static void Main ()
    {
        Console.Write(countStrings(3));
    }
}
 
// This code is contributed by nitin mittal

<?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 countStrings(3) ;
 
// This code is contributed by nitin mittal
?>

<script>
 
// JavaScript program to count all
// distinct binary strings
// without two consecutive 1's
function countStrings(n)
{
    let a = [];
    let b = [];
    a[0] = b[0] = 1;
     
    for(let 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
document.write(countStrings(3));
 
// This code is contributed by rohan07
 
</script>

5

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Fuente: 

Si observamos más de cerca el patrón, podemos observar que el conteo es en realidad (n+2) el número de Fibonacci para n >= 1. Los números de Fibonacci son 0, 1, 1, 2, 3, 5, 8 , 13, 21, 34, 55, 89, 141, …. 

n = 1, count = 2  = fib(3)
n = 2, count = 3  = fib(4)
n = 3, count = 5  = fib(5)
n = 4, count = 8  = fib(6)
n = 5, count = 13 = fib(7)
................

Por lo tanto, podemos contar las strings en tiempo O (Log n) también usando el método 5 aquí .

Otro método :-

Del método anterior, está claro que solo queremos el valor anterior en el bucle for, lo que también podemos hacer reemplazando la array con la variable.

A continuación se muestra la implementación del enfoque anterior: – 

// C++ program to count all distinct binary strings
// without two consecutive 1's
#include <bits/stdc++.h>
using namespace std;
 
int countStrings(int n)
{
    int a = 1, b = 1;
    for (int i = 1; i < n; i++) {
        // Here we have used the temp variable because we
        // want to assign the older value of a to b
        int temp = a + b;
        b = a;
        a = temp;
    }
    return a + b;
}
 
// Driver program to test above functions
int main()
{
    cout << countStrings(3) << endl;
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

class Subset_sum {
    static int countStrings(int n)
    {
        int a = 1;
        int b = 1;
        for (int i = 1; i < n; i++) {
            // Here we have used the temp variable because
            // we want to assign the older value of a to b
            int temp = a + b;
            b = a;
            a = temp;
        }
        return a + b;
    }
    /* Driver program to test above function */
    public static void main(String args[])
    {
        System.out.println(countStrings(3));
    }
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

5

Complejidad temporal: O(N)
Espacio auxiliar: O(1)

Publicación relacionada: 
números de 1 a n bits sin 1 consecutivos en representación binaria.