Задачa 4.
Алгоритм состоит в следующем. На каждом шаге находится человек Х, имеющий наибольшее число Р нереализованных знакомств. Затем находится Р людей, с которыми человек Х собирается реализовать знакомства. Нетрудно понять, что это должны быть люди опять же с наибольшим числом нереализованных знакомств, так как такая стратегия обеспечивает на каждом шаге максимально возможное количество людей с нереализованными еще знакомствами. Человек Х реализует по одному знакомству с каждым из Р выбранных людей и из дальнейшего процесса исключается. При этом число нереализованных знакомств у каждого из Р людей уменьшается на 1. Процесс продолжается до тех пор, пока все знакомства не будут реализованы, или найдется такой человек Х, которому не хватит людей для реализации его нереализованных знакомств. В последнем случае задача не имеет решения. Для поиска человека Х и Р людей для реализации знакомств достаточно каждый раз упорядочивать значения нереализованных знакомств в порядке невозрастания, сохраняя при этом информацию о "имени" (исходном номере) человека.
|
