СТРУКТУРЫ ДАННЫХ. Предварительные сведения. Какие бывают структуры данных? Структура данных 'стек'. Стеком будем называть последовательность элементов, упорядо- ченных по времени их поступления. Эта последовательность доступна только с одного конца (вершины стека). Для работы со стеком необ- ходим указатель вершины стека. Основные операции над стеком следу- ющие: "запомнить в стеке" и "извлечь из стека" (причем извлекается последний из занесенных в стек элементов - то есть элемент с вер- шины стека). Поэтому говорят, что стек -- это структура типа 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.