Задача 3.
Задана полоска длиной 2k клеток и шириной в одну клетку. Полоску сгибают пополам так, чтобы правая половинка оказалась под левой. Сгибание продолжают до тех пор, пока сверху находится больше одной клетки. Необходимо пронумеровать клетки таким образом, чтобы после окончания сгибания полосы номера клеток в получившейся колонке были расположены в порядке 1,2,3,4,...,2k.
|
Решение задачи 3.
Будем моделировать сложение полоски, затем пронумеруем получившуюся колонку клеток числами от 1 до 2n, после чего распечатаем числа, приписанные первой, второй, ..., 2n-ой клетке исходной полоски.
Сначала создаем двусвязный список, состоящий из 2k элементов. Поле next будет указывать на элемент находящийся под данным, а поле last - на элемент находящийся над данным. Для верхнего элемента last=0, а для нижнего next=n+1, где n-общее число элементов. Вначале длина верхней полоски равняется n элементов, после первого сгибания их она станет n/2, после второго - n/4, и т.д. Пусть в данный момент длина верхней полоски есть cn элементов. Значит нам необходимо cn/2 правых элементов опустить под cn/2 левых. Для этого запустим цикл, который будет менять i от 1 до cn/2 и на каждом шаге помещать (cn-i+1)-ю колонку элементов под i-ю, при этом порядок элементов в (cn-i+1)-ой колонке меняется на противоположный. После каждого сгибания cn уменьшается вдвое. Так продолжаем до тех пор пока cn>1.
Программа (программы для задач 3 и 4 написаны В.Белым):
{$A-,B-,D-,E+,F-,I-,L-,N-,O-,R-,S-,V-}
{$M 65520,0,655360}
uses crt;
const
maxk = 13; {Максимальное значение для k}
type
input = record
last,next,new : word;
end;
var
k,i,j,n,cn,half : word;
m : array[1..1 shl maxk] of input;
Procedure concat(a,b : word);
var i,j,nj : word;
begin
i:=a;while m[i].next<>n+1 do i:=m[i].next;
j:=b; while m[j].next<>n+1 do j:=m[j].next;
while j<>0 do
begin
nj:=m[j].last; m[i].next:=j; m[j].last:=i; i:=j; j:=nj;
end;
m[i].next:=n+1;
end;
begin
Write('Enter k...');readln(k);
n:=1 shl k; {Определение длины полоски}
for i:=1 to n do{Начальные значения}
with m[i] do
begin
last:=0;
next:=n+1;
new:=0;
end;
cn:=n;
while cn>1 do {Сгибание полоски}
begin
half:=cn div 2;
for i:=1 to half do concat(i,cn-i+1);
cn:=half;
end;
j:=1;
for i:=1 to n do {Нумерация клеток}
begin
m[j].new:=i; j:=m[j].next;
end;
for i:=1 to n do write(m[i].new:5);
writeln;
end.
Попробуйте найти формулу и написать программу, которая без моделирования складывания полоски по номеру клетки выдавала бы ее номер.
|
