Вопросы: Google, Microsoft, Amazon, VMWare, Bloomberg
Ключевой вывод: это одна из лучших алгоритмических головоломок для изучения пошаговой оптимизации при решении задач.
Постановка головоломки
Есть восемь одинаковых на вид монет, и одна из этих монет фальшивая, она легче настоящих монет. Какое минимальное количество взвешиваний необходимо для идентификации фальшивой монеты на двухчашечных весах без гирь?
Идея решения 1: решение грубой силы
Основная идея состоит в том, чтобы сравнить каждую возможную пару монет, используя баланс. Общее количество пар монет = 8C2 = (8 x 7)/2 = 28. Таким образом, в худшем случае нам нужно выполнить 28 сравнений, чтобы получить фальшивую монету. Критический вопрос: можем ли мы улучшить решение и найти фальшивую монету за меньшее количество сравнений? Будем думать дальше!
Идея решения 2. Использование линейного поиска
Вторая идея заключалась бы в сравнении каждой монеты в линейном порядке.
- Сначала мы сравниваем 1-ю монету со 2-й монетой. Если оба не имеют одинакового веса, то более легкая монета будет фальшивой монетой.
- В противном случае мы сравниваем 2-ю монету с третьей монетой. Если оба не имеют одинакового веса, то более легкая монета будет фальшивой монетой.
- В противном случае мы продолжаем тот же процесс сравнения, пока не найдем фальшивую монету.
- В худшем случае нам нужно выполнить 7 сравнений. Здесь наихудший случай возникает, когда фальшивая монета находится среди двух последних монет.
Теперь мы улучшили решение с 28 сравнений до 7 сравнений. Теперь критический вопрос: можем ли мы подумать об улучшении решения, используя меньшее количество сравнений? Давай подумаем!
Идея решения 3: Сравнение монет попарно
Предположим, мы распределим монеты по 4 группам и начнем сравнивать каждую группу. Вот шаги:
- Разделите эти 8 монет на 4 группы: группа[1] = [1,2], группа[2] = [3,4], группа[3] = [5,6], группа[4] = [7,8]. ]
- Теперь сравним группу[1] с группой[2]. Если группа[1] не будет иметь тот же вес, что и группа[2], то будет присутствовать фальшивая монета с более легкой группой веса.
- Если группа[1] имеет меньший вес, мы сравниваем монету 1 с монетой 2. Какая из монет легче, та и будет фальшивой.
- Если группа [2] легче, то мы сравниваем монету 3 с монетой 4. Какая из монет легче, та и будет фальшивой монетой.
- Если группа [1] имеет тот же вес, что и группа [2], то мы знаем, что [1,2,3,4] хороши. Теперь сравним группу[2] с группой[3]. Если группа[2] не будет иметь тот же вес, что и группа[3], то мы повторяем описанный выше процесс и находим более легкую монету в одном сравнении.
- Если группа[2] имеет тот же вес, что и группа[3], то мы знаем, что монеты [1, 2, 3, 4, 5, 6] хороши. Теперь сравниваем группу[3] с группой[4] и повторяем аналогичную процедуру.
Таким образом, в худшем случае нам нужно выполнить 4 сравнения: 3 сравнения для сравнения монет в группе и одно сравнение для определения фальшивой монеты в более легкой группе.
Теперь мы улучшили решение с 7 сравнений до 4 сравнений. Критический вопрос: можем ли мы улучшить решение и решить его, используя менее 4 сравнений? Давай подумаем!
Идея решения 4: использование стратегии «разделяй и властвуй»
Другая идея основана на стратегии разделяй и властвуй, где мы делим монеты на две равные части и сравниваем их, чтобы получить фальшивые монеты. Вот шаги:
- Делим монеты на две части по 4 монеты и сравниваем их с помощью баланса. Какая бы часть ни была светлее, фальшивая монета будет присутствовать в этой части.
- Теперь берем более светлую часть из 4 монет и делим их на пары по 2 монеты. Сравниваем обе пары и снова отбрасываем более тяжелую пару.
- Наконец, в конце у нас осталось всего две монеты, поэтому фальшивая монета должна быть среди этих двух монет. Теперь мы сравним их обоих и найдем более светлую монету или фальшивую монету.
Эта стратегия похожа на алгоритм бинарного поиска, где на каждом шаге мы выполняем одно сравнение и погружаем проблему в меньшую подзадачу половинного размера ввода. Таким образом, для 8 монет нам нужно выполнить log8 или 3 сравнения, чтобы получить поддельные монеты.
Теперь мы улучшили решение с 4 сравнений до 3 сравнений :) Критический вопрос: можем ли мы еще улучшить решение и решить его, используя менее 3 сравнений? Является ли это возможным? Давай подумаем!
Идея решения 5: Эффективное решение
Это конкретный пример задачи, где нам нужно найти эффективное решение для 8 монет. Таким образом, мы можем углубиться еще на один шаг и использовать эту информацию для получения эффективного решения. Давай подумаем!
- Из данных монет выбираем две группы по три монеты в каждой и кладем их на противоположные чашечки весов. Если их веса одинаковы, фальшивая находится среди двух оставшихся монет, и их взвешивание идентифицирует фальшивую монету.
- Если их веса неодинаковы, то более легкая подделка находится среди трех более легких монет. Берем любые две из них и кладем на противоположные чашечки весов. Если они весят одинаково, третья монета в более легкой группе — фальшивая; если они не весят одинаково, то более легкий - подделка.
Итак, используя описанный выше подход, мы можем решить задачу всего за 2 сравнения.
Идея решения 6: Еще одно эффективное решение
У задачи есть альтернативное решение, при котором второе взвешивание не зависит от результатов первого. Предположим, мы пометили монеты буквами A, B, C, D, E, F, G, H. Мы сравниваем (A, B, C) с (F, G, H) при первом взвешивании. Мы взвешиваем (A, D, F) против (C, E, H) при втором взвешивании.
- Если ABC = FGH (первое взвешивание дает весы), все эти шесть монет настоящие, и поэтому второе взвешивание эквивалентно взвешиванию D против E.
- Если ABC ‹ FGH, только A, B и C могут быть фальшивыми. Следовательно, если при втором взвешивании:
- Если ADF = CEH, B является поддельным.
- Если ADF ‹ CEH, A является подделкой.
- Если ADF › CEH, C — подделка.
- Случай ABC › FGH симметричен описанному выше сценарию. Думать!
Таким образом, этот подход также решает проблему всего за 2 сравнения.
Наслаждайтесь обучением, наслаждайтесь алгоритмами!
