На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Сто этажное здание и 2 мячика. Алгоритм нахождения этажа.
    Здравствуйте, форумчане! По дескретной математике нам задали интересную задачу, может быть кто то уже сталкивался с ней или просто сможет дать ответ. Условие задачи следующее:
    есть сто этажный дом и 2 мячика нужно найти алгоритм(с наименьшим количеством бросков) для поиска того этажа, с которго сброшенный мячик расколется.

    Пробовал найти алгоритм, но нашел тока тривиальный - сбрасывать через каждые 10 этажей. И в худшем случае(если окажется что этаж с которого надо сбросить - это 99) придется потратить 10+9=19 попыток. Но препод сказал что должно получиться 14. Подкиньте плиз идейку ;)
      Ну раз 14 - наименьшее количество бросков, то надо поднятся на четырнадцать етажей и сбросить мяч, потом тодняться ешё на 13 етажей, потом ешё на 12 и .т.д.
        Цитата int0x25 @
        в худшем случае(если окажется что этаж с которого надо сбросить - это 99) придется потратить 10+9=19 попыток

        Считаете плохо... зачем с сотого-то пробовать?
            Бинарный поиск. Проверяем 50-й этаж, если разбился - 25-й, если не разбился - 75-й. И так далее.
              Цитата Pacific @
              Бинарный поиск. Проверяем 50-й этаж, если разбился - 25-й, если не разбился - 75-й. И так далее.

              А если с 50-го разбился, и с 25-го разбился, то дальше мы остались без мячиков :whistle:
                Что-то я не понял условия :unsure: . Для того, чтобы опредилить ПРОИЗВОЛЬНЫЙ этаж, с которого разобъётся шарик - достаточно одной попытки. А именно залезть на сотый этаж и кинуть оттуда, если разобъется - ответ готов. Если нет - то у нас неразбиваемые шарики :P . Ведь вряд ли ж если после этого мы скинем, скажем, с 50 этажа - то шарик разобъётся.
                А если надо определить МИНИМАЛЬНЫЙ этаж - то надо примерно 50 попыток. Начинать кидать с 1 этажа, и продолжать через один. Так как, из условия получается, что у нас 2 попытки. Или может быть int0x25 ты что пропустил из условия, считая это маловажным ;)
                Сообщение отредактировано: _lcf_ -
                  Нет, задачка-то известная. Надо определить минимальный этаж. Но 50 попыток - это слишком. Правильный ответ - действительно 14.
                    Сначала кидаешь с 14 этажа, если не разбился-с 27. Дальше сам...
                      Задача может быть решена методом подбора. Покажу на примере.

                      Допустим, мы хотим проверить, хватит ли 16 бросков.
                      Первым шагом считаем, что первый шарик сразу разобьется, и по 1 этажу придется искать вторым, потратив максимум 15 бросков. Следовательно первый бросок будет сделан с 16 этажа.
                      Далее считаем что первый шарик разобьется на 2 броске, а вторым придется сделать 14 оставшихся бросков. Второй бросок тогда будет с 31 этажа (16+15)... и так далее...

                      Алгоритмизируя, приходим к поиску такого наименьшего X, что сумма чисел от 1 до Х больше заданного количества этажей. Это 14, сумма равна 105. Первые броски производятся соответственно с 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 этажей.
                        А зачем подбором? Можно и мат. последовательность считать:
                        k = xСуммаk = 1k >= 100. На интересует значение k. Получаем 14. :)
                          Всем спасибо за помощь, особенно _lcf_ за конкретную формулу, а то я все таки догадался сегодня до 14,13,12... но не мог понять почему именно,начиная с 14, будет минимальное количество шагов. А как будет выглядеть формула в общем случае если n этажей и k шаров,причем о соотношении n и k ничего неизвестно,т.е. метод золотого сечения по-прежнему не применить?
                            Цитата int0x25 @
                            т.е. метод золотого сечения по-прежнему не применить?

                            :no-sad: попыток мало.
                              Цитата int0x25 @
                              n этажей и k шаров

                              Минимальное k, удовлетворяюшее условию: k*(k + 1)/2 >= n
                                Цитата _lcf_ @
                                А зачем подбором?

                                Чтобы понять, как составить формулу. Не зря я именно после подбора перешел к алгоритмизации, а не сразу. Твоя формула и формула MIF получены именно из этих рассуждений. Вернее, обоснованы ими.
                                1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0.0777 ]   [ 14 queries used ]   [ Generated: 22.11.26, 20:08 GMT ]