Задачи

Задача 8. В длинную деревянную рейку вбили несколько гвоздей. Некоторые пары гвоздей связываются верёвочками так, чтобы выполнялись следующие условия:

1. к каждому гвоздю была привязана хотя бы одна верёвочка;
2. суммарная длина верёвочек была бы минимальной.

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

Замечание. Задача решается без перебора.

Задача 9. Квадрат размером 5ґ 5 вдоль линий сетки разбили на несколько фигурок. Написать программу, которая определяет, можно ли переложить часть фигурок так, чтобы снова образовался квадрат размером 5ґ 5. При перекладывании не разрешается поворачивать и переворачивать фигурки.

Технические требования: Входные данные – символьная матрица размером 5ґ 5. Каждая буква в матрице означает идентификатор фигурки, содержащей соответствующую клетку. Идентификаторами являются большие буквы латинского алфавита. Программа должна выдать другой способ составления квадрата размером 5ґ 5, либо сообщение, что это невозможно.

Замечание. Это стандартная переборная задача. Решается с помощью перебора с возвратом (можно использовать распостранение ограничений).

Задача 10. В океане расположен архипелаг из N островов, каждый из которых имеет форму многоугольника. Острова не соприкасаются и не пересекаются. Эти острова необходимо соединить между собой мостами так, чтобы от любого острова архипелага можно было добраться до любого другого. Каждый мост должен соединять пару островов, при этом суммарная длина мостов должна быть минимальной.

Технические требования: Входными данными являются число островов в архипелаге (N) и N описаний островов. Каждый остров задаётся числом вершин и их координатами в порядке обхода по часовой стрелке. Программа должна вывести два числа – количество мостов и их суммарную длину.

Замечание. Задача решается без перебора.

Задача 11 Разбиение. Массив натуральных чисел A (A1,...,A_n) разбить на два непересекающиеся массива B и C (то есть каждый элемент массива A должен попасть точно в один из двух массивов: B или C), так, чтобы сумма чисел в B равнялась сумме чисел в C.

Технические требования: Входными данными являются количество чисел (n) и последовательность из n чисел. Программа должна вывести два массива чисел B и C.

Замечание. Задача схожа с задачей о рюкзаке и решается перебором с возвратом. Можно использовать распостранение ограничений. Перед перебором имеет смысл упорядочить массив A по невозрастанию.