Все лабораторные работы, за исключением 2b, выполняются на языке C++. Лабораторная работа 2b выполняется на паскале. Вообще говоря, на паскале разрешается выполнить лабораторные работы 1a, 1b, 2a, 2b и 3. Начиная с лабораторной работы 4, они должны выполняться только на C++.
1. Треугольник Паскаля
a. [3 б.] По определению: каждый элемент треугольника является суммой двух элементов
«над» ним. Вывести несколько строк треугольника Паскаля, используя
не более одного одномерного массива (т.е. хранить только текущую строку).
b. [2 б.] По формуле биномиальных коэффициентов. Факториал реализовать рекурсивно.
2. Простые числа
a. [2 б.] По определению: вывести первые несколько простых чисел, проверяя в цикле
каждое число на простоту перебором делителей.
b. [2 б.] Решето Эратосфена. Реализовать алгоритм поиска простых чисел в интервале от
2 до 255 при помощи множеств паскаля (set of byte).
3. Библиотека
[5 б.] В библиотеке хранятся книги, журналы и газеты. Для книг хранится название, автор,
год издания, количество страниц; для журналов — название, год, номер;
для газет — название, год, месяц и день выпуска. Реализовать структуру для
хранения этих данных (вариантная запись в паскале, union в C++).
Данные хранить в файле, реализовать добавление записей, поиск и удаление.
Начиная со следующей лабораторной работы, ваши программы «замолкают»: они должны работать только с файлами input.txt и output.txt (кроме лабораторной работы 9) и не выдавать никакой информации на экран. Убедительная просьба не подключать conio.h к своим программам, начиная с лабораторной работы 4.
4. Системы счисления
[5 б.] Во входном файле input.txt в первой строке через пробел записаны
некоторое (возможно, дробное) число в системе счисления от 2 до 16, основание
системы счисления, в которой записано это число, и основание системы счисления,
в которую требуется перевести число. Программа должна создать файл output.txt
и записать в него ответ: число, переведенное в требуемую систему счисления.
5. Перестановки
Во входном файле input.txt находится число N. Записать в
файл output.txt все перестановки множества {1,...,N}:
a. [4 б.] используя рекурсивный метод поиска перестановок;
b. [4 б.] используя алгоритм Дейкстры (Dijkstra) поиска следующей по алфавиту перестановки.
6. Поиск подстроки в строке
[4 б.] В первой строке входного файла input.txt находится строка, в которой
производится поиск, во второй — шаблон. Найти все вхождения шаблона в
строку. В файл output.txt выдать, с каких символов строки (считая с 0)
начинаются совпадения (разделять индексы пробелом) или записать слово NO,
если совпадение не было найдено. Использовать алгоритм Бойера-Мура (Boyer, Moore).
7. Поиск в массивах
a. [3 б.] В первой строке входного файла input.txt записаны через пробел
числа N (количество элементов, N≤1000) и K
(искомый элемент, целое число), затем N целых чисел, причем каждое из
них больше либо равно предыдущему (т.е. последовательность упорядочена).
Считать эти числа в массив. С помощью бинарного поиска определить, присутствует
ли число K в этом массиве.
b. [5 б.] Хэширование. В первой строке входного файла input.txt записано
число N (количество слов, N≤100000). В следующих N
строках записаны слова длиной до 5 символов включительно, причем известно, что
встречаются не более 3000 различных слов. Вывести в файл output.txt
количество вхождений каждого слова в файл (в каждой строке файла — слово
и количество вхождений через пробел, порядок перечисления слов произвольный).
Для подсчета использовать хэш-таблицу.
c. [7 б.] [для желающих] Реализовать частотный бредогенератор ;) —
подробности на семинаре.
8. Внутренние сортировки
В первой строке входного файла input.txt записано число N
(количество чисел, N≤1000), затем идут N целых чисел.
В файл output.txt вывести эти числа, отсортировав их по возрастанию.
a. [2 б.] Реализовать любую «простую» сортировку (O(N2)).
b. [3 б.] Реализовать сортировку Шелла (Shell).
c. [3 б.] Реализовать быструю сортировку (quick sort, Hoar).
d. [3 б.] Реализовать пирамидальную сортировку (heap sort).
9. Сортировка файлов
[5 б.] Реализовать сортировку файла input.txt методом двухпутевого слияния.
10. Архиватор*
[6 б.] Реализовать архиватор и деархиватор, используя метод Хаффмана.
* для получения оценки «отлично»
А.Г.Фенстер
fenster@forestnet.org
http://fenster.forestnet.org/hci/
ICQ: 9043584