AL13

Молоканов Юрий
Молоканов Юрий

Latest posts by Молоканов Юрий (see all)

Условие

Имеется [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.

MLoops 16

Задача

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex] n>0[/latex]  (количество столбцов) и [latex]m>0[/latex] (количество строк).

123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231

 

Тесты

[latex]m[/latex]    [latex]n[/latex]
4    3 123

231

132

123

8    8 12312312
23123123
13213213
12312312
23123123
13213213
12312312
23123123
 10    27 123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123

 

Код программы

 

ideone.com

Решение

Пронумеруем строки от  [latex]1[/latex]  до  [latex]m[/latex] , столбцы — от  [latex]1[/latex]  до  [latex]n[/latex].

1 2 3 4 5 6 7 n
1 1 2 3 1 2 3 1
2 2 3 1 2 3 1 2  …
3 1 3 2 1 3 2 1
4 1 2 3 1 2 3 1  …
5 2 3 1 2 3 1 2  …
6 1 3 2 1 3 2 1  …
7 1 2 3 1 2 3 1  …  …
 …  …  …  …
m  …  …  …  …

 

Положение символа  [latex]2[/latex] определяется однозначно для всей таблицы [latex]\left (n+m \right )\vdots 3[/latex]. В столбцах, где [latex]n\vdots 3[/latex], положение символа [latex]1[/latex]  —  [latex]\left ( n+m+1 \right )\vdots 3[/latex] , на оставшихся свободных местах — символ [latex]3[/latex] . В столбцах, где [latex]\left ( n-1\right )\vdots 3[/latex], на свободных местах стоит символ [latex]1[/latex]. В оставшихся столбцах на свободных местах стоит символ [latex]3[/latex].

MLoops 17

Павел Загинайло
Павел Загинайло

Latest posts by Павел Загинайло (see all)

Задача

Найти закономерность и написать программу, которая выводит аналогичную таблицу для любых чисел n>0 (количество столбцов) и m>0 (количество строк).

Замечание 1. В некоторых задачах появляется дополнительный параметр k < n.

Тесты

Входные данные Выходные данные
m n  k
13 31 9
5 8 4
20 20 3

 

 

Алгоритм

Программа выполняется с помощью двух циклов. Первый цикл отвечает за строки, второй за столбцы. Метод заключается в том, чтобы узнать, когда мы записываем именно ‘+’, а уже в остальные места записываем ‘.’.  Для начала проверяем делится ли номер строки, уменьшенный на 1, нацело на 6. Если да, то записываем +.  Далее проверяем, делится ли номер столбца,  уменьшенный на 1, на число [latex]k+1[/latex], где [latex]k[/latex] — вводимый параметр. Во всех остальных случаях пишем ‘.’.

Код программы

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

 

MLoops8

Задача

Найти закономерность и написать программу, которая выводит аналогичную таблицу для любых чисел [latex]n>0[/latex] (количество столбцов) и [latex]m>0[/latex] (количество строк).

Входные данные

Два числа:количество столбцов и строк.

Выходные данные

Таблица размером n*m со следующей закономерностью:

+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21

Код

Упрощенный вариант

 

Тесты

[latex]n[/latex] [latex]m[/latex] Выходные данные
1 1  +
7 7 +21++21

1++21++

+21++21

1++21++

+21++21

1++21++

+21++21

 

15 6  +21++21++21++21

1++21++21++21++

+21++21++21++21

1++21++21++21++

+21++21++21++21

1++21++21++21++

 

25 8 +21++21++21++21++21++21++

1++21++21++21++21++21++21

+21++21++21++21++21++21++

1++21++21++21++21++21++21

+21++21++21++21++21++21++

1++21++21++21++21++21++21

+21++21++21++21++21++21++

1++21++21++21++21++21++21

Решение

Для решения сначала нужно найти закономерность чередования символов в таблице. Пусть нумерация столбцов и строк будет начинаться с единицы, тогда, если строка [latex]i \vdots 2[/latex], то символы в ней чередуются по такому принципу: если результат от прибавления номера столбца к 1 кратен 4 ([latex] (j+1)\vdots 4 [/latex]), то в данной строке и столбце находится «1», если же результат от прибавления номера столбца к 2 кратен 4([latex] (j+2)\vdots 4 [/latex]), то в данной строке и столбце находится «2», если ни одно из этих условий не выполняется, значит на данном месте находится «+».

Если же строка [latex]i\vdots 2[/latex], то символы в ней чередуются по такому принципу: если результат от прибавления номера столбца к 3 кратен 4 ([latex] (j+3)\vdots 4[/latex]), то в данной строке и столбце находится «1», а если номер столбца кратен 4([latex] j\vdots 4 [/latex]), то в данной строке и столбце находится «2», если ни одно из этих условий не выполняется, значит на данном месте находится «+».

Ссылки

Код программы 

Упрощенный код