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

01.01.2020Динамическое программирование, Массивы

Учитывая положительное целое число 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) ;

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

Выход:

Источник:
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

0.00 (0%) 0 votes