AL13

Условие

Имеется [latex]n[/latex] черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая — под низ стопки, третья — на стол, четвертая — под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.?

Тестирование

Входные данные Выходные данные
1 1 1
2 2 01
3 5 10011
4 12 101100010011
5 20 00111001101100010011

Здесь нули — черные карточки, единицы — белые, а первый символ строки обозначает карточку, лежащую внизу стопки.

Код

Решение

Алгоритм разбора стопки можно описать следующим образом:

  1. Выкладываем на стол верхнюю карточку.
  2. Пока в стопке есть карты, выполняем действия:
    1. перекладываем под низ стопки верхнюю карточку;
    2. выкладываем на стол верхнюю карточку.

Поэтому для построения стопки нам достаточно обратить эти действия (выкладывание на стол заменить добавлением в стопку, а перекладывание верхней карточки под низ стопки — перекладыванием нижней на ее верх) и выполнять их в обратном порядке. Тогда алгоритм построения будет следующим:

  1. Пока на столе не останется одна карточка, выполняем действия:
    1. добавляем карточку, выложенную на стол последней из имеющихся, на верх стопки;
    2. перекладываем карточку из-под стопки наверх.
  2. Добавляем карточку наверх.

Так как карточки на столе считаем разложенными в нужном по условию порядке, то есть чередующимися по цвету начиная с белой карточки, то при сборе стопки очередная добавляемая карточка будет менять цвет относительно предыдущей, причем последняя добавляемая будет белой.

Для решения задачи удобнее всего будет воспользоваться очередью, поскольку при построении стопки мы добавляем карточки только в один ее конец, а изымаем при перекладывании всегда из противоположного. Более того, в данном случае структуру можно значительно облегчить, оставив из методов только push() и pop(), причем из последнего можно за ненадобностью удалить проверку исключительной ситуации при попытке изъять карточку из пустой стопки, так как по алгоритму прямо перед изъятием всегда выполняется добавление карточки. Карточки могут быть только двух цветов, поэтому узлы очереди будут хранить значения типа bool.

Перейдем к практическому решению. Прежде всего получим количество карточек в требуемой стопке и объявим очередь:

Затем объявим переменную для цвета текущей карточки и инициализируем ее таким образом, чтобы последняя добавляемая карточка была белой. Так как при четном числе карточек в стопке последняя выкладываемая (она же — первая добавляемая) будет черной, а при нечетном — белой, то при кодировании черных и белых цветов как [latex]0[/latex] и [latex]1[/latex] соответственно инициализируется она следующим значением:

Теперь перейдем к сбору стопки. Действуем согласно описанному выше алгоритму: пока в стопке не окажутся все карточки, кроме одной, добавляем карточку на условный верх стопки, перекладываем карточку из-под низа наверх и меняем цвет следующей карточки. После этого добавляем на верх стопки белую карточку:

Наконец, разбираем стопку, начиная с условного низа, и выводим ее как ответ на поставленную задачу:

Ссылки

Код программы на Ideone.com;

Список задач по структурам данных на Algolist.manual.ru.

Related Images: