Методы программирования. Громов Ю.Ю - 51 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

51
Для решения сформулированной выше задачи эквивалентности не-
обходимо сначала определить разбиение множества М на классы эквива-
лентности типа (37), а затем сделать соответствующие выводы.
Разбиение множества М на классы эквивалентности можно начать с
того крайнего случая, когда каждый его элемент один составляет весь
свой класс:
K
1
= {1}, K
2
= {2}, K
3
= {3}, K
4
= {4}, K
5
= {5},
K
6
= {6}, K
7
= {7}, K
8
= {8}, K
9
= {9}. (38)
Теперь, с учётом первого заданного соотношения 1 ≡ 5, следует объ-
единить классы K
1
= {1} и K
5
= {5} в один класс K
1
= {1, 5}. После обра-
ботки соотношений 1 ≡ 5, 6 ≡ 8 и 7 ≡ 2 распределение элементов по клас-
сам (38) примет такой вид:
K
1
= {1, 5}, K
2
= {2, 7}, K
3
= {3}, K
4
= {4}, K
5
= {6, 8}, K
6
= {9}. (39)
Далее на основании соотношения 9 ≡ 8 следует объединить классы
K
5
= {6, 8} и K
6
= {9} с образованием класса K
5
= {6, 8, 9} и т.д.
В приведённном ниже алгоритме для представления ситуаций типа
(37) – (39) в компьютере и эффективного объединения классов использу-
ются древовидные структуры. Элементы множества М становятся узлами
леса и два узла эквивалентны тогда и только тогда, когда они принадле-
жат одному и тому же дереву (классу). Заметим, что два узла принад-
лежат одному и тому же дереву, когда они расположены ниже одного и
того же корня. При объединении классов два дерева легко соединить,
просто полагая одно из них новым поддеревом корня другого дерева.
Алгоритм Е. (Обработка соотношений эквивалентности.)
Пусть М – множество целых чисел 1, 2, …, n и пусть FATHER[1],
FATHER[2], …, FATHER[n] – целочисленные переменные. Пусть вход-
ными данными для этого алгоритма служит некоторое множество соот-
ношений вида (36).
E1. [Начальная установка.] FATHER[k] ← 0 для k = 1, 2, …, n. (Это
означает, что все деревья первоначально состоят только из корня, как в
(38).)
E2. [Ввод новой пары.] Взять из входного потока пару эквивалент-
ных элементов вида j ≡ k. Если входной поток исчерпан, то конец алго-
ритма.
E3. [Найти корни.] Если FATHER[j] ≠ 0, то j ← FATHER[j] и повто-
рить этот шаг. Если FATHER[k] ≠ 0, то k ← FATHER[k] и повторить этот
шаг. (После этой операции j и k перешли в корни двух деревьев, которые
надо соединить. Заметим, что вводимое соотношение j ≡ k избыточно
тогда и только тогда, когда j = k.)
E4. [Соединение деревьев.] Если j ≠ k, то FATHER[j] ← k. Вернуться
на шаг E2. ■

Страницы