- полный перебор
- полный перебор всех вариантов. Покажем, что ряд эвристик позволяет сократить перебор для некоторых наборов исходных данных.
Представим информацию о партиях и их членах с помощью следующего зрительного образа - таблицы. Для примера из формулировки задачи она имеет вид:
Тогда задачу можно переформулировать следующим образом. Найти минимальное число столбцов, таких, что множество единиц из них “покрывают” множество всех строк. Очевидно, что для примера это один столбец - второй. Поговорим о структурах данных.
Const Nmax=150;
Type Nint=0..Nmax+1;
Sset=Set of 0..Nmax;
Person=record
man:Nint;{номер жителя}
number:Nint;{число партий, которые он представляет}
part:Sset;{партии}
end;
Var A:array[Nint] of Person;
Логика формирования исходных данных (фрагмент реализации).
function Num(S:Sset):Nint;{подсчитывает количество элементов в множестве}
var i,ch:Nint;
begin ch:=0;
for i:=1 to N do if i in S then Inc(ch);
Num:=ch;
end;
procedure
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа