ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Sergey Kabikov                       2:5020/175.2   20 Feb 2002  12:16:46
 To : Alexander Shmidt
 Subject : ехилая задачка
 -------------------------------------------------------------------------------- 
 

 Tue Feb 19 2002 18:24, Alexander Shmidt wrote to All:
 
  AS> Есть линия, вдоль которой стоят точки. Они, допустим, прозвольным образом
  AS> пронумерованы от 1 до 100. Есть матрица расстояний между точками (могут
  AS> быть даны не все расстояния). Определить, в каком порядке (без разницы -
  AS> слева направо или наоборот) они могут стоят на линии (то есть, их
  AS> расположение, не противоречащее данной матрице).
  AS> Идея:
  AS> Воспользоваться равенством AB+BC=AC.
  AS> Или надо как-то обобщить то равенство...
 
 Обобщаю :
 1. выбираешь две точки : А и В. Поскольку задача инвариантна по отношению к
 зеркальному обращению оси координат - произвольно считаем В правее А.
 2. для каждой из остальных точек С :
 - если АС + ВС = АВ - ставим ее на расстоянии АС справа от А (между А и В),
 - если АС > ВС - ставим ее на расстоянии ВС справа от В,
 - иначе ставим ее на расстоянии АС слева от А.
 
 С уважением
 Сергей
  
 
 ...HИИ экспериментальной травматологии
 
 --- ifmail v.2.15
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

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

Тема:    Автор:    Дата:    ехилая задачка   Sergey Kabikov   20 Feb 2002 12:16:46   ехилая задачка   Alexander Shmidt   21 Feb 2002 07:14:05