Рубрики

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

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

Примеры:

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

Эта проблема может быть решена с помощью динамического программирования. Пусть a [i] будет числом двоичных строк длины i, которые не содержат никаких двух последовательных единиц и заканчиваются на 0. Аналогично, пусть b [i] будет количеством таких строк, заканчивающихся на 1. Мы можем добавить 0 или 1 к строке, заканчивающейся на 0, но мы можем добавить только 0 к строке, заканчивающейся на 1. Это приводит к рекуррентному отношению:

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

Базовые случаи повторения выше: a [1] = b [1] = 1. Общее количество строк длины i это просто a [i] + b [i].

Ниже приводится реализация вышеуказанного решения. В следующей реализации индексы начинаются с 0. Таким образом, a [i] представляет количество двоичных строк для входной длины i + 1. Аналогично, b [i] представляет двоичные строки для входной длины i + 1.

C ++

// C ++ программа для подсчета всех различных двоичных строк
// без двух последовательных 1
#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];

}

  

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

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

    }

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

    public static void main (String args[])

    {

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

    }

}/ * Этот код предоставлен Раджатом Мишрой * /

python3

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

  

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]

  
# Драйвер программы для тестирования
# выше функции

  

print(countStrings(3))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для подсчета всех различных двоичных файлов
// строки без двух последовательных 1

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

    }

      

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

    public static void Main ()

    {

        Console.Write(countStrings(3));

    }

}

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

PHP

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

  

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

}

  

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

    echo countStrings(3) ;

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


Выход:

5

Источник:
courses.csail.mit.edu/6.006/oldquizzes/solutions/q2-f2009-sol.pdf

Если мы более внимательно посмотрим на паттерн, мы можем заметить, что счет фактически является (n + 2) -ым числом Фибоначчи для n> = 1. Числа Фибоначчи равны 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)
................

Поэтому мы можем посчитать строки за O (Log n), также используя метод 5 здесь .

Похожие сообщения:
Числа от 1 до n бит без последовательных 1 в двоичном представлении.

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

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

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

0.00 (0%) 0 votes