Задачка про стоэтажное здание

Brat Levon · Post by **Brat Levon** » 26 Oct 2001 17:07

Есть стоэтажное здание. У вас имеется два одинаковых куриных (для определенности [img:5629ae39c5]images/smiles/icon_smile.gif[/img:5629ae39c5]) яйца. Про здание известно, что есть этаж с максимальным номером такой, что, если скинуть с него (и с любого этажа ниже этого) яйцо не разбивается, а если подняться на этаж выше - то разобьется. Вопрос - какое минимальное количество сбрасываний гарантирует нахождение такого этажа?

Dmitry67 · Post by **Dmitry67** » 26 Oct 2001 17:49

Newsya · Post by **Newsya** » 26 Oct 2001 18:32

Melkor · Post by **Melkor** » 26 Oct 2001 19:06

<BLOCKQUOTE>quote:<HR>Originally posted by Brat Levon:
Есть стоэтажное здание. У вас имеется два одинаковых куриных (для определенности [img:04a094fc77]images/smiles/icon_smile.gif[/img:04a094fc77]) яйца. Про здание известно, что есть этаж с максимальным номером такой, что, если скинуть с него (и с любого этажа ниже этого) яйцо не разбивается, а если подняться на этаж выше - то разобьется. Вопрос - какое минимальное количество сбрасываний гарантирует нахождение такого этажа?<HR></BLOCKQUOTE>

Вообще-то, я обнаружил, что эта задача, как и задача с пиратами, здесь таки да уже обсуждалась. Причем условие задачи с пиратами несколько изменено, а эта разобрана очень подробно конкретно в данной формулировке... Просто надо выбрать не "show topics from the last 45 days", а все

marinamo · Post by **marinamo** » 28 Oct 2001 00:29

vladl · Post by **vladl** » 28 Oct 2001 01:48

<BLOCKQUOTE>quote:<HR>Originally posted by Newsya:
7?<HR></BLOCKQUOTE>

Nahodim max kolichestvo iteracij pri dvoichnom perebore sredi 100 elementov (etazhej), chto = 7.

[ 27-10-2001: Message edited by: vladl ]

Brat Levon · Post by **Brat Levon** » 28 Oct 2001 05:29

<BLOCKQUOTE>quote:<HR>Originally posted by vladl:

Nahodim max kolichestvo iteracij pri dvoichnom perebore sredi 100 elementov (etazhej), chto = 7.
<HR></BLOCKQUOTE>

Двоичный перебор здесь, я думаю, не пойдет. Например, вы сбросили яйцо с 50-го этажа - оно разбилось, потом сбросили с 25-го - оно тоже разбилось - и что Вы дальше будете делать?

Какой алгоритм приводит к 14, я тоже не знаю. Наилучший известный мне алгоритм требует немного больше бросков.

Brat Levon · Post by **Brat Levon** » 28 Oct 2001 05:31

<BLOCKQUOTE>quote:<HR>Originally posted by Dmitry67:
20 ?<HR></BLOCKQUOTE>

Этот ответ - самый распространенный. Но количество бросков можно уменьшить.

Drom · Post by **Drom** » 28 Oct 2001 06:30

кажется, здесь эта задачка была. 14.

vladl · Post by **vladl** » 28 Oct 2001 06:47

<BLOCKQUOTE>quote:<HR>Originally posted by Brat Levon:


Двоичный перебор здесь, я думаю, не пойдет. Например, вы сбросили яйцо с 50-го этажа - оно разбилось, потом сбросили с 25-го - оно тоже разбилось - и что Вы дальше будете делать?

Какой алгоритм приводит к 14, я тоже не знаю. Наилучший известный мне алгоритм требует немного больше бросков.<HR></BLOCKQUOTE>

Sorry, ja podumal, chto v sbrasivaniji jaic uchastvovalo mnogo ljudej, nu i kazhdogo po dva [img:9d1396a3d5]images/smiles/icon_smile.gif[/img:9d1396a3d5] kurinih.

fly · Post by **fly** » 28 Oct 2001 13:09

Почему не так?
1. Забираемся на 99 этаж. Если яйцо разбилось, то ответ=100, если нет, то
2. Спускаемся на 50 этаж. Бросаем. Если яйцо не разбилось, то нужно исследовать этажи с 51 по 98 =48 этажей, если да, то нужно исследовать этажи с 1 по 49=49 этажей. Это больше, поэтому
3. Спускаемся на 25 этаж. Бросаем. Если яйцо не разбилось, то нужно исследовать этажи с 26 по 49 =24 этажа, если да, то нужно исследовать этажи с 1 по 24=24 этажей, поэтому
4. Спускаемся на 13 этаж. Бросаем. Если яйцо не разбилось, то нужно исследовать этажи с 14 по 24 =11 этажей, если да, то нужно исследовать этажи с 1 по 12=12 этажей. Это больше, поэтому
5. Спускаемся на 7 этаж. Бросаем. Если яйцо не разбилось, то нужно исследовать этажи с 8 по 12 =5 этажей, если да, то нужно исследовать этажи с 1 по 6=6 этажей. Это больше, поэтому
6. Спускаемся на 4 этаж. Бросаем. Если яйцо не разбилось, то нужно исследовать этажи с 5 по 6 =2 этажа, если да, то нужно исследовать этажи с 1 по 3=3 этажа. Это больше, поэтому
7. Спускаемся на 2 этаж. Бросаем. Если яйцо не разбилось, то оно разобьется с 3 этажа, если да, то это 2 этаж, так как с первого этажа оно не разобьется по условию.
Итак ответ [img:2ab46b268a]images/smiles/icon_smile.gif[/img:2ab46b268a] требуется не более 7 тестов
[img:2ab46b268a]images/smiles/icon_smile.gif[/img:2ab46b268a]

marinamo · Post by **marinamo** » 28 Oct 2001 17:38

<BLOCKQUOTE>quote:<HR>Originally posted by Brat Levon:


Какой алгоритм приводит к 14, я тоже не знаю. Наилучший известный мне алгоритм требует немного больше бросков.<HR></BLOCKQUOTE>

Бросаем с 14 этажа, если разбилось исследуем этажи с 1 по 13-й. Если не разбилось прибавляем 13 этажей и бросаем с 27. Если разбилось исследуем с 15 по 26.
Если не разбилось прибавляем 12 и бросаем с 39 и т.д. При любом раскладе кол-во попыток не будет привышать 14.

-ЭР- · Post by **-ЭР-** » 28 Oct 2001 23:23

<BLOCKQUOTE>quote:<HR>Originally posted by Drom:
кажется, здесь эта задачка была. 14.<HR></BLOCKQUOTE>

Хорошо иметь алгоритм, такой, что как-бы не выпало, а количество шагов всегда одинаковое. Например, я первый раз бросаю с n-го этажа, второй - с (n + n - 1) -го, третий - с (n + n + n - 2) -го, и т.д.

Тогда, какая бы ситуация не сложилась, я всегда n раз в худшем случае брошу. Допустим, мне не везет - бросаю я бросаю, а оно все не бьется и не бьется. В этом случае я поднимаюсь вот на столько этажей:

n + (n - 1) + (n -2 ) + ... (n - k - 1) и это все равно 100 (или сколько надо) где k - это сколько раэ я бросал с "реперного" этажа.

По другому это будет

nk - k*k/2 = 100

или

n = 100/k + k/2

Мы хоти минимум, поэтому считаем dn/dk = -100/k*k + 1/2 = 0 или k = 14 (не проверил, что это действительно минимум, а не максимум. но думаю, что минимум), т.е.

n = 100/14 + 14/2 = 14.

Итого: бросать надо с 14, (14+14 -1)=27, (27+14-2)= 39, и так далее со всеми остановками, пока яйцо не треснет.

vladl · Post by **vladl** » 29 Oct 2001 09:06

<BLOCKQUOTE>quote:<HR>Originally posted by fly:
Почему не так?
1. Забираемся на 99 этаж. Если яйцо разбилось, то ответ=100, если нет, то
2. Спускаемся на 50 этаж. Бросаем. Если яйцо не разбилось, то нужно исследовать этажи с 51 по 98 =48 этажей, если да, то нужно исследовать этажи с 1 по 49=49 этажей. Это больше, поэтому
3. Спускаемся на 25 этаж. Бросаем. Если яйцо не разбилось, то нужно исследовать этажи с 26 по 49 =24 этажа, если да, то нужно исследовать этажи с 1 по 24=24 этажей, поэтому
4. Спускаемся на 13 этаж. Бросаем. Если яйцо не разбилось, то нужно исследовать этажи с 14 по 24 =11 этажей, если да, то нужно исследовать этажи с 1 по 12=12 этажей. Это больше, поэтому
5. Спускаемся на 7 этаж. Бросаем. Если яйцо не разбилось, то нужно исследовать этажи с 8 по 12 =5 этажей, если да, то нужно исследовать этажи с 1 по 6=6 этажей. Это больше, поэтому
6. Спускаемся на 4 этаж. Бросаем. Если яйцо не разбилось, то нужно исследовать этажи с 5 по 6 =2 этажа, если да, то нужно исследовать этажи с 1 по 3=3 этажа. Это больше, поэтому
7. Спускаемся на 2 этаж. Бросаем. Если яйцо не разбилось, то оно разобьется с 3 этажа, если да, то это 2 этаж, так как с первого этажа оно не разобьется по условию.
Итак ответ [img:28a5fec70b]images/smiles/icon_smile.gif[/img:28a5fec70b] требуется не более 7 тестов
[img:28a5fec70b]images/smiles/icon_smile.gif[/img:28a5fec70b]<HR></BLOCKQUOTE>

Ja tozhe tak dumal, no jaic malovato [img:28a5fec70b]images/smiles/icon_sad.gif[/img:28a5fec70b] vsego dva. Esli chasto bitsja budut, to skoro issjaknut.