Tanya 4 21 января, 2007 Опубликовано 21 января, 2007 · Жалоба Алгоритм. 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 23 января, 2007 Опубликовано 23 января, 2007 · Жалоба Сводим на вышеупомянутый интервал. Вычисляем 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 23 января, 2007 Опубликовано 23 января, 2007 · Жалоба Спасибо. Можно еще так представить. После того, как значения приведены к интервалу 0...10 и обозначены на этом отрезке точками, сворачиваем этот интервал в кольцо. Теперь находим на кольце максимальное расстояние между соседними точками, и в этом месте разрываем кольцо, снова превращия его в отрезок. Порядок расположения точек на получившимся отрезке даст максимально "плотное округление". А теперь такой вопрос. Вместо описанного Вами "оптимального" алгоритма используется такой упрощенный алгоритм: - определяется самый длинный кабель с временем Тмакс, задержка к нему добавляться не будет - для любого кабеля с задержкой Тх определяется разность Тр=Тмакс-Тх - полученное значение Тр самым обычным способом округляется до ближайшего кратного 10 нс, это будет добавленная задержка "На глазок" он проигрывает оптимальному пренебрежимо мало. Вот Вы и представили себе четки. А про Ваш алгоритм нет времени пока. Пока... Пока. Нет, не пока, вроде на ум такое пришло, что из точек 100, 94.9 и 95.1 вы получите плохо. В два раза хуже. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться