На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Сто этажное здание и 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 получены именно из этих рассуждений. Вернее, обоснованы ими.
                                  MIF, что то я не понял твою формулу k*(k + 1)/2 >= n не мог бы ты разъяснить? Например у нас n=100 этажей и k=3 шаров как тогда найти мин количество этажей?
                                    Формула Мифа это другая запись моей (11 сообщение) формулы. Следует из того, что:
                                    1 + 2 + 3 + ... + k
                                    Можно представить как сумму крайних элементов:
                                    1 + k; 2 + (k - 1); 3 + (k - 2)
                                    1 + k; 1 + k...
                                    которая повторяется k/2 раз.

                                    С тремя шарами посложнее будет...
                                      Теперь понятно, а то я думал это как раз ответ на общий вариант n этажей и k шаров. Я вот думаю в общем случае для k шаров можно делать примерно так : сначала найти разбиение на этажи как для 2 шаров, а потом в каждом промежутке не проходить по одному этажу как это было при одном оставшемся шаре, а использовать метод золотого сечения, либо до того момента как найдется нужный этаж, либо до того момента как останется один шар, и им уже пройти по-одному оставшиеся этажи. Логично ли что это и будет нужным алгоритмом или можно лучше?
                                        С тремя шарами вроде двойная формула:
                                        y=(x-1)Sy=0 (k=ySk=0 k) + 1>= 100
                                        .
                                        Вроде 1 там нужна (?). Хотя формулы так и не пишут :P
                                        Получается х = 9.
                                        (9) -> (8) + 1 -> 36 + 1
                                        (8) -> (7) + 1 -> 28 + 1

                                        Кидаем: 37, 66, 88, 104 (100).
                                        Если на 37 разбивается: 8, 15, 21, 26, 30, 33, 35, 36.
                                        Если на 66 разбивается: 44, 50, 55, 59, 62, 64, 65.

                                        Добавлено
                                        Цитата int0x25 @
                                        использовать метод золотого сечения

                                        Забудь ты про золотое сечение! Тут это не катит. От количества шаров будет зависеть количество вложенных сумм, по принципу: k - шаров, (k - 1) сумм. Осложняется еще все этой вылезшей вдруг единицей.
                                        Сообщение отредактировано: _lcf_ -
                                          _lcf_ спасибо за формулу и за подробное описание того, как она работает!
                                          1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                                          0 пользователей:


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