2015-06-24
1364
Квадрат разбит на 4k равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной (правая половина подкладывается под левую) и горизонтальной (нижняя половина подкладывается под верхнюю) оси симметрии до тех пор, пока все клетки не будут расположены друг под другом. Требуется занумеровать клетки исходного квадрата таким образом, чтобы в результате выполнения операций перегиба номера клеток, расположенных друг под другом, образовали числовую последовательность 1,2,3,...,4k, начиная с верхней клетки.
Решение этой задачи аналогично решению предыдущей задачи со сгибанием полоски с той лишь разницей, что тут будет поочередно производится два сгибания: сначала правая половина под левую, а затем нижнюю под верхнюю
{$A-,B-,D-,E+,F-,G-,I+,L-,N-,O-,R-,S-,V-,X-}{$M 16384,0,655360}uses crt;constmaxk = 6;typeinput = recordlast1,last2,next1,next2,new: word;end;vark,i,j,i1,i2,j1,j2,nj1,nj2,n,n1,cn,half: word;m: array[1..1 shl maxk,1..1 shl maxk] of input;Procedure concat(a,b,c,d: word);var i1,i2,j1,j2,nj1,nj2: word;begini1:=a; i2:=b;while (m[i1,i2].next1<>n+1) and (m[i1,i2].next2<>n+1) dobegini1:=m[i1,i2].next1; i2:=m[i1,i2].next2;end;j1:=c; j2:=d;while (m[j1,j2].next1<>n+1) and (m[j1,j2].next2<>n+1) dobeginj1:=m[j1,j2].next1; j2:=m[j1,j2].next2;end;while j1<>0 dobeginnj2:=m[j1,j2].last2; nj1:=m[j1,j2].last1;m[i1,i2].next1:=j1; m[i1,i2].next2:=j2;m[j1,j2].last1:=i1; m[j1,j2].last2:=i2;i1:=j1; i2:=j2; j1:=nj1; j2:=nj2;end;m[i1,i2].next1:=n+1; m[i1,i2].next2:=n+1;end;beginWrite('Введите k...');readln(k);n:=1 shl k; {Определение числа клеток в одной строке или столбце}n1:=n*n; {Определение числа клеток в матрице}for i:=1 to n dofor j:=1 to n do with m[i,j] do beginlast1:=0; next1:=n+1;last2:=0; next2:=n+1;new:=0;end;cn:=n;while cn>1 do {сгибание матрицы}beginhalf:=cn div 2;for i:=1 to half do {сгиб по вертикали}for j:=1 to cn do concat(j,i,j,cn-i+1);for i:=1 to half do {сгиб по горизонтали}for j:=1 to half do concat(i,j,cn-i+1,j);cn:=half;end;j1:=1;j2:=1;for i:=1 to n1 do {Назначение клеткам новые номера}beginm[j1,j2].new:=i;nj1:=m[j1,j2].next1; nj2:=m[j1,j2].next2;j1:=nj1; j2:=nj2;end;for i:=1 to n do {Вывод результатов}beginfor j:=1 to n do write(m[i,j].new:8);writeln;end;end.Задача №21
|
|
|
Имеется n черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая под низ стопки, третья- на стол, четвертая - под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.
Проще всего взять и промоделировать раскладку карточек: берем стопку из 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 {пока первый элемент не является} {одновременно и последним}beginBEFORE:=BEG; {сохраняем индекс начала списка}BEG:=A[BEG]; {удаляем первый элемент из списка}A[BEFORE]:=COLOR; {раскрашиваем удаленный элемент} {в нужный цвет}COLOR:=1-COLOR; {меняем цвет}A[FIN]:=BEG; {переставляем элемент из}FIN:=BEG; {начала списка в конец}BEG:=A[BEG];A[FIN]:=0end;A[BEG]:=COLOR; {раскрашиваем последний элемент}{списка}for i:=1 to N do {распечатка цветов}if A[i]=0then writeln('элемент',i,' - черный')else writeln('элемент',i,' - белый');
