[Tanya 4]

Алгоритм.

1. Сначала все точки сводятся в интервал (X, X+10)

2. Находится левая крайняя. Сдвигается вправо на 10. Успех - повтор. Нет первого успеха - 3.

3. Находим правую крайнюю сдвигаем влево на 10. Успех - повтор. Нет успеха - выход.

Мне кажется, это не будет работать при определенных наборах. Например, возьмем такой набор:

1

1.1

9

9.1

Разница макс-мин 9.1-1=8.1 нс

 

Понятно, что оптимальный результат должен быть

11

11.1

9

9.1

Это даст разницу макс-мин всего в 2.1 нс

 

Если использовать Ваш алгоритм, то исходный набор не удастся привести к оптимальному, т.к. при сдвиге "левой крайней" точки 1 вправо на 10 получится "неуспех":

11

1.1

9

9.1

Получается макс-мин=11-1.1=9.9 нс, что хуже, чем исходные 8.1 нс

Если сдвинуть самую правую точку 9.1 влево на 10, то опять получится макс-мин=9.9 нс.

Да. Ошибочка вышла.

Однако, ларчик просто открывался.

Сводим на вышеупомянутый интервал.

Вычисляем 10 - (Xmax - Xmin) =A

Находим максимальное расстояние между ближайшими соседями. Если оно больше A, то переносим все, что левее вправо. Или наоборот... Если нет такого расстояния, то все уже в порядке.

Объяснение (задача для младших классов, поэтому не будем вводить термин диаметр множества.) в аллегорической форме.

Представим себе полимерную цепь на вышеупомянутом интервале. Можно еще представить для наглядности, что по краям торчат палки до 0 и 10. Произведем ее сечение, а затем пришьем левый кусок справа к правому. Получится цепь укороченная на длину разрезанной связи и удлиненная на A.

Отсюда вытекает решение. Примечание. Точки с одинаковым значением считаем одной точкой.

Можно еще представить себе четки...

[=AK= 12]

Сводим на вышеупомянутый интервал.

Вычисляем 10 - (Xmax - Xmin) =A

Находим максимальное расстояние между ближайшими соседями. Если оно больше A, то переносим все, что левее вправо. Или наоборот... Если нет такого расстояния, то все уже в порядке.

 

Спасибо. Можно еще так представить. После того, как значения приведены к интервалу 0...10 и обозначены на этом отрезке точками, сворачиваем этот интервал в кольцо. Теперь находим на кольце максимальное расстояние между соседними точками, и в этом месте разрываем кольцо, снова превращия его в отрезок. Порядок расположения точек на получившимся отрезке даст максимально "плотное округление".

 

А теперь такой вопрос.

 

Вместо описанного Вами "оптимального" алгоритма используется такой упрощенный алгоритм:

- определяется самый длинный кабель с временем Тмакс, задержка к нему добавляться не будет

- для любого кабеля с задержкой Тх определяется разность Тр=Тмакс-Тх

- полученное значение Тр самым обычным способом округляется до ближайшего кратного 10 нс, это будет добавленная задержка

 

Численный пример, приводившийся ранее:

1 нс

1.1 нс

9 нс

9.1 нс

Самая большая задержка 9.1 нс

для 1 нс разность 9.1-1=8.1, округляем до 10 нс, в сумме 1+10 = 11 нс

для 1.1 нс разность 9.1-1.1=8.0, округляем до 10 нс, в сумме 1.1+10 = 11.1 нс

для 9 нс разность 9.1-9=0.1, округляем до 0 нс, в сумме 9+0 = 9 нс

 

Получили такой же результат, какой дал бы "оптимальный" алгоритм, однако намного более простым способом.

 

В каких случаях этот алгоритм будет хуже "оптимального"? Вернее, насколько он будет хуже "оптимального" в самом благоприятном для "оптимального" случае?

 

"На глазок" он проигрывает оптимальному пренебрежимо мало.

[Tanya 4]

Спасибо. Можно еще так представить. После того, как значения приведены к интервалу 0...10 и обозначены на этом отрезке точками, сворачиваем этот интервал в кольцо. Теперь находим на кольце максимальное расстояние между соседними точками, и в этом месте разрываем кольцо, снова превращия его в отрезок. Порядок расположения точек на получившимся отрезке даст максимально "плотное округление".

 

А теперь такой вопрос.

 

Вместо описанного Вами "оптимального" алгоритма используется такой упрощенный алгоритм:

- определяется самый длинный кабель с временем Тмакс, задержка к нему добавляться не будет

- для любого кабеля с задержкой Тх определяется разность Тр=Тмакс-Тх

- полученное значение Тр самым обычным способом округляется до ближайшего кратного 10 нс, это будет добавленная задержка

 

 

"На глазок" он проигрывает оптимальному пренебрежимо мало.

Вот Вы и представили себе четки.

А про Ваш алгоритм нет времени пока. Пока... Пока.

Нет, не пока, вроде на ум такое пришло, что из точек 100, 94.9 и 95.1 вы получите плохо. В два раза хуже.