ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Shmidt                     2:464/34.74    19 Feb 2002  19:24:26
 To : All
 Subject : Нехилая задачка
 -------------------------------------------------------------------------------- 
 

       ><  Е  ><  Е  ><   Хау, бледнолицый  All!   ><  Е  ><  Е  ><
 
     (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
 
 Сабж:
 
 Есть линия, вдоль которой стоят точки. Они, допустим, прозвольным образом
 пронумерованы от 1 до 100. Есть матрица расстояний между точками (могут быть
 даны не все расстояния). Определить, в каком порядке (без разницы - слева
 направо или наоборот) они могут стоят на линии (то есть, их расположение, не
 противоречащее данной матрице).
 
 Идея:
 Воспользоваться равенством AB+BC=AC.
 Если выполняется - точки стоят в порядке A, B, C.
 И так столько раз, сколько нужно.
 
 Баги:
 Hе могу придумать лучшее решение.
 А для набора, где есть точки A,B,C,D и даны расстояния AB, BC, CD и AD - решение
 не катит:
 
  __ __ __
 A  B  C  D
 (        )
  ~~~~~~~~
 
 Или надо как-то обобщить то равенство...
 
 Good bye, mister All                            _
                                                /_|  _  _    _/
                                      Smith,   (  | (/ (- /) /   Smith...
                                                  _/
 ... Все в Голом Деде пишут послания, Winamp поставлен на паузу... (с)~Сплин
 --- А у твоего ГолДеда стоит... фильтрация мессаг???
  * Origin: Телепузик спать ложится - программист за комп садится. (2:464/34.74)
 
 

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

Тема:    Автор:    Дата:    Нехилая задачка   Alexander Shmidt   19 Feb 2002 19:24:26   Нехилая задачка   Boris Sivko   20 Feb 2002 23:31:18