Часть 2. Прикладные алгоритмы

1. Составить программу оптимальной по времени сортировки.

Д. Кнут «Искусство программирования для ЭВМ».

Н. Вирт «Алгоритмы + Структуры данных = Программы».

2. Составить программу для кодирования текста шифром Хаффмена.

А.М.Ткачев. Основы программирования на языке С.

3. Разработка алгоритмов фрактальной графики.

4. Составить программу, иллюстрирующую тему «Рекурсия в программировании», с графической иллюстрацией.

4.1. Ханойские башни.

Даны три стержня и n дисков различного размера. Диски можно надевать на стержни, образуя из них башни. Вначале на стержне А в убывающем порядке расположено n дисков. Задача заключается в том, чтобы перенести диски со стержня А на стержень С, сохранив их первоначальный порядок. При переносе необходимо следовать правилам:

1) на каждом шаге со стержня на стержень переносится точно один диск;

2) диск нельзя помещать на диск меньшего размера;

3) для промежуточного хранения используется стержень В.

А.М.Ткачев. Основы программирования на языке С.

4.2. Кривые Серпинского.

5. Составить игровую программу «Кликомания».

6. Составить игровую программу «Кошки - мышки в лабиринте».

6. Составить игровую программу «Тесей в лабиринте».

7. Составить программу – тренажер клавиатуры «Поймай букву (слово, предложение)».

8. Задача «Тур коня».

Требуется: найти полный обход шахматной доски ходом коня с однократным посещением каждого поля.

9. Задача «Восемь ферзей».

На шахматную доску требуется поместить восемь ферзей так, чтобы ни один из них не нападал на другого. Использовать рекурсивный алгоритм решения.

10. Лабиринт.

Сформировать представление лабиринта и определить путь к выходу из произвольной точки.

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

12. Преобразование выражения из инфиксной записи в постфиксную. Вычисление выражения, записанного в постфиксной форме.

13. Анализ скобочного выражения на корректность.

Необходимо проверить соответствие строки символов обычным математическим правилам записи скобочных выражений при использовании скобок трех видов: ( ), [ ] и { }.

Запись корректна, если:

количества открывающих и закрывающих скобок каждого типа совпадают;

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

14. Анализ строки на наличие палиндрома.

15. Задача Джозефуса.

Группа солдат окружена превосходящими силами противника. Надежда на победу без подкрепления исключается, однако для прорыва из лагеря имеется лошадь. Солдаты решают выбрать одного человека и послать его за помощью. Они становятся в круг, и из шляпы выбирается число n и одно из имен. Производится счет по часовой стрелке по кругу, начиная с солдата с выбранным именем. Когда счетчик достигает n, соответствующий солдат удаляется из круга, а счет продолжается снова, начиная со следующего солдата. Последний оставшийся в круге солдат посылается за подмогой.

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

16. Составить программу раскрашивания карты в минимальное число цветов методом исчерпывающего поиска.

Ч. Уэзерелл. «Этюды для программистов».

17. Анализ алгебраических выражений на корректность. Представление выражения, содержащего операнды и бинарные операции, в виде строго бинарного дерева.

А.М.Ткачев. Основы программирования на языке С.

18. Реализация алгоритма быстрой сортировки (сортировки Хоара).

19. Реализация алгоритма пирамидальной сортировки.

А.М.Ткачев. Основы программирования на языке С.

20. Реализация алгоритма поразрядной сортировки.

Метод основан на свойстве значений целых чисел в позиционном представлении.

А.М.Ткачев. Основы программирования на языке С.

21. Сортировка методом турнира с выбыванием (выбором из дерева)

А.М.Ткачев. Основы программирования на языке С.

22. Тестирование быстродействия алгоритмов сортировки (выбора, вставки, пузырьковой и быстрой) при наилучшем, среднем и наихудших случаях, при количестве элементов в массиве 100, 1000.

Наименьший элемент

Напишите программу, которая моделирует рекурсивный алгоритм нахождения k-ro наименьшего элемента в массиве чисел mas при помощи выборки произвольного элемента mas[i] из mas и разделения mas на элементы, которые меньше чем mas[i], равны ему и больше его.

Простые включения

Пусть записи a[1],...,a[i–1] уже размещены в "выходной" части массива; берут элемент a[i] и переносят в выходную часть, вставляя его в подходящее место.

Бинарные включения

Этот метод представляет собой улучшение метода простых включений, который имеет по крайней мере два недостатка:

необходимость перемещения данных, причем при вставке элементов, близких к концу массива, приходится перемещать почти весь массив,

необходимость поиска места для вставки, на что также тратится много ресурсов.