Задача 9.
Составить программу для нахождения произвольного разбиения 20 студентов на 2 команды, численность которых отличается не более чем в 2 раза, если известно, что в любой команде должны быть студенты, обязательно знакомые друг с другом. Круг знакомств задается матрицей (20,20) с элементами
A(ij)={1,если i студент знаком с j
{0,иначе .
|
Решение задачи 9.
Разбиение на группы осуществляется аналогично, как и в Задаче 10. за тем исключением, что в ситуации 3. организуются две новые группы (пара групп, одна из них может оказаться в результате пустой). После разбиения всех людей будем использовать принцип формирования двух результирующих групп, основываясь на идее решения Задачи 2 из главы "Сортировки", учитывая возможности об'единения двух пар групп в одну пару групп произвольным слиянием двух групп из различных пар.
|
