ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexander Shmidt                     2:464/34.74    21 Feb 2002  07:14:05
 To : Sergey Kabikov
 Subject : ехилая задачка
 -------------------------------------------------------------------------------- 
 

       ><  Е  ><  Е  ><   Хау, бледнолицый  Sergey!   ><  Е  ><  Е  ><
 
     (будешь долго за компом сидеть, не то что бледным - зеленым станешь!)
 
  Эй, уважаемые Sergey Kabikov и Alexander Shmidt! Что за "ехилая задачка", а где
 же яйца?!
 
  AS>> Есть линия, вдоль которой стоят точки. Они, допустим, прозвольным
  AS>> образом пронумерованы от 1 до 100. Есть матрица расстояний между
  AS>> точками (могут быть даны не все расстояния). Определить, в каком
  AS>> порядке (без разницы - слева направо или наоборот) они могут
  AS>> стоят на линии (то есть, их расположение, не противоречащее
  AS>> данной матрице). Идея: Воспользоваться равенством AB+BC=AC. Или
  AS>> надо как-то обобщить то равенство...
  SK> Обобщаю :
  SK> 1. выбираешь две точки : А и В. Поскольку задача инвариантна по
  SK> отношению к зеркальному обращению оси координат - произвольно считаем
  SK> В правее А. 2. для каждой из остальных точек С : - если АС + ВС = АВ -
  SK> ставим ее на расстоянии АС справа от А (между А и В), - если АС > ВС -
  SK> ставим ее на расстоянии ВС справа от В, - иначе ставим ее на
  SK> расстоянии АС слева от А.
 
 Дык, я ж говорил, что не работает для случая, когда четыре точки и известны
 расстояния между соседними и для двух крайних:
 
 A   B   C   D
 
 есть AB, BC, CD и между крайними - AD.
 
 То есть, нет таких трех точек, для которых известны все три расстояния между
 ними.
 
 Good bye, mister Kabikov                        _
                                                /_|  _  _    _/
                                      Smith,   (  | (/ (- /) /   Smith...
                                                  _/
 ... Пiнгвiн - то не win. Щоб стояв у кожнiй хатi!
 --- А у твоего ГолДеда стоит... фильтрация мессаг???
  * Origin: аннику упавшей Винды... (2:464/34.74)
 
 

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

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