Как перевезти гопников и философов с одного берега на другой
vk f t

Как перевезти гопников и философов с одного берега на другой

Олим­пи­ад­ная задач­ка для стар­ше­класс­ни­ков. Но спра­ви­тесь ли с ней вы?

Это кавер-версия зада­чи про вол­ка, козу и капу­сту — клас­си­че­скую зада­чу на алго­рит­ми­че­ское мыш­ле­ние. Она очень про­стая для раз­ра­бот­чи­ков, и если вы може­те решить её с пер­во­го раза, може­те гор­дить­ся собой — толь­ко 1 чело­век из 10 реша­ет эту зада­чу пра­виль­но с пер­во­го раза. 

Зачем уметь решать такие зада­чи: помо­га­ет в состав­ле­нии сор­ти­ро­воч­ных алго­рит­мов и успеш­но про­хо­дить собе­се­до­ва­ния в ИТ-компаниях. Так­же важ­но уметь обос­но­вы­вать свой ход мыс­лей.

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

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

Реше­ние

Для пер­вой поезд­ки есть пять вари­ан­тов: 

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

Зна­чит, пер­вым рей­сом пара «философ-гопник» отправ­ля­ет­ся на дру­гой берег:

Алгоритмика в деле: как перевезти гопников и философов с одного берега на другой

Теперь лод­ку надо как-то отпра­вить назад. Но так как фило­соф не уме­ет ей управ­лять, то он оста­ёт­ся на бере­гу, а гоп­ник — воз­вра­ща­ет­ся. Фило­со­фы не взры­ва­ют нико­му мозг:

Алгоритмика в деле: философ остаётся на берегу, а гопник — возвращается

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

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

Алгоритмика в деле: гопник высаживает философа, но сам из лодки не вылезает

Таким обра­зом, у нас на том бере­гу сидят два фило­со­фа, а на этом — один фило­соф и три гоп­ни­ка, на кото­рых он вряд ли смо­жет воз­дей­ство­вать силой дис­кур­са:

Алгоритмика в деле: на том берегу сидят два философа, а на этом — один философ и три гопника

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

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

Алгоритмика в деле: в итоге на том берегу всех будет поровну и всё пройдёт спокойно

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

Поэто­му назад отправ­ля­ют­ся фило­соф и гоп­ник:

Алгоритмика в деле: назад отправляются философ и гопник

Теперь един­ствен­ный без­опас­ный вари­ант — отпра­вить на тот берег двух гоп­ни­ков:

Алгоритмика в деле: теперь единственный безопасный вариант — отправить на тот берег двух гопников

Назад отпра­вим одно­го гоп­ни­ка. Что­бы не выхо­дить из лод­ки, он позо­вёт в неё фило­со­фа (напри­мер, фра­зой «Что вы дума­е­те о солип­сиз­ме?») и вер­нёт­ся с ним обрат­но на тот берег:

Алгоритмика в деле: назад отправим одного гопника, который позовёт в лодку философа

Точ­но так же заби­ра­ем остав­ше­го­ся фило­со­фа:

Алгоритмика в деле: точно так же забираем оставшегося философа

И в ито­ге вся ком­па­ния ока­зы­ва­ет­ся на том бере­гу, без­дон­ное небо — над голо­вой, а нрав­ствен­ный закон — внут­ри:

Алгоритмика в деле: в итоге вся компания оказывается на том берегу

Ещё по теме