Задачки-2

Nataly · Post by **Nataly** » 16 Mar 2001 19:29

ACL,

Вы что думаете, я Ваш ответ не видела [img:fea4ecde3e]http://www.privet.com/ubb/wink.gif[/img:fea4ecde3e]. Только, видимо, кроме меня его никто больше не видел [img:fea4ecde3e]http://www.privet.com/ubb/biggrin.gif[/img:fea4ecde3e].

------------------
Nataly

Zaphod · Post by **Zaphod** » 16 Mar 2001 19:50

Что радует - два таких топика - и гениальные знатоки всего растворились во мраке. И становится где-то ясно, кто есть кто. Приятно!

COPOKA · Post by **COPOKA** » 16 Mar 2001 20:30

<BLOCKQUOTE>quote:<HR>Originally posted by Nataly:
[i:648f9c4348]ACL,

Вы что думаете, я Ваш ответ не видела [img:648f9c4348]http://www.privet.com/ubb/wink.gif[/img:648f9c4348]. Только, видимо, кроме меня его никто больше не видел [img:648f9c4348]http://www.privet.com/ubb/biggrin.gif[/img:648f9c4348].

[/i:648f9c4348]<HR></BLOCKQUOTE>
Вот и неправдочки, видели. Просто наверное не только у меня жизненные реалии вытесняют из головы абстрактное условие задачи, вот народ и пытается найти решение попрактичнее. [img:648f9c4348]http://www.privet.com/ubb/biggrin.gif[/img:648f9c4348] Это ж скока будет стоить весь этот ящик обратно послать... Лучше уж я сама, Ю Пи Эсом... [img:648f9c4348]http://www.privet.com/ubb/biggrin.gif[/img:648f9c4348]

Joker · Post by **Joker** » 16 Mar 2001 22:36

Ну, здорово разогнались [img:928e90cdc1]http://www.privet.com/ubb/smile.gif[/img:928e90cdc1]
Вот еще парочка из числа моих любимых задач — чтобы было чем голову занять в выходные [img:928e90cdc1]http://www.privet.com/ubb/biggrin.gif[/img:928e90cdc1]

1) У вас есть два одинаковых стеклянных шарика. Перед вами 100-этажное здание. Лестница с площадками на каждом этаже. Шарик имеет определенную прочность, т.е. его можно уронить с некоего этажа, не разбив, но вот если уронить со следующего этажа, то он уже разобьется.
Ваша задача — найти этот самый предел прочности шарика. Вопрос в том, кому за сколько бросаний это удастся сделать. Кто сможет предложить оптимальный вариант?

Чтобы было понятнее - пример: начнем с 50-го этажа и будем прибавлять по одному. Если первый шарик сразу разобьется, перейдем на первый этаж и опять начнем двигаться вверх. При такой схеме хватит 50 бросаний. Очевидно, что это плохой (неоптимальный) способ. Кто предложит лучше?

2) (мне эта штучка ОЧЕНЬ понравилась) ПАРАДОКС.
Вы играете в "Поле чудес" и выиграли приз. Ведущий выносит две шкатулочки и говорит: "Там и там деньги, но в одной шкатулке в 10 раз больше, чем в другой. Выбирайте!" Вы показываете на одну шкатулку и открываете ее. Там (к примеру) 100 баксов. И тут коварный ведущий говорит: "Я даю Вам шанс передумать и выбрать другую шкатулку. Хотите?"
Вы рассуждаете так: ОК, 100 баксов, можно считать, в кармане. В другой шкатулке либо 10 баксов, либо 1000. Вероятность 50/50. Но "проиграть" при неудачном выборе можно 90 долларов, а выиграть — 900. Ясно, что математическое ожидание выигрыша больше (сорри за термин). И вы соглашаетесь.
Вроде бы все правильно, да?
И тут вы снова играете и снова выиграли приз. Все то же самое, опять две шкатулки с теми же условиями, но теперь вы [b:928e90cdc1]не успели заглянуть в первую шкатулку[/b:928e90cdc1], как ведущий предложил Вам ту же возможность передумать.
Вы опять рассуждаете: Какая разница, сколько в первой шкатулке? Я все равно не знаю, больше или меньше во второй. В любом случае, я могу потерять 90% этой суммы (если прогадаю при обмене), а выиграть — 900%. Шансы одинаковые, но выиграть можно много больше, чем проиграть. Овчинка явно стоит выделки. И вы, как и в прошлый раз, соглашаетесь и выбираете другую шкатулку.
Опять все правильно, да?
И тут ведущий вас добивает. Он, не давая вам открыть эту другую шкатулку, говорит: "А хотите [b:928e90cdc1]еще раз[/b:928e90cdc1] поменяться?"
Немая сцена.
Итак, чем дальше вы меняетесь (при каждом втором обмене возвращаясь к своему первоначальному выбору), тем больше увеличиваете свои шансы на выбор "правильной" шкатулки. Парадокс налицо.

bemby · Post by **bemby** » 16 Mar 2001 22:52

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[i:ab6b9189db]Итак, чем дальше вы меняетесь (при каждом втором обмене возвращаясь к своему первоначальному выбору), тем больше увеличиваете свои шансы на выбор "правильной" шкатулки. Парадокс налицо.[/i:ab6b9189db]<HR></BLOCKQUOTE>

Нет, почему же? Вероятность выигрыша большей суммы каждый раз одинакова (50%). В чем тут парадокс? Безусловно, выигрыш каждый раз больше, чем проигрыш, вне зависимости от вышкего выбора шкатулки. Так уж условия поставлены.

[This message has been edited by bemby (edited 16-03-2001).]

bemby · Post by **bemby** » 16 Mar 2001 23:03

А задачку с шариком можно решить за 33 (или около того) броска - начать с 3-го этажа и двигаться вверх, пропуская каждый раз по два. Если шарик разобьется - спустится на этаж ниже и кинуть второй. Если он тоже - значит ответ этажом ниже.

Можно совместить это решение с методом дихотомии - т.е. начать с 50-го этажа и если шарик не разобьется, можно применить метод, описанный выше и тогда бросков будет в два раза меньше.

Nataly · Post by **Nataly** » 16 Mar 2001 23:23

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[i:4493c5f785]
1) У вас есть два одинаковых стеклянных шарика. Перед вами 100-этажное здание. Лестница с площадками на каждом этаже. Шарик имеет определенную прочность, т.е. его можно уронить с некоего этажа, не разбив, но вот если уронить со следующего этажа, то он уже разобьется.
Ваша задача — найти этот самый предел прочности шарика. Вопрос в том, кому за сколько бросаний это удастся сделать. Кто сможет предложить оптимальный вариант?

Чтобы было понятнее - пример: начнем с 50-го этажа и будем прибавлять по одному. Если первый шарик сразу разобьется, перейдем на первый этаж и опять начнем двигаться вверх. При такой схеме хватит 50 бросаний. Очевидно, что это плохой (неоптимальный) способ. Кто предложит лучше?
[/i:4493c5f785]<HR></BLOCKQUOTE>

19?

Бросаем с 10-ого этажа первый шарик. Если он разбился, то у нас еше 9 ступенек и 9 попыток, с первой по 9-тую. Таким образом нам надо 10 бросков.
Если не разбился, то кидаем с 20-ого этажа, если разбился, то кидаем начиная с 11-ого. Получаем максимим 9 попыток, люс те 2 для первого шарика и того 11 попыток.
Если не разбился, то кидаем с 30-ого, если разбился, то 9 плюс 3.
...
Если разбился на 100-ом этаже, то 9+10 попыток. Т.е. самый плохой случай это 99-ая ступенька.

Получается 19 попыток.

Про шарики есть еше одна задачка. Дано 100 шариков и 100 ступенек. Все тоже самое. Сколько вам шариков понадобится, чтобы определить "прочность" шариков [img:4493c5f785]http://www.privet.com/ubb/smile.gif[/img:4493c5f785].

------------------
Nataly

Petrovich · Post by **Petrovich** » 16 Mar 2001 23:31

<BLOCKQUOTE>quote:<HR>Originally posted by Zaphod:
[i:e689c8bab8]Что радует - два таких топика - и гениальные знатоки всего растворились во мраке. И становится где-то ясно, кто есть кто. Приятно![/i:e689c8bab8]<HR></BLOCKQUOTE>

А вам не приходит в голову мысль, что "гениальным знатокам всего" не интересно смотреть на задачки прорешанные еще в далёкой юности. Хотя каждому своё, помню на втором или на третьем курсе, выяснилось, что примерно половина студентов не знает что такое "Лента Мебиуса" Мне приятно тоже. [img:e689c8bab8]http://www.privet.com/ubb/smile.gif[/img:e689c8bab8]

Joker · Post by **Joker** » 16 Mar 2001 23:34

Можно достичь результата, [b:972d92c7c1]значительно[/b:972d92c7c1] лучшего, чем 19 [img:972d92c7c1]http://www.privet.com/ubb/wink.gif[/img:972d92c7c1]
Хотя Натали безусловно на верном пути. Опять молодец! [img:972d92c7c1]http://www.privet.com/ubb/smile.gif[/img:972d92c7c1]

[This message has been edited by Joker (edited 16-03-2001).]

Zaphod · Post by **Zaphod** » 16 Mar 2001 23:49

Упс

[This message has been edited by Zaphod (edited 16-03-2001).]

Вот именно, упс. Задачу номер 1 можно сделать вкуснее, если брать, к примеру, все те же 3 шарика (два из исходного варианта задачи и один бывший мыльный - они же вместе могли послужить для решения задачи номер 0) и 212 этажей.

[This message has been edited by Zaphod (edited 16-03-2001).]

Joker · Post by **Joker** » 17 Mar 2001 00:00

<BLOCKQUOTE>quote:<HR>Originally posted by Petrovich:
[i:77a1e1246d] А вам не приходит в голову мысль, что "гениальным знатокам всего" не интересно смотреть на задачки прорешанные еще в далёкой юности.[/i:77a1e1246d]<HR></BLOCKQUOTE> Сочувствую "знатокам", песок из которых сыплется до такой степени, что они добровольно отчислили себя из собственной юности и отреклись от того, что их тогда интересовало. Воистину возраст есть состояние души [img:77a1e1246d]http://www.privet.com/ubb/smile.gif[/img:77a1e1246d]

А еще — делать умную и многозначительную физиономию при слабых умств... ОК, ОК, без наездов... я просто вижу, как умело владеют этим оружием менеджеры у меня в конторе [img:77a1e1246d]http://www.privet.com/ubb/biggrin.gif[/img:77a1e1246d]

Petrovich · Post by **Petrovich** » 17 Mar 2001 00:09

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[i:535afecb6b]Сочувствую "знатокам", песок из которых сыплется до такой степени, что они добровольно отчислили себя из собственной юности и отреклись от того, что их тогда интересовало. Воистину возраст есть состояние души [img:535afecb6b]http://www.privet.com/ubb/smile.gif[/img:535afecb6b][/i:535afecb6b]<HR></BLOCKQUOTE>

Ну так давайте еще таблицу умножения повторим [img:535afecb6b]http://www.privet.com/ubb/biggrin.gif[/img:535afecb6b]

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[i:535afecb6b]А еще — делать умную и многозначительную физиономию при слабых умств... ОК, ОК, без наездов... я просто вижу, как умело владеют этим оружием менеджеры у меня в конторе [img:535afecb6b]http://www.privet.com/ubb/biggrin.gif[/img:535afecb6b][/i:535afecb6b]<HR></BLOCKQUOTE>

А вы предлагаете делать умную и значительную физиономию в сотый раз решая например The Monty Hall Problem [img:535afecb6b]http://www.privet.com/ubb/biggrin.gif[/img:535afecb6b]

P.S. Zaphoda то кто за язык дергал?

tengiz · Post by **tengiz** » 17 Mar 2001 00:16

14? (полный ответ письмом, чтобы не портить удовольствие другим).

Cheers.

[This message has been edited by tengiz (edited 16-03-2001).]

DV · Post by DV » 17 Mar 2001 00:33

<BLOCKQUOTE>quote:<HR>Originally posted by Petrovich:
[i:3e5fce6453] А вы предлагаете делать умную и значительную физиономию в сотый раз решая например The Monty Hall Problem [img:3e5fce6453]http://www.privet.com/ubb/biggrin.gif[/img:3e5fce6453]

[/i:3e5fce6453]<HR></BLOCKQUOTE>

Why "в сотый раз"? Couldn't pass the Bayesian Probability 101 exam? Just a joke. No offense meant.

Zaphod · Post by **Zaphod** » 17 Mar 2001 00:47

<BLOCKQUOTE>quote:<HR>Originally posted by Petrovich:
[i:2645097929]P.S. Zaphoda то кто за язык дергал?[/i:2645097929]<HR></BLOCKQUOTE>

Видишь ли, Петрович, мне на работе скушно последнее время, вот я и валяю дурака, дразню публику. Ну и поделился наблюдениями. [img:2645097929]http://www.privet.com/ubb/smile.gif[/img:2645097929] Ты еще спроси, зачем Джокер народу нервы и самооценку портит?