Нестандартное мышление и логика в программировании – наше все. На собеседовании будьте готовы к тому, что некоторые задачи будут нетривиальными.
1,5 белки, да: такая задача действительно существует. Давайте посмотрим на условие:
1,5 белки за 1,5 минуты съедают 1,5 ореха. Сколько орехов съедят 9 белок за 9 минут?
[spoiler title=’Решение’ style=’default’ collapse_link=’true’]Согласитесь, что 1,5 белки сразу сбивают с толку. На это и рассчитано условие. Здесь важно абстрагироваться от привычных образов и принять во внимание тот факт, что речь идет не о последовательном, а о параллельном выполнении задач. Мне было удобнее представить себе это в виде многопоточности без монитора. Что мы имеем с таким подходом?
1. Если действие выполняется белками параллельно, а не последовательно, 1,5 белки за 1,5 минуты съедают 1,5 ореха. Стало быть, 1 белка за 1,5 минуты съедает 1 орех, а 9 белок за 1,5 минуты съедают 9 орехов.
2. Но это за 1,5 минуты, а нам нужно 9 минут:
9/1,5 = 6.
- Умножаем количество съеденных орехов:
9*6 = 54.
Ответ: 9 белок за 9 минут съедают 54 ореха.[/spoiler]
Условие:
В первой закрытой комнате с низким потолком висит 3 лампы накаливания. В другой такой же комнате установлено 3 переключателя от каждой из них. Можно как угодно дергать переключатели, вот только перейти из 2-ой комнаты в 1-ую разрешено только 1 раз. Как узнать, за какую лампочку отвечает каждый из переключателей?
[spoiler title=’Решение’ style=’default’ collapse_link=’true’]Здесь не нужно быть математиком: достаточно немного поразмыслить. Помните, что логика в программировании – это необходимый инструмент. Так как мы можем дотянуться до лампочки рукой (низкий потолок), следует на некоторое время включить одну из них на пару минут, выключить ее и включить любую другую. Далее переходим в комнату с лампочками и проверяем:
- та, которая горит, соединена с последним переключателем, который мы трогали;
- та, которая не горит и теплая, соединена с первым переключателем, который мы трогали;
- за не горящую и холодную лампочку отвечает переключатель, который мы вообще не трогали.[/spoiler]
Здесь работает чистая математика. Условие:
Бейсбольный мяч с битой вместе стоят $13. Но мяч дешевле бейсбольной биты на $3. Рассчитайте стоимость каждого предмета.
[spoiler title=’Решение’ style=’default’ collapse_link=’true’]1. Предмета два, следовательно, делим сумму на 2:
13/2 = 6,5.
2. Мяч дешевле биты на $3, но и бейсбольная бита дороже мяча на $3. Делим разницу на 2:
3/2 = 1,5.
3. Рассчитываем стоимость каждого предмета:
- мяч – 6,5-1,5 = 5;
- бита – 6,5+1,5 = 8.
Ответ: мяч = $5, бита = $8.[/spoiler]
Логика в программировании не ограничивается только математической составляющей, но она является одной из ключевых. То же самое и в случае с монетами. Условие:
Дано 12 монет, из которых 11 – настоящие, и только 1 – фальшивая. Фальшивая монета отличается от настоящих по массе. Какое минимальное количество взвешиваний необходимо, чтобы обнаружить фальшивую монету? Для взвешивания используются чашечные весы.
[spoiler title=’Решение’ style=’default’ collapse_link=’true’]Задача легкая, хотя многие все равно начинают путаться, отвечая «1» или «2». Минимальное количество взвешиваний – 3, ведь даже если мы взвесим 2 раза, то как мы узнаем, какая из монет фальшивая? Большую часть монет составляют настоящие, так что 2 монеты с одинаковым весом и будут настоящими, третья с другим весом – фальшивой.
Ответ: 3 взвешивания.[/spoiler]
Условие:
Есть 2 веревки и неограниченное количество спичек. Каждая веревка сгорает за час, однако горят они неравномерно, так что нельзя точно узнать, за какое время сгорит определенная часть веревки. Как отмерить с помощью этих двух веревок интервал в 45 минут?
[spoiler title=’Решение’ style=’default’ collapse_link=’true’]Горят веревки действительно неравномерно, но полностью сгорают точно за час. Мы можем:
- Поджечь оба конца одной веревки и только 1 конец второй веревки.
- Как только первая веревка сгорит (пройдет 30 минут, так как горит она с двух концов), поджигаем другой конец второй веревки, и она догорит ровно за 15 минут.[/spoiler]
Условие:
Дана пустая бочка. Нужно наполнить ее водой так, чтобы заполнена была только половина. Использовать палку или другие предметы для измерения нельзя.
[spoiler title=’Решение’ style=’default’ collapse_link=’true’]Да, логика в программировании может подкинуть и физику. А что? Ведь занимаются же как-то машинным обучением, и подобные вещи тоже могут пригодиться.
- Заполняем бочку водой (или полностью, или точно больше половины).
- Наклоняем бочку на 45 градусов: вся лишняя вода выливается, и остается ровно половина.[/spoiler]
Это очень легкая задача, но горе вам, если зададут ее под конец собеседования, когда последние силы покинут, а мыслительный процесс начнет изрядно буксовать. Условие:
12 часов ночи. Идет дождь. Можно ли ожидать, что по истечении 72 часов будет солнечная погода?
[spoiler title=’Решение’ style=’default’ collapse_link=’true’]Ответ: нет, так как через 72 часа также будет ночь.[/spoiler]
Условие:
В офисе расположили 3 автомата с различными напитками. В первом – кофе, во втором – чай, а в третьем – и кофе, и чай (выдает случайным образом). Для любого из них нужна 1 монета. Каждый автомат обозначен наклейкой с названием продукта, который он выдаёт. Вот только на заводе перепутали наклейки, и на каждом из трех автоматов оказалась неправильная. За сколько монет можно выяснить, где какой автомат?
[spoiler title=’Решение’ style=’default’ collapse_link=’true’]Здесь, как и в случае с первой задачей, нужно абстрагироваться от мнимой сложности, ведь задача легкая.
- Бросаем монету в автомат с надписью «чай-кофе». Так как все наклейки расположены неверно, в зависимости от того, что выдаст автомат, мы определим его в «чайный» или «кофейный».
- Допустим, это оказался кофейный автомат. Тогда чайный автомат не может быть ни кофейным, ни чайным: он выдает и чай, и кофе.
- Методом исключения определяем автомат, который выдает чай.
Ответ: за 1 монету.[/spoiler]
А вот вам еще несколько интересных задач, которые рассчитаны исключительно на программистов. Сможете их решить? 😉
- Сколькими способами можно разложить на 6 целых множителей 1 000 000?
- Имеем большой файл в несколько Гб, в котором записаны целые числа. Нужно записать в другой файл все эти числа в отсортированном порядке. Как это сделать максимально эффективно?
- Имеем все тот же большой файл в несколько Гб с целыми числами. Каждое число встречается дважды, но также есть 1 число, которое встречается всего 1 раз. Предложите эффективный алгоритм для поиска этого числа.
Источник: proglib.io
Зачем нужны задачи на логику на собеседовании
Задачи на логику на собеседовании позволяют работодателю сразу оценить такую личностную характеристику, как интеллект кандидата. При этом следует помнить, что оценивать интеллект и логическое мышление по документам об образовании нельзя. Во-первых — далеко не всегда документы подтверждают реальное наличие у соискателя необходимых для занятия определенного рабочего места навыков и умений. А во-вторых, интеллект и логика никак не связаны со знаниями и отражают гибкость ума, а не объем накопленной информации и умений. Конечно же, интеллект можно развивать, но не следует считать это понятие тождественным энциклопедическому знанию.
Часто логические задачи на собеседовании при этом не требуют от кандидата на самом деле особых знаний. Иногда задачи могут казаться сложными и требующими навыков в математике, физике или даже химии, которые могут быть никак не связаны с должностными обязанностями работника. Однако реальный ответ на них может вообще не затрагивать, казалось бы, напрямую интересующую область знаний.
Другие же задачи на собеседовании вообще могут не требовать предоставления точного ответа. В данном случае, интервьюер оценивает непосредственно ход мыслей соискателя и порядок действий, который тот озвучивает.
Самые популярные задачи на логику на собеседовании с ответами
Всего существует большое количество самых разнообразных логических задач, которые могут предусматриваться на собеседовании. При этом многие компании предпочитают разрабатывать собственные методики — и ответы на такие задачи на логику заранее никак не выучить, разве что узнать их у тех, кто проходил интервью с работодателем ранее. Однако есть и ряд достаточно распространенных логических задач, многие из которых уходят корнями в древние времена. Далее будут приведены примеры пяти логических задач на собеседовании с ответами на них:
Задача №1. У вас имеется два ведра — одно объемом на пять литров воды, второе — на три литра. Как отмерять с их помощью четыре литра воды. Эта задача достаточно простая и часто используется даже в школе, однако многие работодатели все равно применяют ее для оценки мыслительных способностей кандидатов.
Ответ: Отмерять четыре литра в таком случае достаточно просто. Следует придерживаться простого порядка действий:
наполнить пятилитровое ведро- перелить воду из него в трехлитровое. В пятилитровом ведре останется два литра.
- Вылить воду из трехлитрового ведра.
- Перелить два литра из пятилитрового ведра в трехлитровое.
- Наполнить снова пятилитровое ведро.
- Долить из пятилитрового ведра недостающий литр воды в трехлитровое — таким образом в пятилитровом ведре останется ровно четыре литра воды.
У этой задачи есть и альтернативный метод решения, которым может удивить испытуемый. Так, согласно ему следует заполнить 5-литровое ведро, после чего опустить в него 3-литровое, так, чтобы оно вытеснило лишнюю воду. После этого — оставшиеся 2 литра воды наливаются в трехлитровое ведро, пятилитровое заполняется полностью и операция по вытеснению лишней жидкости повторяется. Потом 2 литра воды из 3-литрового ведра просто доливаются в 5-литровое.
Задача №2. Если вокруг Земли обернуть верёвку по экватору так, чтобы она обтягивала планету, а потом увеличить длину верёвки на два метра и равномерно поднять над поверхностью Земли, сможет ли в образовавшийся зазор пролезть человек?
Ответ: поначалу кажется, что в сравнении с масштабами планеты, увеличение длины верёвки всего на метр будет практически незаметным. Однако если вспомнить школьный курс математики и следовать формуле вычисления радиуса. При этом знать длину окружности экватора — совсем не обязательно. Достаточно использовать простое уравнение формата Х=2πr, где r – радиус Земли в метрах, а X – длина её окружности. Соответственно, если уравнение примет вид X+1=2πR , где новое значение R будет означать новый радиус Земли, можно будет сделать вывод, что разница между радиусами будет составлять 2/2π . То есть, при увеличении длины верёвки на 2 метра, расстояние её от Земли приблизительно составит 0,3 метра, чего явно будет достаточно для того, чтобы под ней мог пролезть человек.
Задача №3. Есть 8 монет. Одна из них фальшивая и весит легче, чем другие. Как гарантированно определить, какая из монет фальшивка, использовав всего два взвешивания на классических весах. Также может встречаться вариант задачи, предлагающий опрашиваемому самому указать минимально необходимое число взвешиваний для определения фальшивой монеты.
Ответ: двух взвешиваний будет достаточно в абсолютно любой ситуации. При первом взвешивании на каждую из чаш кладется по три монеты. Если чаши остались в равновесии — значит, фальшивая монета среди оставшихся двух — и определить её можно при втором взвешивании. Если же одна из чаш оказалась легче другой — значит фальшивая монета среди трех монет в более легкой чаше. Вторым взвешиванием берутся две любых монеты из этих трех — если чаша отклонится, значит уже можно определить более легкую монету. Если останется в равновесии — значит фальшивой является одна оставшаяся монетка.
Задача №4. Сокровище охраняют два стража, которые пропустят человека, испившего из кувшина. В одном кувшине — смертельный яд, во втором — вода. Известно, что один из стражников всегда врёт, а второй — всегда говорит правду. Какой вопрос следует задать, чтобы не выпить яд? Вариантов этой задачи есть большое множество, однако все они уходят корнями в древнегреческие легенды, где это задание вставало перед одним из мифических героев.
Ответ: Необходимо спросить у любого из стражей, в каком кувшине, по мнению второго, яд. Если вопрос был задан правдивому стражу, он укажет на кувшин с водой, потому что врущий стражник так бы сделал. Если же вопрос задавался тому, кто всегда врёт, то он также указал бы на кувшин с водой, чтобы сказать неправду.
Задача №5 Есть закрытая комната с тремя лампочками накаливания. Выключатели находятся в другой комнате и посмотреть сразу, какой из них связан с какой лампочкой — невозможно. Сколько раз нужно открыть дверь, чтобы узнать, какой выключатель за какую лампочку отвечает?
Ответ: Если решать эту задачу стандартным математическим подходом, то потребуется как минимум два раза открывать дверь, вне зависимости от выбранного способа. Так, можно просто включить одну лампочку — и понять какой выключатель управляет ей, а второй раз — вторую. Однако подвох кроется в формулировке задачи, которая позволяет найти решение за один подход. Так, нужно включить две лампочки, подождать 10 минут и выключить одну из них, после чего — открыть дверь. Включенная лампочка отвечает за единственный включенный выключатель. Осталось потрогать оставшиеся 2 лампочки. Тёплой будет та, которая включалась сначала, холодной — та, за которую отвечает оставшийся выключатель.
Как решать логические задачи на собеседовании, у которых нет единственного ответа
Другой вариант логических задач на собеседованиях предполагает такую постановку задачи, что правильного ответа на неё просто нет, или же напротив — их существует несколько. При этом работодатели в первую очередь оценивают ход мышления сотрудника, скорость принятия решений и вынесения предположений, равно как и нестандартность подхода к поиску ответа.
К таким задачам на логику подготовиться на порядок сложнее. Однако регулярные тренировки, решение задач и загадок, участие в мозговых штурмах, могут помочь развить необходимые навыки. Главное правило, при решении логических задач на собеседовании — это проводить решение вслух, объяснять, почему был предпринят тот или иной шаг и сделан тот или иной вывод.
Подобный подход позволит работодателю или интервьюеру сразу оценить, как именно мыслит соискатель. И даже если ход его мыслей изначально не сходится с предполагаемым и ожидаемым ответом, он может напротив — предвосхитить результаты. Попытки же просто сразу сказать окончательный ответ без объяснений плохо воспринимаются профессиональными менеджерами по персоналу даже тогда, когда этот ответ действительно присутствует и является верным.
Источник: delatdelo.com
Задачи:
1) 5 землекопов за 5 часов выкапывают 5 м канавы. Сколько нужно землекопов, чтобы вырыть 100 м канавы за 100 часов, если продуктивность работы такая же?
2) Воздушный шар движется в потоке воздуха, в южном направлении. В каком направлении будут развеваться флаги на его гондоле?
3) Почему у яйца один конец острый, а другой – тупой?
4) В 12 часов ночи идет дождь. Можно ли ожидать, что через 72 часа выглянет солнце?
5) Как следует бросить мяч, чтобы он непременно к вам вернулся?
6) На пол положили карандаш и попросили нескольких людей по очереди через него перепрыгнуть. С задачей не справился никто. Почему?
7) Ире и Маше подарили по коробке, в каждой из которых 12 конфет. Ира съела несколько конфет. Маша съела столько конфет, сколько осталось в коробке у Иры. Сколько конфет осталось у Иры и Маши на двоих?
8) В деревне жил странный человек. Любимой забавой жителей и гостей деревни была следующая. Чудаку предлагали на выбор монету в 10 центов и бумажную купюру в 10 долларов. Человек всегда выбирал монету. Почему?
9) На закуску делимся с вами задачей, которую якобы использовал Эйнштейн, когда подбирал себе ассистентов. Другая легенда гласит, что эту загадку любил загадывать Льюис Кэролл.
На улице стоят пять домов.
Англичанин живет в красном доме.
У испанца есть собака.
В зеленом доме пьют кофе.
Украинец пьет чай.
Зеленый дом стоит сразу справа от белого дома.
Тот, кто курит Old Gold, разводит улиток.
В желтом доме курят Kool.
В центральном доме пьют молоко.
Норвежец живет в первом доме.
Сосед того, кто курит Chesterfield, держит лису.
В доме по соседству с тем, в котором держат лошадь, курят Kool.
Тот, кто курит Lucky Strike, пьет апельсиновый сок.
Японец курит Parliament.
Норвежец живет рядом с синим домом.
Каждый из домов покрашен в отдельный цвет, в каждом доме живет представитель отдельной национальности, у каждого — свой питомец, своя любимая марка сигарет и напиток.
Вопрос: Кто пьет воду? Кто держит зебру?
Ответы:
1) Те же 5 землекопов. За 1 час 5 землекопов выкапывают 1 м канавы. Значит, за 100 часов они выкопают 100 м.
2) Флаги не будут развиваться; они будут в таком же состоянии, как если бы шар находился на земле при полном безветрии. Дело в том, что относительно воздушной массы, в которой находится шар, он неподвижен, поэтому флаги будут находиться в состоянии покоя.
3) Такая форма позволяет яйцу не укатиться. Если бы яйцо было правильной, симметричной формы – например, круглым – оно могло бы катиться по прямой. Несимметричная форма заставляет яйцо двигаться по кругу. То есть если оно находится, например, на краю пропасти, то шансов укатиться и упасть у яйца меньше. Так природа заботится о сохранении яйца и его содержимого.
4) Нет, солнце не выглянет, потому что через 72 часа (трое суток) будет 12 часов ночи.
5) Нужно бросить его вверх.
6) Потому что карандаш положили вплотную к стене.
7) 12 конфет.
8) Он выбирал монету, потому что знал, что, как только он выберет купюру, люди потеряют к забаве интерес, и он перестанет получать монеты.
9) Японец держит зебру, норвежец пьет воду.
Источник: blog.trud.com
Периодически интервьюеры задают различные задачи, слабо относящиеся к вашей будущей работе. Особенно этим грешат в больших компаниях. Именно там, где каждый большой или маленький начальник думает не о том, что нужно будет делать работнику, а о том, как бы проверить одно из его логических качеств, которые, возможно никогда и не пригодятся в работе. Хотя многие говорят, что интересует не решение этих задач, которые дают на собеседовании, а то, как их решает соискатель.
На собеседовании могут задать несколько типов задач, чтобы посмотреть креативность, широту взглядов и “незашоренность” Часто такие задачи не имеют единственно правильного решения и интерьвьюеру интересен путь по которому кандидат идет, например, “Посчитайте сколько заправок в стране “. Но есть и задачи, которые имеют решение. Это как раз на логику. Здесь представлено несколько логических задач у которых есть правильное решение, нужно только чуть-чуть подумать.
Задача первая: котлеты на сковородке
У вас есть три котлеты и две сковороды. Каждая сторона котлеты жарится одну минуту. На одну сковороду одновременно помещается лишь одна котлета. За какое наименьшее время можно пожарить все котлеты с обеих сторон?
Начинаем решать в лоб. Если взять и пожарить две котлеты с двух сторон, то это займет две минуты. Снимаем две пожаренные котлеты и кладем третью. Тогда ее придется жарить еще две минуты. Что в итоге дает нам четыре минуты общего времени. Это не совсем правильно, поскольку можно пожарить эти котлетки всего за три минуты.
Теперь начинаем думать креативно. У нас есть ресурс – две сковородки. Они могут жарить одновременно. Если мы начнем с двух котлет, то займем ресурс полностью, однако, половина ресурса будет простаивать, когда будет жариться третья. Т.е. для сокращения времени нужно задействовать вторую сковородку, все время. Как это сделать? У нас есть возможность разделить жарку на обжаривание с одной стороны и с другой. Т.е. все время жарки будет 3 котлеты умножить на 2 стороны = 6 этапов. Если есть шесть этапов, которые занимают 6 минут и есть две сковородки на которых эти этапы нужно выполнить, то получается, что реально можно пожарить за три минуты, вопрос только в алгоритме. Тут и приходит решение. После одной минуты, когда пожарилась первая сторона, нужно одну котлету, наполовину пожаренную, снять и положить на ее место сырую. А на третьей минуте, уже пожаренную снять и дожарить оставшуюся на свободной сковородке.
Задача вторая: горючие веревки
Вам даны две верёвки и коробок с достаточным количеством спичек. Про каждую из верёвок достоверно известно, что будучи подожжённой она сгорает полностью за один час. Необходимо отмерить 15 минут. Как это сделать с учётом того, что верёвки горят неравномерно?
Неравномерность горения веревок – это как раз для тех умников, которые решили веревки поделить на четыре части. Этот вариант не подходит. Т.е. нельзя просто разрезать веревку на четыре части и поджечь, это не будет точным измерением, поскольку время горения не соответствует длине. Какая-то часть веревки может сгорать быстрее, а какая-то часть – медленнее.
Продолжаем думать креативно. У нас есть единица измерения – время горения веревки. Это время – 1 час по условиям задачи. Это время никак не соотносится с длиной. Но у нас две веревки, поэтому мы можем как-то время горения одной веревки соотнести с временем горения другой. А теперь ключ к решению задачи. Ведь если веревка горит 1 час, значит ее подожгли с одного конца, следовательно, если ее поджечь с двух концов, то она точно сгорит за 30 минут, конечно будет гореть неравномерно, но время будет точным. Все, у нас есть с чем сравнивать. Поджигаем первую веревку с двух сторон, а вторую только с одной(чтобы засеч время). Первая спокойно горит тридцать минут, и когда она сгорела мы тушим вторую веревку. Получается, что у нас остался кусок веревки, который должен сгореть за пол-часа (какая длина-не важно). Теперь применяем к ней тот же метод, что и для первой – поджигаем с двух сторон и получаем пятнадцать минут горения.
Задача третья: комната с лампочками
Есть закрытая комната, где находятся три лампочки. Снаружи есть три выключателя. Необходимо узнать какую лампочку включает каждый выключатель, но при этом можно зайти в комнату только один раз. (Нельзя бегать и щелкать выключателями).
Конечно, как менеджер, можно привлечь помощников, но нужно использовать иной взгляд на лампочки и обойтись самому. Начинаем размышлять. Комната закрытая, лампочки снаружи не видны. Если включить одну из них, а остальные выключить, а потом пойти посмотреть, мы узнаем какой выключатель управляет горящей лампочкой. По условиям, мы должны сразу же как-то различить и остальные две. Если они не горят, то они совершенно одинаковые. Нам нужно что-то придумать, чтобы при входе в комнату сразу было понятна связь между выключателем и выключенной лампочкой.
Интересный вариант решения нашел на одном из форумов. У нас есть два состояния горит-не горит и два состояния выключателя вкл-выкл, при этом лампочек три. Было бы две, то сложностей – никаких, одну включили, вторую выключили и пошли посмотрели. Значит одна лампочка должна быть включена, вторая выключена, а что делать с третьей? Предложили к третьему выключателю подвести 380 вольт, от которых лампочка перегорает(у ламп накаливания, хорошо видна спираль, если она перегорела, то это видно). Т.е. предложение добавить еще одно состояние исправна-не исправна. Т.е. лампочка теперь может быть в трех состояниях горит/ не горит и исправна/ не горит и неисправна. Поразмыслив над третьим состоянием можно вспомнить, что когда лампочка включена, она нагревается, а если ее выключить, то какое-то время она остается теплой, т.е. получаем разделение не горящих лампочек по теплая-холодная. Следовательно для решения задачи включаем два выключателя на некоторое время, потом выключаем один и идем смотреть. Видим одну горящую лампочку, и две не горящих, одна из которых теплее другой, что указывает на тот выключатель, который только что выключили.
Задача четвертая: золотая цепочка
На постоялый двор приехал путешественник. Денег у него с собой не было, но была золотая цепочка из шести звеньев. Хозяин постоялого двора согласился принять в оплату комнаты за каждый день по одному колечку с этой цепочки, но так чтобы распиленных колец он получил не больше одного. Никто друг другу не доверяет и не хочет платить вперед или заплатить потом, оплата должна быть ежедневной. Как постояльцу нужно распилить цепочку, чтобы можно было ежедневно расплачиваться на протяжении пяти дней?
Чтобы шесть звеньев разъединить и итоге осталось по одному звену, явно не получится распилить одно звено, поскольку колец 6, а соединений 5 то чтобы их разъединить все по одному, нужно как минимум три разреза (5/2 округляем до целого, получается 3).
Здесь что-то не так, начинаем думать креативно. Здесь есть понятие “оплата”, т.е. по условиям задачи нет требования, чтобы постоялец передавал хозяину по одному звену, есть требование, чтобы каждый день у хозяина становилось больше на одно звено. Теперь подходим к самой главной мысли, что хозяин и постоялец могут меняться, или, к примеру, хозяин может давать сдачу. Тогда все тривиально. Пилим одно звено – третье, чтобы была разменная монета 1, 2 и 3 звена, и в первый день турист дает хозяину одно звено, во второй меняет своих два на одно вчерашнее, в третий день может поменять два на три и т.д. Каждый день у хозяина на одно звено больше.
Задача пятая: взвешивание
Есть восемь монет, семь из которых весят одинаково, а одна немного меньше (фальшивая, но без весов не определить). Есть весы с двумя чашками, но нет гирь. Необходимо за минимальное число взвешиваний найти фальшивую.
Начинаем с первого попавшегося алгоритма. Берем первые две монеты и кладем на противоположные чашки весов, если одна легче, то фальшивка найдена, если вес одинаков, то берем следующую пару. Проблема в том, что пар у нас четыре т.е. в самом неудачном случае, нам понадобится четыре взвешивания. Программисты, прочитав это решение, должны были хитро усмехнуться и сказать, “но есть же двоичный поиск, совсем не обязательно взвешивать все пары”.
Для тех, кто далек от программирования вот пример двоичного поиска: Чтобы поймать льва в пустыне нужно поделить пустыню пополам, посмотреть в какой половине лев, затем поделить эту половину пополам, а затем еще пополам, до тех пор пока лев не окажется в клетке. Теперь делим наши восемь монет пополам, кладем по четыре монеты с каждой стороны весов. Монеты с той стороны, которая тяжелее убираем(там нет фальшивки) и делим оставшиеся пополам, получается по две на каждую сторону, теперь осталось всего две монеты для последнего взвешивания. В итоге мы получили три взвешивания. Ура! мы победили! И тут для программистов – холодный душ. Оказывается можно решить задачу всего за два взвешивания. Придется думать…
Быстрее, чем двоичный поиск еще ничего не придумали, т.е. сократить количество взвешиваний можно только отказавшись от взвешивания. Проблемка. Но решение все-таки есть. А если взвешивать не все монеты, а поделить по три, а две отложить? Тогда в случае, если при первом взвешивании будет одинаковый вес, то вторым взвешиванием отложенных двух монет, находим нужную. Если же вес при первом взвешивании не одинаков, то берем те три монетки, которые на легкой стороне, откладываем одну и взвешиваем две оставшихся. Если вес разный, то монета найдена, если вес одинаков, то оставшаяся монета и есть фальшивка.
Задача шестая: как разделить торт
Необходимо разделить круглый торт на на восемь равных частей тремя разрезами.
Вот здесь сразу можно поставить человека в тупик, ведь на первый взгляд нужно четыре разреза, ведь частей 8. Но если посмотреть на это креативнее…
Решение простое, и можно дать как минимум два. Для начала поймем, что реально разрезать один торт на восемь равных частей тремя разрезами нельзя, по крайней мере так, как мы это себе представляем: открыли коробку с тортом и начали резать. Так не пойдет, для восьми частей, нужно четыре разреза. Но их можно сократить, если представить себе торт не как плоский круг, а привлечь пространственное мышление. Сначала делаем два разреза крест на крест, получаем четыре куска. Теперь нужно придумать, как за один раз порезать все четыре куска ровно пополам. Если вспомнить, что никто не ограничивает нас в перестановке уже отрезанных кусков, то просто складываем куски стопкой и режем все вместе – это первый вариант. А если все-таки вспомнить, что торт имеет определенную толщину, то последний разрез делаем не сверху как первых два, а поперек всех кусков посередине торта, отделяя верх от низа, но так, чтобы было ровно. Правда в этом случае половина гостей получит кусок без глазури, но ради науки чем-то нужно жертвовать.
Источник: journal.caseclub.ru