Взрывоопасность

Если в предыдущей задаче нам удалось использовать рекурсивное решение, то здесь придется обходиться итеративным. Как обычно, будем искать число опасных стопок для произвольного N. Сложность в том, что стопки сами по себе разные. Разобьем их на 4 класса:

Тип 1 - опасные, содержат три или более контейнера A подряд.
Тип 2 - не опасны, но наверху лежат два контейнера А.
Тип 3 - не опасны, но наверху лежат один контейнер А (а под ним, если есть, B).
Тип 4 - не опасны, с контейнером B наверху.

Теперь перейдем к стопкам размером N + 1. Каждая стопка из рассмотренных ранее классов породит 2 стопки, причем несложные логические рассуждения (возьмите карандаш) показывают, что:

из стопки 1-го класса получится 2 стопки 1-го класса;
из стопки 2-го класса получится по стопке 1-го и 4-го класса;
из стопки 3-го класса получится по стопке 2-го и 4-го класса;
из стопки 4-го класса получится по стопке 3-го и 4-го класса;

Теперь о граничных (вообще-то, для итеративных схем лучше говорить "о начальных") условиях. Их можно написать как для N = 1 (по одной стопке типа 3 и 4), так и для N = 0 (одна стопка типа 4 - собственно, стопок нет вообще). Заметим, что как и в предыдущей задаче, нам достаточно знать количества стопок высоты на единицу меньшей текущей. После этого решение становится совсем простым.

к занятию № 2

 


Рейтинг ресурсов УралWeb

 

Сайт создан в системе uCoz