Задача про два шарика

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

    Есть два стеклянных шарика и 100-этажный дом. Вы бросаете шарик с разных этажей этого дома, чтобы выяснить, на каком этаже шарик начинает разбиваться от падения (например, на пятом уже разбивается, а на четвёртом ещё нет). Вопрос: какое точное минимальное количество шагов понадобится для того, чтобы точно узнать на каком именно этаже шарики начинают разбиваться?

    Просьба ответ писать белым шрифтом ;)

    UPD! Шаг — это один бросок одного шарика.
    UPD! Шарик начинает разбиваться с определённого этажа.
    UPD! Не все правильно поняли формулировку задачи, поэтому уточняю. Спасибо Aleco. Существуют разные алгоритмы бросания шаров для поиска номера этажа с которого начинается разбиваться шарик. Каждый алгоритм гарантирует определение этажа не более чем за N бросков (например не более чем за 100, если бросать последовательно начиная с нижних этажей). Найдите минимум N и опишите оптимальный алгоритм.
    Поделиться публикацией
    Комментарии 242
      0
      Кста, дом может иметь высоту 100 и четверть от ста и еще 3 этажа.
        –2
        1
          0
          Интересно, но неверно =)
          Задача не просто на логику, немного математики тоже нужно. Мой друг устраивался на позицию программиста ;)
            0
            если это не верно, тогда неверно условие задачи ;)
              0
              Там есть слово "достоверно". Не понимаю просто как, бросив шарик один раз, можно узнать достоверно нужный нам факт...
                0
                бросили с первого этажа - не разбился, подобрали
                бросили со второго - не разбился, подобрали
                ...
                бросили с Н - разбился
                в условие задачи нет того, что шарик поднимать нельзя или двигаться от 100 этажа к первому :)
                  0
                  Прочитайте внимательней =) там написано "шагов", а не "шаров" =)
                    +1
                    сорри - неверно прочитал - вместо шагов - шаров :(
                0
                Почему это "неверно" ? Предположим, что дом у нас такой, что шарик будет разбиваться уже при броске с первого этажа. Сбросив шарик сразу с первого этажа один раз, я сразу узнаю, что минимально необходимый этаж - первый. Больше никаких шагов мне делать не нужно. Формально, если следовать условию задачи, ответ правильный. Ну вот такой вот дом мне попался удобный.
                  0
                  Мы не знаем с какого этажа шарик разобьётся. Нам нужно выяснить ТОЧНОЕ количество шагов, которое нам нужно для того, чтобы ТОЧНО узнать с какого этажа он разобьётся.
                  А если он на первом этаже не разобьётся? Каковы действия дальше?
                    –2
                    В формулировке вопроса нет слова "точно". Там написано "какое минимальное количество шагов понадобится для того, чтобы узнать на каком именно этаже шарики начинают разбиваться". Минимальное количество шагов - один.
                      0
                      Сейчас поправлю.
                        0
                        ничего по-моему не изменилось от ваших поправок, первый этаж - точно один шаг
                          +1
                          во-во, я смогу его ТАК кинуть, что и в подвале разобью =)

                          а может быть земля настолько мягкая, что из сотого не разобьется. =)

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

                          14 27 39 50 60 69 77 84 90 95 99
                        0
                        А если все-таки разобьется? ;)
                      0
                      > Мой друг устраивался на позицию программиста

                      в google
                        0
                        Ваш комментарий неверный! Этот ответ правильный. Перечитайте условие задачи и согласитесь со мной!
                          0
                          Не читал комментарии, но ответ log 100 по основанию 2 в потолок, т.е 7 шагов
                          Не буду писать белым, так как посту уже 5 лет)
                            0
                            Ну так неправильно же :)
                              0
                              Сначала написал, потом подумал)
                        0
                        а) что такое шаг? один бросок? или 2 броска, по одному на шарик?
                        б) мм то есть если один шарик разбился, у нас остался лишь второй? и с этого момента у нас один шарик, который бить нельзя? тогда нам надо стремиться к минимизации суммы k + 100/k, вроде k=10 и ответ таким образом 20 =) влом думать начиная со слова вроде :(
                          0
                          а) Шаг - это один бросок одного шарика.
                          б) Да, верно. Разбить его можно только при последнем броске, с помощью которого мы точно определим этаж.

                          Спасибо за уточнения, внесу в пост.
                            0
                            что верно, предположение или ответ? :) или и то и другое? :)
                              0
                              Ответа не заметил, извини.
                              Нет, ответ другой.
                              0
                              Я правильно понимаю, что если шарик не разбился - то его можно кидать ещё раз(типа, подобрать?)
                                0
                                Да
                            0
                            ответ: 50
                              0
                              Неверно.
                              0
                              не более 51
                                0
                                Ответ меньше 51, тут правильно. Но есть точное число.
                                –2
                                моя вторая и последняя попытка: 51
                                  –1
                                  1
                                    0
                                    Мы за шаг считаем - шаг человека(ногами) или шаг, в плане "поднять на 10 этаж"?
                                      0
                                      Там написано в посте, что есть шаг ;)
                                    –1
                                    35
                                      0
                                      Извините, но я почему-то не могу написать белым цветом.
                                      А то бы высказал мысль почему столько.
                                      0
                                      Пока всё неверно.
                                      Есть один ответ с математическим обоснованием.
                                        0
                                        это вообще-то стандартная задача на отгадывание числа с вопросами больше/меньше. ответ - логарифм от 100 по основанию 2 (округленный вверх)
                                          0
                                          К сожалению, в данном случае попытка, превышающая этаж, только одна.
                                            0
                                            да, я это пропустил
                                        –1
                                        0 - если шарик разобъется уже на первом этаже - не нужно подниматься выше, следовательно ни одного шага не понадобится
                                          +6
                                          ой, ошибся с размером шрифта, уже написал в поддержку, чтобы исправили! не торопитесь минусовать!
                                            0
                                            вот черт, еще и ответ был неверный! но не все условия задачки были опубликованы сначала.
                                          +2
                                          14
                                            0
                                            Верно ;)
                                            Кто хочет разгадать, не читайте это сообщение ;)
                                              0
                                              Так а почему шарика всего два? Если их всего два, тогда как ответ выше может быть правильным? Зачем именно два шарика, а не один?
                                                0
                                                Напишите ответ белыми буквами, плиз.
                                                  +1
                                                  Объяснение словами. Кидаем с 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100. Это позволяет нам добиться минимизации количества шагов.

                                                  Математически это можно объяснить с помощью формулы натурального ряда. 100 = (n*(n+1))/2
                                                  При n=14 получается результат 105, при n=13 меньше ста. Поэтому ответ 14.
                                                    0
                                                    У вас тоже этажи не как у людей номеруются ? В нормальных небоскрёбах, в которых я бывал всё-таки первый этаж - внизу, 14-й - выше, а на самом верху - 100-й. А так - правильно, конечно...
                                                      0
                                                      простите за идеотский вопрос, но почему берется именно такое разложение??? почему к примеру не 10,20,30,40... ???
                                                        0
                                                        Ибо с вашим разложением получится 19 попыток, а не :)
                                                          0
                                                          угу.. ясно... а откуда следует само разложение???
                                                            +4
                                                            Раз уже все карты раскрыты, то можно и в третий раз написать размышления.
                                                            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. Вот так. Можно проверить и убедиться.

                                                            Подробней уж никак не могу :)
                                                              0
                                                              Спасибо... теперь понял... незнание рядов меня подвело... =)))

                                                              вы спасли мою черепную коробку от взрыва =)

                                                              пошел писать ПСЖ =)
                                                                –4
                                                                "Вопрос: какое точное минимальное количество шагов понадобится для того, чтобы точно узнать на каком именно этаже шарики начинают разбиваться?"
                                                                Ну вот вам еще раз вопрос)
                                                                Представьте, что правильный ответ = с 1-го этажа.
                                                                А вы кидаете сначала 14, потом 1. У вас получилось точно 2.
                                                                А "точное минимальное" = 1.
                                                                  0
                                                                  Поясните, пожалуйста, вот это:
                                                                  На каком же этаже нужно бросить шарик еще раз? Очевидно, что на N-1(считая от отсечения).

                                                                  Мне, почему-то, не совсем очевидно… Почему не взять снова N? Или какое-то другое число?
                                                                    0
                                                                    Если брать снова N, то получается что мы увеличиваем число требуемых испытаний для выявления искомого числа т.к. мы уже сделали один бросок чтоб продвинутся до второго N.

                                                                    Например:
                                                                    кинули на 14 — не разбился, кинули на 28 разбился, но нам потребуется теперь проверить 14 этажей, то есть общее число бросков = 1(один раз уже бросили) + (28-14) = 15. А если бы взяли N-1, то кидали с 27. И тогда число оставшихся требуемых проверок былоб 1 + (27-14) = 14.

                                                                    Таким образом переходя от этажа к этажу мы не увлечиваем число требуемых бросков.
                                                                0
                                                                Ну... Если так, то вообще можно делить 100 на два без остатка, даже если округлять вверх то выйдет... 50, 25, 13, 7, 4, 2, 1 = 7 шагов.
                                                                  0
                                                                  К сожалению, шариков всего два :) А нам _ну_позарез_ нужно определить этаж. Поэтому рисковать мы не можем - а вдруг оба шарика разобьются - самому прыгать, что ли? ;)
                                                                    0
                                                                    Вокруг нас матрица, в чём проблема? ;)))
                                                              0
                                                              не понимаю, ну бросите вы с 14го этажа, шарик разобьется, и как вы за один шарик выясните где между первым и 14м этажом он разбивается? :-/
                                                                0
                                                                ааа понял :)
                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                    0
                                                                    если когда разобьется снизу начинать, то все норм
                                                                  0
                                                                  А вообще это типичная задача динамического программирования.
                                                                    0
                                                                    есть так называемый "быстрый" алгоритм поиска, неужели с его помошью не будет меньше итераций? 100 50 25 13 7 4 2 ... или нет?:)
                                                                    зы: поздно конечно, но интересно всеравно
                                                                      0
                                                                      шарика всего два)
                                                                0
                                                                Если не жалко напишите объяснение.
                                                                  0
                                                                  Решал я задачу так: Возьмем число бросков в задаче за N. В таком случае первый этаж, на котором разобьется шар, определен двумя числами: номером броска первого шара, когда он разобьется и номером броска второго шара, когда он разобьется. Сумма этих бросков не должна превышать N.

                                                                  Дальше записываем формулу количества возможных пар этих чисел: (N*(N+1))/2. Это число будет больше либо равно 99. Дальше решаем квадратное уравнение: N^2+N-198=0. Округляем один из корней до 14, потому что нам нужны целые числа. Вот отсюда и ответ.
                                                                    0
                                                                    А если на пальцах? У меня при мысленном моделировании получается никак не меньше 25 в самом худшем случае.
                                                                    Т.е. если кадать первый шарик сначала с 51 этажа, а затем в зависимости от того, разобъётся он или нет начать либо со 2 до 48, либо с 53 до 99, постоянно перепрыгивая через 1 этаж, то 14 никак не получается.
                                                                    Заранее спасибо.
                                                                      +2
                                                                      На пальцах чуть выше в комментариях VaNcHeR объяснил. Я могу свой вариант привести: первая попытка будет с 14 этажа, если разбивается, то идем с первого этажа до 13. В сумме максимум будет 14 попыток. Если на 14 этаже не разбивается, то прибавляем 14-1=13 этажей, кидаем с 27, если разбивается, то начинаем с 15 проверять, опять же за 14 попыток найдем нужный этаж. Ну и так далее, пока не найдем нужный.
                                                                        0
                                                                        Я так понимаю что в вашем небоскрёбе этажи нумеруются сверху ?
                                                                          0
                                                                          Почему же? Снизу. Начинаем на 14, дальше поднимаемся выше.
                                                                          +1
                                                                          респект! понял только после вашего объяснения)
                                                                          0
                                                                          у меня при мысленном моделировании получалось сразу девятнадцать - пробовать с десятого через десять, если бьётся - минус шаг плюс единица и по порядку, пока не)
                                                                          Но это, конечно, первоевголовуприходящее. В варианте же с четырнадцатью, идёте с четырнадцати, и каждый раз уменьшаете промежуток на единицу. Если бьется на четырнадцатом этаже - остаётся проверить предыдущие 13, на 14+13 (два шага сделано) - предыдущее двенадцать и т.д.
                                                                          0
                                                                          Я, если честно, тоже не понимаю. На мой дилетантский взгляд - задача чисто эмпирическая. Если я буду кидать шарики по одному начиная с 1 этажа, потом со 2-го и так далее до того момента, как один из шариков разобьется от падения, то, фактически, количество попыток будет = номеру этажа, при кидании с которого разбивается шарик (прошу прощения за туфтологию). При этом результат будет зависеть от качества стекла.
                                                                          Шариков всего 2, поэтому, если начинать с высоких этажей, можно лишиться шариков до завершения эксперимента.
                                                                            0
                                                                            Ну ваш метод не будет оптимальным.
                                                                        0
                                                                        5 вариантов?
                                                                        –1
                                                                        ответ: 66
                                                                          –1
                                                                          поправка: 34
                                                                          0
                                                                          Сдается мне, что задача формулируется как-то иначе...
                                                                            0
                                                                            Предложите свою версию ;)
                                                                              +2
                                                                              Ну, как минимум, не на каком этаже шарики начинают разбиваться, а при сбрасывании с какого этажа. И наверно нужно определить максимальное, а не минимальное количество шагов, т.к. минимальное может быть любым в пределах от одного до правильного ответа (не вычислял).
                                                                                0
                                                                                Точную формулировку предложить сложно, так как разные люди по-разному трактуют слова. Я попытался изложить условие наиболее понятно и доступно, но Ваши исправления в целом верны, особенно первое.
                                                                                  0
                                                                                  Максимальное минимальное, как-то так )
                                                                                    0
                                                                                    Точная формулировка должна включать в себя и слово "минимальный" и "максимальный". То есть минимум максимума: максимум по всем входам, минимум по всем стратегиям. Классическая формулировка "за какое минимальное число шагов мы можем гарантированно определить этаж в самом худшем [для нас] случае ?"

                                                                                    Если человек подлавливает тебя на формулировке и говорит что минимум - это один бросок, то нужно сказать "молодец - а теперь сформулируй задачу так, чтобы она была нетривиальной". Так как там только один небессмысленный вариант, то дальше всё понятно...
                                                                              0
                                                                              Да, 14 всё-таки. Задачка ничего так, но идея видится почти сразу. Жалко, много сильно неверных ответов
                                                                                0
                                                                                Видимо здесь мало программистов. От дизайнера или верстальщика я умения решать эту задачу требовать бы не стал...
                                                                                  0
                                                                                  что удивительно и деление на 5 и деление на 9 работают :)
                                                                                  0
                                                                                  18?
                                                                                    0
                                                                                    Правильный ответ выше.
                                                                                      0
                                                                                      я уже нагуглил(:
                                                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                                                      0
                                                                                      Вопрос неправильно задан, какое точно не "минимальное", а "максимальное".
                                                                                      Максимальное 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
                                                                                        0
                                                                                        Правильный ответ и решение есть выше.
                                                                                        Каюсь, вопрос сформулирован не совсем корректно, в следующий раз очень постараюсь, чтобы не было путаницы =(
                                                                                          0
                                                                                          С Формулай попутал. Не +1, а более сложнее.
                                                                                            0
                                                                                            Первый раз нужно кидать с 92го этажа, если я нигде не обсчитался...
                                                                                              0
                                                                                              У тебя 2 шарика. Ты кинул с 92. Один разбидся. Остался второй. С какого этажа он разобьётся?
                                                                                            0
                                                                                            Нужен минимум максимума, на самом деле. А вопрос формулируется как "за какое минимальное число шагов мы можем гарантированно определить этаж в самом худшем (для нас) случае ?".
                                                                                            +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.

                                                                                            Веселее задачка, скажем, с четырьма шариками, но если решить эту не методом угадывания, то она тоже становится несложной, а вот если сказать что шариков четыре с самого начала... это уже садизм...
                                                                                              +1
                                                                                              Что вас так удивило? Видите ли, не у всех есть высшее математическое образование
                                                                                              0
                                                                                              А как белым то написать?
                                                                                              У меня получилось - 7
                                                                                                0
                                                                                                Чьёрт побери! Я прошу прощения, но я правильно написал фонт колор="вайт!" бла бла бла /фонт
                                                                                                Незнаю чего оно не сработало. А, помоему, перенос строки оно не так понимает . . .
                                                                                                Задачу решал последовательными приближениями. Кидаем на сотом и 50,если бьется и тот и тот, то кидаем на 25, если и этот бьется, то кидаем на 12, и так далее - 7 шагов - 7 шаров, разве нет? Ну или вверх выше 50-го этажа если на сотом разбился на 50 нет. Разве не так . . .
                                                                                                  0
                                                                                                  Кнопка "предпросмотр" есть, если не уверен.
                                                                                                    +1
                                                                                                    Я в курсе, предпросмотрел, теги поисчезали текст нет, подумал, что так работает предпросмотр . . .
                                                                                                    Прошу прощения . . .
                                                                                                      0
                                                                                                      Так работает 0 кармы. Теперь по идее теги будут пахать ;)
                                                                                                +2
                                                                                                А есть ещё шарики?
                                                                                                А то я один сломал, а другой потерял :(
                                                                                                  +1
                                                                                                  я думаю, все же 7, как выше написал MrDee, так же посчитала. так же как задача про взвешивание монеток с целью определить фальшивую
                                                                                                    0
                                                                                                    так у MrDee 7 шаров, а у автора задачи всего 2. Разве что сама докупишь шары)
                                                                                                      0
                                                                                                      да, я невнимательна.
                                                                                                      тогда 19 шагов
                                                                                                  • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                      0
                                                                                                      комментарии действительно замечательные ))))
                                                                                                      0
                                                                                                      задача поставлена неверно:
                                                                                                      "Вопрос: какое точное минимальное количество шагов понадобится для того, чтобы точно узнать на каком именно этаже шарики начинают разбиваться?"
                                                                                                      точное минимальное мы не знаем, мы знаем точное максимальное - 14. А минимальное может быть 1,2,3,..14
                                                                                                        0
                                                                                                        простите, не хватило сил дочитать комменты. Там уже выше заметили это.
                                                                                                        0
                                                                                                        я минут 10 не мог понять, почему кидая шарики с 100 этажа они начнут разбиваться на n-ом. :)
                                                                                                        теперь понял, что мы иден не сверху-вниз, а наоборот :))
                                                                                                          0
                                                                                                          Я знаю ответ на эту задачку - один из шариков пиз*ит!
                                                                                                          Помню когда прочитал эту шутку (про черепашек) по полу катался, только что вспомнил - опять катаюсь.
                                                                                                            –1
                                                                                                            Уже наверное белым писать и не нужно? Вроде правильный ответ 14 уже пишут все кому не лень.
                                                                                                            А вот у меня тоже, как у MrDee и liolia вышло минимально стопроцентное число бросков стеклошаров – 7.
                                                                                                            Не помню уже, слава богу, математические формулы и методы, но суть такова приблизительно – бросаем шар с 50 этажа, с середины то есть. И смотрим разбился он или уцелел. И дальше уточняем этаж методом выбора серединного из предполагаемых. Ну, например, если разбился, выбираем 25 этаж. И так далее. Разбился на четвертаке – выбираем 13, на тринадцатом – 8 и таким макаром за 7 шагов мы точно поймем на каком этаже шарик начинает не разбиваться (или разбиваться).
                                                                                                            Логика такая. Формулы формулировать лень.
                                                                                                              +3
                                                                                                              Да, друзья, а как же деление отрезка пополам?

                                                                                                              Целочисленное решение лежит на отрезке - 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 шага.
                                                                                                              Поправьте, если не прав...
                                                                                                                0
                                                                                                                Полностью соглашусь с человеком. Алгоритм половинного деления. Используется в поиске и сортировках.
                                                                                                                • НЛО прилетело и опубликовало эту надпись здесь
                                                                                                                  0
                                                                                                                  "Блин - Хабрахабр упал, и я не мог ответить." Насколько я помню, только так и решали схожие задачи на первом курсе (язык Pascal, как сейчас помню). И это, имхо, самый "правильно-человеческий" ответ.
                                                                                                                    0
                                                                                                                    Мне кажется, что 6 - правильная цифра для варианта с безлимитныи количеством шариков. Но, так как шариков всего 2, то они могут все разбиться до получения результата методом половинного деления.
                                                                                                                      0
                                                                                                                      не с безлимитным тогда, а с 6 шариками :-)
                                                                                                                      +1
                                                                                                                      Шаров-то два всего
                                                                                                                        0
                                                                                                                        тогда, да :) не внимателен.
                                                                                                                        0
                                                                                                                        деление отрезка пополам пришло в голову в первую очередь
                                                                                                                        но на 25 этаже второй шарик тоже разбился, а точно число я так и не узнала
                                                                                                                          0
                                                                                                                          Слава тебе Господи хоть кто-то написал про половинное деление...
                                                                                                                          А то намутили всякой непонятной математики в 14 шагов :)
                                                                                                                            0
                                                                                                                            решал также, Ответ: 7 шагов
                                                                                                                              0
                                                                                                                              мы все не обратили внимание, что шаров только 2
                                                                                                                                0
                                                                                                                                согласен, раз шарика два, то умножу 7 на 2, получу 14 :)
                                                                                                                                  0
                                                                                                                                  я не из этих соображений :)
                                                                                                                                  правда после школы давно уж мозги не такие гибкие :)
                                                                                                                              0
                                                                                                                              Шарики стеклянные, а не резиновые.
                                                                                                                              Бросок с 50-го этажа — шарик 1 разбился
                                                                                                                              Далее — с 25-го — шарик 2 разбился.
                                                                                                                              Всё, приехали.
                                                                                                                            0
                                                                                                                            мне эту задачу задавали при поступлении в (мажорную программистскую) школу. К сожалению, не решил, так же начал говорить о половинных делениях и о скидывании с 50го этажа...
                                                                                                                            "Экзаменатор", же сказал что правильный метод - выбрать некий начальный шаг, и начинать кидать с того этажа.
                                                                                                                            проиллюстрирую.
                                                                                                                            примем, что этажей сто. выбираем число такое, чтобы (1+2+..X<=100)
                                                                                                                            идем на X этаж и скидываем шарик. если он не разбивается, значит, поднимаемся на X-1 этажей(то есть, на 1 меньше чем в предыдущем шаге), и кидаем оттуда. если шар разбивается, у нас есть диапазон для поиска, ограниченный точкой где шары не разбиваются, и где уже точно разбиваются. тут ищем линейно.
                                                                                                                            Метод удобен тем, что практически нет удачных\неудачных случаев - количество необходимых скидываний колеблется около одного числа.
                                                                                                                            вроде так-вот.

                                                                                                                            еще один вопрос, который мне задали, был - оцените количество нулей в числе 1000!
                                                                                                                            а вы можете в уме подсчитать?
                                                                                                                              0
                                                                                                                              "оцените количество нулей в числе 1000"

                                                                                                                              если не прибегать к формулам, то получается где-то около трех
                                                                                                                                0
                                                                                                                                ахахах я сначала тоже так подумал, пока с 10 прочтения не заметил там факториал ;)
                                                                                                                                0
                                                                                                                                Как-то привычней слышать задачу о количестве 0 в конце данного числа. :) Именно в Вашей формулировке?
                                                                                                                                  0
                                                                                                                                  Всё просто в числе 1000 три нуля :)
                                                                                                                                    0
                                                                                                                                    200
                                                                                                                                    0
                                                                                                                                    Не могу писать белым по очевидным причинам. Мой вариант - 50. Первый раз кидаем с полтинника и определяем в верхней или в нижней половине дома искать нужный этаж. Разбился значит <=50, не разбился - больше 50. Потом начинаем с 1-го (если разбился) или 51-го этажа (если разбился) и поднимаемся до тех пор пока не сломаем второй шарик. Если шарис не разбился на 48 или 99 этажах соответственно, то последний раз можно не кидать - итак понятно что разобьется (т.к. по условию он обязан разбиться). Итак, в худшем случае получаем 49 или 50 тестов, в зависимости от результата первого. Ответ - 50.
                                                                                                                                      +1
                                                                                                                                      Я — лузер
                                                                                                                                        0
                                                                                                                                        Уморил! )))))))
                                                                                                                                      0
                                                                                                                                      Мой ответ 14.
                                                                                                                                      Подсказка: 14+13+12+11+10+9+8+7+6+5+4+3+2+1 = 105 > 100
                                                                                                                                        +1
                                                                                                                                        Если про программиста, то внесу и свое предложение - 2 :) Think binary => 100b = 4d :)
                                                                                                                                        Ответ уже написали правильный, just joking. :)
                                                                                                                                          +1
                                                                                                                                          Дихотомия)
                                                                                                                                            0
                                                                                                                                            Upd: Добавьте в условие, что шарики одинаковые. В аналогичных задачах бывают уловки на эту тему и задача с таким условием будет иметь совсем иной ответ :)
                                                                                                                                              0
                                                                                                                                              задача некорректна, и "оптимального" алгоритма (такого что с меньшим колличеством бросков ГАРАНТИРОВАННО обойтись нельзя) не существует. Это все равно что попросить за минимальное число вопросов (с ответами да/нет) угадать целое число от 1 до 10. Может сразу угадаешь, а может прийдется 10 вопросов задать (соответственно, если повезет можно за два броска узнать что он разбивается на 12-том, бросив сначала с 11-того а потом с 12-ого). Тут можно спрашивать только об алгоритме который "в среднем" заканчивается за наименьшее число бросков. Наверное что-то около 50-ти (плюс-минус 1).
                                                                                                                                                0
                                                                                                                                                Я конечно не программист, но на мой взгляд, при существующем на данный момент условии задачи, ответ такой:
                                                                                                                                                понадобится точное минимальное количество шагов - два!
                                                                                                                                                Поясню... Один шаг: разбивается, второй шаг: не разбивается (или в обратной последовательности). Причем этажи, понятное дело, соседние. А вот какие этажи и как я их определил/угадал - это уже другой вопрос/задача...

                                                                                                                                                З.Ы. тэг белого текста поставил, но не работает...
                                                                                                                                                  0
                                                                                                                                                  Я не согласна. Есть способ проще посчитать - 50 этаж, затем +/- 25 этажей, +/- 12 этажей и тд. в итоге 7 шагов
                                                                                                                                                    0
                                                                                                                                                    у вас шарик разбился на 50 этаже. У вас отсалось 6 шагов и 1 шарик - что будете делать? :-/
                                                                                                                                                      0
                                                                                                                                                      Они утверждают, что "мы неправы в такой ситуации": например шарик на 50 этаже разбился... а мы берем теперь 25 этаж, - но и тут шарик разбился - вот - пожалуйста - "мы" проиграли.
                                                                                                                                                        0
                                                                                                                                                        Да, я не права, невнимательно прочитала условие задачи)
                                                                                                                                                        Я не учитывала, что шаров - ограниченное число(
                                                                                                                                                          0
                                                                                                                                                          Не "имей" 2 шара, а "имей" 100 друзей (с)
                                                                                                                                                            0
                                                                                                                                                            Выясняется, что условие задачи корректировалось) В общем, при неограниченном числе шаров - 7 шагов.
                                                                                                                                                          0
                                                                                                                                                          Первый шарик разбился на 50 этаже, второй на 75. Вам понадобится больше шариков.
                                                                                                                                                            +1
                                                                                                                                                            зачем кидать шарик с 75-го этажа, если мы выяснили, что они разбиваются уже при броске с 50-го? =)))

                                                                                                                                                            со злости? =)
                                                                                                                                                              0
                                                                                                                                                              Из условия задачи:
                                                                                                                                                              чтобы точно узнать на каком именно этаже шарики начинают разбиваться?

                                                                                                                                                              У вас разбился на 50-м. Это не дает ответа.
                                                                                                                                                                +1
                                                                                                                                                                Хабрачеловек oisee намекает, что нужно было бы бросать с 25-го, а не с 75-го, ибо с 75-го уж точно разобьётся :)
                                                                                                                                                            0
                                                                                                                                                            так вы затратите больше 2-х шариков. предположим, они начинают разбиваться на 12-ом этаже. Первый шарик вы разобьёте на первом шаге (50-ый этаж), второй - на 25-ом этаже. в итоге - закончатся =)

                                                                                                                                                            хотя я тоже сначала также подумал ^_^
                                                                                                                                                            0
                                                                                                                                                            Люди о чем вы?
                                                                                                                                                            Шариков всего два.
                                                                                                                                                            Выяснить ответ можно кидая с первого и поднимаясь выше. Чтобы максимально сократить число бросков мы бросаем первый шарик с 50-го этажа.
                                                                                                                                                            if(разбился)
                                                                                                                                                            next=51;
                                                                                                                                                            else
                                                                                                                                                            next=1;

                                                                                                                                                            i=next;
                                                                                                                                                            while(не разбился)
                                                                                                                                                            {
                                                                                                                                                            бросаемСЭтажа(i);
                                                                                                                                                            i++
                                                                                                                                                            }
                                                                                                                                                              0
                                                                                                                                                              Чуть не так в коде... получается, если разбился берем 51, а надо 1... ну да это мелочи.. в целом задача ясна. Вроде логично.
                                                                                                                                                                0
                                                                                                                                                                Почитайте мой коментарий выше и все поймете
                                                                                                                                                                0
                                                                                                                                                                см. пояснение выше -> http://habrahabr.ru/blog/zadachki/34723.…

                                                                                                                                                                практически во всех случаях вы затратите больше 2-х шариков
                                                                                                                                                                  0
                                                                                                                                                                  Я все понимаю. Шарик разбивается на 1 этаже (как вариант катит). Отсюда - я бросаю с 1 этажа - так... чисто случаенно. Вот и мораль - точное минимальное число = 1. Точное, т.к. единица, а минимальное, т.к. 1 меньше любого "числа" из 100.
                                                                                                                                                                    0
                                                                                                                                                                    в условии задачи говорится про минимальное количество при самом неблагоприятном случае.

                                                                                                                                                                    если говорить про самый благоприятный случай - то ответом будет 0.

                                                                                                                                                                    это если мы заранее знали, или шарики у нас разбились до первого броска =)
                                                                                                                                                                0
                                                                                                                                                                Вроде, такую задачу легко решить на прологе, жаль, что сейчас занят на работе и нет "удобного времени подумать"...
                                                                                                                                                                  0
                                                                                                                                                                  А можно пойти другим путем - измерить геометрические и физические параметры шарика и рассчитать при какой нагрузке произойдет его разрушение. Далее, рассчитываем при броске с какого этажа сила удара будет равна или превысит эту нагрзуку. Итого, немного физики и математики и хватит одного броска. :)
                                                                                                                                                                    0
                                                                                                                                                                    Точнее, можно вообще шары не бросать. :) Значит правильный ответ - 0!
                                                                                                                                                                    0
                                                                                                                                                                    Нет никакого половинного деления. Всего два шара. Задача очень простая. Как оптимально выбрать этаж для броска первого шара - очевидно.
                                                                                                                                                                      0
                                                                                                                                                                      Ну... чисто логически, думаю со 2 этажа - уже должен разбиваться (опыт).
                                                                                                                                                                      0
                                                                                                                                                                      Предлагаю заменить шарики на кошек в условии задачи.
                                                                                                                                                                        0
                                                                                                                                                                        Ребята "сверху" утверждают, что за 14... имхо - это не правильный ответ!
                                                                                                                                                                          +1
                                                                                                                                                                          42
                                                                                                                                                                            0
                                                                                                                                                                            Этот ответ подходит для высоты любого дома...
                                                                                                                                                                              0
                                                                                                                                                                              > этот ответ подходит для любого вопроса...

                                                                                                                                                                              fixed =)
                                                                                                                                                                            0
                                                                                                                                                                            Открываем консоль firebug, пишем туда:
                                                                                                                                                                            for(var i=1;i<100;i++){console.log(i, i/2+100/i)}

                                                                                                                                                                            Отыскиваем минимальное число в правой колонке, ответ — число слева.
                                                                                                                                                                              0
                                                                                                                                                                              e*10^3-12[1] ?
                                                                                                                                                                              0
                                                                                                                                                                              Повторяю, возможно действительно я немного ошибся в формулировке. Очень сложно верно сформулировать, если сам понимаешь, ведь пребываешь в уверенности, что и остальные поймут =) Возможно, у меня проблемы с русским, но я и сейчас не могу толком сформулировать точно. Если кто-то осилит, откорректирую пост.
                                                                                                                                                                              Прошу прощения =(
                                                                                                                                                                                0
                                                                                                                                                                                Нашёл вот это: "за какое минимальное число шагов мы можем гарантированно определить этаж в самом худшем (для нас) случае?"

                                                                                                                                                                                Наверное, так действительно правильнее.
                                                                                                                                                                                0
                                                                                                                                                                                Ну, чем кончилось? Какой ответ:
                                                                                                                                                                                  0
                                                                                                                                                                                  Да уже много раз мелькал, даже белым писать не стоит - 14.
                                                                                                                                                                                  0
                                                                                                                                                                                  На мой взляд, ответ 14 неверен. Вот мой контрпример: если шарик разбивается на 97 этаже, то мы потратим 6 бросков на то, чтобы убедиться, что на 84 он не разбивается и потратим еще один, чтобы узнать о том, что на 98 шарик все-таки разобьется. Далее, перебирая по одному этажу, придется потратить еще целых 13 попыток. Итого - 20 раз. Таким образом, если требуется определить минимальное число бросков, которые требуются для того, чтобы точно определить самый нижний этаж, на котором шарик будет разбиваться, при наличии только двух шариков, 14 попыток может оказаться явно недостаточно. Так что 20 явно ближе к правильному ответу, чем 14.
                                                                                                                                                                                    0
                                                                                                                                                                                    Вы где-то упустили. После 84го надо пробовать бросать с 90го, потом с 95го, 99, 100.
                                                                                                                                                                                      0
                                                                                                                                                                                      Модифицирую свой пример, учивывая вашу поправку: если шарик теряется на 83, то 6 бросков на то, чтобы узнать, что шарик разобьется, а затем, перебирая по одному(иначе никак - шарик-то один остался), потратить еще 12 попыток (с 71 этажа по 83). Отсюда получаем 18.
                                                                                                                                                                                        0
                                                                                                                                                                                        Прошу прощения, осознал свою ошибку. 14.
                                                                                                                                                                                    0
                                                                                                                                                                                    множители числа, образующие минимальную сумму?
                                                                                                                                                                                      0
                                                                                                                                                                                      Эта задача из семейства поиска локального минимума. Вариантов решения много. Я выбрал матод "золотого сечения". За 9 шагов нашел ответ:)
                                                                                                                                                                                        0
                                                                                                                                                                                        Ммм... Мне кажется вы ошиблись... Да, точно, ошиблись.
                                                                                                                                                                                          0
                                                                                                                                                                                          поделитесь опытом пожалуйста... какже это у Вас так получилось?... На скока я помню этот метод и даже попробовал его сюда применить - алгоритм неоптимален, в отличие от описанного выше... Например если шарик только на 99 этаже разбивается - сколько минимально шагов надо сделать точно при методе "золотого сечения" и каким образом? или может быть Вы ошиблись?
                                                                                                                                                                                            0
                                                                                                                                                                                            по методу золотого сечения на каждом шаге отрезок(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 - УРАА!!!!!:)
                                                                                                                                                                                              0
                                                                                                                                                                                              окей... первый этаж с которого бросают 39...
                                                                                                                                                                                              и опачки! шарик разбился!
                                                                                                                                                                                              что дальше? от первого до 39 по одному этажу шагать и чикирить на каком разобьется?... это 40 шагов...
                                                                                                                                                                                              Да, можно применить и такой алгоритм - но это не 9 шагов и не 14...
                                                                                                                                                                                              или на 39 не разбился а на 61 разбился..... и допустим разбиваться начинает на 60.... от 39 до 60 - 21 этаж... т.е. это 22 шага...
                                                                                                                                                                                              Увы, но алгоритм неоптимален!
                                                                                                                                                                                                0
                                                                                                                                                                                                Первый раз бросаем не с 39го, а с 61го. В зависимости от того шарик разбился или нет выбираем половину(Выше-ниже). И эту половину опять разбиваем на части в отношении 61 к 39. Сто этажей этим алгоритмом проходиться за 6-7 разбиений. Это классика. Можно делить и 50 к 50. Пример наглядно демонстрирует оптимальность метода.
                                                                                                                                                                                                  0
                                                                                                                                                                                                  аргументируй?(с) Помните что у Вас всего ДВА шарика! А определить надо с ТОЧНЫЙ этаж, а не ПРОМЕЖУТОК в котором шарик где-то разбивается...
                                                                                                                                                                                                    0
                                                                                                                                                                                                    Насчет двух я забыл...:( сорри. Тогда этот алгоритм даст нам точно окно не более 24х этажей:)
                                                                                                                                                                                                      0
                                                                                                                                                                                                      что, собственно, и требовалось доказать... =)
                                                                                                                                                                                          0
                                                                                                                                                                                          Отличная задача! Спасибо. Я бы сформулировал вопрос так:
                                                                                                                                                                                          Существуют разные алгоритмы бросания шаров для поиска номера этажа с которого начинается разбиваться шарик. Каждый алгоритм гарантирует определение этажа не более чем за N бросков (например не более чем за 100, если бросать последовательно начиная с нижних этажей). Найдите минимум N и опишите оптимальный алгоритм.
                                                                                                                                                                                            0
                                                                                                                                                                                            Мне кажется стоит изменить формулировку. Ведь по условиям задачи ищется не минимальное, а безызбыточное количество шагов, чтобы хабражители не путались. То есть напишите указание, что нужно найти как с минимальными затратами находить этаж в произвольном доме, а то некоторые станут теорию вероятности вспоминать))) А как подсказка можно было бы написать, что при правильном ответе оба шарика в любом случае разобьются)
                                                                                                                                                                                              0
                                                                                                                                                                                              Упс, предыдущим постом Aleco меня опередил)
                                                                                                                                                                                              +1
                                                                                                                                                                                              прям в тему блин :)
                                                                                                                                                                                              какую бы cms выбрать,
                                                                                                                                                                                              и нужна ли она вообще или проще будет не разбираться в ней, а слегка освежить пхп?
                                                                                                                                                                                                +1
                                                                                                                                                                                                Кстати предложенный вариант хоть и логичный, но не самый оптимальный...

                                                                                                                                                                                                Я захотел найти самый оптимальный вариант. Под ним я подразумеваю вариант поиска при котором (количество шагов в данном методе для поиска ответа елси ответ равен "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
                                                                                                                                                                                                  извиняюсь забыл защитить табы от съедания =(
                                                                                                                                                                                                    0
                                                                                                                                                                                                    //P.S. define integer st
                                                                                                                                                                                                    int st;
                                                                                                                                                                                                    0
                                                                                                                                                                                                    Пусть шаг первого шарика оптимален и равен 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) уже не верна? ;)
                                                                                                                                                                                                      0
                                                                                                                                                                                                      Если интересно — мне удалось доказать. Всё решение полностью выложу, схема примерно такая:

                                                                                                                                                                                                      1) Пусть для N этажей можно всё определить минимум за M зашагов. Т. е. всякое определение будет соотвествовать последовательность типа 0...010...01, энтропия будет линейна по log_2(M).
                                                                                                                                                                                                      2) Пусть есть верная оценка для M вида C*N(1/2-epsilon). Находим минимальное N, для которого количество информации об минимальном этаже (log(N) бит) окажется больше log(M).

                                                                                                                                                                                                      Фактически решение ещё интересно тем, что за 13 шагов 100% нельзя всегда уже найти нужный этаж. Но вот поведение на бесконечности — хорошее упражение по теории информации.
                                                                                                                                                                                                        –1
                                                                                                                                                                                                        за что минусанули-то? ошибку нашли — так написали бы, пересмотрел — правильно всё я написал.
                                                                                                                                                                                                      0
                                                                                                                                                                                                      задача была бы интереснее если бы этажей было с миллион а вложенность поиска с десяток хотя бы) то есть кол-во шариков) может порешаем?)
                                                                                                                                                                                                        0
                                                                                                                                                                                                        Придется решать полиномиальное неравенство степени по числу шаров. ;)

                                                                                                                                                                                                        В случает кстати шаров степени двойки решается как корень этой степени из N.
                                                                                                                                                                                                          0
                                                                                                                                                                                                          то есть вы предлагаете на париться по этому поводу, а просто пойти лучше поработать? :)
                                                                                                                                                                                                          хотя я наверное не прав, весь изюм наверное в том что ее можно решить в уме (эту конкретную)
                                                                                                                                                                                                        0
                                                                                                                                                                                                        5 способов, верно?
                                                                                                                                                                                                          –2
                                                                                                                                                                                                          ИМХО 6 попыток

                                                                                                                                                                                                          бросаем с 50, c 75, если не разбился. Или с 25-го если разбился.
                                                                                                                                                                                                          потом 13, потом 6, потом 3, потом 2 например. В обратную сторону аналогично....

                                                                                                                                                                                                          Как-то сей метод называется толи Ньютона, толи секущих.... кароче двойка у меня была по математике.

                                                                                                                                                                                                          Суть, что делим отезок пополам....
                                                                                                                                                                                                            0
                                                                                                                                                                                                            Погугил :)))
                                                                                                                                                                                                            http://elib.ispu.ru/library/math/sem1/in…

                                                                                                                                                                                                            глава 9.
                                                                                                                                                                                                            Задача решинается след методами:
                                                                                                                                                                                                            Метод половинного деления (который я первм описал), методом секущих, методом одной касательной, методом Ньютона и методом хорд. :)))
                                                                                                                                                                                                            формулы сложные тут не помесятся...
                                                                                                                                                                                                              0
                                                                                                                                                                                                              да-да, вот только хотел об этом сказать. В институте на предмете "оптимальное управление" (методы оптимизации) такие задачи приходилось решать. Причем эта - практически типичная.
                                                                                                                                                                                                              Математическим языком это задача условной минимизации, т.е. задача по нахождению минимума функции на конечном отрезке за минимальное количество итераций (шагов). Решается несколькими методами: методом деления отрезка пополам, методом "золотого сечения", методом Ньютона, методом аппроксимации, еще были, не помню :)

                                                                                                                                                                                                              З.Ы. Что-то сейчас взялся решать самым простым и надежным методом - методом деления отрезка пополам. Ответ удивил - 7, а не тот ответ, что предложил автор.
                                                                                                                                                                                                              Ход решения просто: делим отрезок 100 пополам. Кидаем с "серединного" этажа (можно выбрать 50 или 51 - не суть важно). Шар не разбивается (иначе задача не умела бы смысла), далее делим аналогично соответствующий отрезок, пока исковый не сужается до одного точного значения.
                                                                                                                                                                                                              З.З.Ы. Что-то сам засомневался. Возможно, ошибаюсь.
                                                                                                                                                                                                                0
                                                                                                                                                                                                                Ваши решения не работают потому, что шарика ь? Перебирать с первого до 49? Ваши решения оптимальны, если шариков бесконечно много или хотя бы 6, 7, 10 - в зависимости от решения.
                                                                                                                                                                                                                  0
                                                                                                                                                                                                                  Извините, тег съехал. Шарика всего 2.
                                                                                                                                                                                                              0
                                                                                                                                                                                                              Устал читать все комменты, хотел написать свой, но заметил Ваш. В общем, та же идея.
                                                                                                                                                                                                                0
                                                                                                                                                                                                                а если с 50 разбился? :)
                                                                                                                                                                                                                Этот способ не работает.
                                                                                                                                                                                                                –1
                                                                                                                                                                                                                Этот пост о том, как группа людей "придумала ответ"... а потом под этот ответ и "вопрос сделали"!
                                                                                                                                                                                                                  0
                                                                                                                                                                                                                  7 шагов
                                                                                                                                                                                                                  Бросаем со среднего, потом в зависимости от результата с 75 или 25 и т.д., ограничивая диапазон. Хватит 7 шагов.

                                                                                                                                                                                                                  P.S. Сорри, подсказка про ХТМЛ-теги у меня не сработала (ошибка MySQL), не знаю как белым написать.
                                                                                                                                                                                                                    0
                                                                                                                                                                                                                    Пишу тоже самое, что писал выше. Шарика всего 2! Если первый разобьётся на 50-ом этаже, что дальше делать? Ведь второй разбить можно только на шаге, который точно определит этаж, с которого шарики начинают разбиваться.
                                                                                                                                                                                                                    0
                                                                                                                                                                                                                    Минимум - два. Если с первого раза шарик разбился - нужно проверить разобьется ли он этажом ниже.
                                                                                                                                                                                                                    Если не разобьется - вот ответ, который получается минимум за два шага.
                                                                                                                                                                                                                      0
                                                                                                                                                                                                                      А если второй разобьётся? :)))
                                                                                                                                                                                                                        0
                                                                                                                                                                                                                        А если нет?
                                                                                                                                                                                                                        Спрашивается же минимальное. Правда если разобьется с первого этажа - минимальное число шагов - 1.
                                                                                                                                                                                                                        Вот если б спрашивали среднее - тогда было б что посчитать.

                                                                                                                                                                                                                        А вообще можно так.
                                                                                                                                                                                                                        Бросил с первого:
                                                                                                                                                                                                                        --- разбился -> выход;
                                                                                                                                                                                                                        --- нет -> бросаю с десятого:
                                                                                                                                                                                                                        -------- разбился - иду с второго по девятый, пока не разобьется;
                                                                                                                                                                                                                        -------- не разбился - бросаю с 20:
                                                                                                                                                                                                                        --------------------- разбился - иду с 11 по 19, пока не разобьется;
                                                                                                                                                                                                                        --------------------- нет - бросаю с 30 и т.д....
                                                                                                                                                                                                                          0
                                                                                                                                                                                                                          В таком случае - минимум - один, максимум - 20. И всегда можно дойти до решения.
                                                                                                                                                                                                                            –1
                                                                                                                                                                                                                            в подобных задачах под минимумом подразумевается оптимальное решение для варианта самого неблагоприятного размещения.
                                                                                                                                                                                                                            т.е. отбросив случайность вы должны рассматривать самый худший вариант, что может быть для вашего алгоритма.
                                                                                                                                                                                                                            минимум у вас - 20 - это много.
                                                                                                                                                                                                                            правильный ответ 14 ходов.
                                                                                                                                                                                                                              0
                                                                                                                                                                                                                              Все, нашел. В общем-то мысли в верном направлении, по разному подбор следующего этажа.
                                                                                                                                                                                                                              Удачная задача, было интересно подумат