Задачки-2

sha · Post by **sha** » 18 Mar 2001 18:36

Народ вы что?? Какая дихотомия? Какое золотое сечение?

Шариков -- 2 штуки. Следовательно "вниз" может быть только один ход. Все остальное должно быть тихонечно-тихонечко [img:949fc8e115]http://www.privet.com/ubb/smile.gif[/img:949fc8e115] наверх.

Нарисуйте более оптмальный вариант, чем 14, а?

PavelM · Post by **PavelM** » 18 Mar 2001 20:43

sorry, proglyadel chto ih tolko 2

V takom sluchae reshenie takovo:

Berem samyi nevygonyi sluchai - kogda sharik ne razbivaetsa daje s sotogo etaga. Poluchaem chto po lubomu posle broska na 98 etage nam nado imet' 2 popytki v zapase (dlya 99 i 100). Odnako eti ostavshiesya popytki mojno primenit' k 97 i 96 esli na 98 sharik razbivatsa, takim obrazom posle broska na 95 etage nado imet' uje 3 popitki i tak dalee, poluchaem ryad:

100,99,98,95,91,86,80,73,65,56,46,35,23,10

itogo 14

Vrode optimalnee nikak

sha · Post by **sha** » 19 Mar 2001 00:42

Вот тогда дихотомия с 7 попытками. А подвох в чем?

Vladimir Patryshev · Post by **Vladimir Patryshev** » 19 Mar 2001 06:03

<BLOCKQUOTE>quote:<HR>Originally posted by PavelM:
[i:faa7135d64]
Eta zadacha s sharikami ne chto inoe kak poisk tochki ekstremuma empiricheskim putem. Dlya etogo est' kucha metodov:
- metoda kasatelnyh (Newtona);
- metod delenia popolam (dihotomia);
- metod zolotogo sechenia; (0,618/0,382 po-moemu)
Dlya kajdogo iz metodov est' formula rascheta kolichestva iteratsii dlya zadannoy tochnosti. Naskolko ya pomnyu dokazano chto metod zolotogo sechenia odin iz samyh optimalnyh, ya tolko vot formulu ne pomnyu.

No legko pokazat' chto etot metod daet maximum 5 popytok pri blagopriatnom raspologenii iskomoi tochki i 10 popytok pri samom neblagopriatnom pologenii.

takaya vot petrushka
[/i:faa7135d64]<HR></BLOCKQUOTE>

Ах перестаньте. Никакого не экстремума. Просто поиска.

А еше точнее, задача сводится к поиску минимального основания системы счисления, при котором числа до заданного могут быть представлены заданным числом цифр.

Vladimir Patryshev · Post by **Vladimir Patryshev** » 19 Mar 2001 06:10

<BLOCKQUOTE>quote:<HR>Originally posted by PavelM:
[i:cd7c289d77]sorry, proglyadel chto ih tolko 2

V takom sluchae reshenie takovo:

Berem samyi nevygonyi sluchai - kogda sharik ne razbivaetsa daje s sotogo etaga. Poluchaem chto po lubomu posle broska na 98 etage nam nado imet' 2 popytki v zapase (dlya 99 i 100). Odnako eti ostavshiesya popytki mojno primenit' k 97 i 96 esli na 98 sharik razbivatsa, takim obrazom posle broska na 95 etage nado imet' uje 3 popitki i tak dalee, poluchaem ryad:

100,99,98,95,91,86,80,73,65,56,46,35,23,10

itogo 14

Vrode optimalnee nikak

[/i:cd7c289d77]<HR></BLOCKQUOTE>

Гениально! Но Вы же обещали 10 попыток!

И еще... а если он таки возьмет да и разобьется на 100-м этаже? Сколько попыток останется?

В целом, мне Ваше решение чем импонирует: оптимальным подходом. "Если шарик не разобьется на 47-м этаже, но разобьется на 48-м, то сначала надо попробовать 47-й, а потом - 48-й".

Nataly · Post by **Nataly** » 19 Mar 2001 09:50

А вот на такую задачку кто и что скажет? Все теже шарики. Дано 100 шариков и 100 ступенек. Все тоже самое. Сколько вам шариков понадобится, чтобы определить "прочность" шариков?

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

PavelM · Post by **PavelM** » 19 Mar 2001 18:21

<BLOCKQUOTE>quote:<HR>Originally posted by Vladimir Patryshev:
[i:6298bab37c] Гениально! Но Вы же обещали 10 попыток!

И еще... а если он таки возьмет да и разобьется на 100-м этаже? Сколько попыток останется?

В целом, мне Ваше решение чем импонирует: оптимальным подходом. "Если шарик не разобьется на 47-м этаже, но разобьется на 48-м, то сначала надо попробовать 47-й, а потом - 48-й".[/i:6298bab37c]<HR></BLOCKQUOTE>

Vladimir,
Smotrim vnimatel'no.
Nachinaem s 10 etaga, esli ne rasbilsa - perehodim na 23 etag, nu a esli rasbilsa to osatetsa odin sharik i im probuem etagi s 1 po 9, nu i prodoljite sami dal'she.

Esli na 98 etage sharik ne razobietsa, ostaetsa 2 sharika i 2 etaga, mojete probovat' 99,100 ili 100,99 ne vajno.
Nu a esli razbilsa to probuete 96 i 97, poskol'ku na 95 ne rabilsa.

Zaphod · Post by **Zaphod** » 19 Mar 2001 19:23

<BLOCKQUOTE>quote:<HR>Originally posted by Talya:
[i:76515a8569]Бочка. В бочке четыре отверстия, в каждом из которых находится выключатель. Расположенная на бочке лампочка загорается, если все выключатели находятся в одинаковом положении. Вы можете одновременно просунуть руки в любые два отверстия и поменять или нет положения находящихся в них выключателей. После чего бочка вращается вокруг своей оси произвольным образом.[/i:76515a8569]<HR></BLOCKQUOTE>

Решение зависит от того, что вы называете "после чего". Если это "чего" - вынимание рук, то решается в три действия. Если это "чего" - щелканье выключателями - то короче, чем в пять, у меня не получается.

Ну? Опубликовать эти три действия?

Zaphod · Post by **Zaphod** » 19 Mar 2001 19:32

<BLOCKQUOTE>quote:<HR>Originally posted by PavelM:
[i:50819f0d55] Esli na 98 etage sharik ne razobietsa, ostaetsa 2 sharika i 2 etaga, mojete probovat' 99,100 ili 100,99 ne vajno.
Nu a esli razbilsa to probuete 96 i 97, poskol'ku na 95 ne rabilsa.[/i:50819f0d55]<HR></BLOCKQUOTE>

Не могли бы Вы: а) сформулировать задачу, которую Вы решаете; б) доказать, что то, что Вы привели, является решением этой задачи?

Nataly · Post by **Nataly** » 19 Mar 2001 19:34

<BLOCKQUOTE>quote:<HR>Originally posted by Zaphod:
[i:6aba4e49cd] Не могли бы Вы: а) сформулировать задачу, которую Вы решаете; б) доказать, что то, что Вы привели, является решением этой задачи?[/i:6aba4e49cd]<HR></BLOCKQUOTE>

[img:6aba4e49cd]http://www.privet.com/ubb/biggrin.gif[/img:6aba4e49cd] [img:6aba4e49cd]http://www.privet.com/ubb/biggrin.gif[/img:6aba4e49cd] [img:6aba4e49cd]http://www.privet.com/ubb/biggrin.gif[/img:6aba4e49cd]

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

moleg · Post by **moleg** » 19 Mar 2001 19:39

Originally posted by Vladimir Patryshev:
[i:9317c39e6e] Никакого не экстремума. Просто поиска.[/i:9317c39e6e] (поиск ради поиска?) или [i:9317c39e6e]поиск минимального...[/i:9317c39e6e] (это ли не экстремум?)

[i:9317c39e6e]А еше точнее, задача сводится к поиску минимального основания системы счисления, при котором числа [b:9317c39e6e]до заданного[/b:9317c39e6e] могут быть представлены [b:9317c39e6e]заданным[/b:9317c39e6e] числом цифр.[/i:9317c39e6e]
Насколько я понимаю, задано только 2 числа - 100(этажей) и 2(шарика). Стало быть минимальное основание будет 10, но число попыток в этом случае равно 19, как было показано ранее.
Владимир, можно Вас попросить, доказать эквивалентность этих задач.

Joker · Post by **Joker** » 19 Mar 2001 19:40

<BLOCKQUOTE>quote:<HR>Originally posted by PavelM:
[i:42f5e14757]V takom sluchae reshenie takovo: ...
[/i:42f5e14757]<HR></BLOCKQUOTE> Что-то я не пойму, что вы, собственно, обсуждаете. Какое золотое сечение? Какая дихотомия? [img:42f5e14757]http://www.privet.com/ubb/smile.gif[/img:42f5e14757] Решение было найдено и опубликовано [b:42f5e14757]дважды[/b:42f5e14757]. Какой смысл его переписывать в третий раз? Вот если Вы предложите вариант лучше, чем за 14 бросаний, тогда другое дело.
Но пока ничего конструктивного предложено не было...

Zaphod:
Извини, я не врубился насчет "вынимания рук". Это о чем? Решение в 5 шагов опубликовано очень подробно выше. Есть другое, короче? Расскажи! [img:42f5e14757]http://www.privet.com/ubb/wink.gif[/img:42f5e14757]

Nataly · Post by **Nataly** » 19 Mar 2001 20:11

<BLOCKQUOTE>quote:<HR>Originally posted by sha:
[i:f8e778f1b9]Вот тогда дихотомия с 7 попытками. А подвох в чем? [/i:f8e778f1b9]<HR></BLOCKQUOTE>

А причем тут дихотромия и какие такие 7 попыток?

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

prud · Post by **prud** » 19 Mar 2001 20:29

<BLOCKQUOTE>quote:<HR>Originally posted by Zaphod:
[i:946f7c1d25] Решение зависит от того, что вы называете "после чего". Если это "чего" - вынимание рук, то решается в три действия. Если это "чего" - щелканье выключателями - то короче, чем в пять, у меня не получается.

Ну? Опубликовать эти три действия?

[/i:946f7c1d25]<HR></BLOCKQUOTE>

1.Руки вынимать - иначе оторвет же...
2.Публикуйте.

Zaphod · Post by **Zaphod** » 19 Mar 2001 20:34

<BLOCKQUOTE>quote:<HR>Originally posted by Joker:
[i:adab7eb3c7]Zaphod:
Извини, я не врубился насчет "вынимания рук". Это о чем? Решение в 5 шагов опубликовано очень подробно выше. Есть другое, короче? Расскажи! [img:adab7eb3c7]http://www.privet.com/ubb/wink.gif[/img:adab7eb3c7][/i:adab7eb3c7]<HR></BLOCKQUOTE>

Дык.

Действие 1. Вот мы сунули руки в две противоположные дырки. И не вынимаем!
Щелк выключатели вверх - не работает! (Если работает - приехали.) Щелк вниз - не работает! (Если работает - приехали.) Значит, имеем что? Две оставшиеся дырки - в противофазе. Ну и хорошо, и оставляем один выключатель включенным, другой выключенным. И вынимаем руки. Теперь мы находимся в состоянии действия 3 уже приведенного ранее решения задачи. А именно - два соседа включены, другие два - выключены.

Бочка вертится.

Действие 2. Суем руки в соседние дырки. Меряем состояние обоих выключателей. Если они были в фазе - задача решена. Если же они были не в фазе, то теперь состояние таково: каждая противоположно-лежащая пара - в фазе.

Бочка вертится.

Действие 3. Суем руки в противоположные дырки и меняем фазу. Лампочка зажигается, пиво льется, задача решена.