Задача
COM-B1-M11-P023 Без трех нулей
#23
★★★★☆ Уровень 4 из 5
Сколько двоичных строк длины \(9\) не содержат трех нулей подряд?
Последний блок может быть \(1\), \(01\), \(001\).
Пусть \(a_n\) - число строк. Тогда \(a_n=a_{n-1}+a_{n-2}+a_{n-3}\), \(a_0=1\), \(a_1=2\), \(a_2=4\). Получаем \(a_3=7\), \(a_4=13\), \(a_5=24\), \(a_6=44\), \(a_7=81\), \(a_8=149\), \(a_9=274\).
Рекурсия с тремя состояниями последнего блока.