Задачи для практикума

• Информация о курсе
• Содержание курса (старая версия)
• Рекомендуемые материалы

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

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

-- ArtemVoroztsov - 25 Mar 2004