Как надевают носки настоящие программисты
vk f t

Как надевают носки настоящие программисты

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

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

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

Вам нуж­но вый­ти на ули­цу в нос­ках оди­на­ко­во­го цве­та, но из-за бес­по­ряд­ка слож­но достать сам ящик — мож­но вытас­ки­вать отту­да толь­ко по одно­му пред­ме­ту. В ящи­ке щель, в кото­рую вы може­те засу­нуть руку, но не може­те уви­деть, за каким нос­ком потя­ну­лись.

Вопрос: сколь­ко мак­си­маль­но нуж­но достать нос­ков из ящи­ка, что­бы полу­чить пару оди­на­ко­во­го цве­та? А что, если тре­бу­ет­ся взять с собой запас­ной ком­плект и он тоже дол­жен быть одно­го цве­та?

Реше­ние

Для одной пары

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

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

Для двух пар

Две пары могут быть раз­но­го цве­та — давай­те это учтём при реше­нии.

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

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

По-научному такой пере­бор нос­ков и поиск пары назы­ва­ет­ся ком­би­на­то­ри­ка. Она изу­ча­ет все воз­мож­ные ком­би­на­ции из любых объ­ек­тов и коли­че­ство таких соче­та­ний. В ней есть спе­ци­аль­ные фор­му­лы, кото­рые поз­во­ля­ют лег­ко нахо­дить ответ без дол­гих рас­суж­де­ний или под­счё­тов в уме. Напри­мер, с помо­щью ком­би­на­то­ри­ки мож­но быст­ро опре­де­лить коли­че­ство выиг­рыш­ных ком­би­на­ций в «Рус­ском лото» или подо­брать пары дежур­ных в клас­се таким обра­зом, что­бы их состав не повто­рял­ся как мож­но доль­ше. Мы ещё вер­нём­ся к ком­би­на­тор­ным зада­чам в буду­щем.

Ещё по теме