theJam.ru

Логические задачиСортировка гирек

2 августа 2008 | Добавил:

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

За какое минимальное число взвешиваний это можно сделать? Опишите алгоритм действий.

Хотите регулярно получать новые задачи и познавательные топики? Подпишитесь на рассылку

Комментариев: 25

  1. SusAnna пишет:

    Нутром чую, что можно за 7, а пока получается только за 8...
    Мое нутро ошибается?

  2. rin пишет:

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

  3. SusAnna пишет:

    rin, напишите алгоритм для нашей критики :) а зашифровывают обычно просто. читайте ЛС.

  4. rin пишет:

    Хорошо! В общем вот:
    1. взвесим сначала эти пары \12/-\34/ к примеру вторая пара тяжелее
    2. затем взвешиваем \1/-\2/ пусть тяжелее 2
    3. взвешиваем \3/-\4/ тяжелее 4
    4. теперь взвесим лёгкую гирю из "тяжелой" пары(3) с тяжелой гирей из "лёгой"(2) \3/-\2/ по традиции пусть тяжелее 3
    5. самое интересное с чем взвесить 5 гирю? Взвесим её с 3, а вот тут могут возникнуть два различных исхода
    5а. \5/-\3/ тяжелее 5
    6а. \5/-\4/ без разницы, что тяжелее, задача решена за 6 взвешиваний! Но может и так:
    5б. \5/-\3/ тяжелее 3
    6б. \5/-\2/ тяжелее 2 (если легче,то задача решена)
    7б. \5/-\1/ задача решена
    Не дай Бог опять что-нибудь промаргал)

  5. SusAnna пишет:

    rin, а почему Вы не рассматриваете наихудший вариант, когда \12/ == \34/?
    И еще, рассмотрим вариант гирек \12/ - \34/
    1. определили, что 34 тяжелее
    2. Определили, что 2 тяжелее 1
    3. Определили, что 4 тяжелее 3
    4. а теперь по Вашему алгоритму мы определяем 3 и 2. Определили, что 3 тяжелее 2, а если 2 тяжелее 3? Получаем 2>3, 2>1 и 4>3, но мы не знаем как относятся 1 и 3 и как относятся 2 и 4. Для примера рассмотрите вариант весов гирек 3+4 и 1+7.

  6. rin пишет:

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

  7. Nicholas пишет:

    Я знаю 2 алгоритма: один носит имя пузырька, а другой не помню как, но там все попорядку сравниваются, пока не отсортируются. :) Кажется так.

  8. rin пишет:

    Предыдущее моё замечание касалось первой части замечания SusAnnы
    По поводу второй части:
    мы ведь берём лёгкую гирю из тяжёлой пары, а тяжёлую гирю из лёгкой, поэтому если вдруг выйдет 2>3 то гирьки расположатся по убыванию массы так: 4>2>...(это уж точно), а затем действительно возникает ещё одно лишнее взвешивание \1/-\3/...
    тогда тоже только 8

  9. SusAnna пишет:

    вооот, за 8 я уже давно решила, но вот почему-то кажется что можно за 7 по одной такой логике интересной, выношу свои мысли на о(б)суждение:
    Всего вариантов расположения гирек 5! = 125. Обозначим результат сравления "больше" как "1", а "меньше" - "0". Таким образом, после n случаев сравнения мы получим некоторое число в двоичном представлении. Так вот, чтобы однозначно по этому двоичному числу определить выбранное разположение гирек необходимо 7 измерений (т.к. 2^7 = 128, и 3 двоичных числа сравнений - запрещенные комбинации, то есть такие результаты, которых быть не может). Вопрос в том, чтобы найти такую последовательность сравнений, в которой ни один результат не выводился из другого (например 2>3, 3>1, то что 2>1 очевидно и такое измерение будет лишним).

  10. rin пишет:

    Такой вариант я попробовал(обозначил наконец гирьки буквами A B C D E)
    A>B
    C>D
    D>B в противном случае ситуация будет симметричной
    A>B<D<C
    остается еще 4 взвешивания, начал просчитывать варианты и при некоторых раскладах вылазеет 5 взвешивание...
    Кстати не сказал: четвёртое взвешивание сделал А с Е, а затем в одном случае начинал взвешивать А с С, в другом Е с С...

  11. rin пишет:

    не то жирным выделил:)

  12. SusAnna пишет:

    rin, ну и опять та же ошибка...
    "A">"B", "C">"D"
    1. "D">"B" => "A">"B"< "D"<"C", НО! отсюда не известно "A">"D"? и "A">"C"?
    2. "D"< "B" => "A">"B">"D", НО! не известно "C">"B"?
    Блин, это не Вы не то жирным выделили, это надпись <"B" (только без кавычек) воспринимает как тег "жирный" :)

  13. rin пишет:

    Я понимаю что ситуация с А(в первом случае) не ясна, поэтому и говорю, что следующим шагом взвешиваю А с Е , а потом в зависимости, что тяжелее либо А, либо Е, взвешиваю поочередно эту гирьку с гирьками D, C.

  14. SusAnna пишет:

    что-то я Вас не пониамю... Можно весь алгоритм в студию

  15. XANT пишет:

    Предлагаю следующее решение:
    -Первое взвешивание: сравним любые 2 из 5 данных предметов. Пусть A - более легкий, а B - более тяжелый предмет. Тогда результат первого взвешивания запишем в виде A<B (читается: «A легче В»).
    -Второе взвешивание: сравним два других предмета и обозначим более легкий D а более тяжелый - E: D<E.
    Пятый предмет обозначим C.
    -Третье взвешивание: сравним предметы B и E. Обе возникающие здесь возможности приводят к аналогичным рассуждениям, поэтому мы ограничимся рассмотрением случая B<E. В итоге после трех взвешиваний мы знаем, что A<B<E и D<E.
    -Четвертое взвешивание: сравним пятый предмет C с предметом B. Необходимо различать два случая:
    а) B<C;
    б) C<B.
    В первом случае (B<C)
    A<B<E, D<E и B<C.
    -Пятое взвешивание: сравним предметы C и E. Здесь также необходимо различать два возможных случая: E<C или C<E.
    Если A<B<E<C, то место предмета D, более легкого, чем E, можно определить, сравнив A с D и B с D. Таким образом, для полного упорядочения пяти предметов по весу в этом случае необходимо произвести 7 взвешиваний.
    В случае A<B<C<E для определения места D также достаточно произвести два взвешивания, а именно: сначала сравнить D с B, а затем в зависимости от результата взвешивания сравнить D либо с A либо с C. В итоге мы снова производим 7 взвешиваний.

  16. rin пишет:

    2 сентября 2008 в 22:13 размышлял подобно, но какого то черта взвешивал 5й элемент(4е взвешивание) с крайней по весу гирькой А! Какого чёрта не догадался взвешивать её с какой-нибудь стоящей внутри гирькой?

  17. XANT пишет:

    Все нормально, все свои.
    rin именно Вы и другие на 99,9% решили данную задачи ну потом осталось самая малость.

  18. Pantheon пишет:

    А Serge так и не удосужился ни прокомментировать ответы публики, ни правильный ответ дать на задачу :(
    У него самого-то есть правильное решение этой задачи?
    Так каково минимальное количество подходов и как полагается правильно их взвешивать?

  19. SusAnna пишет:

    Pantheon, сомневаться в правильности своего решения может только тот, кто не просчитал другие варианты :)

  20. Serge пишет:

    Pantheon, а я не знаю ответ, вместе с вами думаю

  21. x4m пишет:

    медианная сортировка даёт 8

    . +1 сорт =>
    .. +2 сорт =>
    ... +2 сорт =>
    .... +3 сорт =>
    ..... done

    мидиана не оптимальна, ибо 1 к 1 cmp

  22. Serge пишет:

    x4m, чет я не понял что вы хотели сказать :)

  23. x4m пишет:

    я описал сортировку близкую к qsort, которая допускает сравнение элементов 1к1

    с допущением сравнения 2к2 один из шагов можно соптимиздить на одно сравнение. будет 7

  24. lka пишет:

    гм..
    я так понял что решение за 7ходо так и не описано?
    1) 1<2 (берем любые две и в зависимости от показаний нумеруем легкую 1 тяжелую 2)
    2) 4<5 (аналогично берем еще 2 гири)
    3) 25 то {452})
    для определенности будем считать {125} (второй случай анологично)
    т.е грубо говоря мы определили порядок 3 гирь
    теперь возьмем гирю 3 (ни разу не взвешанную и определим ее мемто минимум 2 взвешивания)
    4) 3>2
    5) 3<5 {1235}
    теперь осталось установить 4 при этом из 2) известно что оно меньше 5 т.е нужно поределить место чреди {123}
    6) 2<4
    7) 3<4 {12345}

  25. Virtus пишет:

    SusAnna пишет:…
    вооот, за 8 я уже давно решила, но вот почему-то кажется что можно за 7 по одной такой логике интересной, выношу свои мысли на о(б)суждение:
    Всего вариантов расположения гирек 5! = 125.
    SusAnna, 5! = 120. Это конечно не влияет на Ваше рассуждение.
    А комментарии видно никто не читает!?

Комментировать!

Друзья, обращаю ваше внимание, что все бессмысленные и пустые сообщения будут удаляться, ровно как и комментарии с заведомо не существующми e-mail адресами. Спасибо!


Случайное:
ОБЗОР ИГРЫ ASSASIN’S CREED ROGUE
Assassin’s Creed Rogue, последняя на сегодняшний день «полноценная», если так можно сказать, часть и
Полезные советы перед началом прохождения The Witcher 3
Относительно недавно состоялся выход, наверное, одной из самых ожидаемых игр как в жанре RPG, так
История возникновения компьютерных игр
Многие пользователи интересуются феноменом огромной популярности индии - игр, несмотря на то, что мн
Обзор Игры FAR CRY 3
Far Cry 3 – это игра, которая у многих ассоциируется всего лишь с одним словом – «безумие». Мы играе
Какие бывают на данный момент типы компьютерных игр?
Классификация компьютерных игр – это достаточно спорный вопрос, поскольку на данный момент предостав


 
2005-2011 theДжем.ru - сайт для тех, кто умеет читать и думать. ↑ вверх
полезно знать