решение задач на логику. Приложение модуль 1. Решение задач можно провести в форме игры Собеседование
 Скачать 20.36 Kb.
|
|
Приложение 1 Математика в программировании Решение задач можно провести в форме игры «Собеседование». Нестандартное мышление и логика в программировании – наше все. На собеседовании будьте готовы к тому, что некоторые задачи будут нетривиальными. Логические и математические задачи, которые нередко встречаются на собеседованиях и могут попасться вам. Основные проблемы, которые часто возникают в процессе интервью, не в отсутствии опыта или подготовки. Даже по-настоящему опытный разработчик может легко "споткнуться" о решение какой-нибудь хитро скроенной задачки. Поэтому мы поговорим не о том, как составлять резюме и выгодно презентовать себя. Фокусируемся на решении нетривиальных задач, которые включают в себя решение логического и/или математического характера. Полторы белки. 1,5 белки за 1,5 минуты съедают 1,5 ореха. Сколько орехов съедят 9 белок за 9 минут? Решение: Согласитесь, что 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. 3. Умножаем количество съеденных орехов:9*6 = 54. Ответ: 9 белок за 9 минут съедают 54 ореха. Лампочки и переключатели Условие: В первой закрытой комнате с низким потолком висит 3 лампы накаливания. В другой такой же комнате установлено 3 переключателя от каждой из них. Можно как угодно дергать переключатели, вот только перейти из 2-ой комнаты в 1-ую разрешено только 1 раз. Как узнать, за какую лампочку отвечает каждый из переключателей? Помните, что логика в программировании – это необходимый инструмент. Так как мы можем дотянуться до лампочки рукой (низкий потолок), следует на некоторое время включить одну из них на пару минут, выключить ее и включить любую другую. Далее переходим в комнату с лампочками и проверяем: та, которая горит, соединена с последним переключателем, который мы трогали; та, которая не горит и теплая, соединена с первым переключателем, который мы трогали; за не горящую и холодную лампочку отвечает переключатель, который мы вообще не трогали. Бейсбольный мяч и бита Здесь работает чистая математика. Условие: Бейсбольный мяч с битой вместе стоят $13. Но мяч дешевле бейсбольной биты на $3. Рассчитайте стоимость каждого предмета. 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. Задача о фальшивой монете Логика в программировании не ограничивается только математической составляющей, но она является одной из ключевых. То же самое и в случае с монетами. Условие: Дано 12 монет, из которых 11 – настоящие, и только 1 – фальшивая. Фальшивая монета отличается от настоящих по массе. Какое минимальное количество взвешиваний необходимо, чтобы обнаружить фальшивую монету? Для взвешивания используются чашечные весы. Задача легкая, хотя многие все равно начинают путаться, отвечая «1» или «2». Минимальное количество взвешиваний – 3, ведь даже если мы взвесим 2 раза, то как мы узнаем, какая из монет фальшивая? Большую часть монет составляют настоящие, так что 2 монеты с одинаковым весом и будут настоящими, третья с другим весом – фальшивой. Ответ: 3 взвешивания. Сжигаем веревки Условие: Есть 2 веревки и неограниченное количество спичек. Каждая веревка сгорает за час, однако горят они неравномерно, так что нельзя точно узнать, за какое время сгорит определенная часть веревки. Как отмерить с помощью этих двух веревок интервал в 45 минут? Горят веревки действительно неравномерно, но полностью сгорают точно за час. Мы можем: Поджечь оба конца одной веревки и только 1 конец второй веревки. Как только первая веревка сгорит (пройдет 30 минут, так как горит она с двух концов), поджигаем другой конец второй веревки, и она догорит ровно за 15 минут. Бочка с водой Условие: Дана пустая бочка. Нужно наполнить ее водой так, чтобы заполнена была только половина. Использовать палку или другие предметы для измерения нельзя. Да, логика в программировании может подкинуть и физику. А что? Ведь занимаются же как-то машинным обучением, и подобные вещи тоже могут пригодиться. Заполняем бочку водой (или полностью, или точно больше половины). Наклоняем бочку на 45 градусов: вся лишняя вода выливается, и остается ровно половина. Дождь и солнце Это очень легкая задача, но горе вам, если зададут ее под конец собеседования, когда последние силы покинут, а мыслительный процесс начнет изрядно буксовать. Условие: 12 часов ночи. Идет дождь. Можно ли ожидать, что по истечении 72 часов будет солнечная погода? Ответ: нет, так как через 72 часа также будет ночь. Кофе-брейк Условие: В офисе расположили 3 автомата с различными напитками. В первом – кофе, во втором – чай, а в третьем – и кофе, и чай (выдает случайным образом). Для любого из них нужна 1 монета. Каждый автомат обозначен наклейкой с названием продукта, который он выдаёт. Вот только на заводе перепутали наклейки, и на каждом из трех автоматов оказалась неправильная. За сколько монет можно выяснить, где какой автомат? Здесь, как и в случае с первой задачей, нужно абстрагироваться от мнимой сложности, ведь задача легкая. Бросаем монету в автомат с надписью «чай-кофе». Так как все наклейки расположены неверно, в зависимости от того, что выдаст автомат, мы определим его в «чайный» или «кофейный». Допустим, это оказался кофейный автомат. Тогда чайный автомат не может быть ни кофейным, ни чайным: он выдает и чай, и кофе. Методом исключения определяем автомат, который выдает чай. Ответ: за 1 монету. Крепкий орешек Вопросом, которые встречаются на собеседовании в компании Microsoft. Задача: Есть 2 пустых ведра: первое объемом 5 л, второе - 3 л. Как с их помощью отмерить 4 литра воды? Сперва наполните пятилитровое ведро. Далее перелейте из него воду в трехлитровое так, чтобы в пятилитровом осталось 2 л воды (полностью заполнив трехлитровое). Вылейте из меньшего ведра всю воду и перелейте в него оставшиеся в большем 2 л. Снова наполните пятилитровое и перелейте один литр в трехлитровое (оно как раз заполнится): так в большем ведре останется 4 л воды. Баночки с таблетками Задача: Есть двадцать баночек с таблетками. Почти во всех таблетки весят по 1 г, и только в одной - по 1,1 г. У нас есть точные весы, с помощью которых нужно определить баночку, каждая таблетка которой весит 1,1 г. Как это сделать, если можно взвесить только 1 раз? Давайте абстрагируемся и представим, что у нас 2 баночки, в одной из которых таблетки более тяжелые. Даже если мы поставим их обе на весы, мы ничего не узнаем. Но если мы достанем из одной баночки 1 таблетку, из другой - 2 и положим их на весы - вот тогда-то и откроется истина. В данном случае вес будет 2,1 или 2,2 (в зависимости от того, сколько каких таблеток мы взяли). Так и определяем нашу баночку. Вернемся к задаче. Из каждой баночки нужно доставать разное количество таблеток. То есть из первой баночки 1 таблетку, из второй - 2, из третьей - 3 и так далее. Если бы каждая таблетка весила по 1 г, общий вес составил бы 210 г. Но поскольку в одной из баночек таблетки тяжелее, вес будет больше. Для определения нужной баночки просто воспользуемся формулой: № тяжелой баночки = (вес - 210) * 10 Но на этом интересные логические и математические задачи не заканчиваются. Идем дальше! Свидание Задача: Парень и девушка договорились встретиться ровно в 21:00. Проблема в том, что у обоих часы идут неправильно. У девушки часы спешат на 2 мин., но она думает, что они на 3 мин. отстают. У парня же часы отстают на 3 мин., но он считает, что они на 2 мин. спешат. Кто из пары опоздает на свидание? Ничего сложного: чистая математика. Если у девушки часы спешат, а она думает, что они отстают, то поторопится и придет на 5 мин. раньше. Парень, наоборот, посчитает, что у него еще 5 минут времени в запасе, отчего на эти самые 5 мин. опоздает. Считаем вес курицы Задача: Длина курицы при измерении от головы до хвоста составит 45 см, а вот от хвоста до головы (если измерять вдоль брюха) - 53 см. По статистике плотность курицы на единицу боковой проекции составляет 8 г/см2. Усредненная высота курицы, если мерить ее вдоль боковой поверхности, - 21 см. Сколько весит килограмм курицы? Килограмм курицы весит 1 килограмм. Книжные страницы Задача: Книга содержит N страниц, которые пронумерованы стандартно: от 1 до N. Если сложить количество цифр (не сами числа), что содержатся в каждом номере страницы, выйдет 1095. Так сколько в книге страниц? Каждый номер страницы имеет цифру на месте единицы, так что есть N цифр, расположенных на месте единицы. А вот после 9 начинаются двухзначные числа, и нам нужно добавить N-9 цифр. То же самое с трехзначными, которые начинаются после 99: добавляем N-99 цифр. Продолжать нет смысла, так как сумма не предполагает более 999 страниц. Получаем следующую формулу: N + (N-9) + (N-99) = 1095 Далее просто решаем: 3N - 108 = 1095 3N = 1203 N = 401 Итого 401 страница. Задача: Математические задачи на собеседованиях бывают и довольно простыми, но зачастую только на первый взгляд. Попробуйте в уме разделить 30 на 1/2 и прибавить 10. Каким будет результат? Первое решение, которое обычно приходит на ум, ошибочно: 30/2 + 10 = 25 Если мы делим на дробь, ее нужно переворачивать и производить умножение: 30*2 + 10 = 70 |