Книга "Алгоритмы и программы"

Задачи из главы 5 "Бинарный поиск, слияние и сортировка"

содержание задачника

1. Напишите программу бинарного поиска по ключу в массиве целых чисел. Решение
2. Оптический танк. Танк должен выехать с базы, пересечь пустынную и болотистую местность и прибыть на пост. Препятствий по пути нет, танк может двигаться в любом направлении. Известно, что прямая, соединяющая базу и пост, проходит по обеим территориям. Определите путь, по которому танк приедет на пост быстрее всего.
   Вход. Первая строка текста содержит два числа - скорости танка по пустыне и болоту (м/с). Вторая строка содержит координаты базы, третья - координаты поста. Известно, что ось Ох разделяет пустынную и болотистую территории (пустынная наверху, болотистая внизу), координата у базы положительна, у поста - отрицательна. Все числа действительные.
   Выход. Вывести два числа: абсциссу координаты места, в котором танк пересекает границу пустынной и болотистой местности, и время движения от базы до поста. Оба числа выводить как дробные, с возможной ошибкой не более $10^{-5}$. Решение
   Пример.
   Вход. 3 5 20 10 8 -9
   Выход. 11.7258 5.84277
3. Написать слияние двух упорядоченных массивов, то есть итоговый массив должен быть упорядоченным.
4. Слияние файлов. В тексте записана неубывающая последовательность положительных чисел. Два таких текста нужно слить в один, то есть получить новый текст, содержащий все исходные числа в порядке неубывания.
   Вход. Каждый текст состоит из нескольких строк или является пустым. Числовые константы могут находиться в нескольких строках и внутри строки разделены пробелами.
   Выход. Строка текста, в которой константы разделены пробелами.
   Пример. Входные тексты. 1 4 7 и 1 2 3. Выходной текст. 1 2 3 4 7
5. Решить предыдущую задачу при условии, что задан список файлов с текстами, количество которых может достигать девяти.
6. Выполнить сортировку пузырьком целочисленного массива. Решение
7. Выполнить сортировку выбором целочисленного массива. Решение
8. Реализуйте сортировку слиянием для массива целых чисел двумя способами (рекурсивный и без рекурсии)
9. Реализуйте алгоритм быстрой сортировки для массива целых чисел.
10. Реализуйте пирамидальную сортировку целочисленного массива.

содержание задачника