Очереди

Приступая к решению задач этого раздела, следует вспомнить, что:

• Для работы с очередью, т. е. последовательностью элементов, в которую элементы всегда добавляются в конец, а удаляются из начала («первым пришел — первым ушел»), нужны обычно следующие операции:

— создать пустую очередь Q (очистить очередь);

— проверить, является ли очередь Q пустой;

— добавить в конец очереди Q элемент х;

— удалить из очереди Q первый эле­мент, присвоив его параметру х.

ЗАДАЧИ

Создать модуль, содержащий: описания полей и элементов, необходимых для построения очереди, основные функции и процедуры по работе с очередью (добавление и удаление элемента, поиск элемента по ключу и вывод). Решить задачу:

1. Разработать программу для определения суммы элементов очереди, заполняя её:

1. Степенями числа 2 (2, 4, 8, 16, 32, …);

2. Определяются как , где n=1, 2, 3, 4, …, 20.

2. Лыжные гонки проводятся отдельно для двух групп участников (в каждой группе не более 15 человек). Результаты соревнований заданы в виде фамилий участников и их результатов в каждой группе. Объединить результаты в обеих группах, упорядочить их в порядке занятых мест и вывести в виде таблицы с заголовком.

3. Для формирования сборной по хоккею предварительно отобрано 30 игроков. На основании протоколов игр (не более16) составлена таблица, в которой содержится штрафное время каждого игрока по каждой игре (2, 5 или 10 мин). Написать программу, которая составляет список кандидатов в сборную в порядке возрастания суммарного штрафного времени. Игрок, оштрафованный на 10 мин, из списка кандидатов исключается.

4. Составить программу для обработки результатов кросса на 500 м для женщин. В кроссе участвует не более 100 студенток. В протоколе указывается фамилия, шифр группы, результат. Получить итоговую таблицу в порядке занятых мест. Определить количество участниц, выполнивших заданный норматив.

5. Результаты соревнований фигуристов представлены оценками судей по 6-ти бальной шкале. Места участников определяются по сумме баллов. Вывести итоговую таблицу в порядке занятых мест. Участников – 15 человек, судейская бригада – 7 человек.

6. Студенты одной группы (не более 25 человек) в сессию сдают четыре экзамена. Составить список студентов, средний балл которых по всем экзаменам не менее 4. Результаты вывести в виде таблицы с заголовком в порядке убывания среднего балла.

7. Результаты экзаменационной сессии заданы в виде списка фамилий студентов и оценок (четыре оценки). Составить список студентов, не имеющих оценок ниже ″4″, и определить их средний балл. Вывести таблицу с заголовком (фамилия и средний балл) в порядке убывания среднего балла.

8. Составить программу по обработке информации о телевизорах: фирма-изготовитель, размер экрана в дюймах, стоимость в тыс. руб. В программе предусмотреть вывод на экран информации о телевизорах, стоимость которых менее указанного значения.

9. Используя очередь, решить следующую задачу (решение описать в виде процедуры).

a) type FR = fi1e of real;

За один просмотр файла f типа FR и без использования дополнительных файлов напечатать элементы файла f в следующем порядке: сначала — все числа, меньшие 0, затем — все числа из отрезка [a, b], и наконец — все осталь­ные числа, сохраняя исходный взаимный порядок в каж­дой из этих трех групп чисел (а и b—заданные числа, а<b).

б) Содержимое текстового файла f, разделенное на стро­ки, переписать в текстовый файл g, перенося при этом в конец каждой строки все входящие в нее цифры (с со­хранением исходного взаимного порядка как среди цифр, так и среди остальных литер строки).

в) type имя = (Анна, ..., Яков);

дети = array [имя, имя] of boolean;

потомки = file of имя;

Считая заданными имя И и массив Д типа дети (Д[х,у]=1, если человек по имени у является ребенком человека по имени х), записать в файл П типа потомки имена всех потомков человека с именем И в следующем порядке: сна­чала — имена всех его детей, затем — всех его внуков затем — всех правнуков и т. д.

СТЕКИ

Приступая к решению задач этого раздела, следует вспомнить, что:

• Для работы со стеком, т. е. последовательностью элементов, в которой элементы всегда добавляются в конец и удаляются из конца («последним пришел — первым ушел») нужны обычно следующие операции:

—создать пустой стек S (очистить стек);

—проверить, является ли стек S пустым;

—добавить в конец стека S элемент х;

—удалить из очереди S последний эле­мент, присвоив его параметру х.

ЗАДАЧИ

Создать модуль, содержащий: описания полей и элементов, необходимых для построения стека, основные функции и процедуры по работе со стеком (добавление и удаление элемента, поиск элемента по ключу и вывод). Решить задачу:

1. Разработать программу для определения суммы элементов стека, заполняя его:

1. Числами Фибоначчи (1, 1, 2, 3, 5, 8, 13, 21, …);

2. Простыми числами (2, 3, 5, 7, 11, 13, 17, …);

2. Результаты соревнований по прыжкам в длину определяются по сумме двух попыток. В протоколе для каждого участника указываются: фамилия, общество, результат первой и второй попытки. Вывести протокол в виде таблицы с заголовком в порядке занятых мест.

3. Составить программу для обработки результатов лыжной гонки. Для каждого участника вводится фамилия, время старта (часы, минуты, секунды), время финиша. Вывести на экран фамилии участников выполнивших заданный норматив.

4. По каждому студенту хранятся следующие анкетные данные: фамилия студента, пол (одна буква М или Ж), год рождения. Вывести на экран список студентов определенного пола с указанием возраста. В конце списка вывести средний возраст.

5. По каждому владельцу автомобиля хранится следующая информация: фамилия, марка, цвет, гос. номер. Вывести на экран список владельцев автомобилей указанной марки и цвета.

6. Составить программу по обработке информации о поездах, отправляющихся с Курского вокзала г. Москвы: номер поезда, станция назначения, время отправления, время в пути. Вывести на экран список поездов до указанной станции, отправляющихся в указанный промежуток времени.

7. Составить программу по обработке информации о торговых точках вблизи вашего дома: название фирмы, ассортимент товаров (продукты питания, одежда, обувь, электроника, хозтовары, культтовары), адрес. Вывести на экран информацию о магазинах, торгующих одинаковыми товарами.

8. Обработать результаты первенства по футболу (участвуют 14 команд). Результаты каждой игры заданы в виде названий команд и счета игры. Сформировать таблицу очков (выигрыш – 2, ничья – 1, проигрыш - 0) и вывести результаты (место, название команды, количество очков) в порядке занятых мест. В случае равенства очков сравниваются разности забитых и пропущенных мячей.

9. Используя стек, решить сле­дующую задачу (решение описать в виде процедуры или функции): напечатать содержимое текстового файла t, выпи­сывая слова каждой его строки в обратном порядке.

10. Описать функцию value (postfix), которая вычисляет как целое число значение выражения (без переменных), записанного в текстовой форме в текстовом файле postfix. Использовать следующий алгоритм вычисления. Выра­жение просматривается слева направо. Если встречается число, то его значение (как целое) заносится в стек, а если встречается знак операции, то из стека извлекаются два последних элемента (это операнды данной операции), над ними выполняется операция, и ее резуль­тат записывается в стек. В конце концов, в стеке оста­нется только одно число — значение всего выражения.

Математические функции

Функция	Назначение функции
Abs(x)	Возвращает абсолютное значение аргумента x
Arctan(x)	Возвращает арктангенс аргумента x
Cos(x)	Возвращает косинус аргумента x
Sin(x)	Возвращает синус аргумента x
Exp(x)	Возвращает экспоненту аргумента x
Ln(x)	Возвращает натуральный логарифм x
Sqr(x)	Возвращает квадрат аргумента x
Sqrt(x)	Возвращает квадратный корень аргумента x
Pi	Возвращает значение числа Пи
Random(x) Randomize	Возвращает случайное число из интервала [0;x] Инициализирует программный генератор случайных чисел.

Процедуры и функции преобразования

Процедура функция	Назначение
Dec(x,n)	Уменьшает на n значение переменной x
Inc	Увеличивает на n значение переменной x
Odd(x)	Проверяет, является ли аргумент x четным числом
Chr(n)	Возвращает символ по его n коду ASCII
Ord(x)	Возвращает ASCII код символа x
Round(x)	Округляет значение x вещественного типа
Trunc(x)	Возвращает целую часть вещественного числа x
Frac(x)	Возвращает дробную часть аргумента x
Int(x)	Возвращает целую часть аргумента x
High(x)	Возвращает старшее значение в диапазоне аргумента x. Возвращаемое значение зависит от типа аргумента.
Low(x)	Возвращает младшее значение в диапазоне аргумента x. Возвращаемое значение зависит от типа аргумента.