|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Alekseyev 2:5015/60 17 Apr 2002 16:04:02
To : Constantin Stefanov
Subject : Эквивалентность формул.
--------------------------------------------------------------------------------
Replying to a message of Constantin Stefanov to All:
CS> Есть две формулы, представленные деревьями. Требуется определить,
CS> являются ли эти два дерева представлениями одной и той же формулы (в
CS> идеале - с учетом коммутативности и ассоциативности, но для начала
CS> сойдет и просто так).
просто так - это как?
CS> Пример:
CS> a + b + c
CS> + +
CS> / \ / \
CS> a + + c
CS> / \ / \
CS> b c a b
CS> Это просто разные варианты расстановки скобок, а формула одна и та же.
Только если сложение ассоциативно.
CS> Как в этом убедиться?
Если интересно, могу предложить эффективный вероятностный алгоритм.
Regards, ш.ш
Max ~
--- FleetStreet 1.27.3.7
* Origin: (2:5015/60)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Эквивалентность формул. 
