Индивидуальное домашнее задание №2. Массивы.

1.	Для заданного набора точек плоскости построить их выпуклую линейную оболочку (наименьший по площади выпуклый многоугольник, содержащий все точки этого множества). Алгоритм решения: построить из каких-нибудь трех точек множества невырожденный треугольник (первый выпуклый многоугольник). Затем на каждом шаге проверять очередную из оставшихся точек на принадлежность текущему многоугольнику. Если она ему не принадлежит, расширять многоугольник, включая эту точку.
2.	Пользователь задает шаблон лабиринта с несколькими выходами и координаты начального положения. Определить, за сколько шагов можно достичь выхода.
3.	Пользователь задает коэффициенты уравнений нескольких прямых на плоскости в виде y=kx+b. Найти точки, формирующие верхнюю огибающую этих прямых.
4.	В массиве натуральных чисел заменить один элемент таким числом, чтобы пузырьковая сортировка измененного массива потребовала минимального числа обменов элементов.
5.	Даны два массива: A[n] и B[m], упорядоченных по неубыванию. Слить их в один упорядоченный по неубыванию массив за время O(m+n).
6.	Для нахождения квадратного корня из числа можно пользоваться алгоритмом … Вычислить корень из заданного натурального числа с указанным количеством цифр в дробной части.
7.	Найти в массиве натуральных чисел самое большое подмножество элементов, в котором любые два элемента имеют одинаковое множество простых делителей.
8.	Дано натуральное число N. Если возможно, разделить множество чисел {1, 2, …, N } на два подмножества таких, что произведение чисел в одном из них равно сумме чисел в другом.
9.	Дана куча камней, на каждом из которых написан его вес. Указать, каким образом следует разделить эту кучу на две части так, чтобы разность их весов была минимальной.
10.	Найти в массиве натуральных чисел самое большое подмножество элементов, в котором любые два числа взаимно просты.
11.	Имеется набор предметов, для каждого из которых указаны его название, вес и стоимость. Требуется составить набор с наибольшей суммарной стоимостью и весом, не превышающим заданного ограничения.	Воробьев Г.
12.	Все деревья в лесу вблизи земли имеют вид цилиндров радиуса R. Их оси симметрии расположены в точках, координаты которых заданы пользователем. Для охоты на волков, находящихся в этом лесу, используется веревка с флажками, которую нужно натянуть вокруг деревьев так, чтобы ни одно дерево не осталось снаружи. Найти наименьшую длину такой веревки.	Коковин А. зачтено
13.	Найти плоский выпуклый многоугольник, являющийся решением заданной пользователем системы неравенств с двумя переменными. Считается, что все неравенства имеют вид . Пользователь задает количество неравенств, а затем коэффициенты каждого из них.	Валитова А.
14.	См. ИДЗ №3 (функции).	Гаврилов А.

Не нашли, что искали? Воспользуйтесь поиском: