ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Max Alekseyev                        2:5015/60      05 Mar 2002  13:25:06
 To : Eugene Grosbein
 Subject : Перебор?
 -------------------------------------------------------------------------------- 
 

 
 Replying to a message of Eugene Grosbein to All:
 
  EG> Есть уравнение:
 
  EG> x[1]+2*x[2]+3*x[3]+...+n*x[n]=b,
  EG> где n и b заданные константы, y[i] - перестановка вектора x[i].
  EG> Вектор y[i] известен, 
 
 Буду считать, что y[] упорядочен по неубыванию, т.е.
 y[1] <= y[2] <= ... <= y[n]
 
  EG> но неизвестно, что это за перестановка.
  EG> Можно ли найти x[i] за время, существенно меньшее,
  EG> чем нужно на полный перебор, O(n!) ?
 
 Сначала определим x[n].
 
 n*x[n] = b - (x[1]+2*x[2]+...+(n-1)*x[n-1])
 
 Максимальное значение того, что стоит в скобках равно
 
 s = y[2] + 2*y[3] + ... + (n-1)*y[n],
 
 а минимальное значение
 
 t = y[n-1] + 2*y[n-2] + ... + (n-1)*y[1].
 
 Поэтому
 b - s <= n*x[n] <= b - t
 или
 (b-s)/n <= x[n] <= (b-t)/n.
 
 Перебираем для x[n] всевозможные значения из y[], которые укладываются в этот
 интервал. Получается задача размерности n-1, которая решается аналогично.
 
 Hе возьмусь сейчас оценить сложность этого алгоритма, но мне кажется, что она
 сильно меньше n!.
 
 Regards,      ш.ш
         Max    ~
 
 --- FleetStreet 1.27.3.7
  * Origin:  (2:5015/60)
 
 

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

Тема:    Автор:    Дата:    Перебор?   Eugene Grosbein   06 Mar 2002 00:27:29   Перебор?   Max Alekseyev   05 Mar 2002 13:25:06