Лабораторная работа № 1 Списки. Стеки. Очереди.
Задача 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.
--------------------------------------------------------------------------------
Задача 4. Квадрат разбит на 4k равновеликих квадратных клеток. Квадрат перегибается поочередно относительно вертикальной (правая половина подкладывается под левую) и горизонтальной (нижняя половина подкладывается под верхнюю) оси симметрии до тех пор, пока все клетки не будут расположены друг под другом. Требуется занумеровать клетки исходного квадрата таким образом, чтобы в результате выполнения операций перегиба номера клеток, расположенных друг под другом, образовали числовую последовательность 1,2,3,...,4k, начиная с верхней клетки.
--------------------------------------------------------------------------------
Задача 5. Дана конечная последовательность, состоящая из левых и правых скобок pазличных заданных типов( «(» «{» «[»«)» «}» «]»). Определить, можно ли добавить в нее цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.
--------------------------------------------------------------------------------
Задача 6. В таблице А размера N за один просмотр необходимо каждый элемент заменить на ближайший следующий за ним элемент, который больше его. Если такого элемента нет, то заменить его на ноль.
ПРИМЕР А=1 3 2 5 3 4
ОТВЕТ А=3 5 5 0 4 0
--------------------------------------------------------------------------------
Задача 7. Одинокий король долго ходил по бесконечной шахматной доске. Известна последовательность из N его ходов (вверх, вниз, влево, вправо, вверх-влево и т.п.).Написать программу, определяющую побывал ли король дважды на одном и том же поле за минимально возможное при заданном N число вычислений.
--------------------------------------------------------------------------------
Задача 8 По кругу расположено N монет гербами вверх и M монет гербами вниз. Обходя круг по ходу часовой стрелки, переворачивает каждую S -тую монету. В первый раз счет начинается с герба. В каком порядке надо расставить монеты, чтобы после K ходов стало L монет, лежащих гербами вверх.
--------------------------------------------------------------------------------
Задача 9.
N серых и M белых мышей сидят по кругу. Кошка ходит по кругу по часовой стрелке и съедает каждую S -тую мышку. В первый раз счет начинается с серой мышки. Составить алгоритм определяющий порядок в котором сидели мышки, если через некоторое время осталось K серых и L белых мышей.
--------------------------------------------------------------------------------
Задача 10.
Из листа клетчатой бумаги размером М*N клеток удалили некоторые клетки. На сколько кусков распадется оставшаяся часть листа?
Пример. Если из шахматной доски удалить все клетки одного цвета, то оставшаяся часть распадется на 32 куска.
--------------------------------------------------------------------------------
Задача 11.
Имеется n черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая под низ стопки, третья- на стол, четвертая - под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.
--------------------------------------------------------------------------------
Задача 12.
Есть министерство из N чиновников, где N натуральное число. У каждого из чиновников могут быть как подчиненные, так и начальники, причем справедливы правила: подчиненные моего подчиненного мои подчиненные, начальники моего начальника - мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника.
Для того чтобы получить лицензию на вывоз меди необходимо получить подпись 1-ого чиновника - начальника всех чиновников. Проблема осложняется тем, что каждый чиновник, вообще говоря, может потребовать "визы", т.е. подписи некоторых своих непосредственных подчиненных и взятку - известное количество долларов. Для каждого чиновника известен непустой список возможных наборов "виз" и соответствующая каждому набору взятка. Пустой набор означает, что данный чиновник не требует виз в данном случае. Чиновник ставит свою подпись лишь после того, как ему представлены все подписи одного из наборов "виз" и уплачена соответствующая взятка.
Необходимо определить и вывести минимальный по сумме уплаченных взяток допустимый порядок получения подписей для лицензии и стоимость.
N<100. Количество наборов для каждого чиновника не превосходит 15.
--------------------------------------------------------------------------------
Задача 13.. Объединить n списков в один список
-----------------------------------------------------------------------------------------------------------------
Задача 14. Поменять местами два элемента в списке
-----------------------------------------------------------------------------------------------------------------
Задача 15. Добавить новый элемент в список перед заданным элементом
-----------------------------------------------------------------------------------------------------------------
Задача 16. Удалить из списка неупорядоченные подсписки
-----------------------------------------------------------------------------------------------------------------
Задача 17. Сделать определённый элемент в списке первым
-----------------------------------------------------------------------------------------------------------------
Задача 18. Реализовать удаление элементов из очереди с приоритетом. Очередь с приоритетом – первым включается – с высшим приоритетом исключается
-----------------------------------------------------------------------------------------------------------------
Задача 19. Реализовать функции работы со стеком (удаление, вставка).
--------------------------------------------------------------------------------
Задача 20.
1. Дана величина a строкового типа из четного количества символов. Получить и напечатать величину b, состоящую из символов первой половины величины a, записанных в обратном порядке, после которых идут символы второй половины величины a, также записанные в обратном порядке. Например, при а = “привет” b должно быть равно “ипртев”.
--------------------------------------------------------------------------------
Задача 21.
Написать процедуру, которая меняла бы в односвязном списке крайние элементы.
--------------------------------------------------------------------------------
Задача22.
Даны четыре стека. Два первых стека пустые, а в двух других находятся натуральные числа. В первый пустой стек поместить четные числа в порядке не убывания, взятые из непустых стеков, во второй пустой стек поместить нечетные числа в порядке не возрастания, так же взятые их непустых стеков. Предполагается, что множества четных чисел и нечетных чисел непустые.
--------------------------------------------------------------------------------
Задача 23.
Используя список, удалить из текста программы комментарии и поместить их в отдельных текстовый файл.
--------------------------------------------------------------------------------
Задача 24.
Дан список вещественных чисел. Все его элементы, не равные нулю, переписать, сохраняя порядок, в начало списка, а нулевые элементы в конец списка. Новый список заводить нельзя.
--------------------------------------------------------------------------------
Задача 25.
Используя очередь, отредактировать текст, оставляя один пробел в каждой серии пробелов.
--------------------------------------------------------------------------------
Задача 26.
Используя список, удалить их текста заданный набор букв.
-----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
Задача**.
Система состоит из двух процессоров P1 и P2, двух стеков S1 и S2 и четырёх очередей F1, F2, F3, F4. В систему могут поступать запросы на выполнение задач двух приоритетов - высший (1) и низший (2). Задачи сначала обрабатываются последовательно процессором P1, затем P2.
Запросы на выполнение задач высшего приоритета, поступающие из генератора задач, ставятся в очередь F1, а поступающие с процессора P1 - в очередь F3. Запросы на выполнение задач низшего приоритета, поступающие с генератора задач, ставятся в очередь F2, а поступающие с процессора P1 - в очередь F4. Процессор P1 обрабатывает запросы из очередей F1 и F2, а процессор P2 - из очередей F3 и F4. Процессор сначала обрабатывает задачи из очереди задач с высшим приоритетом, затем из очереди задач с низшим приоритетом. Если процессор выполняет задачу с низшим приоритетом и приходит запрос на выполнение задачи с высшим приоритетом, то выполняемая задача помещается в соответствующий процессору стек, а пришедшая задача - в процессор. Задача из стека возвращается в процессор, если все задачи большего приоритета обработаны.
--------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------
-----------------------------------------------------------------------------------------------------------------