Предварительные сведения. Какие бывают структуры данных?
Стеком будем называть последовательность элементов, упорядо-
ченных по времени их поступления. Эта последовательность доступна
только с одного конца (вершины стека). Для работы со стеком необ-
ходим указатель вершины стека. Основные операции над стеком следу-
ющие: "запомнить в стеке" и "извлечь из стека" (причем извлекается
последний из занесенных в стек элементов - то есть элемент с вер-
шины стека). Поэтому говорят, что стек -- это структура типа LIFO
- "Last In - First Out" - "последним зашел - первым вышел". Для
представления стека в программе обычно используется одномерный
массив (назовем его B), нумерация элементов которого начинается с
нуля. В этом нулевом элементе массива хранится индекс первого сво-
бодного места в массиве (т.е. увеличенный на 1 индекс вершины сте-
ка). Если массив пуст, то указатель равен 1 (B[0]=1).
Добавление элемента X в стек реализуется очень просто - на
первое свободное место (индекс которого хранится в B[0]) помеща-
ется X, после чего индекс первого свободного места увеличивается
на 1:
B[B[0]]:=x; { Занести в стек }
B[0]:=B[0]+1; { Увеличить указатель }
Если необходимо извлечь элемент x из стека, то берется послед-
ний из занесенных элементов (естественно, только в том случае,
если стек непуст), и указатель на первое свободное место умень-
шается на 1:
if B[0]<>1 { Если стек не пуст }
then
begin
x:=B[B[0]]; { Взять элемент }
B[0]:=B[0]-1; { Уменьшить указатель }
end;
Каждый элемент списка имеет указатель на следующий за ним
элемент (другими словами -- хранит информацию о расположении сле-
дующего элемента), а если список двусвязный (двунаправленный),
то имеет также указатель и на предшествующий элемент. Кроме того
есть переменная, указывающая на первый элемент списка. Например,
двунаправленный список может быть реализован с помощью двумерного
массива A[1..3,1..N], где содержимое A[2,i] определяет позицию
(индекс, адрес) элемента, предшествующего элементу A[1,i], а со-
держимое A[3,i] определяет позицию элемента, следующего за A[1,i].
Основные операции над списком следующие: "удалить из списка"
и "поместить в список".
Например, помещение в список элемента х после элемента A[1,i]
может выглядеть так:
A[1,j]:=x; { Занести в массив }
A[2,j]:=i; { Изменить указатели }
A[3,j]:=A[3,i];
A[3,i]:=j;
Здесь j - адрес свободной позиции в массиве А.
Очередь в программировании, как и очередь в магазине, имеет
начало и конец. Если приходит новый элемент, то он становится в
конец очереди, если необходимо взять элемент из очереди, то он бе-
рется из ее начала. Очередь будем представлять в виде массива.
Пусть у нас есть индекс первого - BEG и последнего - FIN элементов
очереди (если очередь пуста, то BEG=FIN+1; сначала же BEG=1,
FIN=0).
Очередь опишем так: var Queue=array[1..MaxQ] of element;
Тут MaxQ - максимальное число элементов в очереди, element -
какой-то тип данных. В качестве element можно взять структуру сле-
дующего вида:
type element = record
x: byte;
y: byte;
end;
где element - это запись, состоящая из x-овой и y-овой коор-
динаты.
С очередью можно проводить операции:
вставка в очередь InQueue,
удаление из очереди OutQueue.
Procedure InQueue (x : element);
begin
FIN:=FIN+1; { на первое свободное место}
Queue[FIN]:=x; { ставим элемент x }
end;
Procedure OutQueue (var x : element);
begin
x:=Queue[BEG]; { берем первый элемент }
BEG:=BEG+1; { и изменяем указатель }
{ на следующий за ним }
end;
__________________________________________________________
Задача 1
Вводится последовательность, состоящая из N пар символов
(ai,bi). Каждая пара определяет порядок предшествования символов,
например, пара (b,с) означает, что символ "b" предшествует символу
"с". Из порядка (b,с) и (с,a) следует порядок (b,a). Необходимо
определить, является ли введенная последовательность:
а) полной, т.е. все использованные для формирования пар символы
(выбросив повторяющиеся) можно выстроить в цепочку (A1,A2,
..., As) в порядке предшествования;
б) противоречивой, т.е. для некоторых символов x,y можно
получить одновременно порядок как (x,y) так и (y,x);
Задача 2.
Вокруг считающего стоит N человек, из которых выделен первый,
а остальные занумерованы по часовой стрелке числами от 2 до N.
Считающий, начиная с кого-то, ведет счет до M. Человек на котором
остановился счет, выходит из круга. Счет продолжается со следующе-
го человека и так до тех пор, пока не останется один человек.
Определить
a) номер оставшегося человека, если известно M и то, что счет
начинался с первого человека;
b) номер человека c которого начинался счет, если известно M
и номер оставшегося человека L.
Задача 3.
Задана полоска длиной 2^k клеток и шириной в одну клетку. По-
лоску сгибают пополам так, чтобы правая половинка оказалась под
левой. Сгибание продолжают до тех пор, пока сверху находится боль-
ше одной клетки. Необходимо пронумеровать клетки таким образом,
чтобы после окончания сгибания полосы номера клеток в получившейся
колонке были расположены в порядке 1,2,3,4,...,2^k.
Задача 3.1.
"Полоска". Прохоров В.В.
Расположенную вертикально прямоугольную бумажную ленточку с
закрепленным нижним концом стали складывать следующим образом:
- на первом шаге ее согнули пополам так, что верхняя половина
легла на нижнюю либо спереди (П - сгибание) либо сзади (З -
сгибание),
- на последующих n-1 шагах выполняли аналогичное действие с
получающейся на предыдущем шаге согнутой ленточкой, как с единым
целым.
Затем ленточку развернули , приведя ее в исходное состояние.
На ней остались сгибы - ребра от перегибов, причем некоторые из
ребер оказались направленными выпуклостью к нам (К - ребра), а
некоторые - от нас (О -ребра). Ребра пронумеровали сверху вниз
числами от 1 до 2^n-1.
А. Составить программу, запрашивающую:
- строку символов из прописных букв "П" и "З", определяющую
последовательность типов сгибаний,
- номер ребра,
и сообщающую тип этого ребра, получившийся после заданной
последовательности сгибаний.
Б. Составить программу, запрашивающую строку символов из
прописных букв "О" и "К", где нахождение на i-том месте символа
"О" или "К" определяет тип ребра на расправленной полоске, и
выдающую строку из прописных "П" и "З", определяющих
последовательность типов сгибаний, посредством которых получена
ленточка с исходной последовательностью ребер. Если такой строки
не существует, сообщить об этом.
Задача 4.
Квадрат разбит на 4^к равновеликих квадратных клеток. Квадрат
перегибается поочередно относительно вертикальной (правая половина
подкладывается под левую) и горизонтальной (нижняя половина подк-
ладывается под верхнюю) оси симметрии до тех пор, пока все клетки
не будут расположены друг под другом. Требуется занумеровать клет-
ки исходного квадрата таким образом, чтобы в результате выполнения
операций перегиба номера клеток, расположенных друг под другом,
образовали числовую последовательность 1,2,3,...,4^к, начиная с
верхней клетки.
Задача 5.
Даны обозначения двух полей шахматной доски (например, A5 и
C2). Найти минимальное число ходов, которые нужны шахматному коню
для перехода с первого поля на второе.
Задача 6.
Дана конечная последовательность, состоящая из левых и правых
скобок pазличных заданных типов. Как определить, можно ли добавить
в нее цифры и знаки арифметических действий так, чтобы получилось
правильное арифметическое выражение.
Задача 7.
В таблице А размера N за один просмотр необходимо каждый эле-
мент заменить на ближайший следующий за ним элемент, который боль-
ше его. Если такого элемента нет, то заменить его на ноль. Можно
использовать дополнительную память.
ПРИМЕР А=1 3 2 5 3 4
ОТВЕТ А=3 5 5 0 4 0
Задача 8.
В городе расположены n автобусных остановок, обозначенных
числами из N={1,2,....,n}. Имеется R автобусных маршрутов, задан-
ных последовательностями соседних остановок при движении автобуса
в одном направлении:
М1={I11,I12,...,I1m1},
М2={I21,I22,...,I2m2},
.....
Mr={Ir1,Ir2,...,Irmr},
где Ijk натуральное.
Написать программу, которая по заданным номерам остановок I и
J определяет наиболее быстрый путь перемещения пассажира из оста-
новки I в остановку J с использованием имеющихся маршрутов авто-
бусов при условий, что время движения между соседними остановками
у всех маршрутов одинаково и в 3 раза меньше времени изменения
маршрута. Кроме того, автобусы могут двигаться в обоих направлени-
ях.
Задача 9.
Одинокий король долго ходил по бесконечной шахматной доске.
Известна последовательность из N его ходов (вверх, вниз, влево,
вправо, вверх-влево и т.п.).Написать программу, определяющую побы-
вал ли король дважды на одном и том же поле за минимально возмож-
ное при заданном N число вычислений.
Задача 10
По кругу расположено N монет гербами вверх и M монет гербами
вниз. Обходя круг по ходу часовой стрелки, переворачивает каждую S
-тую монету. В первый раз счет начинается с герба. В каком порядке
надо расставить монеты, чтобы после K ходов стало L монет, лежащих
гербами вверх.
Задача 11.
N серых и M белых мышей сидят по кругу. Кошка ходит по кругу
по часовой стрелке и съедает каждую S -тую мышку. В первый раз
счет начинается с серой мышки. Составить алгоритм определяющий по-
рядок в котором сидели мышки, если через некоторое время осталось
K серых и L белых мышей.
Задача 12.
Из листа клетчатой бумаги размером М*N клеток удалили некото-
рые клетки.На сколько кусков распадется оставшаяся часть листа?
Пример. Если из шахматной доски удалить все клетки одного
цвета,то оставшаяся часть распадется на 32 куска.
МОДИФИКАЦИЯ. То же, но перед удалением клеток лист склеили в
цилиндр высотой N.
Задача 13.
Имеется n черных и белых карточек, сложенных в стопку. Кар-
точки раскладываются на стол в одну линию следующим образом: пер-
вая кладется на стол, вторая под низ стопки, третья- на стол, чет-
вертая - под низ стопки и т.д., пока все карточки не будут выложе-
ны на стол. Каким должно быть исходное расположение карточек в
стопке, чтобы разложенные на столе карточки чередовались по цвету:
белая, черная, белая, черная и т.д.
Задача 14.
Фоpма тела задана матpицей А pазмеpности M x N. Элементы
матpицы - натуpальные числа. Элемент А ( i,j ) соответствует высо-
те гоpизонтальной квадpатной площадки pазмеpа 1 x 1 относительно
нижнего основания.Нижнее основание фоpмы горизонтально.
Опpеделить об"ем невытекшей воды, если
a) Тело опускается полностью в воду, затем поднимается;
Пример:
5 3 1
А = 5 2 5
2 5 5
После подъема вода останется только во внутреннем углублении,
над элементом А(2,2)=1.
Объем воды равен 1.
b) В позицию (i0,j0) выливается объем воды V.
Задача 15.
Матрица размера N*M определяет некоторый лабиринт. B матице
элемент 1 обозначает стену, а 0 определяет свободное место. В пер-
вой строке матрицы определяются входы x(i), а в последней выходы
y(i), i=1,..,k, которые должны быть нулевыми элементами.
Необходимо определить, можно ли
а) провести k человек от входа x(i) до выхода y(i) соот-
ветственно, i=1,..,k, таким образом, чтобы каждое свободное место
посещалось не более одного раза.
б) то же,но человека можно выводить чеpез любой из выходов.
Примечание: Движение в лабиринте осуществляется только по
вертикали или горизонтали.
Задача 16.
Вводится скобочное арифметическое выражение. В выражении мо-
гут встречаться открывающая и закрывающая круглые скобки ( и ),
знаки операций +, -, *, / (деление - целочисленное) и цифры от 0
до 9. Найти значение этого скобочного выражения.
Пример: '(3+5*2)/3-1'=3.
Задача 17.
Есть министерство из N чиновников, где N натуральное число. У
каждого из чиновников могут быть как подчиненные,так и начальни-
ки,причем справедливы правила: подчиненные моего подчиненного -
мои подчиненные, начальники моего начальника - мои начальники, мой
начальник не есть мой подчиненный, у каждого чиновника не более
одного непосредственного начальника.
Для того чтобы получить лицензию на вывоз меди необходимо полу-
чить подпись 1-ого чиновника - начальника всех чиновников. Пробле-
ма осложняется тем, что каждый чиновник, вообще говоря, может пот-
ребовать "визы", т.е. подписи некоторых своих непосредственных
подчиненных и взятку - известное количество долларов. Для каждого
чиновника известен непустой список возможных наборов "виз" и соот-
ветствующая каждому набору взятка.Пустой набор означает,что данный
чиновник не требует виз в данном случае. Чиновник ставит свою под-
пись лишь после того,как ему представлены все подписи одного из
наборов "виз" и уплачена соответствующая взятка.
Необходимо определить и вывести минимальный по сумме упла-
ченных взяток допустимый порядок получения подписей для лицензии и
стоимость.
N<100. Количество наборов для каждого чиновника не превосхо-
дит 15.
Задача 1.
Пусть при записи этих N пар встретилось всего K различных
символов, которые образуют множество X.
Идея решения задачи состоит в последовательном присвоении
каждому символу s из Х номера, который определяет количество Р(s)
элементов, предшествующих ему, с учетом свойства транзитивности
(из (с,b) и (b,а) следует (с,а)). Это осуществляется следующим об-
разом:
Первоначально предполагается, что каждому символу не пред-
шествует ни один символ, т.е. Р(s)=0 для любого s.
При просмотре очередной пары (x,y) символу y присваивается
большее из значений P(x)+1, P(y).
Очевидно, что при первом просмотре всех пар из входной после-
довательности определятся все упорядоченные цепочки длины 2, т.е.
состоящие из 2 элементов. Поэтому номера некоторых элементов будут
как минимум 1. При каждом из следующих просмотров входной строки
возможно несколько вариантов.
1. Не произошло изменения ни одного из номеров символов. Если
при этом номера символов различны и лежат в пределах от 0 до
N-1, то эта нумерация определяет полный порядок. Иначе порядок
неполный.
2. Номер некоторого символа превысил N-1. Это произошло пото-
му, что рост номеров неограничен, т.е. осуществляется цикли-
чески. Следовательно порядок противоречив.
Легко понять, что число просмотров не превысит N.
Вариант 2. Рассмотрим следующий метод:
Заведем массивы
A: array [1..N,0..N] of byte
и
Cnt: array[1..N] of byte;
сначала A[i,0]=0 и Cnt[i]=0 для любого i.
Пусть среди 2*N символов, образующих N пар, есть ровно K раз-
личных. Перенумеруем их от 1 до K. Будем считать, что пары составле-
ны не из символов, а из соответствующих им номеров.
В i-ю строчку матрицы A будем заносить те элементы, которые яв-
ляются вторыми элементами в парах с первым элементом i. В A[i,0] бу-
дет храниться текущее число этих элементов. Обработка пары (i,j) бу-
дет выглядеть следующим образом:
A[i,0]:=A[i,0]+1; { количество увеличилось на 1 }
A[i,A[i,0]]:=j; { вставляем j на первое свободное место }
В Сnt[i] будет храниться число пар, у которых элемент i явля-
ется вторым в паре.
Если все символы без повторений, использованные для записи пар,
можно выписать в цепочку в порядке предшествования, то у этой цепоч-
ки должен быть первый символ s, у которого нет предшествующего и кото-
рому соответствует Cnt[s]=0.
Может быть несколько ситуаций:
1. Такой элемент единственный -- следовательно, это начало це-
почки. Отбрасываем s из цепочки и убираем все пары с первым элемен-
том s из множества пар, корректируя при этом массив Cnt:
for i:=1 to A[0,s] do
Сnt[A[s,i]]:=Cnt[A[s,i]]-1;
после чего опять ищем элемент s, у которого нет предшествующего
и которому соответствует Cnt[s]=0.
2. Таких элементов несколько, следовательно, между ними нельзя
определить порядок предшествования -- система неполна.
3. Таких элементов нет -- следовательно, система противоречива.
Задача 2.
Для решения этой задачи используем структуру данных 'список'.
Каждый элемент списка указывает на следующий за ним элемент (другими
словами -- хранит информацию о расположении следующего элемента).
a). Заведем массив A из N ячеек - по числу людей в круге. В каж-
дую из ячеек A[i] занесем номер стоящего следующим за i-ым человека.
Первоначально A[i]=i+1, i=1,...,.N-1, A[N]=1. Начиная счет от теку-
щего человека (человека с номером IndTek, с самого сначала IndTek=1)
будем делать ход - отсчитывать M ячеек, двигаясь по кругу в поисках
человека, который должен выйти из круга. С учетом определения масси-
ва A это будет выглядеть следующим образом:
{ IndTek -- это номер человека, с которого начинается счет }
for i:=1 to M-1 do { Отсчитываем M человек, начиная с IndTek }
begin
IndPred:=IndTek; { в IndPred сохраняем номер текущего
человека в круге }
IndTek:=A[IndTek]; { и вычисляем номер следующего за ним }
end;
После выполнения этого цикла в переменной IndTek будет номер
человека, на котором остановился счет (т.е. номер человека, который
покинул круг), а в переменной IndPred -- номер предшествующего ему
человека в круге.
Удалим человека с номером IndTek. Для этого мы просто изменим
ссылку A[IndPred] у предшествующего ему человека так, чтобы он ука-
зывал не на IndTek, а на следующего за IndTek, т.е. на A[IndTek], и
новый отсчет M-того человека начнем со следующего за удаленным:
A[IndPred]:=A[IndTek];
IndTek:=A[IndTek]; { Новый номер начального человека }
Все вышеописанные операции мы будем повторять до тех пор, пока
в круге не останется одного единственного человека, т.е. до тех пор,
пока A[IndTek] не станет равным IndTek, что означает, что следующим
за человеком с номером IndTek является он сам.
Полностью весь фрагмент программы будет выглядеть так:
{ Инициализация массива A }
for i:=1 to N-1 do
A[i]:=i+1;
A[N]:=1;
{ IndTek -- это номер человека, с которого начинается счет }
IndTek:=1;
while A[IndTek] <> IndTek do
begin
for i:=1 to M-1 do { Отсчитываем M человек, начиная с IndTek }
begin
IndPred:=IndTek; { в IndPred сохраняем номер текущего
человека в круге }
IndTek:=A[IndTek]; { и вычисляем номер следующего за ним }
end;
A[IndPred]:=A[IndTek];
IndTek:=A[IndTek]; { Новый номер начального человека }
end;
writeln('Номер последнего оставшегося человека ',IndTek);
Решения пункта b).
Будем считать, что человек с номером N+i -- это то же самое,
что и человек с номером i.
Предположим, что как и в пункте a), что мы начали счет с перво-
го человека, выбрасывали из круга M-того, и последний оставшийся в
круге человек имеет номер K. Очевидно, что если бы мы начали счет со
второго человека, то последний оставшийся в круге человек имел бы
номер K+1, ..., если с j-го, то K+j-1.
Если номер оставшегося человека L, то из равенства L=K+j-1 оп-
ределяем номер j первого человека (если j<=0, то заменим j на j+N,
считая как и раньше, что человек с номером N+j -- это то же самое,
что и человек с номером j).
Задача 3.
Будем моделировать сложение полоски, затем пронумеруем полу-
чившуюся колонку клеток числами от 1 до 2^n, после чего распечата-
ем числа, приписанные первой, второй, ..., 2^n-ой клетке исходной
полоски.
Сначала создаем двусвязный список, состоящий из 2^k элемен-
тов. Поле 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.
Попробуйте найти формулу и написать программу, которая без
моделирования складывания полоски по номеру клетки выдавала бы ее
номер.
Задача 4.
Решение этой задачи аналогично решению предыдущей задачи со
сгибанием полоски с той лишь разницей, что тут будет поочередно
производится два сгибания: сначала правая половина под левую, а
затем нижнюю под верхнюю
{$A-,B-,D-,E+,F-,G-,I+,L-,N-,O-,R-,S-,V-,X-}
{$M 16384,0,655360}
uses crt;
const
maxk = 6;
type
input = record
last1,last2,next1,next2,new : word;
end;
var
k,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;
begin
i1:=a; i2:=b;
while (m[i1,i2].next1<>n+1) and (m[i1,i2].next2<>n+1) do
begin
i1:=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) do
begin
j1:=m[j1,j2].next1; j2:=m[j1,j2].next2;
end;
while j1<>0 do
begin
nj2:=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;
begin
Write('Введите k...');readln(k);
n:=1 shl k; { Определение числа клеток в одной строке или столбце }
n1:=n*n; { Определение числа клеток в матрице }
for i:=1 to n do
for j:=1 to n do
with m[i,j] do
begin
last1:=0; next1:=n+1;
last2:=0; next2:=n+1;
new:=0;
end;
cn:=n;
while cn>1 do { сгибание матрицы }
begin
half:=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 { Назначение клеткам новые номера }
begin
m[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 { Вывод результатов }
begin
for j:=1 to n do write(m[i,j].new:8);
writeln;
end;
end.
Задача 5.
Идея решения основывается на использовании очереди. Вначале в
очередь помещается элемент, определяющий исходное положение шах-
матного коня, а соответствующая клетка поля помечается как посе-
щенная.
На каждом из следующих шагов алгоритма (пока очередь не пуста
или не помечена конечная клетка) выполняются следующие действия.
1. Из очереди извлекается очередной элемент, который определяет
некоторую позицию (x,y).
2. Находятся клетки в пределах поля, которые достижимы из (x,y)
одним ходом шахматного коня, и которые еще не помечены.
3. Элементы, соответствующие найденным клеткам, помещаются в
очередь, а клетки помечаются как посещенные.
При этом вначале все клетки должны быть непомечены, а метку
желательно ставить такую, чтобы можно было восстановить путь между
полями.
Для этого метку поля можно определить как позицию поля, из ко-
торой она была помечена.
Задача 6.
Идея решения основывается на использовании стека. Считывая
входную последовательность скобка за скобкой, выполняются следую-
щие действия.
1. Если очередная скобка - открывающая, то помещаем ее в стек.
2. Если очередная скобка - закрывающая, то анализируем скобку,
стоящую в вершине стека. Возможно несколько ситуаций:
а) открывающая скобка соответствует очередной закрывающей. В
этом случае она выталкивается из стека, а процесс с новой
входной скобкой.
б) открывающая скобка не соответствует очередной закрывающей
или стек пуст. В этом случае невозможно получить правильное
арифметическое выражение.
Когда все скобки входной строки обработаны, возможны 2 ситуации.
1. Стек пуст. В этом случае можно получить правильное арифме-
тическое выражение.
2. Стек не пуст. В этом случае невозможно получить правильное
арифметическое выражение.
Задача 7.
Необходимо организовать стек для позиций элементов,которые
претендуют быть большими. Для каждого текущего элемента выталки-
вать из стека все позиции, на которых стоят элементы меньше теку-
щего и заменить их текущим. Затем позицию текущего элемента по-
местить в стек.После просмотра всех элементов в стеке будут стоять
позиции элементов,которые надо заменить на ноль.
Задача 8.
Идея решения основывается на использовании очередей. Но если
реализация движения от остановки к остановке по одному маршруту ана-
логична технике, используемой в задаче 6, то возможность изменения
маршрутов несколько усложняет структуру элемента в очереди.
Для этого для каждой остановки введем тройку чисел (О,М,За),
где О - номер остановки, М - номер маршрута, За - величина задержки.
При выборе очередного элемента из очереди возможны 2 ситуации.
1. Продолжается движение по тому же маршруту. В этом случае в
очередь заносятся тройки типа (О',М,За), где О' - номер оста-
новки, соседней О, в маршруте М, а За=0.
2. Изменяется маршрут. В этом случае в очередь заносятся тройки
типа (О,М',За), где М' - номер измененного маршрута, За=3 (за-
держка на пересадку).
При этом новые тройки порождаются только тройками с задержкой,
равной 0. В случае тройки с ненулевой задержкой она вновь помещается
в очередь с уменьшенным на 1 значением задержки.
Задача 9.
Будем хранить в массиве A[1..N,1..2] координаты тех клеток,
где король уже был. Возьмем N достаточно большим, N=500. A[i,1] -
иксовая, A[i,2] - игрековая координата клетки. Пусть в переменной
DLN хранится количество уже сделанных ходов (т.о. в массиве A
после хода номер i будут заняты клетки с первой по i-ую).
Результаты очередного хода заносим в массив A на первое
свободное место (т.е. на место с индексом DLN+1), увеличиваем
количество сделанных ходов DLN:=DLN+1, и проверяем, совпадает
ли хоть одна из позиций, на которых король уже был, с текущей
позицией:
for i:=1 to DLN-1 do
if (A[i,1]=A[DLN,1]) and
(A[i,2]=A[DLN,2]) { проверка совпадения }
then begin
writeln('совпадение на ходах ',DLN,' и ',i);
halt; { останов }
end;
Давайте посмотрим, как можно вводить ходы короля. Он из
клетки k может пойти на 8 соседних позиций.
1 2 3 Будем вводить направление перемещения короля
8 К 4 цифрой от 1 до 8.
7 6 5
Заведем массив XOD=array[1..8,1..2]=((-1,1),(0,1),(1,1),
(1,0),(1,-1),(0,-1),(-1,-1),(-1,0));
В массив заносятся смещения по x- и y-координатам, соот-
ветствующие направлениям от 1 до 8. Координаты короля после сде-
ланного хода вычисляются по формулам
x:=x+XOD[i,1]; y:=y+XOD[i,2];
Задача 10.
Монеты лежат на N+M позициях. Пронумеруем эти позиции по по-
рядку по контуру от 1 до N+M.
Заведем массив A из N+M ячеек. Первоначально все ячейки нуле-
вые. Начиная счет от первой ячейки, будем делать ход - отсчитывать
S ячеек (считаем, что за N+M-ым элементом следует непосредственно
1-ый элемент массива) и заменять в этой ячейке число i на число
1-i (т.е. 0 на 1, а 1 на 0). После k-того хода остановимся.
Рассмотрим возникшую ситуацию. После каждого хода переворачи-
вается одна монета, при этом разность количества монет, лежащих
гербами вверх и количества монет, лежащих гербами вниз либо увели-
чивается, либо уменьшается на 2. Например, если переворачивается
монета, лежащая гербом вверх, то при этом увеличивается на 1 коли-
чество монет гербом вниз и уменьшается на 1 количество монет гер-
бом вверх.
Предположим, что после k ходов в массиве A стало p единиц -
т.е. p монет, по сравнению с начальным положением, будут перевер-
нуты после k-ого хода.
В случае, если L>=N, то (L-N) монет, которые лежали гербами
вниз, должны после k-ого хода быть перевернуты гербами вверх. (Ес-
ли p<(L-N), то это, очевидно, невозможно сделать). Среди оставших-
ся p-(L-N) перевернутых монет должна быть половина гербами вверх и
половина - вниз, чтобы при перевороте суммарное число монет герба-
ми вверх и вниз не изменилось. Следовательно, число p-(L-N) должно
быть четным, иначе условию задачи удовлетворить нельзя. Пусть
p-(L-N) = 2v. Должно быть, очевидно, v<=N, v+(L-N)<=M.
Итак, в случае L>=N, если не выполняется хотя бы одно из не-
равенств
p-(L-N)=2v>=0,
v<=N,
v+(L-N)<=M,
то преобразование начальной конфигурации в конечную невозможно.
Иначе на (L-N) мест, помеченных в массиве A единицами, выс-
тавляем монеты гербами вниз. На оставшиеся 2v=p-(L-N) помеченных
единицами позиций кладем v монет гербами вниз и v гербами вверх в
произвольном порядке. На остальные позиции кладем оставшиеся моне-
ты опять же в произвольном порядке, чтобы в общей сложности было N
монет гербами вверх и M - гербами вниз.
Но мы еще не учли тот факт, что счет начинается с первой мо-
неты гербом вверх:
а) Если в массиве A первый элемент нулевой, то в случае, если
среди (N+M)-p монет есть хоть одна гербом вверх (что эквивалентно
выполнению условия N-v>0), то ее и кладем в первую позицию. Если
все (N+M)-p монеты - гербом вниз (т.е. N-v=0), то размещение монет
невозможно.
б) Если же A[1]=1, то среди p монет должна быть по крайней
мере одна, которую необходимо положить гербом вверх, иначе, опять
же, размещение невозможно.
Случай N-L>0 разбирается аналогично.
Задача 11.
Как и в задаче 10 заполняем сначала массив A нулями, перену-
меровываем по порядку N+M позиций от 1 до N+M. Начиная с первой
позиции (серая мышка) делаем ход - отсчитываем S нулевых позиций
по порядку (считаем, что позиция, где сидела съеденная мышка, по-
мечается единицей, несъеденная мышка - нулем; за N+M-ой позицией
располагается первая) и выставляем в соответствующую позицию 1 -
мышка съедена. Далее отсчет начинаем со следующей за съеденной мы-
ши. (Для более быстрого поиска S-той мышки среди оставшихся в кру-
ге можно использовать список, описанный в задаче 2).
Делаем P=(N+M)-(K+L) ходов.
По условию задачи в первой позиции сидит серая мышка. Есть
A[1]=1 (первая мышь была съедена), то в оставшихся P-1 единичной
позиции в произвольном порядке расставляем N-K-1 серых и M-L белых
мышей. В оставшихся незанятыми позициях рассаживаем опять же в
произвольном порядке оставшихся мышей.
Если A[1]=0, и K=0, то начальной расстановки не существует
(все серые мыши съедены, а должна остаться еще одна в первой пози-
ции); если же K<>0, то в единичных позициях рассаживаем N-K серых
и M-L белых мышей, а в оставшихся позициях - в первую позицию -
серую мышь, а во все остальные - белых и серых в произвольном по-
рядке.
Задача 12.
Идея решения состоит в последовательном определении множества
клеток, принадлежащих тому же куску, что и некоторая фиксированная
клетка.
Начиная с некоторой непомеченной клетки (начальной), которая
помечается, помечаются все клетки, имеющие с ней общую сторону. За-
тем, используя вновь помеченные клетки, помечается множество клеток,
имеющих с ними общую сторону и т.д., пока на некоторой итерации не
будет помечено ни одной новой клетки. Множество клеток, помеченных
таким образом, и составляет единый кусок листа максимального разме-
ра.
Для подсчета общего количества кусков необходимо подсчитать ко-
личество клеток, выбранных в качестве начальных. Новая начальная
клетка выбирается из множества клеток, не помеченных на предыдущих
итерациях. Для хранения вновь помеченных клеток можно использовать
очередь или стек, а пометку клеток можно проводить в матрице размера
N*M.
Задача 13.
Проще всего взять и промоделировать раскладку карточек: берем
стопку из n черных и белых карточек и начинаем расклад как гово-
рится в задаче - первая на стол, вторая под низ, третья на стол, и
т.д. при этом первой выложенной карточке приписывается белый цвет,
а каждой последующей - цвет, не совпадающий с цветом предыдущей
карточки. Повторяет так, пока не найдем раскраску всех n карточек.
Для этой задачи возьмем такую структуру данных как список. У
списка есть начало и конец, и каждый элемент его указывает на сле-
дующий за ним элемент. Будем считать , что у последнего элемента
списка указатель на следующий за ним равен 0. Список можно
представлять массивом. Например, если в списке 4 элемента, то
массив будет выглядеть так:
1 2 3 4
┌───┬───┬───┬───┐
A │ 2 │ 3 │ 4 │ 0 │
└───┴───┴───┴───┘
т.е. за первым элементом находится 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,' - белый');
Задача 14.
Для реализации данного алгоритма нам понадобится структура
данных "очередь". Очередь в программировании, как и очередь в ма-
газине, имеет начало и конец. Если приходит новый элемент, то он
становится в конец очереди, если необходимо взять элемент из оче-
реди, то он берется из ее начала. Очередь будем представлять в ви-
де массива. Пусть у нас есть индекс первого - BEG и последнего -
FIN элементов очереди (если очередь пуста, то BEG=FIN+1; сначала
же BEG=1, FIN=0).
Очередь опишем так: var Queue=array[1..MaxQ] of element;
Тут MaxQ - максимальное число элементов в очереди, element -
какой-то тип данных. В задаче ниже в качестве element можно взять
такой
type element = record
x: byte;
y: byte;
end;
где element - это запись, состоящая из x-овой и y-овой коор-
динаты элемента матрицы A=array[0..M+1,0..N+1] of integer. Индексы
матрицы принимают такое значение из-за того, что мы будем окайм-
лять матрицу нулевыми элементами (так будет проще проверять выли-
вание за край фигуры).
С очередью можно проводить операции:
вставка в очередь InQueue,
удаление из очереди OutQueue.
Procedure InQueue (x : element);
begin
FIN:=FIN+1; { на первое свободное место}
Queue[FIN]:=x; { ставим элемент x }
end;
Procedure OutQueue (var x : element);
begin
x:=Queue[BEG]; { берем первый элемент }
BEG:=BEG+1; { и изменяем указатель }
{ на следующий за ним }
end;
Находим максимальный элемент D в матрице A. Пока все элементы
в матрице A не станут равны D, повторяем следующую последователь-
ность действий:
а) Находим в матрице минимальный ненулевой элемент z (если их
несколько, то берем любой из них), и заносим его в очередь (оче-
редь сначала пустая). Если этот минимальный ненулевой элемент z=D,
то СТОП.
Сначала считаем, что p=D - это минимальный граничный элемент
области, заполненной элементами со значением z.
б) Для каждого еще не просмотренного элемента очереди (пусть
в матрице этот элемент находится в позиции (i,j)) повторяем следу-
ющее:
Для каждого соседа (сверху, снизу, справа, слева) данного
элемента (i,j) проводим проверку-просмотр:
ЕСЛИ (сосед <> z)
ТО P=min{P,сосед}
ИНАЧЕ ЕСЛИ сосед еще не просмотрен
ТО координата соседа - в очередь (в очереди появился
еще один непросмотренный элемент)
т.е. мы ищем минимальный окаймляющий элемент области, заполненной
элементами со значением z.
Фрагмент программы поиска:
var Delta = array [1..4,1..2] of integer =
((0,1),(1,0),(-1,0),(0,-1));
{ Delta - возможные смещения соседних клеток от текущей клетки }
Current, neighbor : element;
z : integer;
....
{ Будем обозначать то, что элемент в матрице уже просмотрен }
{ умножением его на -1 }
{ минимальный ненулевой элемент матрицы имеет значение z }
while BEG<>FIN+1 do begin
OutQueue(Current);
for i:=1 to 4 do begin
neighbor.x:=Current.x+Delta[i,1],
neighbor.y:=Current.y+Delta[i,2],
if A[neighbor.x,neighbor.y]=z
then InQueue(neighbor)
else p:=min(A[neighbor.x,neighbor.y],p);
end;
end;
Если в очереди нет больше непросмотренных элементов, то, если
p<z (случай, когда данная область имеет "слив" за границы матрицы)
в матрице во все просмотренные элементы из очереди заносим значе-
ние D (делаем их равными накопленному значению, чтобы больше их не
рассматривать).
Если же p>z, то высчитываем, сколько воды поместится в
"бассейн" с глубиной дна z и с высотой ограждающего бордюра p:
Объем = (p-z)* количество просмотренных элементов в очереди.
Добавляем полученный объем к ранее найденному объему воды,
заполняющему матрицу до высоты x.
Заполняем в матрице элементы, соответствующие просмотренным
элементам из очереди, значением p ("Доливаем" воды в "бассейн" до
уровня p).
Переход на пункт а).
Суммарный полученный объем воды и является искомым.
Окаймление матрицы, упомянутое выше, может выглядеть сле-
дующим образом: матрица [1..N, 1..M] окаймляется нулями так:
вводятся дополнительные нулевые 0-ая и (N+1)-ая строки и 0-ой
и (M+1)-ый столбцы
var A: array[0..N+1,0..M+1] of byte;
{ ввод и окаймление нулями}
for i:=1 to N do begin
A[i,0]:=0; A[i,M+1]:=0;
for j:=1 to M do read(A[i,j]);
end;
for j:=0 to M+1 do begin
A[0,j]:=0; A[N+1,j]:=0;
end;
Задача 15.
Легко заметить, что для существования решения необходимо прово-
дить людей от самого левого входа к самому левому выходу,от самого
правого - к правому и т.д. Поэтому приведем решение только для слу-
чая б).
Основная стратегия человека, вошедшего в самый левый вход,
состоит в прохождении лабиринта, используя наиболее левые свободные
места лабиринта, т.е. он должен двигаться, держась правой рукой за
"стенку" лабиринта. Этот процесс можно формализовать следующим обра-
зом. Находясь в очередной позиции лабиринта, он должен помнить, с
какой стороны он пришел сюда (слева, справа, сверху, снизу), и, ру-
ководствуясь этой информацией, вобрать следующее наиболее предпочти-
тельное направление в новую позицию (куда он может пойти и где еще
не был). При этом удобно использовать стек, в верхушке которого на-
ходятся координаты текущей позиции и направление, по которому в нее
пришли. При этом все посещенные клетки метятся. Легко заметить, что
если в позицию попали сверху, то наилучшим направлением будет нале-
во, затем вниз, направо, и наконец назад (вверх). Аналогично можно
определить наилучшие направления для других случаев.
Эта стратегия повторяется каждым из людей, при этом позиции,по-
меченные предыдущими людьми, считаются запрещенными для следующих.
Задача 16.
Для упрощения вычислений рассмотрите преобразование выра-
жения в обратную польскую запись, т.е. в такую бесскобочную
форму, в которой операнды записываются в том же порядке, что и
в исходном выражении, а каждый знак операции следует не-
посредственно за операндами, над которыми эта операция прово-
дится.
Пример: Выражение '(3+5*2)/3-1' преобразуется в '3 5 2 *
+ 3 / 1 -' (сначала будет выполняться операция * над предыду-
щими двумя операндами 5 и 2, результат 10 помещается на место
чисел 5 и 2. Затем - операция + над предыдущими двумя операн-
дами 3 и 10, результат 13 помещается на место 3 и 10, и т.д.
Выражение в ходе вычисления будет принимать вид:
3 5 2 * + 3 / 1 -
3 10 + 3 / 1 -
13 3 / 1 -
4 1 -
3.
Алгоритм вычисления скобочного арифметического выражения.
Преобразуем сначала выражение в обратную польскую запись. Каж-
дой операции и открывающей скобке припишем приоритет:
приоритет
┌─────────────┬──────────┐
│ ( │ 0 │
│ +,- │ 1 │
│ *,/ │ 2 │
│ пустой стек │ 0 │
└─────────────┴──────────┘
Шаг 1. Если во входной строке нет литер, то перейти к ша-
гу 6; иначе прочитать следующий элемент (скобку, операцию или
операнд) и обозначить его через x.
Шаг 2. Если x - операнд, то перенести его в выходную
строку, поместить вслед за ним разделитель и вернуться у шагу
1.
Шаг 3. Если x - открывающая скобка, то поместить ее в
стек и вернуться к шагу 1. Если x - закрывающая скобка, то пе-
рейти к шагу 4; иначе перейти к шагу 5.
Шаг 4. Если элемент, находящийся на вершине стека, не яв-
ляется открывающей скобкой, то перенести его из стека в выход-
ную строку, поместить за ним разделитель, а затем повторить
шаг 4. Если на вершине стека находится открывающая скобка,
удалить ее из стека и вернуться к шагу 1.
Шаг 5. Если приоритет элемента на вершине стека не меньше
приоритета x, то перенести этот элемент из стека в выходную
строку, поместить за ним разделитель, а затем повторить шаг 5.
Иначе поместить x на вершину стека и вернуться к шагу 1.
Шаг 6. Освободить стек, удаляя каждый раз по одному эле-
менту и помещая его в выходную строку с последующим разделите-
лем. Закончить работу.
Пример:
Этот алгоритм переводит выражение '(3+5*2)/3-1' в
'3 5 2 * + 3 / 1 -'.
Если в ходе построения обратной польской записи не пере-
носить знак операции в выходную строку (где он бы стоял не-
посредственно за теми операндами, над которыми должна выпол-
няться эта операция), а взять из выходной строки два последних
операнда, выполнить над ними операцию, и результат поместить
снова в выходную строку, то у нас после шага 6 в выходной
строке окажется искомый результат.
Рассмотрим вычисления на примере выражения (3+5*2)/3-1
Очередной элемент После обработки элемента
входной строки ──────────────────────────────────
стек выходная строка
( ( пустая
3 ( 3
+ ( + 3
5 ( + 3 5
* ( + * 3 5
2 ( + * 3 5 2
) пуст Вместо переноса знака * в
выходную строку, мы выпол-
няем умножение над двумя
последними элементами выходной строки, при этом 5 и 2 из нее
извлекаются, а результат умножения 10 - помещается в выходную
строку. Она принимает вид: 3 10.
Далее мы должны были бы перенести знак + из стека в вы-
ходную строку, но вместо этого опять же выполняем сложение над
двумя последними элементами и результат помещаем в выходную
строку, так что она становится следующей:
13
/ / 13
3 / 13 3
- - Выполняем деление 13 на 3,
Результат в выходную строку
4
1 - 4 1
входная строка пуст В выходную строку помещаем
пустая результат 4-1=3. Это и есть
значение выражения.
Естественно в место выходной строки использовать стек
чисел. Операции проводятся над двумя верхними элементами сте-
ка. Результат снова помещается в стек.
Задача 17.
Так как могут быть потребованы подписи лишь непосредственных
подчиненных, то для любого разумного способа получения лицензии
подпись всех подписавших чиновников, кроме первого, используются в
одном и только одном наборе. Таким образом, мы можем определить
стоимость подписи любого чиновника как минимум по соответствующим
ему набором сумм стоимостей подчиненных и взятии для набора. Таким
образом, мы получаем простой и эффективный рекурсивный алгоритм
определения стоимостей чиновников.
Но у этой задачи есть маленький подводный камень, а именно,
должно быть заведено глобальное множество уже пройденных чиновни-
ков, что исключает повторную обработку этих чиновников. Сложность
алгоритма - линейна по суммарному числу элементов в наборе.