Попалась тут очередная реклама Яндекс.Практикума с задачей. Честно говоря, никогда особо не вникал, что такое Яндекс.Практикум, но задачи от него частенько попадаются. И вот на эту решил обратить особое внимание. Заинтересовала она меня тем, что её условия мне более-менее знакомы и я уже имел опыт решения подобных задач, ну и, кроме того, обратил внимание, какое откровенно дилетантское, неоптимальное решение этой задачи предлагают авторы Яндекс.Практикума. В статье по ссылке написано, что данная задача проверяет навыки алгоритмического мышления и очень распространена в IT-компаниях (я так понимаю, в качестве одного из вопросов на собеседовании при приёме на работу). Лично я никогда не сталкивался на собеседованиях с подобной задачей, но вполне готов поверить, что эта задача или её вариации встречаются на собеседованиях в IT-компанию. Почему я так легко готов в это поверить? Дело в том, что данная задача слишком уж характерная, слишком показательная именно для IT-сферы. Она позволяет легко понять, насколько человек вообще в теме, насколько хорошо он понимает, как кодируется информация в вычислительной технике, и тем страннее такой дилетантский подход от людей, которые, вроде бы, должны в этой теме разбираться неплохо. Но обо всём по порядку. Начнём с условия. Цитирую по указанной статье:
Представьте, что вы работаете в лаборатории, которая ищет средство от смертельной болезни. Вам на испытание пришла партия из 1 000 пробирок с лекарством, которое нужно опробовать на людях. Проверка санкционирована Минздравом, у вас имеются все лицензии, но есть проблема. Вы узнаёте, что одну пробирку перепутали и по ошибке отправили вместо лекарства ядовитый реактив. Внешне он ничем не отличается от медикамента.
Вам нужно как можно скорее передать пробирки в больницы для запуска клинического теста, но отправлять отравленную пробирку нельзя: погибнут люди. Тесты всех пробирок займут месяцы, это очень долго. Но у вас есть лабораторные мыши. Вы знаете, что лекарство безвредно для них, а даже капля яда их убьёт за сутки. Но у вас только 10 мышей, а пробирок — 1 000.
Как определить, где яд, как можно быстрее? За какое время можно гарантированно найти пробирку с ядом?
Давайте сначала разберём решение, которое предлагают "специалисты" из Яндекс.Практикума. Не буду в точности цитировать их решение, расскажу лишь суть. Предлагается разделить пробирки поровну или примерно поровну по количеству мышей и поить каждую мышь смесью из всех пробирок в каждой группе. Таким образом, через день мы сузим круг поиска до 100 пробирок, и у нас останется 9 мышей, дальше у нас останется 11 или 12 подозрительных пробирок и 8 мышей, затем одна или две пробирки и 7 мышей и, наконец. на последнем этапе, если у нас останется 2 неразрешённые пробирки, попоим двух мышей из этих семи содержимым этих пробирок и на 4-й день узнаем-таки, в какой пробирке был яд.
Что с этим решением не так? В принципе, всё так за исключением того, что оно неоптимальное. Как должен мыслить настоящий IT-специалист? Напомню, что IT расшифровывается как "Information Technology" - информационные технологии. Значит, IT-специалист должен прежде всего уметь грамотно работать с информацией, уметь выжимать максимум информации, используя имеющиеся у него средства. Что у нас имеется в данной задаче? 1000 пробирок и 10 мышей. Пробирки - это объект исследования. Информацию непосредственно от них мы получить не можем, об этом нам недвусмысленно даётся понять в условии. Значит, остаются мыши, которых мы можем поить лекарствами из пробирок. Какую информацию мы можем получить от мышей? Тут очевидно, что каждая мышь в результате испытаний может либо остаться живой, либо погибнуть, т.е. иметь одно из двух состояний. Удобно эти состояния описывать цифрами 1 или 0. Путь 0 будет соответствовать живой мыши, а 1 - мёртвой. Если бы у нас была только одна мышь, после любых испытаний с ядами у нас могло бы быть только 2 варианта: мышь жива или мышь мертва. С двумя мышами у нас уже может быть 4 различных вариантов исходов испытаний: обе мыши живы, обе мертвы, первая жива, вторая мертва или первая мертва, вторая жива. В виде единичек и ноликов это можно записать проще: 00, 01, 10 или 11. Заметим, что при добавлении каждой новой мыши, число исходов возрастает вдвое. В самом деле, для каждого из двух состояний каждой новой мыши возможны любые комбинации оставшихся мышей. Если мы добавляем третью мышь, для каждого её состояния возможны уже известные нам 4 комбинации состояний оставшихся двух мышей, а значит, всего 8 состояний. Для каждого из двух состояний 4-й мыши возможны любые комбинации из оставшихся трёх мышей, которых, как мы знаем, 8, т.е. всего 8·2=16... Нетрудно заметить, что для n мышей число комбинаций получается как произведение из n двоек, т.е. 2^n (2 в степени n). На языке теории информации это значит, что состояние каждой мыши может нам дать 1 бит информации, а всего с помощью n битов можно закодировать 1 из 2^n различных вариантов. У нас 10 мышей, значит, комбинация из живых и мёртвых мышей теоретически может дать нам 10 бит информации уже через день. Хватит ли нам этих 10 бит? Давайте возведём 2 в 10-ю степень и посмотрим, что получится: 2^10=1024 вариантов. Очевидно, это больше числа пробирок, которых, напомню, 1000, а значит, уже за один день при помощи мышей теоретически можно получить достаточно информации, чтобы определить, какая пробирка отравлена. Пока это только теоретически, потому что пока мы ещё не знаем, как из 1024 возможных комбинаций выбрать 1000, как каждой из этих комбинаций сопоставить свою пробирку, как добиться того, чтобы после наших испытаний комбинация из живых и отравленных мышей в точности соответствовала бы пробирке с ядом, но мы уже видим, что информации, которую можно выжать из одномоментного состояния 10-ти мышей, в принципе вполне хватает, чтобы определить пробирку с ядом, а интуиция нам подсказывает, что для оптимального решения подобных задач все ресурсы должны быть задействованы по максимуму.
Прежде чем перейти к описанию, как это сделать, немного теории. Запись информации в виде комбинации из двух разных объектов, которой мы пользовались, называется двоичным кодом. Это могут быть два разных символа, например, 0 и 1, точка и тире... в цифровой технике это могут быть два разных уровня сигнала: высокий и низкий, наличие или отсутствие намагниченности определённого участка, наличие или отсутствие заряда, наличие или отсутствие канавки на поверхности CD и т.д. и т.п. Главное тут не физический способ записи, а возможность её чтения и интерпретации. Важно, что в современной цифровой технике практически вся информация записывается в виде двоичных кодов. Ну и конечно, в виде двоичных кодов можно записывать числа. Остановимся сначала на целых неотрицательных числах. Для того, чтобы записать целое неотрицательное число в виде двоичного кода достаточно перевести его в т.н. двоичную систему счисления. Я сейчас не буду долго останавливаться на том, что такое двоичная система счисления и как в ней записываются числа, расскажу только основные моменты. Давайте для начала вспомним, как числа записываются в привычной нам десятичной системе счисления, например, число 4639. Мы говорим, что у нас есть 4 тысячи, 6 сотен, 3 десятка и 9 единиц. Значение единицы в каждом разряде в 10 раз больше чем в предыдущем (более правом) разряде. Иными словами, записывая 4639, мы подразумеваем число, равное 4·1000+6·100+3·10+9 или по-другому 4·10³+6·10²+ 3·10¹+9·10°. Аналогичным образом записываются числа и в двоичной системе, только вместо степеней 10 тут используются степени двойки. Например, число 1010011101, записанное в двоичной системе, означает 1·2^9 + 0·2^8 + 1·2^7 + 0·2^6 + 0·2^5 + 1·2^4 + 1·2^3 + 1·2^2 + 0·2^1 + 1·2^0=512 + 128 + 16 + 8 + 4 + 1=669. Если мы хотим перевести число из десятичной системы в двоичную, можно воспользоваться следующим простым способом: последовательно делить нацело на 2 сначала это число, потом результат первого деления и т.д., пока не останется 0 и выписать остатки от такого деления справа налево. Например, если мы захотим перевести число 669 обратно в двоичную систему, мы сначала его разделим нацело на 2, получим 334 и запомним остаток 1, потом разделим 334 на 2, получим 167 и запомним остаток 0 и т.д. пока не дойдём до нуля. Удобно результаты каждого такого деления записывать в столбик, выписывая справа, за вертикальной чертой остатки, как это показано ниже:
669|1
334|0
167|1
83|1
41|1
20|0
10|0
5|1
2|0
1|1
0|
Теперь осталось выписать остатки снизу вверх: 1010011101. Как видим, получилось исходное число. Ещё одна вещь, которая нам может пригодиться при работе с двоичной системой - научиться считать в ней. Полезно было бы вместо того, чтобы переводить в двоичную систему каждое последующее число, переходить от одного числа к следующему напрямую, как мы, например, знаем, что после числа 543 идёт число 544, после числа 54799 идёт число 54800 и т.д. Этому тоже довольно просто научиться. Надо только представить, что в десятке вдруг оказалось не 10 единиц, а только две, т.е. после 1 идёт сразу 10. Вспомним, как мы переходим от одного числа к следующему в десятичной системе: любую последнюю цифру, кроме 9, мы заменяем на следующую по значению и больше ничего в числе не меняем. 9 мы заменяем на 0 и переходим к следующему разряду (напоминаю, что разряды считаются справа налево), в следующем разряде поступаем аналогичным образом: заменяем любую цифру кроме 9 на следующую, а 9 заменяем на 0 и переходим к следующему разряду. И так поступаем до тех пор, пока у нас не закончатся девятки. Если 9 стоит в последнем (самом левом) разряде, заменяем, как обычно, её на 0, а перед ней ставим 1, добавляя ещё один разряд (как если бы он уже был и в нём стоял 0). В двоичной системе мы делаем практически всё то же самое, только учитывая, что тут всего две цифры: 0 и 1, а роль девятки выполняет единица. Иными словами, для того, чтобы перейти от одного числа, записанного в двоичной системе к следующему, меняем цифру в самом правом разряде: 0 заменяем на 1 и ничего больше не делаем, 1 заменяем на 0 и переходим к следующему (слева) разряду, проводя в нём аналогичную замену. Если кто-то ещё не знаком с двоичной системой счисления, попробуйте потренироваться, просто представив, что в десятке не 10 единиц, а всего две, а я для примера просто запишу 10 первых натуральных чисел в двоичной системе:
1, 10, 11, 100, 101, 110, 111, 1000, 1001, 1010.
И ещё один штришок, касаемо двоичной системы (да и вообще любой позиционной системы), который, вроде бы, очевиден, но не лишним будет о нём упомянуть. Иногда бывает необходимо записывать двоичное число строго определённым количеством разрядов, даже если некоторые разряды нам не нужны. В этом случае, если цифр в числе меньше чем разрядов, которыми оно записывается, мы просто добавляем слева нужное количество нулей. Например, если бы нам обязательно требовалось использовать 16 разрядов, а у нас было бы 9-значное двоичное число, например, уже упомянутое выше число 1010011101, то мы могли бы записать это число как 0000001010011101.
Теперь как это всё применить к нашей задаче. Для начала каждой мыши сопоставим свой двоичный разряд, т.е. свою цифру в двоичном номере пробирки: первой мыши сопоставим первый (самый правый) разряд, второй - второй (справа) и т.д. Мыши будут нашими индикаторами: некими объектами, которые будут показывать одно из двух значений: 0 - мышь жива или 1 - мышь мертва. Таким образом, мы можем закодировать любое двоичное число от 0000000000 => 0 до 1111111111 => 1023.
Теперь пронумеруем пробирки. Мы можем сделать сначала в десятичной системе, а потом переведём в двоичную, а можем - сразу в двоичной по изложенному выше принципу, чтобы не тратить лишнее время. Кроме того, замечу, что удобней начать нумерацию с нуля, а не с единицы, поскольку для нуля у нас уже есть запись в двоичной системе, зато нет записи для 2^10=1024. В нашем случае это не особо важно, т.к. на 1000 номеров в любом случае хватить, но если бы у нас было не 1000, а 1024 пробирки, уже бы не хватило, а вот если бы мы их нумеровали с нуля, хватило бы.
Теперь каждую мышь будем поить из тех пробирок, двоичная запись номера которых даёт единицу в разряде, соответствующем этой мыши. Например, как мы помним, мы начинаем счёт с нулевой пробирки. Двоичная запись её номера будет 0000000000. Это значит, что из неё мы не будем поить ни одну мышь, соответственно, если после испытаний ни одна мышь не погибнет, это будет означать, что именно нулевая пробирка содержала яд. Первая пробирка имеет номер в двоичной записи: 0000000001, значит, из неё мы будем поить только первую мышь (помним, что нумерация разрядов идёт справа налево), дальше идёт 0000000010 - из неё поим вторую мышь, следующая 0000000011 - из неё поим 1-ю и 2-ю мышь и т.д. Возьмём ещё какую-нибудь пробирку, чтобы уже было совсем понятно. Например, 739-й пробирке будет соответствовать номер 1011100011, значит, поим из неё 1-ю, 2-ю, 6-ю, 7-ю, 8-ю и 10-ю мышь (обратите внимание, кстати, мышей мы нумеруем, начиная с единицы). Обратите внимание на простоту и гениальность такого решения: каждая мышь поится из множества разных пробирок, но погибают только те мыши, которые поились из отравленной пробирки и ни одна мышь, которая из неё не поилась, не погибает. Но мы знаем, что из отравленной пробирки поились только те мыши, которые соответствуют единичным разрядам в номере этой пробирки, значит, если, например, погибли 1-я, 2-я, 4-я, 7-я и 9-я мыши, то была отравлена пробирка, двоичная запись номера которой 0101001011, которой соответствует номер 331 в 10-чном выражении. И никакой ошибки тут быть не может, т.к. нам известно, что отравлена только одна пробирка и её двоичный код уникален, т.е. код любой другой пробирки отличался бы от её кода хотя бы в одном разряде, а значит, если бы отравленной пробиркой была бы какая-то другая, по крайней мере одна из погибших мышей была бы жива или, наоборот, по крайней мере, одна из живых мышей погибла бы.
Собственно, всё. Вот так решается эта задача всего за один день. Теперь осталось разобраться, что же не так с решением "специалистов" из Яндекс.Практикума. Ответ тут довольно очевиден: они совершенно не умеют использовать имеющиеся средства для получения максимального количества информации. Обратите внимание, как неэффективно они используют мышей. При их решении в первый день возможен только один из десяти вариантов: погибла первая мышь, погибла вторая мышь ... погибла 10-я мышь. Варианты, когда не гибнет ни одна мышь, либо гибнут, например, вторая, третья и пятая мыши, тут просто невозможны. А это значит, что из всех возможных 1024 вариантов комбинаций они используют только 10, получая в первый день вместо 10-и бит всего чуть более трёх. Ясно, что такой способ будет крайне неэффективным, поэтому если вам когда-нибудь попадётся подобная задача на собеседовании, рекомендую её решать моим способом. Хотя, наверное, для человека, далёкого от сферы IT такой метод решения "в лоб" - первое, что приходит в голову.
На этом на сегодня всё. Если хотите, чтобы я подробней написал о кодировании информации двоичными цифрами или ещё о чём-нибудь, пишите.
