Рубрики

Деревья решений — фальшивая (поддельная) головоломка с монетами (12 монетная головоломка)

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

Легко: учитывая справедливый баланс в две кастрюли и N одинаково выглядящих монет, из которых только одна монета легче (или тяжелее) . Чтобы выяснить нечетную монету, сколько минимального количества взвешивания требуется в худшем случае ?

Сложно: Учитывая два сковорода справедливого баланса и N идентично выглядящие монеты, из которых только одна монеты м AY быть неисправен. Как мы можем проследить, какая монета, если таковая имеется, является нечетной, а также определить, является ли она легче или тяжелее в минимальном количестве испытаний в худшем случае?

Давайте начнем с относительно простых примеров. После прочтения каждой проблемы постарайтесь решить ее самостоятельно.

Проблема 1: (Легко)

Дано 5 монет, из которых одна монета легче . В худшем случае, сколько минимального количества взвешивания требуется, чтобы вычислить нечетную монету?

Назовите монеты 1, 2, 3, 4 и 5. Мы знаем, что одна монета легче. Учитывая лучшее из баланса, мы можем сгруппировать монеты двумя различными способами: [(1, 2), (3, 4) и (5)] или [(12), (34) и (5)]. Мы можем легко исключить такие группы, как [(123) и (45)], так как мы получим очевидный ответ. Любая другая комбинация попадет в одну из этих двух групп, например [(2) (45) и (13)] и т. Д.

Рассмотрим первую группу, пары (1, 2) и (3, 4). Мы можем проверить (1, 2), если они равны, мы продолжим с (3, 4). Нам нужно два взвешивания в худшем случае. Такая же аналогия может быть применена, когда монета тяжелее.

Во второй группе взвесьте (12) и (34). Если баланс (5) неисправен, в противном случае выберите более легкую пару, и нам нужно еще одно взвешивание, чтобы найти нечетное.

Обе комбинации требуют двух взвешиваний в случае 5 монет с предварительной информацией, что одна монета легче.

Анализ: В общем, если мы знаем, что монета тяжелая или легкая, мы можем проследить монету в журнале 3 (N) испытаний (с округлением до следующего целого числа). Если мы представляем результат баланса в виде тройного дерева, каждый лист представляет результат. Поскольку любая монета из N монет может быть дефектной, нам нужно получить 3-арное дерево, имеющее минимум N листьев. 3-арное дерево на k-м уровне будет иметь 3 k листьев и, следовательно, нам нужно 3 k > = N.

Другими словами, в k испытаниях мы можем исследовать до 3 тыс. Монет, если мы знаем, является ли дефектная монета тяжелее или легче. Учитывая, что монета тяжелее, убедитесь, что 3 проб достаточно для того, чтобы найти нечетную монету среди 12 монет, потому что 3 2 <12 <3 3 .

Проблема 2: (Сложно)

Мы дали 4 монеты, из которых только одна монеты ма у дефектных. Мы не знаем, являются ли все монеты подлинными или какие-либо дефектные присутствуют. Сколько весов требуется в худшем случае, чтобы вычислить лишнюю монету, если она есть? Нам также нужно сказать, тяжелее это или легче.

Из приведенного выше анализа мы можем думать, что достаточно k = 2 испытаний, так как трехуровневое дерево с двумя уровнями дает 9 листьев, что больше, чем N = 4 (прочитайте проблему еще раз). Обратите внимание, что невозможно решить проблему выше 4 монет за два взвешивания. Дерево решений подтверждает факт (попробуйте нарисовать).

Мы можем сгруппировать монеты двумя различными способами: [(12, 34)] или [(1, 2) и (3, 4)]. Рассмотрим комбинацию (12, 34), соответствующее дерево решений приведено ниже. Синие листья — правильные результаты, а красные — невозможные случаи. Мы пришли к невозможным случаям из-за допущений, сделанных ранее на пути.

Результатом может быть (12) <(34), т.е. мы перейдем к левому поддереву или (12)> (34), то есть перейдем к правому поддереву.

Левое поддерево возможно двумя способами,

  • А) 1 или 2 могут быть легче ИЛИ
  • Б) 3 или 4 могут быть тяжелее.

Далее в левом поддереве, как второе испытание, мы взвешиваем (1, 2) или (3, 4). Рассмотрим (3, 4), так как аналогия для (1, 2) аналогична. Итог второго следа может быть тремя способами

  • A) (3) <(4), получая 4 как дефектную более тяжелую монету, ИЛИ
  • B) (3)> (4) с получением 3 в качестве дефектной более тяжелой монеты ИЛИ
  • C) (3) = (4), что дает двусмысленность. Здесь нам нужно еще одно взвешивание, чтобы сравнить подлинную монету с 1 или 2. На рисунке я взял (3, 2), где 3 подтверждено как подлинное. Мы можем получить (3)> (2), в котором 2 светлее, или (3) = (2), в котором 1 светлее. Обратите внимание, что невозможно получить (3) <(2), это противоречит нашему предположению, наклоненному влево.

Точно так же мы можем проанализировать правильное поддерево. Нам нужно еще два взвешивания на правом поддереве.

Всего нам нужно 3 взвешивания, чтобы отследить нечетную монету. Обратите внимание, что мы не можем использовать два результата 3-арных деревьев. Также дерево не является полным деревом, средняя ветвь прекращается после первого взвешивания. На самом деле, мы можем получить 27 листьев 3-х уровневого полного 3-арного дерева, но только у нас 11 листов, включая невозможные случаи.

Анализ: Учитывая N монет, все могут быть подлинными, или только одна монета является дефектной. Нам нужно дерево решений с как минимум (2N + 1) листьями, соответствующими выходам. Потому что может быть N листьев, чтобы быть легче, или N листьев, чтобы быть тяжелее, или один подлинный случай, в общей сложности (2N + 1) листьев.

Как объяснялось ранее, тройное дерево на уровне k может иметь до 3 k листьев, и нам нужно дерево с 3 k > (2N + 1).

Другими словами, нам нужно как минимум k> log 3 (2N + 1) взвешивания, чтобы найти неисправный.

Обратите внимание на приведенный выше рисунок, что не все ветви генерируют листья, то есть мы пропускаем действительные выходные данные по некоторым ветвям, что приводит к большему количеству испытаний Когда это возможно, мы должны сгруппировать монеты таким образом, чтобы каждая ветвь приносила действительный результат (простыми словами, генерируем полное 3-арное дерево). Задача 4 описывает этот подход 12 монет.

Проблема 3: (Особый случай двух панорамирования баланса)

Нам дают 5 монет, группу из 4 монет, из которых одна монета неисправна (мы не знаем , тяжелее она или легче), и одна монета является подлинной. Сколько взвешивания требуется в худшем случае, чтобы определить нечетную монету, тяжелее она или легче?

Пометьте монеты как 1, 2, 3, 4 и G (подлинные). Теперь у нас есть некоторая информация о чистоте монет. Нам нужно использовать это в группировках.

Мы можем лучше всего сгруппировать их как [(G1, 23) и (4)]. Ни одна другая группа не может сгенерировать полное 3-арное дерево, попробуйте сами. Следующая диаграмма поясняет процедуру.

Средний случай (G1) = (23) говорит сам за себя, то есть 1, 2, 3 являются подлинными, а четвертая монета может быть вычислена легче или тяжелее в еще одном испытании.

Левая часть дерева соответствует случаю (G1) <(23). Это возможно двумя способами: либо 1 должен быть легче, либо любой из (2, 3) должен быть тяжелее. Первый случай очевиден, когда следующее взвешивание (2, 3) сбалансировано, в результате чего 1 становится легче. Более поздний случай может быть (2) <(3), в результате чего 3 будет тяжелее, или (2)> (3), в результате 2 будет тяжелее. Узлы листа на левой ветви названы так, чтобы отражать эти результаты.

Правая часть дерева соответствует случаю (G1)> (23). Это возможно двумя способами: либо 1 тяжелее, либо любой из (2, 3) должен быть легче. Первый случай очевиден, когда следующее взвешивание (2, 3) сбалансировано, в результате чего 1 становится тяжелее. В последнем случае (2) <(3) можно получить 2 как более легкую монету или (2)> (3) получить 3 как более легкую.

В вышеуказанной задаче при любой возможности нам понадобится только два взвешивания. Мы можем использовать все результаты двухуровневого полного трехуровневого дерева. Мы начали с (N + 1) = 5 монет, где N = 4, в итоге мы получили (2N + 1) = 9 листов. На самом деле у нас должно быть 11 результатов, так как мы смотрели с 5 монетами, где другие 2 результата? Эти два результата могут быть объявлены в корне самого дерева (до первого взвешивания). Можете ли вы понять, что эти два результата получаются?

Если мы наблюдаем цифру, то после первого взвешивания проблема уменьшается до «мы знаем три монеты, либо одна может быть легче (тяжелее), либо одна из двух других может быть тяжелее (легче)». Это можно решить за одно взвешивание (см. Задачу 1).

Анализ: При наличии (N + 1) монет одна является подлинной, а остальные N могут быть подлинными или только одна монета является дефектной. Требуемое дерево решений должно привести к минимуму (2N + 1) листьев. Поскольку общие возможные результаты (2 (N + 1) + 1), количество взвешиваний (испытаний) определяется высотой тройного дерева, k> = log 3 [2 (N + 1) + 1]. Обратите внимание на знак равенства .

Переставляя k и N, мы можем взвесить максимум N <= (3 k — 3) / 2 монеты в k испытаниях .

Задача 4: (Классическая головоломка из 12 монет)

Вам дают два баланса справедливости. У вас есть 12 одинаково выглядящих монет, из которых одна может быть легче или тяжелее. Как найти нечетную монету, если таковая имеется, в минимальных испытаниях, а также определить, является ли дефектная монета легче или тяжелее, в худшем случае?

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

Давайте назовем монеты 1, 2,… 8, A, B, C и D. Мы можем объединить монеты в 3 группы, а именно (1234), (5678) и (ABCD). Взвесьте (1234) и (5678). Вам рекомендуется нарисовать дерево решений при чтении процедуры. Результатом может быть три способа,

  1. (1234) = (5678), обе группы равны. Дефектная монета может быть в группе (ABCD).
  2. (1234) <(5678), то есть первая группа имеет меньший вес, чем вторая группа.
  3. (1234)> (5678), то есть первая группа весит больше, чем вторая группа.

Выход (1) может быть решен еще двумя взвешиваниями как частный случай двух панорамирования, приведенного в задаче 3. Мы знаем, что группы (1234) и (5678) являются подлинными, и дефектная монета может быть в (ABCD). Выберите одну подлинную монету из любой взвешенной группы и перейдите к (ABCD), как описано в Задаче 3.

Результаты (2) и (3) являются особенными. В обоих случаях мы знаем, что (ABCD) является подлинным. А также мы знаем, что несколько монет легче, а несколько монет тяжелее. Нам нужно перетасовать взвешенные две группы таким образом, чтобы мы получили дерево решений меньшей высоты.

Рассмотрим второй результат, где ( 1234 ) <( 5678 ). Это возможно, когда любая монета среди (1, 2, 3, 4) легче или любая монета среди (5, 6, 7, 8) тяжелее. Мы выявили более легкую или более тяжелую возможность после первого взвешивания. Если мы поступим так же, как в задаче 1, мы не будем генерировать наилучшее дерево решений. Давайте перетасуем монеты как ( 123 5 ) и ( 4 BCD) как новые группы (возможны разные перемешивания, они также приводят к минимальному взвешиванию). Если мы снова взвесим эти две группы, результат может быть представлен тремя способами: i) ( 123 5 ) <( 4 BCD), в результате чего один из 1, 2, 3 будет легче, что аналогично проблеме 1, описанной выше, нам нужно еще одно взвешивание, ii) ( 123 5 ) = ( 4 BCD), получая один из 6, 7, 8 тяжелее, что аналогично проблеме 1, описанной выше, нам нужно еще одно взвешивание iii) ( 123 5 )> ( 4 BCD), получая либо 5 как более тяжелая монета или 4 как более легкая, за счет еще одного взвешивания.

Аналогичным образом мы также можем решить правильное поддерево (третий результат, где ( 1234 )> ( 5678 )) еще в двух взвешиваниях.

Мы можем решить головоломку из 12 монет за 3 взвешивания в худшем случае.

Несколько интересных головоломок:

  1. Решить задачу 4 с N = 8 и N = 13. Сколько минимальных испытаний требуется в каждом случае?
  2. Дана функция int weight (A [], B []), где A и B — массивы (необязательно равного размера). Функция возвращает -1, 0 или 1. Она возвращает 0, если сумма всех элементов в A и B равна, -1, если A <B, и 1, если A> B. Учитывая массив из 12 элементов, все элементы равны, кроме один. Странный элемент может быть как у других, меньше или больше, чем у других. Напишите программу для поиска нечетного элемента (если есть), используя взвешивание () минимальное количество раз.
  3. Возможно, вы видели 3-пан баланса в научных лабораториях в школьные дни. Учитывая баланс с 3 панами (4 результата) и N монет, сколько минимальных испытаний необходимо, чтобы выяснить нечетную монету?

Ссылки:

Аналогичная проблема была представлена в одном из упражнений книги «Введение в алгоритмы Левитина». В частности, прочитайте раздел 5.5 и раздел 11.2, включая упражнения.

— — — Венки . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Деревья решений — фальшивая (поддельная) головоломка с монетами (12 монетная головоломка)

0.00 (0%) 0 votes