Пятница - время поломать голову над непростыми задачками.

← →
Sandman25 © (2004-10-18 09:26) [80]

[63] MBo © (15.10.04 18:04)

Красиво. Я не поверил, что решение предыдущей задачи могло использоваться :(

← →
MBo © (2004-10-18 09:44) [81]

>Sandman25 © (18.10.04 09:26) [80]
>Красиво.
Да, красиво. приведу один из путей
(MinMax переставляет переменные при сравнении)
(7) MinMax(1,2,3,4,5,6)
(6) MinMax(2,3,4,5,7)
(4) MinMax(3,4,5,8)
(3) Sort(4,5,9)

← →
MBo © (2004-10-18 09:53) [82]

P.S.
Я писал, что задача 12 имет практическое значение - это медианная фильтрация, использующаяся в обработке изображений - пиксел заменяется медианой окрестности 3х3 - что позволяет удалять определенные виды шумов, не особо портя резкие края ( что случается, например, при свертке с гауссовым окном или простом усреднении)

← →
Sandman25 © (2004-10-18 10:21) [83]

[82] MBo © (18.10.04 09:53)

Думаю, что для изображений нельзя говорить о независимости чисел. Есть корреляция между цветами соседних пикселей. Вероятно, можно решение еще оптимизировать.
За пример из [81] спасибо.

← →
WL (2004-10-18 11:26) [84]

В 12 вроде бы можно обойтись 18 сравнениями

← →
MBo © (2004-10-18 12:49) [85]

>WL (18.10.04 11:26) [84]
>В 12 вроде бы можно обойтись 18 сравнениями
Не знаю... Интересно было бы посмотреть на алгоритм.
Где-то встречал, что теорет. минимум - 19.

← →
default © (2004-10-18 15:41) [86]

MBo © (18.10.04 07:59) [79]
может я что не понял, но стержень может поместиться и вне "линзы"
к тому же в формуле думаю множителя 1/2 в числителе нету

← →
MBo © (2004-10-18 16:21) [87]

>default © (18.10.04 15:41) [86]
>может я что не понял, но стержень может поместиться и вне "линзы"
Чтобы левый конец стержня, параллельного оси X, лежал внутри полукруга - ставим его в (-r,0) и двигаем (соблюдая параллельность) до (0,r). Центр стержня при этом идет по дуге радиуса r, сдвинутой на a вправо.
Аналогично для правого конца. Искомая площадь - пересечение полукругов.

>думаю множителя 1/2 в числителе нету
?
такой множитель есть в знаменателе, возникает - как половина площади круга

← →
WL (2004-10-18 21:46) [88]

12.
Пусть на к-ом шаге имеем упорядоченную последовательность A1<=A2<=...<=An из n элементов, в которую надо добавить элемент B. Сначала сравниваем B со средним элементом (A[n div 2]) и далее гоним его влево или вправо, пока не встанет на свое место, чтобы опять получилась упорядоченная последовательность. Очевидно, что максимальное количество сравнений при таком добавлении = (1 + n div 2)

1. Берем последовательность из одного элемента [A1] и добавляем A2 (1 сравнение)
2. [A1<=A2] + A3 (всего сравнений: 1 + 2 = 3)
3. [A1<=A2<=A3] + A4 (3+2=5)
4. [A1<=A2<=A3<=A4] + A5 (5+3=8)
5. [A1<=A2<=A3<=A4<=A5] + A6 (8+3=11)
6. По описанным ранее соображениям отбрасываем 1-ый и 6-ой элементы, т.к. они не смогут стать средними из 9: [A1<=A2<=A3<=A4<=A5<=A6] -> [A1<=A2<=A3<=A4] + A7 (11+3=14)
7. Отбрасываем 1-ый и 5-ый [A1<=A2<=A3<=A4<=A5] -> [A1<=A2<=A3] + A8 (14+2=16)
8. Отбрасываем 1-ый и 4-ый [A1<=A2<=A3<=A4] -> [A1<=A2] + A9 (16+2=18)

← →
MBo © (2004-10-19 08:06) [89]

>WL (18.10.04 21:46) [88]
ЗдОрово!
Сортировка вставками+отбрасывание. Логических изъянов навскидку не нашел. Тест вроде бы проходит.
Правда, здесь требуется дополнительная структура данных. У Кнута (3т,5.3.3) указано, что при таких условиях медиану 9 элементов можно найти за 15 сравнений

← →
WL (2004-10-19 11:06) [90]

>MBo © (19.10.04 08:06) [89]
Теоретически, если так критичны память и скорость, то это вполне можно реализовать на N листах не особо читаемого кода без дополнительных структур и функций только с помощью if then else... хотя выглядеть будет действительно ужасно.
Наверное можно и с помощью 15, но это уже будет нетривиальная последовательность сравнений...

сегодня по пути в универ едя в трамвае я задумался о задаче 8
и меня "озарило" хех, как всё оказалось просто:
допустим что стержень лежит на столе под определённым углом по отношению к горизонтальной
оси, придвинем его концы, оставляя угол таким же, к окружности, получим хорду длины
2a, опустим из центра окружности радиуса r прямые в концы этой хорды, очевидно они будут
равны по длине радиусу r и прямую в центр этой хорды, очевидно точка пересечения этой
прямой и хорды есть центр стержня, получается равнобедренный треугольник,
расстояние от центра окружности(или стола, особого смысла это не имеет) до центра стержня по
теореме Пифагора будет R=|sqrt(r^2-a^2)|. И далее продвигая стержен с соблюдение постоянтсва
угла по окружности центр стержня, совершенно очевидно, опишет окружность радиуса R.
Очевидно, всё сказанное верно для стержня расположенного под любым углом. И опять же,
совершенно ясно, что если центр стержня смещать к центру стола то края стержня также не будут
вылезать за него. Таким образом искомая вероятность будет отношение площади окружности которую
описывает стержень при его движении по ней к площади стола и получим:
Pi*R^2/Pi*r^2=1-a^2/r^2. Вот и всё. Никаких интегралов никаких углов, всё очень просто разрешилось.

сорри, неправильно описал, вот так верно:
придвинем концы стержня к окружности, получим хорду длины
2a, опустим из центра окружности радиуса r прямые в концы этой хорды, очевидно они будут
равны по длине радиусу r и прямую в центр этой хорды, очевидно точка пересечения этой
прямой и хорды есть центр стержня, получается равнобедренный треугольник,
расстояние от центра окружности(или стола, особого смысла это не имеет) до центра стержня по
теореме Пифагора будет R=|sqrt(r^2-a^2)|. И далее продвигая стержен по окружности центр стержня, совершенно очевидно, опишет окружность радиуса R.
И совершенно ясно, что если центр стержня смещать к центру стола то края стержня также не будут
вылезать за него. Таким образом искомая вероятность будет отношение площади окружности которую
описывает центр стерженя при его движении по ней к площади стола и получим:
Pi*R^2/Pi*r^2=1-a^2/r^2. Вот и всё.

>default © (19.10.04 13:46) [92]
Это ты нашел вероятность того, что целиком на столе лежит стержень, перпендикулярный радиусу

MBo © (19.10.04 13:51) [93]
признаю, вы правы, я здорово поторопился...
вашего решения я так и не понял...если начертить на бумаге, то
можно стержень, не нарушая параллельности, поместить и вне линзы образуемой пересечением смещённых на a и -a от центра окружностей
откуда это решение?оно ваше?оно точно правильно?

Пятница - время поломать голову над непростыми задачками. Найти похожие ветки