Алканы

From

Anthone Tikhonov ()

To

Egor Tsygvintsev

Date

2002-10-11T13:57:25Z

Area

RU.ALGORITHMS

From: "Anthone Tikhonov" <ia26@vtb.ru>

 ET> необходими написать прогу (на пасе, бо иного пока не знаю), которая бы
 ET> считала количество изомеров алкана по заданному кол-ву атомов углерода в
 ET> молекуле. напомню, что алкан - соединение вида С(n)H(2n+2), например
Насколько я понимаю, задача состоит в том чтобы посчитать,
сколько существует графов без циклов из N элементов
Скорей всего есть красивая формула, но я ее не помню.
Если надо выдать все варианты алкана - я бы делал так - 
рекурсия по количеству атомов углерода
1) Для 4х элементов 2 графа с-с-с-с с-с-с - сохранили где-то в массиве
                                      |
                                      с
2) Для 5 - по-очереди добавляем к каждому из графов из 4х атомов
по еще одному атому - для 
каждого графа по-очереди к каждой вершине. Если в массиве для 5 еще нет
такого, или топологически эквивалентного графа, добавляем
3) И так далее
Самое сложное - сравнить 2 графа на топ. эквивалентность, я бы делал
так - в одном графе выбрал вершину с наибольшим количеством 
соседей, назвал бы ее корнем, в другом - перебирал бы 
все вершины с таким же кол-вом соседей, называя их по-очереди корнями, 
при этом сравнивая 2 графа с учетом корня
2 графа равны с учетом корня если у них равны все поддеревья, 
выходящие из этого корня - здесь опять рекурсия. Поддеревья из 
1 и из 2х эл-в считаются одинаковыми

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/400)