Рубрики

Считать строки с последовательными 1

Учитывая число n, подсчитайте количество строк длиной n с последовательными 1 в них.

Примеры:

Input  : n = 2
Output : 1
There are 4 strings of length 2, the
strings are 00, 01, 10 and 11. Only the 
string 11 has consecutive 1's.

Input  : n = 3
Output : 3
There are 8 strings of length 3, the
strings are 000, 001, 010, 011, 100, 
101, 110 and 111.  The strings with
consecutive 1's are 011, 110 and 111.

Input : n = 5
Output : 19

Обратную проблему подсчета строк без последовательных 1 можно решить с помощью динамического программирования (см. Решение здесь ). Мы можем использовать это решение и найти необходимое количество, используя следующие шаги.

1) Вычислить количество двоичных строк без последовательных 1, используя подход, обсуждаемый здесь . Пусть это количество будет с .

2) Количество всех возможных двоичных строк с последовательными 1 равно 2 ^ n, где n — длина ввода.

3) Всего двоичных строк с последовательным 1 равно 2 ^ n — c.

Ниже приведена реализация вышеуказанных шагов.

C ++

// C ++ программа для подсчета всего
// двоичные строки с двумя последовательными единицами
#include <iostream>

using namespace std;

  
// Возвращает счетчик двоичной длины n
// строки с последовательными 1

int countStrings(int n)

{

  // Считаем двоичные строки без последовательных 1.

  // Смотрите обсуждаемый подход

  // ( http://goo.gl/p8A3sW )

    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];

    }

  

    // Вычитаем a [n-1] + b [n-1] из 2 ^ n

    return (1<<n) - a[n-1] - b[n-1];

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    cout << countStrings(5) << endl;

    return 0;

}

Джава

// Java-программа для подсчета всего
// двоичные строки с двумя последовательными единицами

  

class GFG {

  

    // Возвращает счетчик двоичной длины n

    // строки с последовательными 1

    static int countStrings(int n)

    {

     // Считаем двоичные строки без последовательных 1.

     // Смотрите обсуждаемый подход

     // ( http://goo.gl/p8A3sW )

        int a[] = new int[n], 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];

        }

  

       // Вычитаем a [n-1] + b [n-1]

 from 2^n

        return (1 << n) - a[n - 1] - b[n - 1];

    }

  
// Программа драйвера для проверки вышеуказанных функций

   public static void main(String args[])

    {

        System.out.println(countStrings(5));

    }

}

  
// Этот код предоставлен Никитой Тивари.

Python 3

# Python 3 программа для подсчета всех
# отдельные двоичные строки с
# два последовательных 1

  

  
# Возвращает счетчик длины n
# двоичные строки с
# последовательных 1

def countStrings(n) :

      

    # Количество двоичных строк без

    # 1 подряд.

    # Смотрите подход, обсуждаемый на

    # ( http://goo.gl/p8A3sW )

    a = [0] * n

    b = [0] * 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]

      

      

    # Вычтите a [n-1] + b [n-1] из 2 ^ n

    return (1 << n) - a[n - 1] - b[n - 1]

      
# Драйверная программа

print(countStrings(5))

  

  
# Этот код добавлен
# Никита Тивари.

C #

// программа для подсчета всего
// двоичные строки с двумя
// последовательные 1

using System;

  

class GFG {

  

    // Возвращает счетчик длины n

    // двоичные строки с

    // последовательные 1

    static int countStrings(int n)

    {

        // Считаем двоичные строки без

        // последовательные 1

        // Смотрите обсуждаемый подход

        // ( http://goo.gl/p8A3sW )

        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];

        }

  

        // Вычитаем a [n-1] + b [n-1]

        // из 2 ^ n

        return (1 << n) - a[n - 1] - b[n - 1];

    }

  

    // Драйвер программы

    public static void Main()

    {

        Console.WriteLine(countStrings(5));

    }

}

  
// Этот код предоставлен Anant Agarwal.

PHP

<?php
// PHP программа для подсчета всех
// отдельные двоичные строки
// с двумя последовательными 1
// Возвращает счетчик двоичной длины n
// строки с последовательными 1

  

function countStrings($n)

{

      

    // Считаем двоичные строки без последовательных 1.

    // Смотрите обсуждаемый подход

    // ( http://goo.gl/p8A3sW )

    $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];

    }

  

    // Вычитаем a [n-1] + b [n-1] из 2 ^ n

    return (1 << $n) - $a[$n - 1] - 

                       $b[$n - 1];

}

  

    // Код драйвера

    echo countStrings(5), "\n";

  
// Этот код предоставлен Аджитом
?>


Выход :

19

Оптимизация:
Временная сложность вышеуказанного решения составляет O (n). Мы можем оптимизировать вышеуказанное решение для работы в O (Logn).

Если мы более внимательно посмотрим на схему подсчета строк без последовательных 1-х, мы можем заметить, что счет фактически является (n + 2) -ым числом Фибоначчи для n> = 1. Числа Фибоначчи равны 0, 1, 1, 2. , 3, 5, 8, 13, 21, 34, 55, 89, 141,….

n = 1, count = 0  = 21 - fib(3) 
n = 2, count = 1  = 22 - fib(4)
n = 3, count = 3  = 23 - fib(5)
n = 4, count = 8  = 24 - fib(6)
n = 5, count = 19 = 24 - fib(7)
................

Мы можем найти n-е число Фибоначчи за O (Log n) время (см. Метод 4 здесь ).

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Считать строки с последовательными 1

0.00 (0%) 0 votes