Задание 8 Параграф 10 ГДЗ Босова 11 класс (Информатика)

Задача

Муравьи идут друг за другом по неровной лесной тропе. На их пути встречаются ямки, в которые могут провалиться несколько муравьёв. Когда ямка заполняется муравьями, остальные муравьи проходят через неё, а затем по одному вытаскивают провалившихся. Например, вот как четыре муравья проходят через ямку, вмещающую двух муравьёв.

Пусть по тропе идут 8 муравьёв. В каком порядке они будут идти после преодоления участка с четырьмя ямками, вмещающими 2, 4, 5 и 1 муравья соответственно? Какую структуру данных иллюстрирует данный пример?

Подробный ответ

Ямки работают как стек: сначала в ямку проваливаются несколько первых муравьёв, затем остальные проходят дальше, а потом муравьи выбираются из ямки в обратном порядке.

Исходный порядок муравьёв: $$87654321$$.

После первой ямки, вмещающей 2 муравьёв, порядок станет:

$$12876543$$

После второй ямки, вмещающей 4 муравьёв:

$$34561287$$

После третьей ямки, вмещающей 5 муравьёв:

$$78216345$$

После четвёртой ямки, вмещающей 1 муравья:

$$57821634$$

Следовательно, пример иллюстрирует структуру данных стек.