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

← →
MBo © (2004-10-15 08:37) [0]

1. Мальчик с секундомером решил измерить глубину колодца, бросив туда камень.
Он ошибся в два раза, поскольку забыл, что скорость звука не бесконечна.
Какова глубина колодца (сопротивлением воздуха пренебречь)?

2. Программист Вася услышал где-то, что каждый человек должен в своей жизни
вырастить дерево. Дерево он стал растить так: начал с одного узла,
затем рандомом с вероятностью 2/3 вывел из него два новых,
а с оставшейся 1/3 закрыл этот узел для дальнейшего роста.
С двумя новыми узлами (если они появились) поступил так же.
И так далее. Какова вероятность того, что Васино дерево выжрет всю память и завесит комп?

3. Стенька Разин плывет по Волге. В первом же селе он берет
на свою ладью самую красивую девушку. В следующем,
если встречает еще более красивую, берет ее, а первую бросает "в набежавшую волну".
Сколько девушек будут выброшены после посещения N>>1 сел?

4. За прошедшую неделю в хит-параде Шлюз-ТВ произошли серь±зные изменения.
Первая десятка осталась той же, но
1) Молодая певица Однокайте переместилась на одну строку.
2) Дуэт Ви-2 передвинулся на 2 позиции.
3) Группа ТриаГра скакнула на 3 пункта
.... ну и так далее до ........
9) ансамбля Нано- шагнувшего аж на 9 ступеней.

Могла ли десятая участница, славящаяся своей стабильностью Валерьяна,
и в этот (который уже!) раз остаться на прежней позиции?

5. Будка Бобика имеет форму круга единичного радиуса.
Длина цепи, закрепленной у входа в будку - Pi.
Какова площадь территории, контролируемой Бобиком?

6. Какой максимальный объём может иметь многогранник с суммарной длиной рёбер 1 ?

7. Cколько на свете разных задач, если на момент формулирования этой задачи
в ветках "пятничные задачки" было помещено N задач и М из них встречалось дважды?
Пусть задачи берутся равновероятно из некоторого списка.
Для оценки используем N = 675, M = 10.

8. Тонкий стержень длины 2a лежит на круглом столе радиуса r>a.
Какова вероятность того, что ни один из концов стержня не выступает за край стола?

9. Пусть в пачку сигарет вложена случайная карта из колоды в 52 листа.
Сколько в среднем нужно купить пачек, чтобы собрать целую колоду для получения приза?

10. В замке появились два привидения: Пение и Смех. Одно из них поет, другое хохочет.
В течение каждой минуты каждое из них либо звучит, либо молчит.
Поведение же их в последующую минуту зависит от событий предыдущей минуты следующим образом:
Пение в последующую минуту ведет себя так же, как и в предыдущую, если только
в предыдущую минуту не было игры на органе при молчащем Смехе.
В противном случае оно меняет свое поведение на противоположное.
Если в предыдущую минуту горела свеча, то Смех будет звучать или молчать в зависимости от того, звучало или молчало Пение.
Если свеча не горела, то Смех будет делать противоположное тому, что делало Пение.
В настоящую минуту и Смех и Пение оба звучат.
Какие действия со свечой и органом нужно совершить, чтобы установить и
поддерживать тишину в замке?

11. Алгоритмически-программистская задача:
Какое минимальное количество сравнений необходимо для нахождения
минимального и максимального значений в наборе из 6 переменных?

12. Посложнее:
На основе решения задачи 11 найти минимальное число сравнений для
нахождения СРЕДНЕГО элемента из 9 переменных.
(задача имеет прикладное значение)

← →
Nikolay M. © (2004-10-15 08:55) [1]

> 1.

180м? Конечно, если камень мальчик уронил, а не бросил :)

← →
SergP. (2004-10-15 08:55) [2]

> 1. Мальчик с секундомером решил измерить глубину колодца,
> бросив туда камень.
> Он ошибся в два раза, поскольку забыл, что скорость звука
> не бесконечна.
> Какова глубина колодца (сопротивлением воздуха пренебречь)?
>

(2*V^2)/g V - скорость звука, g - ускорение свободного падения...

Хм... Получается колодец глубиной порядка 19 км ??????

Или это я что-то намутил?

← →
SergP. (2004-10-15 08:59) [3]

Или напомните мне скорость звука в атмосфере при нормальных условиях...

← →
Nikolay M. © (2004-10-15 09:04) [4]

> SergP. (15.10.04 08:59) [3]

330 м/с. Черт, я перепутал, я считал из расчета 30 м/с, а ведь чувствовал, что маловато :(

← →
MBo © (2004-10-15 09:13) [5]

>SergP.
>Nikolay M
Неверно.
На самом деле получается не колодец, а шахта

← →
Nikolay M. © (2004-10-15 09:16) [6]

Нехреновый колодец в 21.78 километра. Это у какой бабушки на даче такой выкопан? :)
Или опять неправильно?

← →
MBo © (2004-10-15 09:22) [7]

> 21.78 километра
нет

← →
Думкин © (2004-10-15 09:22) [8]

от 3 до 4 км. :( Со скорстью звука - от давления зависит еще она, поэтому тут можно в дебри влезть.

← →
Думкин © (2004-10-15 09:33) [9]

если 330 - то 3,7 км примерно. Если же учитывать возрастание скорости, то глубже.

← →
dmitry99 © (2004-10-15 09:33) [10]

3. N/2

← →
Ega23 © (2004-10-15 09:36) [11]

9.
51!

← →
Ega23 © (2004-10-15 09:38) [12]

6. Одна кубическая единица

← →
MBo © (2004-10-15 09:44) [13]

>3. N/2
нет

>9. 51!
нет. Вопрос, конечно должен звучать так - какое минимальное количество пачек в среднем нужно купить?

>6. Одна кубическая единица
нет. Обрати внимание, что СУММА длин ребер=1

← →
MBo © (2004-10-15 09:50) [14]

>Думкин © (15.10.04 09:33) [9]
>если 330 - то 3,7 км примерно.
Угу
d=2*(Sqrt(2)-1)^2*c^2/g

← →
Rule © (2004-10-15 09:55) [15]

Во блин задачки елки палки ...

← →
Думкин © (2004-10-15 09:56) [16]

#ifdef offtop
Насчет глубин колодцев:
http://chaika4444.narod.ru/yakutsk1_4.html
#endif

← →
Ega23 © (2004-10-15 10:00) [17]

>6. Одна кубическая единица
нет. Обрати внимание, что СУММА длин ребер=1

Тогда 1/1728 кубических единиц.

← →
Sandman25 © (2004-10-15 10:00) [18]

5. Сумма гармонического ряда.
1/2 + 1/3 + 1/4 + ... + 1/N

← →
Sandman25 © (2004-10-15 10:01) [19]

[18] Sandman25 © (15.10.04 10:00)

Это был ответ для 3 задачи, не для 5.

← →
Sandman25 © (2004-10-15 10:02) [20]

4. Нет. Сумма от 1 до 9 = 45 - нечетная.

← →
Ega23 © (2004-10-15 10:04) [21]

Кстати, в 1-й задаче не сказано, в какую сторону ошибся мальчик. Т.е. в 2 раза больше, или в 2 раза меньше. :о)
Физического смысла не имеет, а вообще-то интересное решение может получиться. :о)

← →
Sandman25 © (2004-10-15 10:13) [22]

6.

Надо сравнить объем куба и тетраэдра.
Для куба имеем (1/8)^3=0,002
Для тетраэдра имеем (1/6)^3*sqrt(2)/12=0,0005

Ответ. 0.125^3

← →
MBo © (2004-10-15 10:14) [23]

>Тогда 1/1728 кубических единиц
Это куб. Объем близок к максимуму, но оказывается, существует многогранник с бОльшим объемом (не особо сложный).

Sandman25 © (15.10.04 10:00) [18]
3. Сумма гармонического ряда.
1/2 + 1/3 + 1/4 + ... + 1/N

верно

4. Нет. Сумма от 1 до 9 = 45 - нечетная.
Верно

← →
Sandman25 © (2004-10-15 10:15) [24]

[22] Sandman25 © (15.10.04 10:13)

Вру. У куба 12 ребер, а не 8. Поэтому
(1/12)^3 = 0,000578

Ответ: (1/12)^3 = 0,000578

← →
msguns © (2004-10-15 10:17) [25]

>4. Не только могла, но и должна, т.к. у этой талантливой исполнительницы всегда одна и та же позиция. Называется "Фанерная поза"

← →
Sandman25 © (2004-10-15 10:23) [26]

11. 7:
1<2
^ ^
3<4
^ ^
5<6

← →
Ega23 © (2004-10-15 10:29) [27]

MBo © (15.10.04 10:14) [23]

Гы. Бесконечность. Цилиндр с радиусом 1/(4*Pi) :о)

← →
VICTOR_ (2004-10-15 10:58) [28]

7.
44887.5

← →
Sandman25 © (2004-10-15 12:25) [29]

12.
Mean = (a1 + a2 + ... + a9) / 9.
Ни одного сравнения :)

← →
MBo © (2004-10-15 12:29) [30]

>Sandman25 © (15.10.04 10:23) [26]
7 сравнений - верно

>12. Mean = (a1 + a2 + ... + a9) / 9.
>Ни одного сравнения :)
Не то - не среднее, а средний по рангу элемент, например, из
1,2,5,29,30,40,50,50,60 это будет 30

← →
MBo © (2004-10-15 12:32) [31]

>VICTOR_ (15.10.04 10:58) [28]
7.44887.5

примерно в 2 раза ошибка

[22] Sandman25 © (15.10.04 10:13)
>Вру. У куба 12 ребер, а не 8.

Как я уже сказал, есть многогранник с большим объемом, чем куб

← →
Agent13 © (2004-10-15 12:40) [32]

10. Сначала не делать ничего, через минуту Смех замолкнет.
Тогда играть на органе, через минуту замолкнет Пение. Прератить игру на органе, зажечь свечу. Вроде бы оба должны молчать :)

← →
Sandman25 © (2004-10-15 12:41) [33]

12. Делим на 4 пары - 4 сравнения.
Находим минимум среди бОльших (3 сравнения), максимум среди меньших (3 сравнения). Сравниваем оставшееся девятое число с минимумом.
1) больше либо равно - ответ: минимум
2) меньше. Сравниваем девятое число с максимумом:
2a) больше либо равно - ответ: максимум.
иначе девятое число.
В худшем случае получаем 12 сравнений, в наилучшем - 8 (если максимум среди меньших искать не понадобилось из-за срабатывания 1).

← →
Ega23 © (2004-10-15 12:43) [34]

MBo © (15.10.04 12:32) [31]

(SQRT(3))/2916 ?

← →
Sandman25 © (2004-10-15 12:50) [35]

[33] Sandman25 © (15.10.04 12:41)

в 2a ошибка. меньше либо равно.

← →
default © (2004-10-15 13:01) [36]

Ega23 © (15.10.04 10:04) [21]
естественно что в два раза больше
время которое звук шёл со дна колодца до мальчика он считал
временем движения камня(то есть дополнительное расстояние)
вообще задача несложная с моими скромными познаниями в физике быстро решилась...

← →
MBo © (2004-10-15 13:04) [37]

>Agent13 © (15.10.04 12:40) [32]
Первую строку можно безболезненно удалить.

>Sandman25 © (15.10.04 12:41) [33]
Ты что-то не то ищешь...
А сравнений для нахождения медианы, увы, будет несколько больше приведенных тобой чисел.

>Ega23 © (15.10.04 12:43) [34]
(SQRT(3))/2916
Точно.

← →
default © (2004-10-15 13:13) [38]

просьба к MBo, как как-то Думкин делал, публиковать периодически список номеров решённых задач и ведилять его жирным шрифтом

← →
MBo © (2004-10-15 13:40) [39]

>default ©
решены
1,3,4,6,10,11
не решены пока
2,5,7,8,9,12

← →
VICTOR_ (2004-10-15 13:56) [40]

7.
22106.25

← →
MBo © (2004-10-15 14:37) [41]

>VICTOR_ (15.10.04 13:56) [40]
>7. 22106.25
Близко к известному мне решению. формула какая получилась?

← →
NeyroSpace © (2004-10-15 14:42) [42]

А Можно уточнить условия 2й задачи? Значит ли это что вер-ть появ-ния одного узла следующего уровня 1/3 или имеется ввиду, что появится могут только 2а узла одновременно с вер-тью 2/3?
А в результате нужно найти формулу для выч. вероятности n-го уровня?

← →
VICTOR_ (2004-10-15 14:45) [43]

7.
N^2/2M - N

← →
SergP. (2004-10-15 14:48) [44]

> [24] Sandman25 © (15.10.04 10:15)
> [22] Sandman25 © (15.10.04 10:13)
>
> Вру. У куба 12 ребер, а не 8. Поэтому
> (1/12)^3 = 0,000578
>
> Ответ: (1/12)^3 = 0,000578

Рискну предположить что искомый многогранник - призма с правильным треугольником в основании, причем длина всех ребер одинаковая и равна 1/9

S=((1/9)^3)*sqrt(3)/4 =0.0005939

← →
SergP. (2004-10-15 14:53) [45]

> [34] Ega23 © (15.10.04 12:43)
> MBo © (15.10.04 12:32) [31]
>
> (SQRT(3))/2916 ?

блин... Уже ответили... не заметил...

← →
default © (2004-10-15 15:42) [46]

5. может Pi^2*(1+Pi/2)? примерно 25

← →
Sandman25 © (2004-10-15 15:50) [47]

5. Напугала постановка задачи... Когда нарисовал, оказалось элементарно -
pi*(pi^3-1)/2

← →
Sandman25 © (2004-10-15 15:51) [48]

[47] Sandman25 © (15.10.04 15:50)

Ошибся с рисунком. Все-таки не элементарно...

← →
NeyroSpace © (2004-10-15 16:06) [49]

Если считать, что появится могут только 2а узла одновременно с вер-тью 2/3, то вер-ть появления:
узлов 1го уровня = 1
узлов 2го уровня = вер-ть появл 1го * (кол-во узлов 1го) * 2/3
узлов 3го уровня = вер-ть появл 2го * (кол-во узлов 2го) * 2/3
...
или ошибаюсь?

← →
MBo © (2004-10-15 16:09) [50]

>SergP
>искомый многогранник - призма с правильным треугольником в основании
Да

>default © (15.10.04 15:42) [46]
нет
>Sandman25 © (15.10.04 15:51) [48]
В принципе, задача сложная, думаю, достаточно будет описания.

>VICTOR_ (15.10.04 14:45) [43]
в моей оценке просто N^2/2M

>NeyroSpace © (15.10.04 14:42) [42]
1/3 - вероятность вымирания
2/3 - вероятность появления двух дочерних узлов одновременно
Найти вероятность бесконечного роста.

← →
Sandman25 © (2004-10-15 16:18) [51]

[50] MBo © (15.10.04 16:09)

Описание чего?
Рисуем фигуру - полукруг (площадь pi^3/4) плюс нечто подковообразное c радиусом от pi до 2. Площадь последнего, наверное, считается через интегрирование.

← →
Jeer © (2004-10-15 16:28) [52]

>1. Мальчик с секундомером решил измерить глубину колодца, >бросив туда камень.
> Он ошибся в два раза, поскольку забыл, что скорость звука не >бесконечна.
> Какова глубина колодца (сопротивлением воздуха пренебречь)?

Задача, в принципе, неккоректна.
1. Путь камня криволинеен. Значит, возможно, он ударился о стенку, а это - не глубина колодца.
Или колодец прорыт по кривизне предполагаемой линии падении камня.
Т.е. нужны вводные данные по широте колодца и его диаметру(размеру). Размерами камня пренебрегаем-с.
В силу криволинейности пути туда - криволинеен путь оттуда.
Тут уж вопросы распространения звука в ограниченном канале.
3. Сила Корриолиса тоже отклонит камень. Те же вводные.

← →
VICTOR_ (2004-10-15 16:43) [53]

> >VICTOR_ (15.10.04 14:45) [43]
> в моей оценке просто N^2/2M

Согласен, стормозил второй раз :(((

← →
oldman © (2004-10-15 17:00) [54]

8. А насколько r>a?
:)))

← →
MBo © (2004-10-15 17:17) [55]

>VICTOR_ (15.10.04 16:43) [53]
>Согласен, стормозил второй раз :(((
Возможно, и нет - оценка делалась для больших N.

>oldman © (15.10.04 17:00) [54]
>8. А насколько r>a? :)))
не играет роли

← →
default © (2004-10-15 17:23) [56]

Sandman25 © (15.10.04 16:18) [51]
Pi^3/2 наверно...

какое интересно описание требуется?
собака может следить за площадью фигуры описываемой ниткой при её наматывании на цилиндр
сначала собака может оббежать площадь Pi^3/2 выше касательной к к окружности из точки конуры, дальнейшее движение возможно уже лишь при наматывании верёвки по длине окружности(до полукокружности)каждый раз проводя касат-ую к оружности в конечной точки намотки верёвки по длине окружности получим сектор
по какую-то сторону касательной радиуса pi/длина намотки на окружность и тд сектора перекрываются...

← →
default © (2004-10-15 17:27) [57]

Pi-длина...
конечно
MBo, так уравнение этой кривой можно вывести?

← →
Sandman25 © (2004-10-15 17:42) [58]

12.
Находим минимальный элемент (8 сравнений), затем следующий (1 сравнение), затем третий (минимальный из оставшихся - 6 сравнений), затем четвертый (1 сравнение) и, наконец, ответ (минимальный из оставшихся - 4 сравнения). Итого - 20 сравнений.

← →
MBo © (2004-10-15 17:46) [59]

>default © (15.10.04 17:23) [56]
>default © (15.10.04 17:27) [57]
>MBo, так уравнение этой кривой можно вывести?
Да, описано правильно - это эвольвента окружности, часть спирали.
http://mathworld.wolfram.com/CircleInvolute.html
Для нахождения площади можно проинтегрировать в R-fi координатах.

← →
MBo © (2004-10-15 17:52) [60]

>Sandman25 © (15.10.04 17:42) [58]
20 сравнений - верно, это минимум. Твой путь пока не проверял, известный мне отличается - в нем не определяются достоверно минимальные или максимальные элементы

← →
Sandman25 © (2004-10-15 17:52) [61]

[58] Sandman25 © (15.10.04 17:42)

Неправильно. По-моему, будет 8+7+6+5+4=30 сравнений. Либо существенное усложнение алгоритма.

← →
Sandman25 © (2004-10-15 17:53) [62]

[60] MBo © (15.10.04 17:52)

Ответ просто совпал. Я не решил задачу. Каков правильный алгоритм?

← →
MBo © (2004-10-15 18:04) [63]

>Sandman25 © (15.10.04 17:53) [62]
>Каков правильный алгоритм?
Как я писал, решение 11 задачи поможет:
Начальный этап алгоритма основан на том, что в любой выборке 6 элементов из 9 минимальный элемент имеет ранг менее пяти, а максимальный - более 5, и могут быть отброшены.

← →
VICTOR_ (2004-10-15 18:28) [64]

Рискну предположить
8.
r^2-a^2

← →
MBo © (2004-10-15 18:30) [65]

>VICTOR_ (15.10.04 18:28) [64]
>Рискну предположить 8.r^2-a^2

Нет. выражение посложнее.

← →
VICTOR_ (2004-10-15 19:02) [66]

8.
a^2/(r^2-a^2)

2 VICTOR_ [66]
как вы это получили?
У меня в этой задачке получаются интегралы с arcsin , взять которые я сейчас затрудняюсь

8. 1 - (2 / 3 * r^4 + a^2)

1. Решение системы:

g * T^2 g * (t + T)^2 ------- = v * t = --------------- 2 4
Здесь условно: T - время полета камешка, t - время "полета" звука, v - скорость звука.

Ответ, кажись, тут уже привели

А про Стеньку я так и не понял. Вы бы хоть дали вероятность того, что в следующем селе есть девушка красивее той, которая в текущий момент на ладье.

P.S. 8. Кстати, к формуле из [68] приводит вычисление тройного интеграла интеграла:

Pi/2 R R | | | | | | ( (x + a * cos(Phi))^2 + (y + a * sin(Phi))^2 ) dx dy d(Phi) | | | 0 -R -R
где R = r^2.

Упс, еще надо интеграл поделить на 2 * Pi * r^4

P.S. При решении я допускаю, что стержень могут положить центром тяжести чуть-чуть за край стола, в квадрат:
{(x,y) | -r <= x <= x, -r <= y <= r}

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

← →
VICTOR_ (2004-10-16 14:18) [73]

8.1 - A(2R-A)/R^2
Пусть
S - площадь стола
Sx - площадь на столе, которая удовлетворяет условию
X - радиус площади на столе, которая удовлетворяет условию
X = R - A
S=pi*R^2
Sx=pi*X^2=pi*((R-A)^2)
Вероятность попадания центра стержня в условие
V=Sx/S=pi*((R-A)^2)/pi*R^2 = 1 - A(2R-A)/R^2

> 1. Мальчик с секундомером решил измерить глубину колодца,
> бросив туда камень.
> Он ошибся в два раза, поскольку забыл, что скорость звука
> не бесконечна.
> Какова глубина колодца (сопротивлением воздуха пренебречь)?
>

Ошибся в 2 раза - это со временем или с глубиной?

← →
VICTOR_ (2004-10-16 14:35) [75]

> Ошибся в 2 раза - это со временем или с глубиной?

Из условия очевидно, что ошибся в 2 раза именно в результате - то есть с глубиной

Aldor © (16.10.04 11:24) [69]
действия Стеньки можно представить так:
приплывает он в село, выбирает в нём самую красивую девушку(поэтому можно считать что в селе всего лишь одна девушка)
и сравнивает её с тем что были
вначале никого не было у него в лодке поэтому самая красивая в селе будет в его лодке, вероятность этого 1, затем ту что в лодке сравнивает с "единственной" в другом селе, вероятность того что он отдаст предпочтение второй(ровно как и первой в данном случае) есть 1/2, в третьем селе вер-ть что он выберет
ту что из этого села будет 1/3(все подобные вероятности и есть вероятности что будет выкидываться девушка из лодки, на первом шаге она равна естественно 0) и тд
поэтому и результат 1/2 + 1/3 + ... + 1/N
только слагаемые тут не вероятности, а как бы девушки представляемые этими вероятностями думаю понятно почему так
вопрос был при N>>1
поскольку не известно на сколько много и учитывая что этот(гармоничский) ряд расходится ответ может быть таким же(>>1 ну или бесконечность если под N>>1 подразумевалась бесконечность)

VICTOR_ (16.10.04 14:18) [73]
это точно не верно
ты почему то считаешь что ТОЛЬКО если центр стержня угодит в Sx то будет выполнено условие не выхода за края обоих концов стержня
это не так, можешь начертить две концентрические окружности и увидишь что стержень может поместиться и вне окружности Sx
более того одна и та же площадь стола делится между площадями куда если угодит центр стержня не будет выхода за края и когда будет
разница в угле наклона стержня

Согласен с [77] , при попытке посчитать вероятность для этого кольца , где важен угол наклона стержня , у меня и выплылвает интеграл с arcsin. Формула из [68] про 8. так , как она там зписана , тоже неверна , так как там складываются величины с разными размерности: м^2 и м^4 .

8. - Ответа верного не было.
Если центр стола взять за начало координат, ось X направить параллельно стержню так, чтобы он находился в верхней полуплоскости, то центр стержня, не выступающего за края, лежит внутри части полукруга, ограниченной дугами окружностей радиуса r с центрами в точках -a и a (пересекаются они в точке на оси Y с коорд. Sqrt(r^2-a^2)искомая вероятность - отношение площади полученной фигуры ("полулинзы") к PiR^2/2

(R^2*ArcCos(a/R)-a*Sqrt(R^2-a^2))/(PiR^2/2)

5. 5/6*Pi^3

2. При решении можно воспользоваться таким трюком - раз уж у нас процесс смахивает на бесконечный, ничего не изменится при добавлении в его начало еще одного шага.
(для наводки - найти сопротивление между точками A и B бесконечной лесенки из одноомных резисторов)
A-R- -R- -R- -R- -... | | | | B-- R --R --R --R-....

>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)

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

[82] MBo © (18.10.04 09:53)

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

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

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

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

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

>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)

>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 от центра окружностей
откуда это решение?оно ваше?оно точно правильно?

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