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