Загадка о тысяче пробирок
vk f t

Загадка о тысяче пробирок

Кавер-версия клас­си­че­ской голо­во­лом­ки про 1 000 буты­лок вина. Про­ве­ря­ет навы­ки алго­рит­ми­че­ско­го мыш­ле­ния и очень рас­про­стра­не­на в ИТ-компаниях.

Так как чрез­мер­ное упо­треб­ле­ние алко­го­ля вре­дит ваше­му здо­ро­вью, у нас будет зада­ча про лекар­ства. Пред­ставь­те, что вы рабо­та­е­те в лабо­ра­то­рии, кото­рая ищет сред­ство от смер­тель­ной болез­ни. Вам на испы­та­ние при­шла пар­тия из 1 000 про­би­рок с лекар­ством, кото­рое нуж­но опро­бо­вать на людях. Про­вер­ка санк­ци­о­ни­ро­ва­на Мин­здра­вом, у вас име­ют­ся все лицен­зии, но есть про­бле­ма. Вы узна­ё­те, что одну про­бир­ку пере­пу­та­ли и по ошиб­ке отпра­ви­ли вме­сто лекар­ства ядо­ви­тый реак­тив. Внешне он ничем не отли­ча­ет­ся от меди­ка­мен­та.

Вам нуж­но как мож­но ско­рее пере­дать про­бир­ки в боль­ни­цы для запус­ка кли­ни­че­ско­го теста, но отправ­лять отрав­лен­ную про­бир­ку нель­зя: погиб­нут люди. Тесты всех про­би­рок зай­мут меся­цы, это очень дол­го. Но у вас есть лабо­ра­тор­ные мыши. Вы зна­е­те, что лекар­ство без­вред­но для них, а даже кап­ля яда их убьёт за сут­ки. Но у вас толь­ко 10 мышей, а про­би­рок — 1 000.

Как опре­де­лить, где яд, как мож­но быст­рее? За какое вре­мя мож­но гаран­ти­ро­ван­но най­ти про­бир­ку с ядом?

Самопроверка

Преж­де чем узнать реше­ние, ответь­те на такие вопро­сы:

  • Раци­о­наль­но ли выби­рать какие-то отдель­ные бутыл­ки из общей мас­сы или нуж­но про­те­сти­ро­вать всё?
  • Есть ли в усло­вии зада­чи лимит по коли­че­ству вве­дён­но­го лекар­ства?
  • Обя­за­ны ли мы тести­ро­вать одну мышь толь­ко одной про­бир­кой? Мож­но ли исполь­зо­вать одно живот­ное несколь­ко раз или дать ему лекар­ства из несколь­ких про­би­рок?
Реше­ние

Сна­ча­ла кажет­ся, что решить зада­чу нере­аль­но — мышей в 100 раз мень­ше, чем про­би­рок. Зна­чит, нам нуж­но как-то научить­ся быст­ро сокра­щать коли­че­ство эле­мен­тов, кото­рые нуж­но про­ве­рить.

Мы зна­ем, что даже кап­ля яда убьёт мышь за сут­ки. Зна­чит, если мы сме­ша­ем эту кап­лю с насто­я­щим лекар­ством, яд тоже сра­бо­та­ет. Вос­поль­зу­ем­ся этим так:

Раз­де­лим все про­бир­ки на рав­ные груп­пы — по 100 про­би­рок в каж­дой.

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

Теперь у нас оста­лось 100 про­би­рок и девять мышей. Види­те, мы за сут­ки сокра­ти­ли коли­че­ство про­би­рок в 10 раз. Будем исполь­зо­вать этот же при­ём и даль­ше: делить сосу­ды на рав­ные груп­пы и делать сме­си. На вто­рой день раз­де­лим 100 про­би­рок на девять групп :

Восемь групп по 11 про­би­рок и одна груп­па из 12 про­би­рок.

Как види­те, на совсем рав­ные части поде­лить не полу­чи­лось, но это не кри­тич­но — зада­ча всё рав­но реша­ет­ся. Теперь даём сме­си мышам и через сут­ки смот­рим, какое живот­ное погиб­нет на этот раз.

Пред­по­ло­жим самый слож­ный слу­чай — яд был в сме­си из 12 про­би­рок. У нас оста­ёт­ся восемь мышей и 12 про­би­рок. Их тоже делим на восемь групп:

Четы­ре груп­пы по две про­бир­ки, и четы­ре груп­пы по одной про­бир­ке.

Сно­ва даём веще­ство мышам и через сут­ки смот­рим на резуль­тат. Если погиб­ла особь, кото­рая пила толь­ко из одной про­бир­ки, — то она и была отрав­ле­на, а зна­чит, мы нашли яд за три дня. Если эта мышь дегу­сти­ро­ва­ла смесь из двух сосу­дов, то на сле­ду­ю­щий день мы берём эти две про­бир­ки, две мыши из тех, что оста­лись, и обе­им даём попро­бо­вать своё лекар­ство. Через сут­ки мы тоже узна­ем, где был яд.

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

Ответ: мак­си­мум за четы­ре дня мы най­дём сосуд с ядом.

На подумать

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

Допу­стим, у нас был бы бес­ко­неч­ный запас вре­ме­ни и те же 10 мышей. Мы даём каж­дой по одной кап­ле из одной из про­би­рок в день. Если яд в рай­оне трид­ца­той про­бир­ки, мы узна­ем об этом через три дня. Если в 1 000-й, то для поис­ка отра­вы потре­бу­ет­ся 100 дней. Если бы сосу­дов было 10 тысяч, то пона­до­би­лось бы 1 000 дней. Вре­мя испол­не­ния алго­рит­ма рас­тёт линей­но: чем боль­ше про­би­рок, тем боль­ше дней.

Теперь посмот­рим на наш алго­ритм: что­бы про­ве­рить 1 000 про­би­рок, нуж­но четы­ре дня. Если бы образ­цов было 10 тысяч, потре­бо­ва­лось бы пять дней. Воз­рас­та­ние чис­ла про­би­рок в 10 раз уве­ли­чи­ло вре­мя испол­не­ния толь­ко на 25%.

Это и есть нели­ней­ная ско­рость выпол­не­ния. Пред­ставь­те, насколь­ко такие алго­рит­мы более эффек­тив­ны на боль­ших мас­си­вах дан­ных.

Ещё по теме