Стеком будем называть последовательность элементов, упорядоченных по времени их поступления. Эта последовательность доступна только с одного конца (вершины стека). Для работы со стеком необходим указатель вершины стека. Основные операции над стеком следующие:
"запомнить в стеке" и "извлечь из стека" (причем извлекается последний из занесенных в стек элементов - то есть элемент с вершины стека). Поэтому говорят, что стек -- это структура типа 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.
Задана полоска длиной 2k клеток и шириной в одну клетку. Полоску сгибают пополам так, чтобы правая половинка оказалась под левой. Сгибание продолжают до тех пор, пока сверху находится больше одной клетки. Необходимо пронумеровать клетки таким образом, чтобы после окончания сгибания полосы номера клеток в получившейся колонке были расположены в порядке 1,2,3,4,...,2k.
Задача 3.1.
"Полоска". Прохоров В.В.
Расположенную вертикально прямоугольную бумажную ленточку с закрепленным нижним концом стали складывать следующим образом:
- на первом шаге ее согнули пополам так, что верхняя половина легла на нижнюю либо спереди (П - сгибание) либо сзади (З сгибание),
- на последующих n-1 шагах выполняли аналогичное действие с получающейся на предыдущем шаге согнутой ленточкой, как с единым целым.
Затем ленточку развернули , приведя ее в исходное состояние. На ней остались сгибы - ребра от перегибов, причем некоторые из ребер оказались направленными выпуклостью к нам (К - ребра), а некоторые - от нас (О -ребра). Ребра пронумеровали сверху вниз числами от 1 до 2n-1.
А. Составить программу, запрашивающую:
- строку символов из прописных букв "П" и "З", определяющую последовательность типов сгибаний, - номер ребра, и сообщающую тип этого ребра, получившийся после заданной последовательности сгибаний.
Б. Составить программу, запрашивающую строку символов из прописных букв "О" и "К", где нахождение на i-том месте символа "О" или "К" определяет тип ребра на расправленной полоске, и выдающую строку из прописных "П" и "З", определяющих последовательность типов сгибаний, посредством которых получена ленточка с исходной последовательностью ребер. Если такой строки не существует, сообщить об этом.
Задача 4.
Квадрат разбит на 4k равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной (правая половина подкладывается под левую) и горизонтальной (нижняя половина подкладывается под верхнюю) оси симметрии до тех пор, пока все клетки не будут расположены друг под другом. Требуется занумеровать клетки исходного квадрата таким образом, чтобы в результате выполнения операций перегиба номера клеток, расположенных друг под другом, образовали числовую последовательность 1,2,3,...,4k, начиная с верхней клетки.
Задача 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) Тело опускается полностью в воду, затем поднимается;
Пример:
После подъема вода останется только во внутреннем углублении, над элементом А(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.
