Файл: Zadachi.doc

В задачах 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;

для вычисления z^m (z — вещественное, m — натуральное) и с её помощью подсчитать значение выражения a⁷ + b⁸ .

3. Описать рекурсивную функцию

function fib(n : integer) : integer;

для вычисления n-ого (n  40) числа Фибоначчи.

Указание.

Последовательность чисел Фибоначчи f_k образуется так:

f₀=1, f₁=1, f_k = f_k-2 + f_k-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.

Списки, стеки, очереди

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 после i-ого элемента списка.

20. Создать список из 20 элементов, информационные поля которой содержат случайные числа из интервала [–50, 50]. Удалить из списка последний отрицательный элемент.

21. Создать очередь, информационные поля которой содержат числа из текстового файла. Удалить из списка за каждым вхождением элемента с информационным полем, равным d, один элемент, если он отличен от d.

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

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

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

25. Считалочка. N ребят расположены по кругу. (Каждому присвоен номер по порядку). Начав отсчёт от первого, удаляют каждого k-ого, смыкая при этом круг. Определить номер последнего, оставшегося в круге. (kN)

Указание:

для решения задачи использовать очередь, в которой ссылочное поле последнего элемента содержит адрес первого элемента..

26. Написать программу, проверяющую правильность расстановки скобок в арифметическом выражении. Скобки могут быть круглыми, квадратными и фигурными.

27. Преобразовать последовательность действительных чисел, записанных в файле, расположив сначала отрицательные числа последовательности, а затем неотрицательные. При этом порядок как отрицательных, так и неотрицательных чисел изменяется на обратный

Указание.

для решения задачи создать два стека: с отрицательными и с неотрицательными числами последовательности.

28. Даны целые числа a₁, a₂, … a_n, содержащиеся в текстовом файле. Вычислить значение выражения p₁ + 10 + p₂  100 + p₃  1000 + … , где p₁, p₂ , p₃ , … — встречающиеся в последовательности положительные числа, взятые в обратном порядке (начиная с последнего встретившегося положительного числа).

Указание

для решения задачи сформировать стек из положительных чисел последовательности.

29. Написать программу для вычисления значения выражения, представленного в обратной польской записи.

Указание

просматривая строку, в которой записано выражение, анализируем очередной символ. Если это число, то записываем его в стек. Если это знак операции, то достаём два элемента из стека, выполняем арифметическую операцию, определяемую этим знаком, и заносим результат в стек.

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

32. Создать очередь, информационные поля которой содержат числа из текстового файла. Из каждой группы подряд идущих одинаковых чисел оставить только одно.

33. Создать очередь из 20 элементов, информационные поля которой содержат случайные числа из интервала [–50,50]. Удалить из списка все числа, по модулю большие числа 20. Использовать метод фиктивного элемента.

34. Дана последовательность символов, состоящая из английских букв и цифр, записанных в текстовом файле. Используя запись в стек, получить число, составленное из цифр последовательности, записанных в обратном порядке. Полученное число записать в текстовый файл.

35. Дана последовательность символов, состоящая из английских букв и цифр, записанных в текстовом файле. Используя запись в стек, получить текст, составленный из английских букв последовательности, записанных в обратном порядке. Полученный текст записать в текстовый файл.

36. Создать очередь, информационные поля которой содержат числа из текстового файла. Подсчитать число максимальных элементов списка.

37. Создать очередь, информационные поля которой содержат числа из текстового файла. Из каждой группы подряд идущих одинаковых чисел оставить только одно.

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

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

элемент списка — число последующих отрицательных элементов.

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

41. Дана последовательность x₁, x₂,…, x_n вещественных чисел, записанных в текстовом файле. Вычислить произведение сумм: .

42. Дана последовательность x₁, x₂,…, x_n вещественных чисел, записанных в текстовом файле. Вычислить произведение сумм:

.

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.