Задачи для практикума
Требуется написать программу, которая делает указанное в задаче действие.
- Степень числа. Вычислите
a^n
с точностью до 16 знаков в мантиссе за логарифмическое поn
время. А сколько времени портебуется для вычисления абсолютно точного ответа (со всеми знаками)? - Числа Фибоначчи. Вычислите число Фибоначчи
Fn
за 1) экспоненциальное, 2) линейное, 3) логарифмическое время поn
время, 4) оцените сложность задачи с учётом длинной арифметики. 0 < n < 1001. - Расстановка ферзей. Расставьте на доске 8 ферзей так, чтобы они не били друг друга.
- Лабиринт. Дана карта лабиринта, на которой отмечены ячейки A и B. Найдите кратчайший путь из A в B. Придумайте алгоритм, работающий в худшем случае время порядка N^2, где N есть длина стороны лабиринта.
- Матрицы. Расставьте скобки в произведении нескольких матриц, чтобы умножение заняло минимальное время.
- Наибольшая общая подпоследовательность. Дано две последовательности целых чисел. Найдите наибольшую общую подпоследовательность.
- Наибольшая возрастающая подпоследовательность. Дана последовательность целых чисел. Найдите наибольшую возрастающую подпоследовательность.
- Провода. Дано несколько кусков провода целочисленной длины. Нужно отрезать
K
кусочков одинаковой максимально возможной целочисленной длины. - Self-describing sequence. Натуральнозначная последовательность
f
такова, чтоf(n)
равно количеству элементовn
в ней. Кроме того, она неубывающая и первые её элементы равныf(1) = 1, f2 = 2, f3 = 2
. Напишите программу, котрая вычисляет f(n). - Максимально удаленная пара. Напишите программу, которая за за N log N находит две самые удаленные точки из данных точек на плоскости.
- Атлеты. У атлетов есть масса и сила (сколько килограмм может атлет держать на плечах). Найдите высоту максимальной башни из атлетов. Параметры атлетов даны.
- Два круга и точки. Покройте данное множество точек на плоскости двумя кругами минимального радиуса.
- Колонны и бассейн. Дан квадратный зал с колоннами. Поместите между колонн круглый бассейн максимального радиуса.
- Самолёты и скрывающийся преступник. На поле скрывапется преступник. Для его поиска организовали самолеты, которые пролетели по прямым линиям над полем. У самолетов извествен радиус обзора. Есть ли точка на поле, где преступник мог скрытся?
- Проверка корректности словаря. Даны термины и для каждого термина указано, через какие другие термины он определяется. Проверьте, что словарь корректен, то есть нет циклических определений и у каждого термина есть ровно одно определение либо нет совсем (аксиоматическое понятие).
- Открытки и конверты. Дано открытки и конверты. В каждый из конвертов помещается не всякая открытка. Нужно распределить как можно больше открыток по конвертам (в один конверт одна открытка).
- Упаковка коробок. Упакуйте коробки друг в друга получив минимальное количество коробок. Известно, что никакие две коробки не поместятся ни в какую другую, если их поставить рядом. Коробка со сторонами x1, x2, x3, x1 <= x2 <= x3, помещается в коробку со сторонами y1, y2, y3, y1 <= y2 <= y3, если x1 < y1, x2 < y2, x3 < y3.
- Кордон. Дана система дорог. Известно что преступник скрывается в городе A. Нужно не дать ему попасть в города B1, B2 и B3. Каково минимальное количество дорог, которое нужно перекрыть?
- Корень из перестановки. Дана перестановка
A
. Найдите какую-нибудь перестановку, которая, если её применить дважды, даст перестановкуA
. - Минимальное число резисторов. Составьте схему из минимального числа резисторов единичного сопротивления, сопротивление которой будет равно данному рациональному числу. (Разбейте данный прямоугольник с рациональным отнощением сторон на минимальное число квадратов).
- Путь между отрезков. Дано множество отрезков на плоскости и две токи. Проверьте, существет ли непрерывный путь, соединяющий эти точки.
- Прибивание отрезков. Дано несколько отрезков на прямой. Можно ли поставить на этой прямой несколько точек, чтобы на каждом отрезке лежала ровно одна точка? Если да, то каково минимальное число точек?