Условие
Имеется [latex]n[/latex] черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая — под низ стопки, третья — на стол, четвертая — под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.?
Тестирование
| № | Входные данные | Выходные данные |
| 1 | 1 | 1 |
| 2 | 2 | 01 |
| 3 | 5 | 10011 |
| 4 | 12 | 101100010011 |
| 5 | 20 | 00111001101100010011 |
Здесь нули — черные карточки, единицы — белые, а первый символ строки обозначает карточку, лежащую внизу стопки.
Код
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> using namespace std; // Узел. Используется в очереди struct node { bool val; // Значение узла node *next; // Указатель на следующий узел node(int v, node *n = NULL) { val = v; next = n; } }; // Очередь. Используется как представление стопки struct Queue { node *head; Queue(node *h = NULL) { head = h; } void push(bool v) { // Добавить элемент в очередь head = new node(v, head); } bool pop() { // Изъять элемент из очереди if(head != NULL && (head -> next) != NULL) { node *i = head; node *p = i; while(i -> next != NULL) { p = i; i = i -> next; } bool v = i -> val; p -> next = NULL; delete i; return v; } else { node *n = head; bool v = head -> val; head = head -> next; delete n; return v; } } }; int main() { int n; // Количество карточек в стопке cin >> n; Queue cards; bool t = n % 2; // Цвет текущей карточки. Инициализируется цветом последней выкладываемой карточки for(int i = 0; i < n - 1; i++) { // Собираем стопку, не добавляя верхнюю карточку cards.push(t); // Добавляем текущую карточку cards.push(cards.pop()); // Перекладываем карточку из-под стопки наверх t = !t; // Меняем цвет текущей карточки } cards.push(1); // Добавляем белую карточку наверх for(int i = 0; i < n; i++) // Выводим полученную стопку cout << cards.pop(); return 0; } |
Решение
Алгоритм разбора стопки можно описать следующим образом:
- Выкладываем на стол верхнюю карточку.
- Пока в стопке есть карты, выполняем действия:
- перекладываем под низ стопки верхнюю карточку;
- выкладываем на стол верхнюю карточку.
Поэтому для построения стопки нам достаточно обратить эти действия (выкладывание на стол заменить добавлением в стопку, а перекладывание верхней карточки под низ стопки — перекладыванием нижней на ее верх) и выполнять их в обратном порядке. Тогда алгоритм построения будет следующим:
- Пока на столе не останется одна карточка, выполняем действия:
- добавляем карточку, выложенную на стол последней из имеющихся, на верх стопки;
- перекладываем карточку из-под стопки наверх.
- Добавляем карточку наверх.
Так как карточки на столе считаем разложенными в нужном по условию порядке, то есть чередующимися по цвету начиная с белой карточки, то при сборе стопки очередная добавляемая карточка будет менять цвет относительно предыдущей, причем последняя добавляемая будет белой.
Для решения задачи удобнее всего будет воспользоваться очередью, поскольку при построении стопки мы добавляем карточки только в один ее конец, а изымаем при перекладывании всегда из противоположного. Более того, в данном случае структуру можно значительно облегчить, оставив из методов только push() и pop(), причем из последнего можно за ненадобностью удалить проверку исключительной ситуации при попытке изъять карточку из пустой стопки, так как по алгоритму прямо перед изъятием всегда выполняется добавление карточки. Карточки могут быть только двух цветов, поэтому узлы очереди будут хранить значения типа bool.
Перейдем к практическому решению. Прежде всего получим количество карточек в требуемой стопке и объявим очередь:
|
1 2 3 |
int n; cin >> n; Queue cards; |
Затем объявим переменную для цвета текущей карточки и инициализируем ее таким образом, чтобы последняя добавляемая карточка была белой. Так как при четном числе карточек в стопке последняя выкладываемая (она же — первая добавляемая) будет черной, а при нечетном — белой, то при кодировании черных и белых цветов как [latex]0[/latex] и [latex]1[/latex] соответственно инициализируется она следующим значением:
|
1 |
bool t = n % 2; |
Теперь перейдем к сбору стопки. Действуем согласно описанному выше алгоритму: пока в стопке не окажутся все карточки, кроме одной, добавляем карточку на условный верх стопки, перекладываем карточку из-под низа наверх и меняем цвет следующей карточки. После этого добавляем на верх стопки белую карточку:
|
1 2 3 4 5 6 |
for(int i = 0; i < n - 1; i++) { cards.push(t); cards.push(cards.pop()); t = !t; } cards.push(1); |
|
1 2 |
for(int i = 0; i < n; i++) cout << cards.pop(); |
Ссылки
Код программы на Ideone.com;
Список задач по структурам данных на Algolist.manual.ru.