ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Anthone Tikhonov                     2:5020/400     11 Oct 2002  13:57:25
 To : Egor Tsygvintsev
 Subject : Алканы
 -------------------------------------------------------------------------------- 
 

  ET> необходими написать прогу (на пасе, бо иного пока не знаю), которая бы
  ET> считала количество изомеров алкана по заданному кол-ву атомов углерода в
  ET> молекуле. напомню, что алкан - соединение вида С(n)H(2n+2), например
 
 Hасколько я понимаю, задача состоит в том чтобы посчитать,
 сколько существует графов без циклов из 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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор