Задача 13.
Имеется n черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая под низ стопки, третья- на стол, четвертая - под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.
|
Решение задачи 13.
Проще всего взять и промоделировать раскладку карточек: берем стопку из n черных и белых карточек и начинаем расклад как говорится в задаче - первая на стол, вторая под низ, третья на стол, и т.д. при этом первой выложенной карточке приписывается белый цвет, а каждой последующей - цвет, не совпадающий с цветом предыдущей карточки. Повторяет так, пока не найдем раскраску всех n карточек.
Для этой задачи возьмем такую структуру данных как список. У списка есть начало и конец, и каждый элемент его указывает на следующий за ним элемент. Будем считать , что у последнего элемента списка указатель на следующий за ним равен 0. Список можно представлять массивом. Например, если в списке 4 элемента, то массив будет выглядеть так:
т.е. за первым элементом находится A[1]=2 элемент, ..., за 4-ым - A[4]=0 (т.к. 4-ый элемент списка последний).
Пусть у нас есть указатель на начальный элемент списка и на последний (BEG и FIN соответственно). В списке n элементов.
Рассмотрим процедуру удаления элемента из начала списка (это соответствует переносу карточки на стол):
BEG:=A[BEG]; {теперь новый первый элемент списка - второй элемент старого списка}
Рассмотрим операторы перестановки элемента из начала списка в конец (это соответствует перемещению карточки сверху стопки под низ ее):
A[FIN]:=BEG; {следующей за последним элементом - бывший первый}
FIN:=BEG; {меняем ссылку на последний элемент}
BEG:=A[BEG] {новый первый элемент}
A[FIN]:=0 {корректировка ссылки у последнего элемента}
Фрагмент программы будет выглядеть так:
for i:=1 to N-1 do A[i]:=i+1;
A[N]:=0; {установка ссылок в списке}
BEG:=1; FIN:=N;
COLOR:=1; {белый цвет = 1, черный = 0}
while A[BEG]<>0 do {пока первый элемент не является} {одновременно и последним}
begin
BEFORE:=BEG; {сохраняем индекс начала списка}
BEG:=A[BEG]; {удаляем первый элемент из списка}
A[BEFORE]:=COLOR; {раскрашиваем удаленный элемент}
{в нужный цвет}
COLOR:=1-COLOR; {меняем цвет}
A[FIN]:=BEG; {переставляем элемент из}
FIN:=BEG; {начала списка в конец}
BEG:=A[BEG];
A[FIN]:=0
end;
A[BEG]:=COLOR; {раскрашиваем последний элемент}
{списка}
for i:=1 to N do {распечатка цветов}
if A[i]=0
then writeln('элемент',i,' - черный')
else writeln('элемент',i,' - белый');
|
