Пролог

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

Постановка задачи:

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

--Как при помощи 10 мышей найти колбу с отравой? Спойлер: надо применить бинарные вычисления

--Сколько времена потребуется чтобы найти отраву? Спойлер: 1 час

--Как при этом погубить как можно меньше мышей? Спойлер: приоритет надо отдавать номерам с меньшим количеством взведенных бит

Иногда задачу перефразируют в контексте компьютеры и вирусы. Якобы есть 200 программ, одна программа с вирусом и есть 9 DeskTop-ов для проверки. Вирусная программа через неделю после установки сносит OS и стирает жесткие диски. Надо за 1 неделю выявить эту бажную программу.

Определения

бит - разряд в десятичной представлении числа. Бит может принимать только значение 0 или 1.

триггер - физический прибор для хранения одного бита информации.

регистр - массив триггеров. Физический прибор для хранения целых чисел.

Решение

По сути это задача на знание двоичной системы счисления.

Фаза 1: Занумеровать пробирки

Каждой пробирке надо поставить в соответствие десятично число от 1 до 1000. Можно на каждую пробирку наклеить номер.

Фаза 2: Заполнить таблицу двоичного представления чисел номеров колб

Как известно в мире существует множество систем счисления. Вот самые распространенные: двоичная, Восьмеричная, десятичная и шестнадцатеричная.

вот первые несколько номеров

фаза 3: Занумеровать мышей

Каждой мыши надо присвоить порядковый номер. От нуля до 9. Мышь будет выступать в качестве бита (триггера).

Фаза 4: Мышь это бит

Мышей мы занумеровали, чтобы сделать из массива мышей воображаемый регистр.

Фаза 5: угощение мышей

А теперь настало время угощать мышей. Делать это надо аккуратно. Сейчас объясню как. Мы берём пробирку, смотрим на ее номер, переводим номер в двоичное представление, выписываем номера установленных в 1 битов и даем испить из этой пробирки только тем мышам, у которых номер совпадает с номером установленного единичного бита.

Пример:

Вот колба 564. Бинарное представление 564=0b 0010_0011_0100. Установленные биты это:2,4,5,9. Это значит, что из колбы 564 надо дать попробовать по капле мышам 2, 4, 5 и 9 . Остальных пропустить.

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

После этого можно садиться и просто ждать. Через час должно умереть от одной до 9 мышей.

Фаза 6: Анализ результата эксперимента

Мы подбираем погибших мышей, выписываем их номера и составляем двоичное число в котором установлены в один те разряды, которые соответствуют номерам погибших мышей. Переводим это двоичное число в десятичное и , таким образом , мы и получим десятичный номер той пробирки в которой и была отрава. Таким образом, мы за один час найдем номер с отравленной колбой.

Фаза 7: Как при этом погубить как можно меньше мышей?

Более сложная вариация этой классической задачи состоит в том, что накладывает дополнительное ограничение, что надо по возможности умертвить, как можно меньше мышей. При этом обычно уменьшают количество исходных пробирок до 100. Решается это достаточно просто. При нумерации пробирок надо отдавать предпочтение тем номерам в которых меньше всего установленных в 1 битов. Можно сказать, что появляются новые виртуальные номера (оптимальные номера) пробирок.

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

При умной кодировке для поиска отравы среди 100 колб в жертву придется принести максимум три мыши из 10. А при наивной кодировке погибнет аж 6 мышей! Вот такие пирожки с капустой, понимаете?

А в остальном всё то же самое.

Итоги

Теперь и вы умеете решать классическую задачу про мышей и отраву и можете объяснить решение другим.

Как видите двоичная кодировка далеко не всегда оптимальная. Вспомните хотя бы коды Грея для кодировки диска абсолютных энкодеров. Есть ещё код Джонсона и прочие двоичные коды.

Если вам при устройстве на работу задают эту задачу, то сначала сделайте вид, что Вы никогда не слышали про эту задачу, задумайтесь на 20...40 секунд и только потом начните воспроизводить это решение.

Ссылки