Теоретичні відомості для практичного завдання №5

Задача полягає в підрахунку кількості послідовностей довжиною n, які складаються лише з нулів і одиниць, і в яких не зустрічаються три одиниці підряд.

Щоб розв'язати цю задачу, ми можемо скористатися динамічним програмуванням. Давайте визначимо dp[i] як кількість допустимих послідовностей довжиною i, де не зустрічаються три одиниці підряд.

Тепер розглянемо останній символ в такій послідовності довжиною i:

1. Якщо останній символ - 0, то перед ним може стояти будь-який допустимий символ, тобто dp[i-1] (кількість допустимих послідовностей довжиною i-1).
2. Якщо останній символ - 1, то перед ним не може стояти ще одна 1, але може стояти 0, тому перед ним може стояти dp[i-2] (кількість допустимих послідовностей довжиною i-2).

Таким чином, ми отримуємо рекурентне співвідношення: dp[i] = dp[i-1] + dp[i-2]

Початкові значення: dp[0] = 1 (порожня послідовність) dp[1] = 2 (0 або 1) dp[2] = 3 (00, 01, 10)

Ми можемо обчислити dp[n], щоб отримати кількість допустимих послідовностей довжиною n.

Зазначимо, що для великих значень n може бути необхідно використовувати арифметику з великими числами або оптимізовані методи, такі як модульна арифметика, щоб обробити великі числа та уникнути переповнення.