На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Оставь надежду всяк сюда входящий
1) На раздел распространяются все правила форума.
2) Ответы на головоломки необходимо давать только в теге SPOILER. Сообщения в обход этого правила будут удаляться. Постоянное
нарушение данного пункта правил, повлечет за собой наказание.
3) Автор темы должен указать, известно ли ему решения задачи и сроки в которые он опубликует решение.Рекомендуется вести список отгадавших в первом сообщении.
4) При создании новой темы, в описании или в самом названии четко укажите разновидность задачи.
5) Полная версия правил раздела, находится в теме правила раздела.
Модераторы: Братец Лис
Страницы: (52) « Первая ... 50 51 [52]   ( Перейти к последнему сообщению )  
> Интересные задачки
    Цитата ya2500 @
    Геннадий моделирует игру конвея на поле N*M, засевая его клетками жизни с вероятностью 1/3; и хочет сделать границы поля такими, чтобы развитие ситуации на его поле выглядело как можно более похожим на то, как если бы его поле было частью бесконечного поля, засеянного клетками жизни с вероятностью 1/3. ВОПРОС: как можно этого добиться?

    А... нужно, чтобы была эмуляция бесконечного поля. Тогда генерировать вначале бордюр с шансом 1/3 на живую клетку, в остальные ходы сначала прогонять всё поле как если бы снаружи ничего не было, а потом с шансом 1/3 рожать новую клетку при 2 соседях и с ним же очищать живую клетку при трех. Для углов шанс 1/2 и рожать при 1 соседе, а удалять при двух, а если их три, то удалять с 100% шансом.
    Сообщение отредактировано: Vesper -
    Долог путь в бессмертие... я еще вернусь.
    Профильный скилл "Телепатия" 8%
    ТРОЛЛЬ - Троян Разрушительный Опасный, Лучше ЛинятЬ (с) Freezing Spell
    Прошу потестить игру.
      но таки
      очередная задачка:

      Имеется N монет, некоторые из них правильные и весят по 10г, а остальные фальшивые, весом по 9г. За какое наименьшее число взвешиваний на одночашечных весах со стрелкой можно определить все фальшивые монеты?

      Добавлено
      (количество фальшивых монет неизвестно)
        В этой задаче существенным является обязательность наличия монет по крайней мере одного из видов. Иначе задача становится неразрешимой.
        И конкретный вес монет не важен. Важно только что все нормальные монеты одного веса. Все фальшивые тоже одного веса и легче нормальных.

        Ясно, что N-1 взвешивания достаточно. Просто берём одну монету и сравниваем с ней все остальные. Получаем два класса: более лёгкие и равные по весу; или равные по весу и более тяжёлые. В первом классе будут фальшивые монеты, во втором правильные.
        И в любом случае понадобится не менее примерно 0,63*N взвешиваний, так как весы могут при взвешивании быть только в 3 положениях (предполагается, что стрелка без шкалы)
        Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
          amk,весы одночашечные.
          Мои религиозные убеждения не позволяют мне комментировать код.
          Моё мировоззренье таково: в программе комментария ни одного!
            Цитата amk @
            В этой задаче существенным является обязательность наличия монет по крайней мере одного из видов.


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

            Цитата amk @
            так как весы могут при взвешивании быть только в 3 положениях (предполагается, что стрелка без шкалы)

            Цитата MIF @
            amk,весы одночашечные.


            MIF, точно.

            user posted image

            Добавлено
            - то есть, например, первым шагом можно положить все монеты в чашу и узнать их общий вес. Что, на мой взгляд, вполне себе неплохой ход.
            Сообщение отредактировано: ya2500 -
              Цитата ya2500 @
              Если наличие хотя бы одной монеты каждого вида как-то упростит задачу, то можно рассмотреть решение для этого случая.
              Для указанных весов это требование излишне. Но для них грубая верхняя граница не N-1, а N (взвесить отдельно каждую монету). Нижняя граница у меня получается не намного ниже.

              С весами с картинки задача неразрешима (у них в лучшем случае погрешность порядка веса одной монетки). Существуют электронные весы для взвешивания относительно малых масс (порядка 200–300 г), с погрешностью около 0.1 г

              С рычажными весами для относительно малого числа монет уменьшить число взвешиваний меньше N-1 у меня не получилось.
              С этими весами у меня пока самый эффективный алгоритм получается таким:

              Взвешиваем все монеты, определяем общее число фальшивых монет, складываем все монеты в одну кучку (потом кучек будет больше) и кладём в неё бумажку (условно) с указанием числа фальшивых монет в ней.
              Берём любую из кучек, если в ней нет фальшивых монет, откладываем их к нормальным монетам, если все фальшивые - откладываем к фальшивым.
              Иначе, делим кучку пополам (с разницей в одну монету), одну кучку взвешиваем, определяем число фальшивых в ней, вычитанием определяем их число во второй половинке, и формируем кучки (с условными бумажками).
              Когда кучек не останется, все монеты будут поделены на нормальные и фальшивые.
              Для четырёх монет такой алгоритм требует от одного до трёх взвешиваний (как для трёх монет).

              Худший случай, если фальшивыми являются ровно половина монет, и они при делении кучек будут распределяться строго поровну.
              Несколько наихудших случаев

              Тогда для 8 монет получим:
              номер_последнего_взвешивания: число_кучек*размер_кучки(число_фальшивых_в_кучке)
              0: 1*8(4)
              1: 2*4(2)
              3: 4*2(1)
              7: 4*1(0), 4*1(1) - разделение завершено.

              12 монет:
              0: 1*12(6)
              1: 2*6(3)
              3: 2*3(1), 2*3(2)
              7: 2*1(0), 4*2(1), 2*1(1)
              11: 6*1(0), 6*1(1)

              20 монет:
              0: 1*20(10)
              1: 2*10(5)
              3: 2*5(2), 2*5(3)
              7: 4*2(1), 2*3(1), 2*3(2)
              15: 6*1(0), 4*2(1), 6*1(1)
              19: 10*1(0), 10*1(1)

              256 монет:
              0: 1*256(128)
              1: 2*128(64)
              3: 4*64(32)
              7: 8*32(16)
              15: 16*16(8)
              31: 32*8(4)
              63: 64*4(2)
              127: 128*2(1)
              255: 128*1(0), 128*1(1)

              Нечётные группы везде делились так, чтобы в чётной части ровно половина монет оказывались фальшивыми, остальные попадали в нечётную часть.
              Как легко заметить, что во всех рассмотренных наихудших случаях больше одного взвешивания сэкономить не получается
              Зато ожидаемое число взвешиваний получается заметно меньше.


              Добавлено
              Ошибка, я забыл про самое первое взвешивание, и в худшем случае требуемое число взвешиваний всегда получается равным числу монет.
              Сообщение отредактировано: amk -
              Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                Цитата amk @
                С рычажными весами для относительно малого числа монет уменьшить число взвешиваний меньше N-1 у меня не получилось.
                Цитата amk @
                Ошибка, я забыл про самое первое взвешивание, и в худшем случае требуемое число взвешиваний всегда получается равным числу монет.


                И для миллиона монет, в худшем случае, получится миллион взвешиваний? Даже действуя по оптимальному алгоритму? Кхмм... Мне не известен верный ответ, но мне известно, что его найти должно быть непросто... и неужели это он и есть?
                  Я проверял все наборы до 8 монет (сидел на больничном, так что времени было много). И всегда находился набор, который требовал количества взвешиваний, равного числу монет.

                  Ну и почему я склоняюсь к тому, что верхняя граница всегда равна числу монет.
                  Ясно, что монеты всегда можно взвесить по одной, так что необходимое число взвешиваний не может быть больше числа монет.

                  Для одной монеты всегда требуется одно взвешивание.
                  При двух монетах мы можем взвесить две монеты вместе (при этом сразу определяются случаи, когда обе монеты нормальные, или обе фальшивые). При этом если среди них есть монеты обеих видо, мы не можем сказать, какая их них какая. Поэтому придётся производить второе взвешивание.
                  Аналогично можно разобрать три, четыре монеты и т.д.

                  Фактически в начале мы имеет кучку монет с неизвестным количеством фальшивых монет и ни одной, количество фальшивых в которых известно.
                  Каждое взвешивание делит какую-то кучку на две части. Если делится начальная кучка, то количество фальшивых известно для взвешенной части, и неизвестно для оставшейся. Иначе известны оба.
                  Главное, что мы можем сказать: количество кучек с известным количеством фальшивых монет равно числу произведённых взвешиваний. Естественно, предполагается, что мы не взвешиваем заново всю кучку целиком. Но, в худшем случае, мы можем сказать, что все монеты в кучке нормальные или все фальшивые, только для кучек из одной монеты, а значит нам придётся разбить исходную кучку на отдельные монеты, а для этого потребуется число взвешиваний, равное числу монет.
                  Комбинирование при взвешивании монет из разных кучек не уменьшает число взвешиваний, лишь немного усложняет процедуру.
                  Всё написанное выше это всего лишь моё мнение, возможно ошибочное.
                  1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
                  0 пользователей:
                  Страницы: (52) « Первая ... 50 51 [52] 


                  Рейтинг@Mail.ru
                  [ Script Execution time: 0,1365 ]   [ 14 queries used ]   [ Generated: 21.01.20, 23:58 GMT ]