Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 242
Кста, дом может иметь высоту 100 и четверть от ста и еще 3 этажа.
1
Интересно, но неверно =)
Задача не просто на логику, немного математики тоже нужно. Мой друг устраивался на позицию программиста ;)
Задача не просто на логику, немного математики тоже нужно. Мой друг устраивался на позицию программиста ;)
если это не верно, тогда неверно условие задачи ;)
Там есть слово "достоверно". Не понимаю просто как, бросив шарик один раз, можно узнать достоверно нужный нам факт...
Почему это "неверно" ? Предположим, что дом у нас такой, что шарик будет разбиваться уже при броске с первого этажа. Сбросив шарик сразу с первого этажа один раз, я сразу узнаю, что минимально необходимый этаж - первый. Больше никаких шагов мне делать не нужно. Формально, если следовать условию задачи, ответ правильный. Ну вот такой вот дом мне попался удобный.
Мы не знаем с какого этажа шарик разобьётся. Нам нужно выяснить ТОЧНОЕ количество шагов, которое нам нужно для того, чтобы ТОЧНО узнать с какого этажа он разобьётся.
А если он на первом этаже не разобьётся? Каковы действия дальше?
А если он на первом этаже не разобьётся? Каковы действия дальше?
В формулировке вопроса нет слова "точно". Там написано "какое минимальное количество шагов понадобится для того, чтобы узнать на каком именно этаже шарики начинают разбиваться". Минимальное количество шагов - один.
А если все-таки разобьется? ;)
> Мой друг устраивался на позицию программиста
в google
в google
Ваш комментарий неверный! Этот ответ правильный. Перечитайте условие задачи и согласитесь со мной!
Не читал комментарии, но ответ log 100 по основанию 2 в потолок, т.е 7 шагов
Не буду писать белым, так как посту уже 5 лет)
Не буду писать белым, так как посту уже 5 лет)
а) что такое шаг? один бросок? или 2 броска, по одному на шарик?
б) мм то есть если один шарик разбился, у нас остался лишь второй? и с этого момента у нас один шарик, который бить нельзя? тогда нам надо стремиться к минимизации суммы k + 100/k, вроде k=10 и ответ таким образом 20 =) влом думать начиная со слова вроде :(
б) мм то есть если один шарик разбился, у нас остался лишь второй? и с этого момента у нас один шарик, который бить нельзя? тогда нам надо стремиться к минимизации суммы k + 100/k, вроде k=10 и ответ таким образом 20 =) влом думать начиная со слова вроде :(
ответ: 50
не более 51
моя вторая и последняя попытка: 51
1
35
Пока всё неверно.
Есть один ответ с математическим обоснованием.
Есть один ответ с математическим обоснованием.
0 - если шарик разобъется уже на первом этаже - не нужно подниматься выше, следовательно ни одного шага не понадобится
14
Верно ;)
Кто хочет разгадать, не читайте это сообщение ;)
Кто хочет разгадать, не читайте это сообщение ;)
Так а почему шарика всего два? Если их всего два, тогда как ответ выше может быть правильным? Зачем именно два шарика, а не один?
Напишите ответ белыми буквами, плиз.
Объяснение словами. Кидаем с 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100. Это позволяет нам добиться минимизации количества шагов.
Математически это можно объяснить с помощью формулы натурального ряда. 100 = (n*(n+1))/2
При n=14 получается результат 105, при n=13 меньше ста. Поэтому ответ 14.
Математически это можно объяснить с помощью формулы натурального ряда. 100 = (n*(n+1))/2
При n=14 получается результат 105, при n=13 меньше ста. Поэтому ответ 14.
У вас тоже этажи не как у людей номеруются ? В нормальных небоскрёбах, в которых я бывал всё-таки первый этаж - внизу, 14-й - выше, а на самом верху - 100-й. А так - правильно, конечно...
простите за идеотский вопрос, но почему берется именно такое разложение??? почему к примеру не 10,20,30,40... ???
Ибо с вашим разложением получится 19 попыток, а не :)
угу.. ясно... а откуда следует само разложение???
Раз уже все карты раскрыты, то можно и в третий раз написать размышления.
1. Если бросать шарик подряд, начиная с 1-го этажа и до 100-го, то получим допустимое, но не оптимальное решение. Думаем, как его улучшить.
2. У нас ведь есть два шарика! Т.е., один можно разбить, получив с этого какую-то информацию. Например, если бросить его с 50-го этажа, то можно сразу узнать, какую половину здания дальше рассматривать. Это хорошо, но всё еще не оптимально.
3. А что если бросать шарик через какие-то промежутки? Например, бросать его на 10, 20, 30м этаже? Как только он разобьётся, мы будем знать, на каком промежутке искать дальше. Таким образом можно сократить количество бросков до 19ти. Но и этого нам мало.
4. Мы заметили, что если бросать с промежутком в 10, то если шарик разобьётся сразу, то вторым шариком мы сможем обнаружить нужный этаж гораздо раньше. Т.е., мы могли бы бросать сразу не с 10го этажа, а выше, и в итоге быстрее добрались бы до верха. Допустим, что мы решили бросать с N-го этажа. Тогда, очевидно, что если первый шарик разобьётся сразу, то нам понадобится еще max N-1 шагов, чтобы узнать нужный этаж. Т.е., в случае, если шарик разбивается сразу, нам нужно всего 1+N-1=N бросков. Ну, а что будет, если шарик сразу не разобьётся?
5. Первым броском мы отсекли N этажей. Т.е., мы можем перейти к той же задаче, что и раньше, только этажей стало меньше. На каком же этаже нужно бросить шарик еще раз? Очевидно, что на N-1(считая от отсечения). Действительно, если шарик разобьётся получим: 1(первый неудачный бросок)+1(бросок на N+N-1 этаже)+N-2(бросаний второго шарика) - количество бросаний, нужное для определения этажа, если шарик разобьётся в первую или во вторую попытку.
6. Продолжаем заниматься отсечением. Размеры отсечений у нас получаются N,N-1,N-2 и т.д. Логично, что отсечения когда-то должны закончится. Значит, случится, что сумма всех отсечений будет больше высоты здания. Т.е. N+N-1+N-2. По известной ф-ле суммы арифметической прогрессии, это будет равно N*(N+1)/2. Для того, чтобы сумма отсечений покрывала весь дом, достаточно N=14(а N=13 недостаточно).
7. Вот так. Можно проверить и убедиться.
Подробней уж никак не могу :)
1. Если бросать шарик подряд, начиная с 1-го этажа и до 100-го, то получим допустимое, но не оптимальное решение. Думаем, как его улучшить.
2. У нас ведь есть два шарика! Т.е., один можно разбить, получив с этого какую-то информацию. Например, если бросить его с 50-го этажа, то можно сразу узнать, какую половину здания дальше рассматривать. Это хорошо, но всё еще не оптимально.
3. А что если бросать шарик через какие-то промежутки? Например, бросать его на 10, 20, 30м этаже? Как только он разобьётся, мы будем знать, на каком промежутке искать дальше. Таким образом можно сократить количество бросков до 19ти. Но и этого нам мало.
4. Мы заметили, что если бросать с промежутком в 10, то если шарик разобьётся сразу, то вторым шариком мы сможем обнаружить нужный этаж гораздо раньше. Т.е., мы могли бы бросать сразу не с 10го этажа, а выше, и в итоге быстрее добрались бы до верха. Допустим, что мы решили бросать с N-го этажа. Тогда, очевидно, что если первый шарик разобьётся сразу, то нам понадобится еще max N-1 шагов, чтобы узнать нужный этаж. Т.е., в случае, если шарик разбивается сразу, нам нужно всего 1+N-1=N бросков. Ну, а что будет, если шарик сразу не разобьётся?
5. Первым броском мы отсекли N этажей. Т.е., мы можем перейти к той же задаче, что и раньше, только этажей стало меньше. На каком же этаже нужно бросить шарик еще раз? Очевидно, что на N-1(считая от отсечения). Действительно, если шарик разобьётся получим: 1(первый неудачный бросок)+1(бросок на N+N-1 этаже)+N-2(бросаний второго шарика) - количество бросаний, нужное для определения этажа, если шарик разобьётся в первую или во вторую попытку.
6. Продолжаем заниматься отсечением. Размеры отсечений у нас получаются N,N-1,N-2 и т.д. Логично, что отсечения когда-то должны закончится. Значит, случится, что сумма всех отсечений будет больше высоты здания. Т.е. N+N-1+N-2. По известной ф-ле суммы арифметической прогрессии, это будет равно N*(N+1)/2. Для того, чтобы сумма отсечений покрывала весь дом, достаточно N=14(а N=13 недостаточно).
7. Вот так. Можно проверить и убедиться.
Подробней уж никак не могу :)
Спасибо... теперь понял... незнание рядов меня подвело... =)))
вы спасли мою черепную коробку от взрыва =)
пошел писать ПСЖ =)
вы спасли мою черепную коробку от взрыва =)
пошел писать ПСЖ =)
"Вопрос: какое точное минимальное количество шагов понадобится для того, чтобы точно узнать на каком именно этаже шарики начинают разбиваться?"
Ну вот вам еще раз вопрос)
Представьте, что правильный ответ = с 1-го этажа.
А вы кидаете сначала 14, потом 1. У вас получилось точно 2.
А "точное минимальное" = 1.
Ну вот вам еще раз вопрос)
Представьте, что правильный ответ = с 1-го этажа.
А вы кидаете сначала 14, потом 1. У вас получилось точно 2.
А "точное минимальное" = 1.
Поясните, пожалуйста, вот это:
Мне, почему-то, не совсем очевидно… Почему не взять снова N? Или какое-то другое число?
На каком же этаже нужно бросить шарик еще раз? Очевидно, что на N-1(считая от отсечения).
Мне, почему-то, не совсем очевидно… Почему не взять снова N? Или какое-то другое число?
Если брать снова N, то получается что мы увеличиваем число требуемых испытаний для выявления искомого числа т.к. мы уже сделали один бросок чтоб продвинутся до второго N.
Например:
кинули на 14 — не разбился, кинули на 28 разбился, но нам потребуется теперь проверить 14 этажей, то есть общее число бросков = 1(один раз уже бросили) + (28-14) = 15. А если бы взяли N-1, то кидали с 27. И тогда число оставшихся требуемых проверок былоб 1 + (27-14) = 14.
Таким образом переходя от этажа к этажу мы не увлечиваем число требуемых бросков.
Например:
кинули на 14 — не разбился, кинули на 28 разбился, но нам потребуется теперь проверить 14 этажей, то есть общее число бросков = 1(один раз уже бросили) + (28-14) = 15. А если бы взяли N-1, то кидали с 27. И тогда число оставшихся требуемых проверок былоб 1 + (27-14) = 14.
Таким образом переходя от этажа к этажу мы не увлечиваем число требуемых бросков.
Ну... Если так, то вообще можно делить 100 на два без остатка, даже если округлять вверх то выйдет... 50, 25, 13, 7, 4, 2, 1 = 7 шагов.
не понимаю, ну бросите вы с 14го этажа, шарик разобьется, и как вы за один шарик выясните где между первым и 14м этажом он разбивается? :-/
А вообще это типичная задача динамического программирования.
есть так называемый "быстрый" алгоритм поиска, неужели с его помошью не будет меньше итераций? 100 50 25 13 7 4 2 ... или нет?:)
зы: поздно конечно, но интересно всеравно
зы: поздно конечно, но интересно всеравно
Если не жалко напишите объяснение.
Решал я задачу так: Возьмем число бросков в задаче за N. В таком случае первый этаж, на котором разобьется шар, определен двумя числами: номером броска первого шара, когда он разобьется и номером броска второго шара, когда он разобьется. Сумма этих бросков не должна превышать N.
Дальше записываем формулу количества возможных пар этих чисел: (N*(N+1))/2. Это число будет больше либо равно 99. Дальше решаем квадратное уравнение: N^2+N-198=0. Округляем один из корней до 14, потому что нам нужны целые числа. Вот отсюда и ответ.
Дальше записываем формулу количества возможных пар этих чисел: (N*(N+1))/2. Это число будет больше либо равно 99. Дальше решаем квадратное уравнение: N^2+N-198=0. Округляем один из корней до 14, потому что нам нужны целые числа. Вот отсюда и ответ.
А если на пальцах? У меня при мысленном моделировании получается никак не меньше 25 в самом худшем случае.
Т.е. если кадать первый шарик сначала с 51 этажа, а затем в зависимости от того, разобъётся он или нет начать либо со 2 до 48, либо с 53 до 99, постоянно перепрыгивая через 1 этаж, то 14 никак не получается.
Заранее спасибо.
Т.е. если кадать первый шарик сначала с 51 этажа, а затем в зависимости от того, разобъётся он или нет начать либо со 2 до 48, либо с 53 до 99, постоянно перепрыгивая через 1 этаж, то 14 никак не получается.
Заранее спасибо.
На пальцах чуть выше в комментариях VaNcHeR объяснил. Я могу свой вариант привести: первая попытка будет с 14 этажа, если разбивается, то идем с первого этажа до 13. В сумме максимум будет 14 попыток. Если на 14 этаже не разбивается, то прибавляем 14-1=13 этажей, кидаем с 27, если разбивается, то начинаем с 15 проверять, опять же за 14 попыток найдем нужный этаж. Ну и так далее, пока не найдем нужный.
у меня при мысленном моделировании получалось сразу девятнадцать - пробовать с десятого через десять, если бьётся - минус шаг плюс единица и по порядку, пока не)
Но это, конечно, первоевголовуприходящее. В варианте же с четырнадцатью, идёте с четырнадцати, и каждый раз уменьшаете промежуток на единицу. Если бьется на четырнадцатом этаже - остаётся проверить предыдущие 13, на 14+13 (два шага сделано) - предыдущее двенадцать и т.д.
Но это, конечно, первоевголовуприходящее. В варианте же с четырнадцатью, идёте с четырнадцати, и каждый раз уменьшаете промежуток на единицу. Если бьется на четырнадцатом этаже - остаётся проверить предыдущие 13, на 14+13 (два шага сделано) - предыдущее двенадцать и т.д.
Я, если честно, тоже не понимаю. На мой дилетантский взгляд - задача чисто эмпирическая. Если я буду кидать шарики по одному начиная с 1 этажа, потом со 2-го и так далее до того момента, как один из шариков разобьется от падения, то, фактически, количество попыток будет = номеру этажа, при кидании с которого разбивается шарик (прошу прощения за туфтологию). При этом результат будет зависеть от качества стекла.
Шариков всего 2, поэтому, если начинать с высоких этажей, можно лишиться шариков до завершения эксперимента.
Шариков всего 2, поэтому, если начинать с высоких этажей, можно лишиться шариков до завершения эксперимента.
5 вариантов?
ответ: 66
Сдается мне, что задача формулируется как-то иначе...
Предложите свою версию ;)
Ну, как минимум, не на каком этаже шарики начинают разбиваться, а при сбрасывании с какого этажа. И наверно нужно определить максимальное, а не минимальное количество шагов, т.к. минимальное может быть любым в пределах от одного до правильного ответа (не вычислял).
Точную формулировку предложить сложно, так как разные люди по-разному трактуют слова. Я попытался изложить условие наиболее понятно и доступно, но Ваши исправления в целом верны, особенно первое.
Максимальное минимальное, как-то так )
Точная формулировка должна включать в себя и слово "минимальный" и "максимальный". То есть минимум максимума: максимум по всем входам, минимум по всем стратегиям. Классическая формулировка "за какое минимальное число шагов мы можем гарантированно определить этаж в самом худшем [для нас] случае ?"
Если человек подлавливает тебя на формулировке и говорит что минимум - это один бросок, то нужно сказать "молодец - а теперь сформулируй задачу так, чтобы она была нетривиальной". Так как там только один небессмысленный вариант, то дальше всё понятно...
Если человек подлавливает тебя на формулировке и говорит что минимум - это один бросок, то нужно сказать "молодец - а теперь сформулируй задачу так, чтобы она была нетривиальной". Так как там только один небессмысленный вариант, то дальше всё понятно...
Да, 14 всё-таки. Задачка ничего так, но идея видится почти сразу. Жалко, много сильно неверных ответов
18?
Вопрос неправильно задан, какое точно не "минимальное", а "максимальное".
Максимальное 34. Первый раз кидаем шарик на 3 этаже, если разбивается, то идём на 1 и кидаем второй шарик, если он не разбился, то правильный ответ 2 этаж.
Каждый раз идём на +3 этажа. Если шарик разбивается, то спускаемся на -2. Таким образом 100/3=33 +1 в остатке. Максимально 34 шага. На 99 добираемся за 33, и спускаемся на 97 последний раз. То есть самый неудачный вариант, если шарик рабивается на 97 или 98 этаже, много походить придётся. А если он и на 100 на разбивается?
34!
Можно ещё подойти как программист и математик. И написать алгоритм для решения задачи с 3, 4 шариками, 100, 200 этажей. Но как?
Попробуем?
Если шарика 2, то шаг +3. То есть делим число этажей на 3 и прибавляем 1.
Если шариков 3? Шаг будет ... 6
Если 4 шарика? Шаг будет ... 12
Если 5 шариков? Шаг будет ... 24
То есть шаг=3*(2 в_степени(число_шариков-2))
Формула(шариков больше 3!) = 3*(2 в_степени(число_шариков-2))+1
Максимальное 34. Первый раз кидаем шарик на 3 этаже, если разбивается, то идём на 1 и кидаем второй шарик, если он не разбился, то правильный ответ 2 этаж.
Каждый раз идём на +3 этажа. Если шарик разбивается, то спускаемся на -2. Таким образом 100/3=33 +1 в остатке. Максимально 34 шага. На 99 добираемся за 33, и спускаемся на 97 последний раз. То есть самый неудачный вариант, если шарик рабивается на 97 или 98 этаже, много походить придётся. А если он и на 100 на разбивается?
34!
Можно ещё подойти как программист и математик. И написать алгоритм для решения задачи с 3, 4 шариками, 100, 200 этажей. Но как?
Попробуем?
Если шарика 2, то шаг +3. То есть делим число этажей на 3 и прибавляем 1.
Если шариков 3? Шаг будет ... 6
Если 4 шарика? Шаг будет ... 12
Если 5 шариков? Шаг будет ... 24
То есть шаг=3*(2 в_степени(число_шариков-2))
Формула(шариков больше 3!) = 3*(2 в_степени(число_шариков-2))+1
Правильный ответ и решение есть выше.
Каюсь, вопрос сформулирован не совсем корректно, в следующий раз очень постараюсь, чтобы не было путаницы =(
Каюсь, вопрос сформулирован не совсем корректно, в следующий раз очень постараюсь, чтобы не было путаницы =(
С Формулай попутал. Не +1, а более сложнее.
Нужен минимум максимума, на самом деле. А вопрос формулируется как "за какое минимальное число шагов мы можем гарантированно определить этаж в самом худшем (для нас) случае ?".
Я худею, дорогая редакция. Тривиальная задача из маткружка. Если вы кидаете шарик с этажа L, то он либо разбивается, либо нет. Если он разбился, то придётся перебирать этажи L+1, L+2, ..., N уже по одному (выбора нет), если не разбился, то имеем ту же задачу. То есть если обозначить максимальное число этажей, обслуживаемых k бросками как f(k), то f(k)=f(k-1)+k, f(2)=3. Можно написать точную фурмулу (там будет участвовать корень квадратный и целая часть), можно просто посчитать что f(2)=3, f(3)=6, f(4)=10, f(5)=15, f(6)=21, f(7)=28, f(8)=36, f(9)=45, f(10)=55, f(11)=66, f(12)=78, f(13)=91, f(14)=105. 14 бросков как и насчитал OlegD.
Веселее задачка, скажем, с четырьма шариками, но если решить эту не методом угадывания, то она тоже становится несложной, а вот если сказать что шариков четыре с самого начала... это уже садизм...
Веселее задачка, скажем, с четырьма шариками, но если решить эту не методом угадывания, то она тоже становится несложной, а вот если сказать что шариков четыре с самого начала... это уже садизм...
А как белым то написать?
У меня получилось - 7
У меня получилось - 7
Чьёрт побери! Я прошу прощения, но я правильно написал фонт колор="вайт!" бла бла бла /фонт
Незнаю чего оно не сработало. А, помоему, перенос строки оно не так понимает . . .
Задачу решал последовательными приближениями. Кидаем на сотом и 50,если бьется и тот и тот, то кидаем на 25, если и этот бьется, то кидаем на 12, и так далее - 7 шагов - 7 шаров, разве нет? Ну или вверх выше 50-го этажа если на сотом разбился на 50 нет. Разве не так . . .
Незнаю чего оно не сработало. А, помоему, перенос строки оно не так понимает . . .
Задачу решал последовательными приближениями. Кидаем на сотом и 50,если бьется и тот и тот, то кидаем на 25, если и этот бьется, то кидаем на 12, и так далее - 7 шагов - 7 шаров, разве нет? Ну или вверх выше 50-го этажа если на сотом разбился на 50 нет. Разве не так . . .
А есть ещё шарики?
А то я один сломал, а другой потерял :(
А то я один сломал, а другой потерял :(
я думаю, все же 7, как выше написал MrDee, так же посчитала. так же как задача про взвешивание монеток с целью определить фальшивую
задача поставлена неверно:
"Вопрос: какое точное минимальное количество шагов понадобится для того, чтобы точно узнать на каком именно этаже шарики начинают разбиваться?"
точное минимальное мы не знаем, мы знаем точное максимальное - 14. А минимальное может быть 1,2,3,..14
"Вопрос: какое точное минимальное количество шагов понадобится для того, чтобы точно узнать на каком именно этаже шарики начинают разбиваться?"
точное минимальное мы не знаем, мы знаем точное максимальное - 14. А минимальное может быть 1,2,3,..14
я минут 10 не мог понять, почему кидая шарики с 100 этажа они начнут разбиваться на n-ом. :)
теперь понял, что мы иден не сверху-вниз, а наоборот :))
теперь понял, что мы иден не сверху-вниз, а наоборот :))
Я знаю ответ на эту задачку - один из шариков пиз*ит!
Помню когда прочитал эту шутку (про черепашек) по полу катался, только что вспомнил - опять катаюсь.
Помню когда прочитал эту шутку (про черепашек) по полу катался, только что вспомнил - опять катаюсь.
Уже наверное белым писать и не нужно? Вроде правильный ответ 14 уже пишут все кому не лень.
А вот у меня тоже, как у MrDee и liolia вышло минимально стопроцентное число бросков стеклошаров – 7.
Не помню уже, слава богу, математические формулы и методы, но суть такова приблизительно – бросаем шар с 50 этажа, с середины то есть. И смотрим разбился он или уцелел. И дальше уточняем этаж методом выбора серединного из предполагаемых. Ну, например, если разбился, выбираем 25 этаж. И так далее. Разбился на четвертаке – выбираем 13, на тринадцатом – 8 и таким макаром за 7 шагов мы точно поймем на каком этаже шарик начинает не разбиваться (или разбиваться).
Логика такая. Формулы формулировать лень.
А вот у меня тоже, как у MrDee и liolia вышло минимально стопроцентное число бросков стеклошаров – 7.
Не помню уже, слава богу, математические формулы и методы, но суть такова приблизительно – бросаем шар с 50 этажа, с середины то есть. И смотрим разбился он или уцелел. И дальше уточняем этаж методом выбора серединного из предполагаемых. Ну, например, если разбился, выбираем 25 этаж. И так далее. Разбился на четвертаке – выбираем 13, на тринадцатом – 8 и таким макаром за 7 шагов мы точно поймем на каком этаже шарик начинает не разбиваться (или разбиваться).
Логика такая. Формулы формулировать лень.
Да, друзья, а как же деление отрезка пополам?
Целочисленное решение лежит на отрезке - 1..100. Функция - неубывающая.
Шаг 1: Бросаем с 50: 1..49, 50 (знаем результат - разбился или нет), 51..100
Шаг 2: Пусть например разбился, идем ниже, на 25: 1..24, кидаем с 25, 26..49
Шаг 3: 1..12, кидаем с 13, 14..24
Шаг 4: 1..6, кидаем с 7, 7..12
Шаг 5: 1..3, кидаем с 4, 5..6
Шаг 6: 1, кидаем с 2, 3
Ответ гарантированно становится известным после 6 шага.
Поправьте, если не прав...
Целочисленное решение лежит на отрезке - 1..100. Функция - неубывающая.
Шаг 1: Бросаем с 50: 1..49, 50 (знаем результат - разбился или нет), 51..100
Шаг 2: Пусть например разбился, идем ниже, на 25: 1..24, кидаем с 25, 26..49
Шаг 3: 1..12, кидаем с 13, 14..24
Шаг 4: 1..6, кидаем с 7, 7..12
Шаг 5: 1..3, кидаем с 4, 5..6
Шаг 6: 1, кидаем с 2, 3
Ответ гарантированно становится известным после 6 шага.
Поправьте, если не прав...
Полностью соглашусь с человеком. Алгоритм половинного деления. Используется в поиске и сортировках.
"Блин - Хабрахабр упал, и я не мог ответить." Насколько я помню, только так и решали схожие задачи на первом курсе (язык Pascal, как сейчас помню). И это, имхо, самый "правильно-человеческий" ответ.
Мне кажется, что 6 - правильная цифра для варианта с безлимитныи количеством шариков. Но, так как шариков всего 2, то они могут все разбиться до получения результата методом половинного деления.
Шаров-то два всего
деление отрезка пополам пришло в голову в первую очередь
но на 25 этаже второй шарик тоже разбился, а точно число я так и не узнала
но на 25 этаже второй шарик тоже разбился, а точно число я так и не узнала
Слава тебе Господи хоть кто-то написал про половинное деление...
А то намутили всякой непонятной математики в 14 шагов :)
А то намутили всякой непонятной математики в 14 шагов :)
решал также, Ответ: 7 шагов
Шарики стеклянные, а не резиновые.
Бросок с 50-го этажа — шарик 1 разбился
Далее — с 25-го — шарик 2 разбился.
Всё, приехали.
Бросок с 50-го этажа — шарик 1 разбился
Далее — с 25-го — шарик 2 разбился.
Всё, приехали.
мне эту задачу задавали при поступлении в (мажорную программистскую) школу. К сожалению, не решил, так же начал говорить о половинных делениях и о скидывании с 50го этажа...
"Экзаменатор", же сказал что правильный метод - выбрать некий начальный шаг, и начинать кидать с того этажа.
проиллюстрирую.
примем, что этажей сто. выбираем число такое, чтобы (1+2+..X<=100)
идем на X этаж и скидываем шарик. если он не разбивается, значит, поднимаемся на X-1 этажей(то есть, на 1 меньше чем в предыдущем шаге), и кидаем оттуда. если шар разбивается, у нас есть диапазон для поиска, ограниченный точкой где шары не разбиваются, и где уже точно разбиваются. тут ищем линейно.
Метод удобен тем, что практически нет удачных\неудачных случаев - количество необходимых скидываний колеблется около одного числа.
вроде так-вот.
еще один вопрос, который мне задали, был - оцените количество нулей в числе 1000!
а вы можете в уме подсчитать?
"Экзаменатор", же сказал что правильный метод - выбрать некий начальный шаг, и начинать кидать с того этажа.
проиллюстрирую.
примем, что этажей сто. выбираем число такое, чтобы (1+2+..X<=100)
идем на X этаж и скидываем шарик. если он не разбивается, значит, поднимаемся на X-1 этажей(то есть, на 1 меньше чем в предыдущем шаге), и кидаем оттуда. если шар разбивается, у нас есть диапазон для поиска, ограниченный точкой где шары не разбиваются, и где уже точно разбиваются. тут ищем линейно.
Метод удобен тем, что практически нет удачных\неудачных случаев - количество необходимых скидываний колеблется около одного числа.
вроде так-вот.
еще один вопрос, который мне задали, был - оцените количество нулей в числе 1000!
а вы можете в уме подсчитать?
Не могу писать белым по очевидным причинам. Мой вариант - 50. Первый раз кидаем с полтинника и определяем в верхней или в нижней половине дома искать нужный этаж. Разбился значит <=50, не разбился - больше 50. Потом начинаем с 1-го (если разбился) или 51-го этажа (если разбился) и поднимаемся до тех пор пока не сломаем второй шарик. Если шарис не разбился на 48 или 99 этажах соответственно, то последний раз можно не кидать - итак понятно что разобьется (т.к. по условию он обязан разбиться). Итак, в худшем случае получаем 49 или 50 тестов, в зависимости от результата первого. Ответ - 50.
Мой ответ 14.
Подсказка: 14+13+12+11+10+9+8+7+6+5+4+3+2+1 = 105 > 100
Подсказка: 14+13+12+11+10+9+8+7+6+5+4+3+2+1 = 105 > 100
Если про программиста, то внесу и свое предложение - 2 :) Think binary => 100b = 4d :)
Ответ уже написали правильный, just joking. :)
Ответ уже написали правильный, just joking. :)
Дихотомия)
Upd: Добавьте в условие, что шарики одинаковые. В аналогичных задачах бывают уловки на эту тему и задача с таким условием будет иметь совсем иной ответ :)
задача некорректна, и "оптимального" алгоритма (такого что с меньшим колличеством бросков ГАРАНТИРОВАННО обойтись нельзя) не существует. Это все равно что попросить за минимальное число вопросов (с ответами да/нет) угадать целое число от 1 до 10. Может сразу угадаешь, а может прийдется 10 вопросов задать (соответственно, если повезет можно за два броска узнать что он разбивается на 12-том, бросив сначала с 11-того а потом с 12-ого). Тут можно спрашивать только об алгоритме который "в среднем" заканчивается за наименьшее число бросков. Наверное что-то около 50-ти (плюс-минус 1).
Я конечно не программист, но на мой взгляд, при существующем на данный момент условии задачи, ответ такой:
понадобится точное минимальное количество шагов - два!
Поясню... Один шаг: разбивается, второй шаг: не разбивается (или в обратной последовательности). Причем этажи, понятное дело, соседние. А вот какие этажи и как я их определил/угадал - это уже другой вопрос/задача...
З.Ы. тэг белого текста поставил, но не работает...
понадобится точное минимальное количество шагов - два!
Поясню... Один шаг: разбивается, второй шаг: не разбивается (или в обратной последовательности). Причем этажи, понятное дело, соседние. А вот какие этажи и как я их определил/угадал - это уже другой вопрос/задача...
З.Ы. тэг белого текста поставил, но не работает...
Я не согласна. Есть способ проще посчитать - 50 этаж, затем +/- 25 этажей, +/- 12 этажей и тд. в итоге 7 шагов
у вас шарик разбился на 50 этаже. У вас отсалось 6 шагов и 1 шарик - что будете делать? :-/
Они утверждают, что "мы неправы в такой ситуации": например шарик на 50 этаже разбился... а мы берем теперь 25 этаж, - но и тут шарик разбился - вот - пожалуйста - "мы" проиграли.
Первый шарик разбился на 50 этаже, второй на 75. Вам понадобится больше шариков.
Люди о чем вы?
Шариков всего два.
Выяснить ответ можно кидая с первого и поднимаясь выше. Чтобы максимально сократить число бросков мы бросаем первый шарик с 50-го этажа.
if(разбился)
next=51;
else
next=1;
i=next;
while(не разбился)
{
бросаемСЭтажа(i);
i++
}
Шариков всего два.
Выяснить ответ можно кидая с первого и поднимаясь выше. Чтобы максимально сократить число бросков мы бросаем первый шарик с 50-го этажа.
if(разбился)
next=51;
else
next=1;
i=next;
while(не разбился)
{
бросаемСЭтажа(i);
i++
}
Вроде, такую задачу легко решить на прологе, жаль, что сейчас занят на работе и нет "удобного времени подумать"...
А можно пойти другим путем - измерить геометрические и физические параметры шарика и рассчитать при какой нагрузке произойдет его разрушение. Далее, рассчитываем при броске с какого этажа сила удара будет равна или превысит эту нагрзуку. Итого, немного физики и математики и хватит одного броска. :)
Нет никакого половинного деления. Всего два шара. Задача очень простая. Как оптимально выбрать этаж для броска первого шара - очевидно.
Предлагаю заменить шарики на кошек в условии задачи.
Ребята "сверху" утверждают, что за 14... имхо - это не правильный ответ!
42
Открываем консоль firebug, пишем туда:
for(var i=1;i<100;i++){console.log(i, i/2+100/i)}
Отыскиваем минимальное число в правой колонке, ответ — число слева.
for(var i=1;i<100;i++){console.log(i, i/2+100/i)}
Отыскиваем минимальное число в правой колонке, ответ — число слева.
Повторяю, возможно действительно я немного ошибся в формулировке. Очень сложно верно сформулировать, если сам понимаешь, ведь пребываешь в уверенности, что и остальные поймут =) Возможно, у меня проблемы с русским, но я и сейчас не могу толком сформулировать точно. Если кто-то осилит, откорректирую пост.
Прошу прощения =(
Прошу прощения =(
Ну, чем кончилось? Какой ответ:
На мой взляд, ответ 14 неверен. Вот мой контрпример: если шарик разбивается на 97 этаже, то мы потратим 6 бросков на то, чтобы убедиться, что на 84 он не разбивается и потратим еще один, чтобы узнать о том, что на 98 шарик все-таки разобьется. Далее, перебирая по одному этажу, придется потратить еще целых 13 попыток. Итого - 20 раз. Таким образом, если требуется определить минимальное число бросков, которые требуются для того, чтобы точно определить самый нижний этаж, на котором шарик будет разбиваться, при наличии только двух шариков, 14 попыток может оказаться явно недостаточно. Так что 20 явно ближе к правильному ответу, чем 14.
Вы где-то упустили. После 84го надо пробовать бросать с 90го, потом с 95го, 99, 100.
множители числа, образующие минимальную сумму?
Эта задача из семейства поиска локального минимума. Вариантов решения много. Я выбрал матод "золотого сечения". За 9 шагов нашел ответ:)
Ммм... Мне кажется вы ошиблись... Да, точно, ошиблись.
поделитесь опытом пожалуйста... какже это у Вас так получилось?... На скока я помню этот метод и даже попробовал его сюда применить - алгоритм неоптимален, в отличие от описанного выше... Например если шарик только на 99 этаже разбивается - сколько минимально шагов надо сделать точно при методе "золотого сечения" и каким образом? или может быть Вы ошиблись?
по методу золотого сечения на каждом шаге отрезок(100 этажей) делться в пропорции - "меньший к большему - как больший к целому", и отбрасываеться тот, который не содержит решение. И того в случае с 99м:
1. 100*0.61 = 61этаж и выше. Ищем из 39 этажей.
2. 100-(39*0.61) = 76
3. 100-(24*0.61) = 85
4. 100-(15*0.61) = 91
5. 100-(9*0.61) = 94
6. 100-(6*0.61) = 97
7. 100-(3*0.61) = 99 - УРАА!!!!!:)
1. 100*0.61 = 61этаж и выше. Ищем из 39 этажей.
2. 100-(39*0.61) = 76
3. 100-(24*0.61) = 85
4. 100-(15*0.61) = 91
5. 100-(9*0.61) = 94
6. 100-(6*0.61) = 97
7. 100-(3*0.61) = 99 - УРАА!!!!!:)
окей... первый этаж с которого бросают 39...
и опачки! шарик разбился!
что дальше? от первого до 39 по одному этажу шагать и чикирить на каком разобьется?... это 40 шагов...
Да, можно применить и такой алгоритм - но это не 9 шагов и не 14...
или на 39 не разбился а на 61 разбился..... и допустим разбиваться начинает на 60.... от 39 до 60 - 21 этаж... т.е. это 22 шага...
Увы, но алгоритм неоптимален!
и опачки! шарик разбился!
что дальше? от первого до 39 по одному этажу шагать и чикирить на каком разобьется?... это 40 шагов...
Да, можно применить и такой алгоритм - но это не 9 шагов и не 14...
или на 39 не разбился а на 61 разбился..... и допустим разбиваться начинает на 60.... от 39 до 60 - 21 этаж... т.е. это 22 шага...
Увы, но алгоритм неоптимален!
Первый раз бросаем не с 39го, а с 61го. В зависимости от того шарик разбился или нет выбираем половину(Выше-ниже). И эту половину опять разбиваем на части в отношении 61 к 39. Сто этажей этим алгоритмом проходиться за 6-7 разбиений. Это классика. Можно делить и 50 к 50. Пример наглядно демонстрирует оптимальность метода.
Отличная задача! Спасибо. Я бы сформулировал вопрос так:
Существуют разные алгоритмы бросания шаров для поиска номера этажа с которого начинается разбиваться шарик. Каждый алгоритм гарантирует определение этажа не более чем за N бросков (например не более чем за 100, если бросать последовательно начиная с нижних этажей). Найдите минимум N и опишите оптимальный алгоритм.
Существуют разные алгоритмы бросания шаров для поиска номера этажа с которого начинается разбиваться шарик. Каждый алгоритм гарантирует определение этажа не более чем за N бросков (например не более чем за 100, если бросать последовательно начиная с нижних этажей). Найдите минимум N и опишите оптимальный алгоритм.
Мне кажется стоит изменить формулировку. Ведь по условиям задачи ищется не минимальное, а безызбыточное количество шагов, чтобы хабражители не путались. То есть напишите указание, что нужно найти как с минимальными затратами находить этаж в произвольном доме, а то некоторые станут теорию вероятности вспоминать))) А как подсказка можно было бы написать, что при правильном ответе оба шарика в любом случае разобьются)
прям в тему блин :)
какую бы cms выбрать,
и нужна ли она вообще или проще будет не разбираться в ней, а слегка освежить пхп?
какую бы cms выбрать,
и нужна ли она вообще или проще будет не разбираться в ней, а слегка освежить пхп?
Кстати предложенный вариант хоть и логичный, но не самый оптимальный...
Я захотел найти самый оптимальный вариант. Под ним я подразумеваю вариант поиска при котором (количество шагов в данном методе для поиска ответа елси ответ равен "1") + (шагов если ответ равен "2") + ... + (шагов если ответ равен "100") будет минимальным
{т.е. сумарное время поиска для всех возможных вариантов минимально}
Вот я решил задачу влоб.
int main()
{
int t=0; //tester
int n=0; //сумма количества шагов потраченных на поиск каждого из возможных правильных вариантов ответа
int i; //правильный ответ
for(st=1;st = i )
{
t-=st;
t++;
n++;
while (t != i)
{
t++;
n++;
}
}
}
t=0;
}
if (n<1500) printf("step:\t%d;\tcycles:\t%d\n",st,n);
n=0;
}
}
//кому интересно скомпильте, и самым оптимальным будет совсем не шаг через 14
Я захотел найти самый оптимальный вариант. Под ним я подразумеваю вариант поиска при котором (количество шагов в данном методе для поиска ответа елси ответ равен "1") + (шагов если ответ равен "2") + ... + (шагов если ответ равен "100") будет минимальным
{т.е. сумарное время поиска для всех возможных вариантов минимально}
Вот я решил задачу влоб.
int main()
{
int t=0; //tester
int n=0; //сумма количества шагов потраченных на поиск каждого из возможных правильных вариантов ответа
int i; //правильный ответ
for(st=1;st = i )
{
t-=st;
t++;
n++;
while (t != i)
{
t++;
n++;
}
}
}
t=0;
}
if (n<1500) printf("step:\t%d;\tcycles:\t%d\n",st,n);
n=0;
}
}
//кому интересно скомпильте, и самым оптимальным будет совсем не шаг через 14
Пусть шаг первого шарика оптимален и равен K, т. е. тестируют на этаже K. Далее — K+K-1 этаж, потом K+K-1+K-2 и т. д. пока не перепрыгнем через сотый.
Сумма всех положительных члегов арифметической прогрессии будет равна (K+1)K/2, надо чтобы покрывался этаж 100, это начит надо решить для натуральных K неравенство K(K+1) > 200, т. е. Kmin=14
Т. е. получается для проверки N этажей надо максимум N^(1/2) итераций.
Кто может показать, что оценка N^(1/2 - \epsilon) уже не верна? ;)
Сумма всех положительных члегов арифметической прогрессии будет равна (K+1)K/2, надо чтобы покрывался этаж 100, это начит надо решить для натуральных K неравенство K(K+1) > 200, т. е. Kmin=14
Т. е. получается для проверки N этажей надо максимум N^(1/2) итераций.
Кто может показать, что оценка N^(1/2 - \epsilon) уже не верна? ;)
Если интересно — мне удалось доказать. Всё решение полностью выложу, схема примерно такая:
1) Пусть для N этажей можно всё определить минимум за M зашагов. Т. е. всякое определение будет соотвествовать последовательность типа 0...010...01, энтропия будет линейна по log_2(M).
2) Пусть есть верная оценка для M вида C*N(1/2-epsilon). Находим минимальное N, для которого количество информации об минимальном этаже (log(N) бит) окажется больше log(M).
Фактически решение ещё интересно тем, что за 13 шагов 100% нельзя всегда уже найти нужный этаж. Но вот поведение на бесконечности — хорошее упражение по теории информации.
1) Пусть для N этажей можно всё определить минимум за M зашагов. Т. е. всякое определение будет соотвествовать последовательность типа 0...010...01, энтропия будет линейна по log_2(M).
2) Пусть есть верная оценка для M вида C*N(1/2-epsilon). Находим минимальное N, для которого количество информации об минимальном этаже (log(N) бит) окажется больше log(M).
Фактически решение ещё интересно тем, что за 13 шагов 100% нельзя всегда уже найти нужный этаж. Но вот поведение на бесконечности — хорошее упражение по теории информации.
задача была бы интереснее если бы этажей было с миллион а вложенность поиска с десяток хотя бы) то есть кол-во шариков) может порешаем?)
5 способов, верно?
ИМХО 6 попыток
бросаем с 50, c 75, если не разбился. Или с 25-го если разбился.
потом 13, потом 6, потом 3, потом 2 например. В обратную сторону аналогично....
Как-то сей метод называется толи Ньютона, толи секущих.... кароче двойка у меня была по математике.
Суть, что делим отезок пополам....
бросаем с 50, c 75, если не разбился. Или с 25-го если разбился.
потом 13, потом 6, потом 3, потом 2 например. В обратную сторону аналогично....
Как-то сей метод называется толи Ньютона, толи секущих.... кароче двойка у меня была по математике.
Суть, что делим отезок пополам....
Погугил :)))
http://elib.ispu.ru/library/math/sem1/in…
глава 9.
Задача решинается след методами:
Метод половинного деления (который я первм описал), методом секущих, методом одной касательной, методом Ньютона и методом хорд. :)))
формулы сложные тут не помесятся...
http://elib.ispu.ru/library/math/sem1/in…
глава 9.
Задача решинается след методами:
Метод половинного деления (который я первм описал), методом секущих, методом одной касательной, методом Ньютона и методом хорд. :)))
формулы сложные тут не помесятся...
да-да, вот только хотел об этом сказать. В институте на предмете "оптимальное управление" (методы оптимизации) такие задачи приходилось решать. Причем эта - практически типичная.
Математическим языком это задача условной минимизации, т.е. задача по нахождению минимума функции на конечном отрезке за минимальное количество итераций (шагов). Решается несколькими методами: методом деления отрезка пополам, методом "золотого сечения", методом Ньютона, методом аппроксимации, еще были, не помню :)
З.Ы. Что-то сейчас взялся решать самым простым и надежным методом - методом деления отрезка пополам. Ответ удивил - 7, а не тот ответ, что предложил автор.
Ход решения просто: делим отрезок 100 пополам. Кидаем с "серединного" этажа (можно выбрать 50 или 51 - не суть важно). Шар не разбивается (иначе задача не умела бы смысла), далее делим аналогично соответствующий отрезок, пока исковый не сужается до одного точного значения.
З.З.Ы. Что-то сам засомневался. Возможно, ошибаюсь.
Математическим языком это задача условной минимизации, т.е. задача по нахождению минимума функции на конечном отрезке за минимальное количество итераций (шагов). Решается несколькими методами: методом деления отрезка пополам, методом "золотого сечения", методом Ньютона, методом аппроксимации, еще были, не помню :)
З.Ы. Что-то сейчас взялся решать самым простым и надежным методом - методом деления отрезка пополам. Ответ удивил - 7, а не тот ответ, что предложил автор.
Ход решения просто: делим отрезок 100 пополам. Кидаем с "серединного" этажа (можно выбрать 50 или 51 - не суть важно). Шар не разбивается (иначе задача не умела бы смысла), далее делим аналогично соответствующий отрезок, пока исковый не сужается до одного точного значения.
З.З.Ы. Что-то сам засомневался. Возможно, ошибаюсь.
Устал читать все комменты, хотел написать свой, но заметил Ваш. В общем, та же идея.
а если с 50 разбился? :)
Этот способ не работает.
Этот способ не работает.
Этот пост о том, как группа людей "придумала ответ"... а потом под этот ответ и "вопрос сделали"!
7 шагов
Бросаем со среднего, потом в зависимости от результата с 75 или 25 и т.д., ограничивая диапазон. Хватит 7 шагов.
P.S. Сорри, подсказка про ХТМЛ-теги у меня не сработала (ошибка MySQL), не знаю как белым написать.
Бросаем со среднего, потом в зависимости от результата с 75 или 25 и т.д., ограничивая диапазон. Хватит 7 шагов.
P.S. Сорри, подсказка про ХТМЛ-теги у меня не сработала (ошибка MySQL), не знаю как белым написать.
Минимум - два. Если с первого раза шарик разбился - нужно проверить разобьется ли он этажом ниже.
Если не разобьется - вот ответ, который получается минимум за два шага.
Если не разобьется - вот ответ, который получается минимум за два шага.
А если второй разобьётся? :)))
А если нет?
Спрашивается же минимальное. Правда если разобьется с первого этажа - минимальное число шагов - 1.
Вот если б спрашивали среднее - тогда было б что посчитать.
А вообще можно так.
Бросил с первого:
--- разбился -> выход;
--- нет -> бросаю с десятого:
-------- разбился - иду с второго по девятый, пока не разобьется;
-------- не разбился - бросаю с 20:
--------------------- разбился - иду с 11 по 19, пока не разобьется;
--------------------- нет - бросаю с 30 и т.д....
Спрашивается же минимальное. Правда если разобьется с первого этажа - минимальное число шагов - 1.
Вот если б спрашивали среднее - тогда было б что посчитать.
А вообще можно так.
Бросил с первого:
--- разбился -> выход;
--- нет -> бросаю с десятого:
-------- разбился - иду с второго по девятый, пока не разобьется;
-------- не разбился - бросаю с 20:
--------------------- разбился - иду с 11 по 19, пока не разобьется;
--------------------- нет - бросаю с 30 и т.д....
В таком случае - минимум - один, максимум - 20. И всегда можно дойти до решения.
в подобных задачах под минимумом подразумевается оптимальное решение для варианта самого неблагоприятного размещения.
т.е. отбросив случайность вы должны рассматривать самый худший вариант, что может быть для вашего алгоритма.
минимум у вас - 20 - это много.
правильный ответ 14 ходов.
т.е. отбросив случайность вы должны рассматривать самый худший вариант, что может быть для вашего алгоритма.
минимум у вас - 20 - это много.
правильный ответ 14 ходов.
Все, нашел. В общем-то мысли в верном направлении, по разному подбор следующего этажа.
Удачная задача, было интересно подумать :-))
Тогда нужно писать "минимальное максимальное число шагов до ответа", звучит не по-русски, но точнее, чем "минимальное число шагов", читая условие я должен читать условие, а не гадать, что под этим кто-то подразумевает.
Удачная задача, было интересно подумать :-))
Тогда нужно писать "минимальное максимальное число шагов до ответа", звучит не по-русски, но точнее, чем "минимальное число шагов", читая условие я должен читать условие, а не гадать, что под этим кто-то подразумевает.
ну, автор в данном случае понадеялся, что люди читающие его разумны по умолчанию и будут не лазейки искать, а решать :)
эдакая презумция разума.
просто в вашем понимании вешать задачу вообще не было бы смысла - можно рассмотреть наиболее выгодное расположение.
эдакая презумция разума.
просто в вашем понимании вешать задачу вообще не было бы смысла - можно рассмотреть наиболее выгодное расположение.
Я не разумен?
Разные точки зрения могут быть на решение, на ответ, но никогда - на условие задачи, что в данной теме имело место. :-)
Разные точки зрения могут быть на решение, на ответ, но никогда - на условие задачи, что в данной теме имело место. :-)
Да, признаю, дополнительные объяснения автора, появившиеся не сразу, я прочитал значительно позже того, как сделал неправильные суждения о вопросе, ставящемся в условии задачи. :-)
Как правило те, кто решают сходу задачу правильно, всё понимают правильно.
И это неслучайно, т.к. они хотят задачу решить, а не доказать, что автор так недалек, что вот упустил тут возможность другого ответа.
Это моё мнение, конечно, но просто понять смысл условия даже, если оно не совсем корректно было бы задано, понять можно и отталкиваться надо от этого.
Видимо, в данном случае сыграло роль, что вам до этого момента не приходилось решать подобных задачек - потому вы недопоняли.
Но это не страшно :)
И это неслучайно, т.к. они хотят задачу решить, а не доказать, что автор так недалек, что вот упустил тут возможность другого ответа.
Это моё мнение, конечно, но просто понять смысл условия даже, если оно не совсем корректно было бы задано, понять можно и отталкиваться надо от этого.
Видимо, в данном случае сыграло роль, что вам до этого момента не приходилось решать подобных задачек - потому вы недопоняли.
Но это не страшно :)
1. Кидаем с 50 - не разбисля
2. 75 - да
3. 62 - нет
4. 70 - да
5. 66 - нет
6. 68 - да
ответ: - 6 шагов
2. 75 - да
3. 62 - нет
4. 70 - да
5. 66 - нет
6. 68 - да
ответ: - 6 шагов
36?
Или я что-то туплю, или всё элементарно. Эта задача же сводиться к поиску элемента в упорядоченном массиве(элементы - номера этажей, упорядочены по возрастанию). Первый способ, который приходит на ум - бинарный поиск. Т.е. бросаем с 50 этажа - если разбился - этажи с 51 по 100 не рассматриваем. Не разбился - с 1 по 50 не рассматриваем дальше. Далее, оставшуюся половину делим снова пополам, т.е. повторяем итерацию. И так до тех пор, пока не найдём нужный этаж. Так что считать сейчас некогда - пишу впопыхах. Но примерно нужно будет сделать всего 6-7 шагов. Поправьте, если я не прав.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача про два шарика