Типизированные и нетипизированные файлы
1. Дана строка S. Если S является допустимым именем файла, то вывести True и создать файл с этим именем. Если файл с именем S создать нельзя, то вывести False.
2. Даны имена четырех файлов. Вывести количество файлов с указанными именами, которые имеются в текущем каталоге.
3. Дано имя файла целых чисел. Вывести количество его элементов. Если файла с таким именем не существует, то вывести –1.
4. Дано число k и файл, содержащий ненулевые целые числа. Вывести элемент файла с номером k (элементы файла нумеруются от нуля). Если такой элемент отсутствует, то вывести 0.
5. Дан файл целых чисел, содержащий не менее четырех элементов. Вывести его нулевой, первый, предпоследний и последний элементы.
6. Даны имена двух файлов вещественных чисел. Известно, что один из них существует и содержит не менее двух элементов, а другой в текущем каталоге отсутствует. Создать отсутствующий файл и записать в него нулевой и последний элементы существующего файла.
7. Дан файл целых чисел. Вывести количество содержащихся в нем серий (то есть наборов последовательно расположенных одинаковых элементов).
8. Дан файл вещественных чисел. Найти количество его локальных минимумов1|максимумов2|экстремумов3.
9. Дан файл вещественных чисел. Найти количество его участков убывания1|возрастания2|монотонности3.
10. Даны два файла произвольного типа. С помощью процедуры Rename поменять местами их содержимое.
11. Дан файл произвольного типа. С помощью процедур BlockRead и BlockWrite создать его копию с новым именем.
12. Дано целое число N (< 5) и N файлов одного и того же типа с именами Name1, ..., Name5. С помощью процедур BlockRead и BlockWrite объединить содержимое этих файлов (в указанном порядке) в новом файле с именем Name0.
13. Даны два файла одного и того же типа. С помощью процедур BlockRead и BlockWrite добавить к первому файлу содержимое второго файла, а ко второму файлу — содержимое первого.
14. Даны три файла одного и того же типа, но разного размера. С помощью процедур BlockRead и BlockWrite заменить содержимое самого длинного1|короткого2 файла на содержимое самого короткого1|длинного2.
15. Дан файл целых чисел. Создать новый файл, содержащий те же элементы, что и исходный файл, но в обратном порядке.
16. Даны три файла целых чисел одинакового размера с именами NameA, NameB и NameC. Создать новый файл с именем NameD, в котором чередовались бы элементы исходных файлов с одним и тем же номером: A0, B0, C0, A1, B1, C1, A2, B2, C2, ... .
17. Даны четыре файла целых чисел разного размера с именами NameA, NameB, NameC и NameD. Создать новый файл с именем NameE, в котором чередовались бы элементы исходных файлов с одним и тем же номером (как в задании 16). "Лишние" элементы более длинных файлов в результирующий файл не записывать.
18. Дан файл вещественных чисел с именем Name1. Создать два новых файла с именами Name2 и Name3, первый из которых содержит элементы исходного файла с четными номерами (0, 2, 4, ...), а второй — с нечетными (1, 3, 5, ...).
19. Дан файл, содержащий ненулевые целые числа. Создать новый файл, содержащий только положительные1|отрицательные2|четные3|нечетные4 числа исходного файла (в том же порядке).
20. Дан файл целых чисел. Создать новый файл, содержащий длины всех серий исходного файла.
21. Дан файл вещественных чисел. Создать файл целых чисел, содержащий длины всех убывающих1|возрастающих2|монотонных3 последовательностей его элементов.
22. Дан файл вещественных чисел. Заменить в нем все элементы на их квадраты.
23. Дан файл вещественных чисел. Заменить в файле каждый элемент, кроме начального и последнего, на его среднее арифметическое с предыдущим и последующим элементом.
24. Дан файл целых чисел с элементами A(i), i = 0, ..., N–1 (N — размер файла). Заменить исходное расположение его элементов на следующее: A(0), A(N–1), A(1), A(N–2), A(2), ... .
25. Дан файл целых чисел. Если его размер меньше 50, то дополнить его нулями до 50 элементов; если его размер больше 50, то урезать его до 50 элементов.
26. Дан файл целых чисел. Удалить в нем все положительные1|отрицательные2|четные3|нечетные4 числа.
27. Дан файл целых чисел. Продублировать в нем все числа, принадлежащие диапазону 5..10.
28. Дан файл, содержащий ненулевые целые числа. Заменить в нем все положительные1|отрицательные2|четные3|нечетные4 числа двумя нулями.
29. Дан файл вещественных чисел. Поменять в нем местами минимальный и максимальный элементы.
30. Даны два файла вещественных чисел с именами Name1 и Name2, элементы которых упорядочены по возрастанию1|убыванию2. Объединить эти файлы в новый файл с именем Name3, сохранив упорядоченность элементов.
31. Даны два целых числа i и j и файл вещественных чисел, содержащий элементы квадратной матрицы (по строкам). Вывести элемент матрицы, расположенный в i-й строке и j-м столбце (строки и столбцы нумеруются от 1). Если требуемый элемент отсутствует, то вывести 0.
32. Даны два целых числа i и j и файл вещественных чисел, содержащий элементы прямоугольной матрицы (по строкам), причем начальный элемент файла содержит количество столбцов матрицы. Вывести элемент матрицы, расположенный в i-й строке и j-м столбце (строки и столбцы нумеруются от 1). Если требуемый элемент отсутствует, то вывести 0.
33. Дан файл вещественных чисел, содержащий элементы квадратной матрицы (по строкам). Создать файл, содержащий элементы матрицы, транспонированной к исходной.
34. Дан файл вещественных чисел, содержащий элементы прямоугольной матрицы (по строкам), причем начальный элемент файла содержит количество столбцов матрицы. Создать новый файл той же структуры, содержащий матрицу, транспонированную к исходной.
35. Даны два файла вещественных чисел с именами NameA и NameB, содержащие элементы квадратных матриц A и B (по строкам). Создать новый файл с именем NameC, содержащий элементы произведения A·B. Если матрицы A и B нельзя перемножать, то оставить файл NameC пустым.
36. Даны два файла вещественных чисел с именами NameA и NameB, содержащие элементы прямоугольных матриц A и B (по строкам), причем начальный элемент каждого файла содержит количество столбцов соответствующей матрицы. Создать файл той же структуры с именем NameC, содержащий произведение A·B. Если матрицы A и B нельзя перемножать, то оставить файл NameC пустым.
37. Дан файл вещественных чисел, содержащий элементы [верхней треугольной]1|[нижней треугольной]2|трехдиагональной3 матрицы (по строкам). Создать новый файл, содержащий элементы ненулевой части данной матрицы (по строкам).
38. Даны два целых числа i и j и файл вещественных чисел, содержащий ненулевую часть [верхней треугольной]1|[нижней треугольной]2|трехдиагональной3 матрицы (по строкам). Вывести порядок матрицы и ее элемент, расположенный в i-й строке и j-м столбце (строки и столбцы нумеруются от 1). Если требуемый элемент находится в нулевой части матрицы, то вывести 0; если элемент отсутствует, то вывести –1.
39. Дан файл вещественных чисел, содержащий ненулевую часть [верхней треугольной]1|[нижней треугольной]2|трехдиагональной3 матрицы (по строкам). Создать новый файл, содержащий все элементы данной матрицы (по строкам).
40. Даны два файла вещественных чисел с именами NameA и NameB, содержащие ненулевые части [верхних треугольных]1|[нижних треугольных]2 матриц A и B (по строкам). Создать новый файл с именем NameC, содержащий ненулевую часть произведения A·B исходных матриц (по строкам). Если матрицы A и B нельзя перемножать, то оставить файл NameC пустым.
41. Дано целое число N (< 5) и N файлов целых чисел разного размера с именами Name1,..., Name. Объединить их содержимое в новом файле целых чисел с именем Name0, используя следующий формат: в начальном элементе файла Name0 хранится число N, в следующих N элементах хранятся размеры исходных файлов, а затем последовательно размещаются данные из каждого исходного файла.
42. Дан файл целых чисел, содержащий данные из нескольких (не более четырех) файлов в формате, описанном в задании 41. Восстановить файлы, использованные при создании исходного файла, присвоив им имена вида «<n>.tst», где <n> — порядковый номер файла (n = 1, 2, ...).
43. Дан символьный файл, содержащий по крайней мере один символ пробела. Удалить все его элементы, расположенные после первого1|последнего2 символа пробела, включая и сам этот пробел.
44. Дан символьный файл, содержащий по крайней мере один символ пробела. Удалить все его элементы, расположенные перед первым1|последним2 символом пробела, включая и сам этот пробел.
45. Дан символьный файл. Упорядочить его элементы по возрастанию1|убыванию2 их кодов.
46. Дано число k и строковый файл с именем Name1, содержащий непустые строки. Создать два новых файла: строковый с именем Name2, содержащий первые1|последние2 k символов каждой строки исходного файла (если строка короче k символов, то она сохраняется целиком), и символьный с именем Name3, содержащий k-й символ каждой строки (если строка короче k, то в файл Name3 записывается пробел).
47. Дан строковый файл, содержащий непустые строки. Создать новый файл, содержащий все строки исходного файла наименьшей1|наибольшей2 длины (в том же порядке).
48. Дан строковый файл с именем NameS, содержащий даты в формате "день/месяц/год", причем под день и месяц отводится по две позиции, а под год — четыре. Создать файлы целых чисел с именами Name1 и Name2, содержащие соответственно значения [дней и месяцев]1|[дней и лет]2|[месяцев и лет]3 для дат из исходного строкового файла (в том же порядке).
49. Дан строковый файл, содержащий даты в формате "день/месяц/год", причем под день и месяц отводится по две позиции, а под год — четыре. Вывести строку, содержащую самую раннюю1|позднюю2 весеннюю3|летнюю4|осеннюю5|зимнюю6 дату. Если даты с требуемым временем года в файле отсутствуют, то вывести дату "01/01/1900".
50. Дан строковый файл, содержащий даты в формате "день/месяц/год", причем под день и месяц отводится по две позиции, а под год — четыре. Создать новый строковый файл, в котором даты из исходного файла располагались бы в порядке возрастания1|убывания2.
Студент
В задачах 1..15 использовать типизированный файл c информацией о студентах факультета Stud.dat со структурой:
const NumSemestr=10;
type
TStud=record
FIO : string[80]; // фамилия имя отчество
Year : TDateTime; // дата рождения
// средние оценки за семестр
MedB : array [1..NumSemestr] of real;
Kurs : byte; // курс
Group: byte; // группа
End;
1. Убедиться в отсутствии задолженностей для выбранного студента-выпускника (наличие положительных оценок за все десять семестров).
2. Вывести список студентов, для которых дни рождения попадают на дни текущей недели.
3. Вывести список студентов, у которых средний балл постоянно увеличивается от семестра к семестру.
4. Вывести список студентов, у которых средний балл постоянно уменьшается за всё время обучения.
5. Вывести информацию о самых молодых студентах с указанием возраста — N человек, начиная с самого молодого, N определяется вводом.
6. Вывести информацию о средних баллах по курсам.
7. Вывести информацию об однофамильцах.
8. Организовать поиск студентов по ФИО, курсу, группе, году рождения.
9. Определить группы студентов, у которых средний балл ниже факультетского среднего.
10. Вывести информацию о студентах, которые стали учиться хуже, чем на 1-ом курсе.
11. Упорядочить список студентов заданной группы по среднему баллу, вывести его.
12. Вывести список студентов, у которых средний балл больше 40.
13. Вывести студента с наибольшим средним баллом на каждом курсе.
14. Вывести студента с наименьшим средним баллом на каждом курсе.
15. Составить список 5 студентов с максимальным средним баллом.
Рекурсия
1. Описать рекурсивную функцию для подсчёта количества запятых в данном текстовом файле.
2. Описать рекурсивную функцию
function step(z : real; m:byte):real;
для вычисления zm (z — вещественное, m — натуральное) и с её помощью подсчитать значение выражения a7 + b8 .
3. Описать рекурсивную функцию
function fib(n : integer) : integer;
для вычисления n-ого (n £ 40) числа Фибоначчи.
Указание.
Последовательность чисел Фибоначчи fk образуется так:
f0=1, f1=1, fk = fk-2 + fk-1.
4. Описать рекурсивную функцию
function arifm(a, d, k : integer) : integer;
для вычисления k-ого элемента арифметической прогрессии
(a — первый элемент прогрессии, d — разность прогрессии).
5. Создать очередь из чисел, записанных в текстовом файле, с помощью рекурсивной процедуры procedure add(var r : link).
6. Описать рекурсивную функцию
function memb(r:link; b:integer): boolean;
проверяющую, входит ли элемент с информационным полем b в список r.
7. Описать рекурсивную процедуру
procedure dele(var r:link; w:integer);
удаляющую из списка r первое вхождение элемента с информационным полем w.
8. Используя функцию memb, проверить, входит ли число, введённое в поле Edit1, в созданный список. Если да, то удалить из списка первое вхождение этого числа с помощью процедуры dele и вывести преобразованный список в текстовый файл с помощью процедуры out. В противном случае вывести сообщение: «Такого элемента нет».
9. Создать очередь с помощью рекурсивной процедуры
procedure add(var r: link).
10. Описать рекурсивную функцию
function neg(r: link): boolean;
проверяющую, имеется ли в списке элемент с отрицательным информационным полем.
11. Описать рекурсивную функцию
function nmemb(r: link; b:integer):integer;
подсчитывающую количество вхождений элемента с информационным полем b в список r.
12. Описать рекурсивную функцию
function max(r: link): integer;
для нахождения максимума в списке r.
13. Написать рекурсивную функцию для нахождения биномиальных коэффициентов
14. Для заданного М вычислить все 
15. Задано конечное множество имен жителей некоторого города, причем для каждого из жителей перечислены имена его детей. Жители А и Б называются родственниками, если:
либо А — ребенок Б,
либо Б — ребенок А,
либо существует некий В такой, что А является родственником В, а В является родственником Б. Перечислить все пары жителей города, которые являются родственниками.
16. Подсчитать количество различных представлений заданного натурального N в виде суммы не менее двух попарно различных положительных слагаемых. Представления, отличающиеся порядком слагаемых, различными не считаются.
17. Вычислить определитель заданной матрицы, пользуясь формулой разложения по первой строке:
где матрица B получается вычеркиванием из А первой строки и k-го столбца.
18. Построить синтаксический анализатор для понятия простое_выражение,
простое выражение ::= простой_ идентификатор | (простое_выражение знак_операции простое_выражение);
простой идентификатор: := буква;
знак_операци::= + | – | *;
19. Написать процедуру, которая по заданному простому логическому выражению вычисляет его значение.
логическое выражение.:= TRUE | FALSE | NOT логическое_выражение |
(логическое_выражение знак_операции логическое_выражение);
знак_операщш::= AND | OR;
20. Расставить на шахматной доске 8 ферзей таким образом, чтобы ни один не угрожал другому.
21. Получить расстановки 8 ладей на шахматной доске, при которых ни одна ладья не угрожает другой.
22. Получить все перестановки элементов 1,..., 6.
23. Получить все размещения из 10 элементов 1, 2,..., 10 по 3 в каждом. Размещением называется выборка из п указанных элементов т неповторяющихся элементов.
24. На шахматной доске определигь поля, в которые может попасть конь за п ходов из указанной позиции.
25. Имеются n городов. Некоторые из них соединены дорогами известной длины.
· Найти кратчайшие маршруты из заданного города в остальные.
· Найти кратчайший маршрут, начинающийся в заданном городе и проходящий через все остальные.
26. Найти расстановку 5 ферзей, при которой каждое поле шахматной доски будет находиться под ударом хотя бы одного из них.
27. «Задача о рюкзаке». Имеется М различных предметов, известны вес каждого предмета и его стоимость. Определить, какие предметы надо положить в рюкзак, чтобы общий вес не превышал заданной границы, а общая стоимость была максимальной.
28. Даны целое п от 2 до 20 и вещественное Е>0. Найти с точностью Е все корни n-го многочлена Чебышева Тп(х), определяемого формулами Т0 (х) = 1; Т1 (х) = х; Тk (х) = 2хTk-1 (х) - Тк-2 (х), (к = 2,3,...).
29. Найти расстановку 5 ферзей, при которой каждое поле шахматной доски будет находиться под ударом хотя бы одного из них.
30. Покрыть все клетки шахматной доски ходом коня, начальное положение коня на поле с координатами x0, y0
31. Задана система двусторонних дорог. Найти замкнутый путь, проходящий через каждую вершину и длиной не более 100 км.
32. Прямоугольная матрица содержит ячейки двух типов — "белые" и "черные". Написать процедуру, находящую хотя бы один путь от первой строки матрицы до последней по "белым" ячейкам. Переход возможен только в соседнюю ячейку: левую, правую, верхнюю, нижнюю, то есть при изменении только одного индекса.
Списки, стеки, очереди
1. Реализовать функцию поиска элемента Е в односвязном списке L.
2. Подсчитать число максимальных элементов списка.
3. В списке A хранится информация о людях (фамилия, имя, отчество, профессия). Имеется список В, содержащий перечень профессий. Удалить из списка А тех людей, чья профессия не указана в списке В.
4. Дан список слов. Из каждой группы подряд идущих одинаковых слов оставить только одно.
5. Дан текстовый файл. Распечатать слова, имеющие максимальную длину.
6. Дан список вещественных чисел. Проверить, упорядочены ли числа по возрастанию или по убыванию.
7. Дан список вещественных чисел. Для каждого элемента списка напечатать число отрицательных элементов, следующих за ним.
8. Реализовать проект "Частотный словарь". В качестве обрабатываемого текста можно использовать, например, модули этого проекта. Результатом должно явиться перечисление всех "слов" в алфавитном порядке с частотой их появления. Отметить, что частота появления таких слов, как begin и end, всегда одинакова.
9. Создать приложение, проверяющее правильность расстановки скобок в арифметическом выражении.
10. Даны два стека. Используя процедуры ИзСтека, ВСтек и функцию СтекПуст подсчитать общее число элементов в стеках. В качестве вспомогательных структур разрешается использование переменных целых типов. Алгоритм должен предусматривать восстановление исходного расположения элементов в стеках.
11. Дан текстовый файл А. Переписать его содержимое в файл В, перенося при этом в конец каждой строки все входящие в нее знаки препинания.
12. Даны две очереди X и Y, содержащие вещественные числа. Из каждой очереди одновременно извлекается по одному числу, х и у соответственно. Если х < у, то число (х + у) помещается в конец очереди X, иначе число (х–у) помещается в конец очереди Y. Необходимо определить число шагов, через которое одна из очередей станет пустой.
13. Создать очередь, информационные поля которой содержат целые числа из текстового файла. Вставить в список новый элемент с информационным полем d после каждого элемента с четным числом в информационном поле.
14. Создать очередь из 20 элементов, информационные поля которой содержат случайные числа из интервала [–30, 30]. Вставить в список новый элемент с информационным полем 100 за каждым отрицательным числом.
15. Создать очередь, информационные поля которой содержат строки из файла. Удалить из списка элементы, информационные поля которых равны строке S.
16. Создать очередь из 20 элементов, информационные поля которой содержат случайные числа из интервала [–40, 40]. Удалить из списка все отрицательные числа.
17. Создать очередь, информационные поля которой содержат числа из текстового файла. Вставить в конец списка (после последнего элемента) новый элемент с информационным полем d.
18. Создать очередь, информационные поля которой содержат числа из текстового файла. Вставить в начало списка (перед первым элементом) новый элемент с информационным полем d.
19. Создать очередь, информационные поля которой содержат числа из текстового файла. Вставить новый элемент с информационным полем d после 9-ого элемента списка.
20. Создать очередь из 20 элементов, информационные поля которой содержат случайные числа из интервала [–50, 50]. Удалить из списка последний отрицательный элемент.
21. Создать очередь, информационные поля которой содержат числа из текстового файла. Удалить из списка за каждым вхождением элемента с информационным полем, равным d, один элемент, если он отличен от d.
22. Создать очередь, информационные поля которой содержат строки из файла (список фамилий учащихся). Удалить из списка фамилии, начинающиеся с буквы ′ С ′.
23. Создать очередь, информационные поля которой содержат строки из файла (список фамилий учащихся). Удалить из списка первую фамилию, начинающуюся с буквы ′ К ′. (Учесть, что такая фамилия может оказаться первой в списке.)
24. Создать очередь, информационные поля которой содержат строки из файла (список фамилий учащихся, упорядоченный по алфавиту). Вставить в этот список новую фамилию с сохранением порядка.
25. Считалочка. N ребят расположены по кругу. (Каждому присвоен номер по порядку). Начав отсчёт от первого, удаляют каждого k-ого, смыкая при этом круг. Определить номер последнего, оставшегося в круге. (k£N)
Указание:
для решения задачи использовать очередь, в которой ссылочное поле последнего элемента содержит адрес первого элемента..
26. Написать программу, проверяющую правильность расстановки скобок в арифметическом выражении. Скобки могут быть круглыми, квадратными и фигурными.
27. Преобразовать последовательность действительных чисел, записанных в файле, расположив сначала отрицательные числа последовательности, а затем неотрицательные. При этом порядок как отрицательных, так и неотрицательных чисел изменяется на обратный
Указание.
для решения задачи создать два стека: с отрицательными и с неотрицательными числами последовательности.
28. Даны целые числа a1, a2, … an, содержащиеся в текстовом файле. Вычислить значение выражения p1 ×+ 10 + p2 × 100 + p3 × 1000 + … , где p1, p2 , p3 , … — встречающиеся в последовательности положительные числа, взятые в обратном порядке (начиная с последнего встретившегося положительного числа).
Указание
для решения задачи сформировать стек из положительных чисел последовательности.
29. Написать программу для вычисления значения выражения, представленного в обратной польской записи.
30.
| Обычная запись | Обратная польская запись |
| (b + c) * d | b c + d * |
| a + (b + c) * d | a b c + d * + |
| (6 + 8)/2 + 11 | 6 8 + 2 / 11 + |
Указание
просматривая строку, в которой записано выражение, анализируем очередной символ. Если это число, то записываем его в стек. Если это знак операции, то достаём два элемента из стека, выполняем арифметическую операцию, определяемую этим знаком, и заносим результат в стек.
31. Создать очередь, информационные поля которой содержат числа из текстового файла. Вставить в список за каждым отрицательным числом новый элемент с информационным полем, равным модулю данного отрицательного числа.
32. Создать очередь, информационные поля которой содержат числа из текстового файла. Из каждой группы подряд идущих одинаковых чисел оставить только одно.
33. Создать очередь из 20 элементов, информационные поля которой содержат случайные числа из интервала [–50,50]. Удалить из списка все числа, по модулю большие числа 20. Использовать метод фиктивного элемента.
34. Дана последовательность символов, состоящая из английских букв и цифр, записанных в текстовом файле. Используя запись в стек, получить число, составленное из цифр последовательности, записанных в обратном порядке. Полученное число записать в текстовый файл.
35. Дана последовательность символов, состоящая из английских букв и цифр, записанных в текстовом файле. Используя запись в стек, получить текст, составленный из английских букв последовательности, записанных в обратном порядке. Полученный текст записать в текстовый файл.
36. Создать очередь, информационные поля которой содержат числа из текстового файла. Подсчитать число максимальных элементов списка.
37. Создать очередь, информационные поля которой содержат числа из текстового файла. Из каждой группы подряд идущих одинаковых чисел оставить только одно.
38. Создать очередь, информационные поля которой содержат вещественные числа из текстового файла. Проверить, упорядочены ли числа по возрастанию или по убыванию.
39. Создать очередь, информационные поля которой содержат вещественные числа из текстового файла. Для каждого элемента списка определить число отрицательных элементов, следующих за ним. Результаты записать в текстовый файл в виде:
элемент списка — число последующих отрицательных элементов.
40. Создать очередь, информационные поля которой содержат вещественные числа из текстового файла. Проверить, образуют ли числа, хранящиеся в списке, арифметическую или геометрическую прогрессию.
41. Дана последовательность x1, x2,…, xn вещественных чисел, записанных в текстовом файле. Вычислить произведение сумм: 
.
42. Дана последовательность x1, x2,…, xn вещественных чисел, записанных в текстовом файле. Вычислить произведение сумм:
.
43. Дан список слов. Из каждой группы подряд идущих одинаковых слов оставить только одно.
44. Дан текстовый файл. Распечатать слова, имеющие максимальную длину.
Сортировки
1. Написать программу, которая наглядно иллюстрирует работу следующих методов сортировки:
ü пузырьковая;
ü шейкерная.
Провести сравнение этих сортировок по количеству сравнений, по количеству обменов. Для этого построить графики зависимостей данных величин от количества элементов массива.
2. Написать программу, которая наглядно иллюстрирует работу следующих методов сортировки:
ü простыми вставками;
ü бинарными вставками.
Провести сравнение этих сортировок по количеству сравнений, по количеству обменов. Для этого построить графики зависимостей данных величин от количества элементов массива.
3. Примером сортировки по двум ключам может служить список файлов, имеющих одинаковые имена и разные расширения. Список упорядочен по именам, а для каждого имени – по расширениям.
Написать программу, которая сортирует элементы массива по двум ключам. Элементом массива является запись, два поля которой – два ключа
4. В магазине строительных материалов в продаже имеются стеновые панели, которые характеризуются следующими величинами:
ü ширина,
ü длина,
ü количество штук,
ü цена за 1 м2.
Вывести в порядке возрастания цены сведения о тех стеновых панелях, общая площадь которых не менее заданной.
5. Есть некий измерительный прибор, работа которого зависит от входных параметров a и x, а результат определяется следующей формулой у = a sin(ax) cos2 (x/a). Проводится серия опытов для значений xt ,х2,... xn, a = const. Вывести результат в виде таблицы, упорядоченной по убыванию значений показаний прибора, полученных в ходе опытов.
6. В чемпионате России по футболу принимают участие 16 команд. Для каждой команды известен список игроков, каждый игрок из команды имеет свой рейтинг. Вывести список команд в порядке убывания вероятности победы в чемпионате. Рейтинг команды равен сумме рейтингов игроков. Вероятность победы равна рейтингу команды минус сумма рейтингов 11 лучших игроков.
7. Элемент хэш-таблицы содержит информацию о номере телефона и фамилию человека, который доступен по этому телефону. То есть у одного человека может быть несколько телефонов: домашний, рабочий, мобильный и т.п. Напишите программу, которая по заданной фамилии выводит все номера телефонов, по которым доступен этот человек.
8. Упорядочить массив размера N по возрастанию1|убыванию2.
9. Дано множество A из N точек с целочисленными координатами. Порядок на координатной плоскости определим следующим образом: (x1, y1) < (x2, y2), если либо x1 < x2, либо x1 = x2 и y1 < y2. Расположить точки данного множества по возрастанию1|убыванию2 в соответствии с указанным порядком.
10. Из двух упорядоченных по невозрастанию массивов A(M) и B(N) получить путем слияния упорядоченный по убыванию массив C; удаляемые элементы собрать в массиве D. Подсчитать количество элементов в массивах C и D.
11. Заданы два одномерных массива А(N) и В(N). Сформировать массив С(2*N), содержащий элементы обоих массивов, расположенные в порядке возрастания.
12. Путем слияния из возрастающего A(M) и невозрастающего B(N) массивов получить возрастающий массив C (с удалением совпадающих элементов). Подсчитать количество элементов в массиве С.
13. Задан массив записей, поле key которого – целые числа. Написать программу, которая наглядно демонстрирует сортировку массива по ключу key:
ü методом простого слияния;
ü методом естественного слияния.
Количество элементов массива таково, что все элементы отображаются на экране. В данных сортировках используется дополнительный массив
14. Задан массив записей, поле key которого – целые числа. Написать программу, которая наглядно демонстрирует пирамидальную сортировку по ключу key. Массив изображен в виде последовательности элементов. При построении пирамиды на экране массив отображается не только в виде последовательности, но и в виде построенной пирамиды.
15. Написать программу, иллюстрирующую работу сортировки Хоара:
16. реализовать рекурсивным методом;
17. реализовать нерекурсивным методом;
18. реализовать любым из методов, но учитывать, что для сортировки массива маленького размера лучше применять какой-нибудь другой метод сортировки (например, простыми вставками, пузырьком ...).
19. Написать программу, которая наглядно иллюстрирует работу следующих методов сортировки:
ü пузырьковая
ü шейкерная
20. Провести сравнение сортировок методом пузырька и шейкерной по количеству сравнений, по количеству обменов. Для этого построить графики зависимостей данных величин от количества элементов массива.
21. Написать программу, которая иллюстрирует работу метода Шелла с одной из формул вычисления шага сортировки:
h[k–1] = 3h[k] + 1, h[t]=1, t = [log3n]–l;
h[k–1] = 2h[k] + 1, h[t]=1, t = [log2n]–l;
2k–l;
2k +1;
(2k–(–l)k)/3;
(3k–l)/2;
числа Фибоначчи.
22. Реализовать сортировку массива целых чисел методом двухпутевых вставок при использовании следующих дополнительных структур данных:
ü массива;
ü двунаправленного списка.
Программа должна наглядно иллюстрировать работу данного алгоритма.
23. Исследовать зависимость количества сравнений в сортировках простыми и бинарными вставками от количества элементов в этих массивах. При этом отобразить необходимое количество перестановок.
24. Написать программу, которая иллюстрирует сортировку массива распределяющим подсчетом. Элементом массива является запись следующего типа:
record
ch : char;
key : integer
end;
Указание.
Ключом сортировки является поле целого типа.
25. В магазине строительных материалов в продаже имеются стеновые панели, которые характеризуются следующими величинами:
ü ширина,
ü длина,
ü количество штук,
ü цена за 1 м2.
Вывести в порядке возрастания цены сведения о тех стеновых панелях, общая площадь которых не менее заданной.
26. Есть некий измерительный прибор, работа которого зависит от входных параметров a и x, а результат определяется следующей формулой у = a sin(ax) cos2 (x/a). Проводится серия опытов для значений xt ,х2,... xn, a = const. Вывести результат в виде таблицы, упорядоченной по убыванию значений показаний прибора, полученных в ходе опытов.
27. Информация агентства по продаже недвижимости содержит следующие сведения о квартирах:
ü район, в котором находится квартира,
ü этаж,
ü количество комнат,
ü общая площадь,
ü цена за 1 м2.
Клиент, обращаясь в агентство, имеет возможность указать вес для каждого из критериев (важный критерий имеет большой вес, незначительный – маленький), а агентство, в свою очередь, предлагает ему список квартир, упорядоченный по невозрастанию суммы весов.
28. В чемпионате России по футболу принимают участие 16 команд. Для каждой команды известен список игроков, каждый из команды имеет рейтинг. Вывести список команд в порядке убывания вероятности победы в чемпионате. Вероятность победы равна рейтингу команды – сумме рейтингов 11 лучших игроков.
Разбор выражений
1. Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:
<выражение> ::= <цифра> | <выражение> + <цифра> |
<выражение> – <цифра>
2. Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:
<выражение> ::= <терм> | <выражение> + <терм> |
<выражение> – <терм>
<терм> ::= <цифра> | <терм> * <цифра>
3. Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:
<выражение> ::= <терм> | <выражение>+<терм> |
<выражение>–<терм>
<терм> ::= <элемент> | <терм> * <элемент>
<элемент> ::= <цифра> | (<выражение>)
4. Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом:
<выражение> ::= <цифра> | (<выражение><знак><выражение>)
<знак> ::= + | – | *
5. Проверить правильность выражения, заданного в виде строки S (выражение определяется по тем же правилам, что и в задании 1). Если выражение составлено правильно, то вывести 0, в противном случае вывести номер первого ошибочного (или лишнего) символа в строке S.
6. Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом ("T" — True, "F" — False):
<выражение> ::= T | F | And (<операнды>) | Or (<операнды>)
<операнды> ::= <выражение>,<выражение>
7. Вывести значение логического выражения, заданного в виде строки S. Выражение определяется следующим образом ("T" — True, "F" — False):
<выражение> ::= T | F | And (<операнды>) | Or (<операнды>) |
Not (<выражение>)
<операнды> ::= <выражение> | <выражение>,<операнды>
8. Проверить правильность расстановки скобок в строке S. Текст в строке S определяется следующим образом:
<текст> ::= <элемент> | <элемент><текст>
<элемент> ::= a | b | c | (<текст>) | [<текст>] | {<текст>}
Если текст составлен правильно, то вывести True, иначе вывести False.
9. Проверить правильность расстановки скобок в строке S (текст в строке S определяется по тем же правилам, что и в задании 8). Если текст составлен правильно, то вывести 0; в противном случае вывести номер первой ошибочной скобки или –1, если в строке недостаточно закрывающих скобок.
Деревья
1. Дано упорядоченное дерево глубины N (> 0), каждая внутренняя вершина которого имеет K (< 9) непосредственных потомков, которые нумеруются от 1 до K. Корень дерева имеет номер 0. Записать в текстовый файл все возможные пути, ведущие от корня к листьям (каждый путь записывается в отдельной строке файла). Перебирать пути, начиная с "самого левого" и заканчивая "самым правым", при этом первыми заменять конечные элементы пути.
2. Дано упорядоченное дерево глубины N (> 0), каждая внутренняя вершина которого имеет K (< 9) непосредственных потомков, которые нумеруются от 1 до K. Корень дерева имеет номер 0. Записать в текстовый файл все пути, ведущие от корня к листьям и удовлетворяющие следующему условию: никакие соседние элементы пути не нумеруются одной и той же цифрой. Каждый путь записывается в отдельной строке файла. Порядок перебора путей — тот же, что в задании 1.
3. Дано упорядоченное дерево глубины N (N > 0 — четное), каждая внутренняя вершина которого имеет два непосредственных потомка: A с весом 1 и B с весом –1. Корень дерева C имеет вес 0. Записать в текстовый файл все пути от корня к листьям, удовлетворяющие следующему условию: суммарный вес элементов пути равен 0. Каждый путь записывается в отдельной строке файла. Порядок перебора путей — тот же, что в задании 1.
4. Дано упорядоченное дерево глубины N (N > 0) того же типа, что и в задании 3. Записать в текстовый файл все пути от корня к листьям, удовлетворяющие следующему условию: суммарный вес элементов для любого начального отрезка пути неотрицателен1|неположителен2. Каждый путь записывается в отдельной строке файла. Порядок перебора путей — тот же, что в задании 1.
5. Дано упорядоченное дерево глубины N (N > 0 — четное) того же типа, что и в задании 3. Записать в текстовый файл все пути от корня к листьям, удовлетворяющие следующим условиям: суммарный вес элементов для любого начального отрезка пути неотрицателен1|неположителен2, а суммарный вес всех элементов пути равен 0. Каждый путь записывается в отдельной строке файла. Порядок перебора путей — тот же, что в задании 1.
6. Подсчитать сумму элементов на k-ом уровне заданного двоичного дерева (корень считать узлом 1-го уровня).
7. Подсчитать число узлов на k-ом уровне заданного двоичного дерева (корень считать узлом 1-го уровня).
8. Подсчитать минимум из чисел, содержащихся в листьях заданного двоичного дерева.
9. Подсчитать максимум элементов на k-ом уровне заданного двоичного дерева (корень считать узлом 1-го уровня).
10. Дано вещественное x, целое k. Подсчитать количество чисел, меньших x, в узлах ниже k-ого уровня заданного двоичного дерева.
11. Упорядочить строки данного текстового файла в порядке возрастания их длин.
12. Отсортировать в алфавитном порядке слова в заданном текстовом файле, основываясь на k-ой литере каждого слова. Например, если k=3, то слова должны быть отсортированы по возрастанию значения в третьей литере. Если длина слова меньше k, то будем предполагать, что его k-ой литерой, реально не существующей, служит пробел.
13. Проверить, является ли данное двоичное дерево деревом поиска.
14. В заданном дереве найти поддерево двоичного поиска с максимальным количеством элементов.
15. Реализовать нерекурсивную процедуру печати всех элементов заданного двоичного дерева.
16. Реализовать рекурсивную процедуру печати всех элементов заданного двоичного дерева.
17. Описать логическую функцию, проверяющую на равенство два заданных двоичных дерева.
18. Описать логическую функцию, определяющую, есть ли в заданном двоичном дереве хотя бы два одинаковых элемента.
19. Описать процедуру, которая для заданного N строит двоичное дерево, в котором N полных уровней и на каждом уровне i располагаются узлы, информационные части которых равны i.
20. Дан текстовый файл. Слова содержат не более 20 символов. Определить частоту использования каждого слова в тексте. Результат оформить в виде таблицы, содержащей слова в лексикографическом порядке.
21. Даны два текстовых файла A и В. Максимальная длина слова — 20 символов. Занести в файл С те слова из файла A, которых нет в файле В. Для хранения слов файла В и ускорения поиска среди них воспользуйтесь деревом двоичного поиска. В некоторой файловой системе каталог файлов организован в виде упорядоченного дерева. Каждый узел обозначает файл и содержит имя файла, а также, среди прочего, дату последнего обращения к нему, закодированную в виде целого числа. Написать программу, которая обходит дерево и удаляет все файлы, последнее обращение к которым происходило до определенной даты.
22. Подсчитать сумму элементов на k-ом уровне заданного двоичного дерева (корень считать узлом 1-го уровня).
23. Подсчитать число узлов на k-ом уровне заданного двоичного дерева (корень считать узлом 1-го уровня).
24. Подсчитать минимум из чисел содержащихся в листьях заданного двоичного дерева.
25. Подсчитать максимум элементов на k-ом уровне заданного двоичного дерева (корень считать узлом 1-го уровня).
26. Дано вещественное x, целое k. Подсчитать количество чисел, меньших x, в узлах ниже k-ого уровня.
27. Создано некоторое оглавление с использованием разного количества отступов, или символов табуляции. Построить дерево-оглавление.
28. Проверить, является ли данное двоичное дерево деревом поиска.
29. Дан текстовый файл. Слова содержат не более 20 символов. Определить частоту использования каждого слова в тексте. Результат оформить в виде таблицы, содержащей слова в лексикографическом порядке.
30. В заданном дереве найти поддерево двоичного поиска с максимальным количеством элементов.
31. Подсчитать число узлов в заданном двоичном дереве.
32. Подсчитать число узлов на k-ом уровне заданного двоичного дерева (корень считать узлом 1-ого уровня).
33. Даны два текстовых файла A и В. Максимальная длина слова — 20 символов. Занести в файл С те слова файла A, которых нет в файле В. Для хранения слов файла В и ускорения поиска воспользуйтесь деревом двоичного поиска.
34. Реализовать нерекурсивную процедуру печати всех элементов заданного двоичного дерева.
35. Реализовать рекурсивную процедуру печати всех элементов заданного двоичного дерева.
36. Описать логическую функцию, проверяющую на равенство два заданных двоичных дерева.
37. Описать логическую функцию, определяющую, есть ли в заданном двоичном дереве хотя бы два одинаковых элемента.
38. Описать процедуру, которая для заданного N строит двоичное дерево, в котором N полных уровней и на каждом уровне i располагаются узлы, информационные части которых равны i.
Графы
1. Найти все вершины графа, недостижимые из заданной.
Указание:
использовать рекурсивную процедуру проверки доступности одной вершины из другой.
2. Раскрасить граф минимальным количеством цветов. Каждая вершина должна быть «окрашена» в цвет, отличный от цвета смежных вершин.
3. Определить, является ли связанным заданный граф.
Указание:
использовать рекурсивную процедуру проверки доступности одной вершины из другой.
4. Найти длину кратчайшего цикла в графе.
5. Найти все циклы, не содержащие вершин.
6. Определить вершину, удалением которой можно свести граф к дереву.
7. Найти вершину заданного графа, которая принадлежит каждому пути между двумя заданными вершинами.
8. Задана система односторонних дорог. Найти путь, соединяющий города А и Б, не проходящий через заданное множество вершин.
9. Задана система двусторонних дорог. Найти замкнутый путь, проходящий через каждую вершину и длиной не более 100 км.
10. Найти город в системе двусторонних дорог, у которого сумма расстояний до любого города минимальна.
11. По системе двусторонних дорог определить, есть ли в ней город, из которого можно добраться в любой другой менее чем за 100 км. Разрешается построить дополнительно 3 дороги.
12. По системе двусторонних дорог определить, можно ли, закрыв какие-либо 3 из них, добиться того, чтобы из города А нельзя было попасть в город Б.
13. Задана система двусторонних дорог. N-периферией называется множество городов, расстояние от которых до выделенного города больше N. Определить N-периферию для заданного N.
14. Определить, изоморфны ли 2 графа.
15. Построить такой многоугольник (не обязательно выпуклый) с вершинами в заданном множестве, периметр которого максимален.
16. Найти минимальное множество прямых, на которых можно разместить все точки заданного множества.
17. В 3-мерном пространстве задано множество точек. Найти разбиение этого множества на 2 непустых и непересекающихся множества, чтобы их центры тяжести находились наиболее близко друг к другу.
18. Неориентированный граф называется двудольным, если его можно раскрасить в два цвета так, что концы любого ребра будут разного цвета. Составить алгоритм проверки, является ли заданный граф двудольным (число действий не превосходит N + M).
Указание:
каждую связную компоненту можно раскрашивать отдельно;
выбрав цвет одной вершины и обходя ее связную компоненту, определяется единственно возможный цвет остальных.
Замечание
В этой задаче безразлично, производить поиск в ширину или в глубину.
19. Решить задачу 17 для ориентированного графа (вывести все вершины, доступные из данной по дугам; граф может содержать циклы).
20. Доказать, что алгоритм Дейкстры можно модифицировать так, чтобы для N городов и N маршрутов он требовал не более
O(N +K ln N) операций.
Указание:
на каждом шаге выбрать невыделенный город с минимальной стоимостью и скорректировать цены для всех городов, в которые из него есть маршруты. Если известен города, стоимость до которого минимальна, то хватило бы O(n + k) действий. Вычисление минимального элемента в массиве обходится в множитель log n.
21. С эйлеровыми циклами связана задача китайского почтальона, условие которой звучит так: ребрам неориентированного графа приписаны положительные веса. Необходимо найти цикл, проходящий через каждое ребро графа не менее одного раза и такой, чтобы сумма весов с учетом кратности прохождения ребер была бы минимальна.
Замечание
Эта задача часто встречается на практике. Например, при решении задач планирования проверки электрических, телефонных или железнодорожных линий, при решении задач доставки почты или продуктов питания и т. п.
Оглавление
1. Линейные алгоритмы.. 3
2. Логическое выражение. 6
3. Условный оператор. 7
4. Циклы.. 11
5. Последовательности чисел. 15
6. Строки. 17
7. Одномерные массивы.. 26
8. Процедуры и функции. 32
Задания. 32
9. Матрицы.. 36
10. Множества. 41
11. Перечислимый тип. 42
13. Файлы.. 45
13.1. Текстовые файлы.. 45
13.2. Типизированные и нетипизированные файлы.. 53
13.3. Студент. 58
14. Рекурсия. 59
15. Списки, стеки, очереди. 63
16. Сортировки. 67
17. Разбор выражений. 73
18. Деревья. 74
19. Графы.. 77
Сборник задач
по программированию
для студентов специальности 230201
«Информационные системы и технологии»
Составители: Тюкачев Николай Аркадьевич
Михайлова Елена Евгеньевна
Вощинская Гильда Эдгаровна
Михайлов Евгений Михайлович
Заказ № 384 от 11.02.2010 г. Тираж 100 экз. Лаборатория оперативной полиграфии ВГУ