Рубрики

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 65

Пусть a n представляет количество битовых строк длины n, содержащих две последовательные единицы. Что такое рекуррентное отношение для n ?
(A) a n – 2 + a n – 1 + 2 n – 2
(B) a n – 2 + 2a n – 1 + 2 n – 2
(C) 2a n – 2 + a n – 1 + 2 n – 2
(D) 2a n – 2 + 2a n – 1 + 2 n – 2

Ответ: (А)
Объяснение: простое решение
Один из способов решить эту проблему — попытаться использовать небольшие значения и исключить варианты.

a0 = 0  
a1 = 0  
a2 = 1  ["11"]
a3 = 3  ["011", "110", "111"] 
a4 = 8  ["0011", "0110", "0111", "1101",
                    "1011", "1100", "1110", "1111"]

Если мы проверим 3 , то увидим, что только A и C удовлетворяют этому значению. Среди (A) и (C) только (A) удовлетворяет для 4 .

Другое решение (с доказательством)

A string of length n (n >= 2) can be formed by 
following 4 prefixes

1) 11 followed by a string of length n-2
2) 00 followed by a string of length n-2
3) 01 followed by a string of length n-2
4) 10 followed by a string of length n-2

Number 1 has already two consecutive 1's so number 
of binary strings beginning with number 3 is 2n-2
as remaining n-2 bits can have any value.

Number 2 has two 0's so remaining n-2 bits must have
two consecutive 1's. Therefore number of binary strings
that can be formed by number 2 is an-2.

Number 3 and Number 4 together form all strings of length
n-1 and two consecutive 1's.

Тест на этот вопрос

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

ВОРОТА | GATE-CS-2015 (набор 1) | Вопрос 65

0.00 (0%) 0 votes