Задача о двоичной мыши и тысяче пробирок
vk f t

Задача о двоичной мыши и тысяче пробирок

Самое луч­шее объ­яс­не­ние дво­ич­ной систе­мы счис­ле­ния

Помни­те зада­чу про мышей и испор­чен­ную пар­тию лекар­ства? Там у нас было 10 мышей и 1000 про­би­рок. В одной из про­би­рок яд. Нуж­но про­ве­рить, в какой про­бир­ке яд, за мини­маль­ное коли­че­ство дней. 

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

Но что если отрав­лен­ную про­бир­ку надо най­ти за одно изме­ре­ние? Воз­мож­но ли это? Давай­те посмот­рим.

Реше­ние

Что­бы най­ти про­бир­ку с ядом за один день, нам надо при­звать на помощь дво­ич­ную систе­му счис­ле­ния. Но для нача­ла раз­бе­рём­ся с при­выч­ной — деся­тич­ной.

Десятичная система счисления

Она самая зна­ко­мая из всех, и мы ей поль­зу­ем­ся каж­дый день. В её осно­ве — 10 цифр, от 0 до 9, поэто­му она и назы­ва­ет­ся деся­тич­ной.

Мы поль­зу­ем­ся деся­тич­ной систе­мой, осо­бо не рефлек­си­руя. Напри­мер, мы видим чис­ло 436 — мы авто­ма­ти­че­ски его рас­кла­ды­ва­ем: четы­ре сот­ни + три десят­ка + шесть.

Толь­ко что мы раз­ло­жи­ли чис­ло на раз­ря­ды: 4 — это раз­ряд сотен, 3 — раз­ряд десят­ков, 6 — раз­ряд еди­ниц. Полу­ча­ет­ся, что:

436 = (4 × 100) + (3 × 10) + (6 × 1)

436 = (4 × 10²) + (3 × 10¹) + (6 × 10 в нуле­вой сте­пе­ни)

Полу­ча­ет­ся, что наша деся­тич­ная запись чис­ла — это про­сто крат­кая фор­ма запи­си длин­но­го выра­же­ния, где какие-то чис­ла умно­жа­ют­ся на десят­ки в раз­ных сте­пе­нях.

Двоичная система

Дво­ич­ная систе­ма — это то же самое, толь­ко вме­сто десят­ки — двой­ка. Вме­сто сте­пе­ней десят­ки мы исполь­зу­ем сте­пе­ни двой­ки. Вме­сто деся­ти цифр от 0 до 9 мы исполь­зу­ем две: 0 и 1. 

Что­бы пере­ве­сти чис­ла из дво­ич­ной систе­мы счис­ле­ния в деся­тич­ную, нуж­но то же самое, что и рань­ше: воз­во­дить двой­ку в сте­пень раз­ря­да и умно­жать на 0 или 1. Рас­смот­рим на при­ме­ре:

Любое деся­тич­ное чис­ло мож­но пред­ста­вить в виде дво­ич­но­го, и наобо­рот. Теперь попро­бу­ем исполь­зо­вать это зна­ние в реше­нии зада­чи. 

Битовая глубина

У нас 1000 про­би­рок. Запи­шем это чис­ло в дво­ич­ной систе­ме счис­ле­ния:

1000 в деся­тич­ной = 1111101000 в дво­ич­ной

Это мак­си­маль­ное чис­ло, кото­рое нам пона­до­бит­ся при нуме­ра­ции, и оно состо­ит из 10 нолей и еди­ниц. Полу­ча­ет­ся, что бито­вая глу­би­на реше­ния этой зада­чи — 10. А у нас как раз 10 мышей. Это и будем исполь­зо­вать при рас­чё­тах.

Немного магии

Зная, что у нас 10 бит на чис­ло, про­ну­ме­ру­ем каж­дую про­бир­ку таким обра­зом:

1 — 0000000001

2 — 0000000010

3 — 0000000011

4 — 0000000100

...

999 — 1111100111

1000 — 1111101000

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

А теперь начи­на­ет­ся магия. Берём каж­дую про­бир­ку и смот­рим, на каких местах сто­ят еди­ни­цы. Мышам в этих клет­ках даём кап­лю веще­ства:

пер­вая про­бир­ка: 0000000001 — даём кап­лю мыши в самой пра­вой клет­ке

вто­рая про­бир­ка: 0000000010 — даём кап­лю мыши во вто­рой клет­ке спра­ва

тре­тья про­бир­ка: 0000000011 — даём по кап­ле двум мышам из пер­вой и вто­рой кле­ток спра­ва

чет­вёр­тая про­бир­ка: 0000000100 — даём кап­лю мыши тре­тьей клет­ке спра­ва

...

999 про­бир­ка: 1111100111 — даём по кап­ле мышам из пер­вых пяти кле­ток сле­ва, про­пус­ка­ем две клет­ки, даль­ше капа­ем трём остав­шим­ся

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

Напри­мер, наут­ро мы заме­ти­ли, что шесть мышей сле­ва и одна спра­ва живы, осталь­ные три мерт­вы. Запи­шем это в дво­ич­ной систе­ме: 

0000001110

Пере­ве­дём вруч­ную или на каль­ку­ля­то­ре это в деся­тич­ную систе­му и полу­чим чис­ло 14. Это и есть номер нашей про­бир­ки с ядом.

В чём секрет

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

Ещё по теме