Перед тем как кидаем яйцо вычисляем случайное число Х
Где Х - число от 1 до 3
Предположем яйцо разбиватся с 63 этажа.Обозначим это X.
1. 100/rand(1,3) ,выпало 66.66
66.66 > X,Да значит делим опять на 3
Взависимости от результата идем в лево или вправо.
Так как нам нужно знать только где > X то это делает вообще все очень очень просто.
Так как бинарный поиск работает на нахождения конкретного числа.
Это обыкновенный бинарный поиск.Но я бы делил не на 2 ,а на 3.
http://en.wikipedia.org/wiki/Binary_search_algorithm
Полная Версия: Еще задачки 2
| Цитата (twin @ 15.02.2015 - 13:55) |
| С 100-го нет смысла кидать. |
Все равно по идее сотый этаж проверять надо.
_____________
Свои мозги еще никто не отменял.
Телепатов нету.
| Цитата (Oyeme @ 15.02.2015 - 13:58) |
| Перед тем как кидаем яйцо вычисляем случайное число Х Где Х - число от 1 до 3 Предположем яйцо разбиватся с 63 этажа.Обозначим это X. 1. 100/rand(1,3) ,выпало 66.66 66.66 > X,Да значит делим опять на 3 Итд Это обыкновенный бинарный поиск.Но я бы делил не на 2 ,а на 3. http://en.wikipedia.org/wiki/Binary_search_algorithm |
Не совсем уверен, но мне кажется в данном случае це не канает, потому что у нас все 2 яйца. Worst Case проверить не удастся.
_____________
Свои мозги еще никто не отменял.
Телепатов нету.
| Цитата (waldicom @ 15.02.2015 - 12:59) | ||
Все равно по идее сотый этаж проверять надо. |
Это как в задаче про буратино. Буратине дали три яблока. Два он съел, сколько осталось? Три? А вот фиг. Не известно, сколько у него их было. Мораль: всегда обнуляйте переменные.
В условиях ясно сказано:
| Цитата |
| Известно что яйцо разбивается при падении, начиная с определенной высоты бросания. |
_____________
Если вам недостаточно собственных заблуждений, можно расширить их мнениями экспертов.
Нужно уважать мнение оппонета. Ведь заблуждаться - его святое право.
Настаивал, настаиваю и буду настаивать на своем. На кедровых орешках.
| Цитата (waldicom @ 15.02.2015 - 13:01) | ||
Не совсем уверен, но мне кажется в данном случае це не канает, потому что у нас все 2 яйца. Worst Case проверить не удастся. |
| Цитата |
| Нужно придумать алгоритм, позволяющий, имея только два яйца, определить этаж, начиная с которого яйца бьются, за наименьшее число попыток. |
Если яйцо разбилось в самом начале.Решение найдено.
Мы делаем поиск до тех пор пока яйцо не будет разбито.
Нам не нужно знать конкретный этаж.
| Цитата (Oyeme @ 15.02.2015 - 14:03) | ||
Если яйцо разбилось в самом начале.Решение найдено. Мы делаем поск до тех пор пока яйцо не будет разбито. Нам не нужно знать конкретный этаж. |
Как не нужно? Так можно сразу с сотого кинуть и все, задача решена. Или же я не так понял задачу.
_____________
Свои мозги еще никто не отменял.
Телепатов нету.
Oyeme
| Цитата |
| Если яйцо разбилось в самом начаде.Решение найдено. Мы делаем поск до тех пор пока яйцо не будет разбито. |
Если разобъется, поиск по этому алгоритму станет невозможен. Придется проверять всё, что ниже. А это минимум еще 33.
_____________
Если вам недостаточно собственных заблуждений, можно расширить их мнениями экспертов.
Нужно уважать мнение оппонета. Ведь заблуждаться - его святое право.
Настаивал, настаиваю и буду настаивать на своем. На кедровых орешках.
| Цитата (twin @ 15.02.2015 - 13:07) | ||
Oyeme
Если разобъется, поиск по этому алгоритму станет невозможен. |
Кроме бинарного поиска в голову ничего не приходит..
Или
Я бы только делал через формулы Лапласа
Остальное это гадание на гущей.
Формула
Oyeme, нужно узнать конкретный этаж, начиная с которого яйцо разбивается. Кроме того, я ж написал выше - тут нет вероятностей. Вон уже предложен алгоритм с МАХ = 18 (или 19), но и это не предел...
twin, waldicom, не ссорьтесь, горячие финские парни
Решение "десяток" неплохое, но не лучшее... думайте дальше
twin, waldicom, не ссорьтесь, горячие финские парни
Решение "десяток" неплохое, но не лучшее... думайте дальше
stump
сразу нет, но чисто из интереса - как это выглядит в применении к нашим яйцам ?
сразу нет, но чисто из интереса - как это выглядит в применении к нашим яйцам ?
Alchemist
А что, это похоже на ссору?
_____________
Если вам недостаточно собственных заблуждений, можно расширить их мнениями экспертов.
Нужно уважать мнение оппонета. Ведь заблуждаться - его святое право.
Настаивал, настаиваю и буду настаивать на своем. На кедровых орешках.
А что, это похоже на ссору?
_____________
Если вам недостаточно собственных заблуждений, можно расширить их мнениями экспертов.
Нужно уважать мнение оппонета. Ведь заблуждаться - его святое право.
Настаивал, настаиваю и буду настаивать на своем. На кедровых орешках.
Alchemist
Колись уже, интриган)))
_____________
Если вам недостаточно собственных заблуждений, можно расширить их мнениями экспертов.
Нужно уважать мнение оппонета. Ведь заблуждаться - его святое право.
Настаивал, настаиваю и буду настаивать на своем. На кедровых орешках.
Колись уже, интриган)))
_____________
Если вам недостаточно собственных заблуждений, можно расширить их мнениями экспертов.
Нужно уважать мнение оппонета. Ведь заблуждаться - его святое право.
Настаивал, настаиваю и буду настаивать на своем. На кедровых орешках.
| Цитата (twin @ 15.02.2015 - 14:02) | ||||||
Это как в задаче про буратино. Буратине дали три яблока. Два он съел, сколько осталось? Три? А вот фиг. Не известно, сколько у него их было. Мораль: всегда обнуляйте переменные. В условиях ясно сказано:
|
Эммм... Действительно, ступил
_____________
Свои мозги еще никто не отменял.
Телепатов нету.
Здесь расположена полная версия этой страницы.