COM-B1-M10-P015 Без трех нулей

Используйте последние блоки \(1\), \(01\), \(001\).

Пусть \(a_n\) - число строк длины \(n\). Допустимая строка заканчивается на \(1\), \(01\) или \(001\), если смотреть на последний блок нулей. Поэтому \(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\), \(a_{10}=504\).

Трехчленная рекурсия через последний блок.