Этим постом мы также завершаем первый сезон сериала головоломок. Поддерживать его было трудно, но интересно. Нам особенно было радостно, когда наши читатели находили решения, и описывали их на сайте или в соцсетях. Вот все 15 серий, в каждой есть условие, к каждой дано решение в следующем номере. К последней задаче ответ дан в конце этого поста.
- Двойные фамилии
- Спрятанное решение
- Остров хамелеонов
- Номер Тьюринга
- Время великих учёных
- Прогуливающиеся джентльмены
- Часы с одинаковыми стрелками
- Вирус в колонии бактерий
- Шесть шахматных коней
- Задача о беглеце
- Чеширский кот и число палиндромов
- Карточная головоломка Конвея
- Задача о необычном замке
- Алгоритмическая головоломка о лягушках
- Задача Сфинкса о разрезании лестниц
Пишите в комментариях, понравились ли вам эти сложные задачи на логику и алгоритмы. Лайкните этот пост, если вам понравился формат и вы ждёте продолжения сериала.
Логические задачи с ОТВЕТАМИ. Задачи на собеседовании. Часть 1
Решение задачи о разрезании лестниц
Если вы не решали эту задачу, прежде чем читать приведенный ниже текст, прочитайте условие и попробуйте решить самостоятельно!
Ответ. Первым очевидным решением является уже «разрезанный вариант», состоящий из самой фигуры тримино, то есть n = 2 . Все остальные ответы можно выразить так: разрезание возможно для любого n, которое можно представить в виде n = 3k или n = 3k+2 , где k > 1 .
Решение и алгоритм разрезания «лестниц». Очевидно, что разрезание на тримино в первую очередь возможно только, если сама лестничная фигура делится без остатка на 3. Общее число квадратов в фигуре определяется как сумма арифметической прогрессии, то есть:
Если n = 3k , а k – четное ( k = 2m ), то
Тогда число квадратов делится на 3.
В случае если n = 3k и k – нечетное ( k = 2m + 1 )
То есть вновь суммарное число квадратов делится на 3.
Аналогично можно показать, что для n = 3k + 1 деление всех квадратов на 3 без остатка невозможно, а для n = 3k + 2 вновь работает и для четных, и для нечетных k .
Как мы указали в подсказке к задаче хорошей идеей будет попытаться решить задачу для n , равных 3, 5, 6, 9, а далее – обобщить результаты.
Следующие рисунки демонстрируют невозможность разрезать «лестницы» для n = 3 и n = 5 .
Теперь покажем, что любая лестница, для которой n = 3k и k > 1 , может быть выложена плиткой из тримино по рекурсивному алгоритму. Возьмем первые примеры c k = 2 ( n = 6 ) и k = 3 ( n = 9 ).
Красивая задача с собеседования в Яндекс (2022)
Если n = 3k и k – четное целое число большее или равное 2 (т. е. n = 6m = 6 + 6(m – 1) , где m > 1 ), лестница может быть разрезана на три составляющие:
- лестницу для n = 6 , способ разрезания для которой показан выше,
- лестницу для n = 6 (m-1) , которую можно замостить рекурсивно с помощью этого описания,
- прямоугольник размером 6 × 6 (m – 1) , который разбивается на прямоугольники 3 × 2 , каждый из которых представляет собой две сцепленных фигурки тримино.
Если n = 3k и k – нечетное целое число:
- лестницу для n = 9 ,
- лестницу для n = 6(m-1) ,
- прямоугольник размером 9 × 6(m – 1) .
Оба случая представлены ниже на рисунке.
Наконец, если n = 3k + 2 , k> 1 , лестницу можно выложить из трех составляющих (см. рисунок):
- самой фигурки триминой, занимающей n = 2 ,
- прямоугольника 2 × 3k ,
- фигуры лестницы, которая соответствует уже рассмотренному случаю 3k .
Таким образом, мы рассмотрели все варианты разрезания лестниц для любых n , подчиняющихся описанному в ответе условию.
Как решали задачу читатели Библиотеки программиста? Самым сложным для решающих задачу оказалось описать способ построения ряда. Сами решения были найдены. Правильную последовательность n привел пользователь krotbsod:
Примеры замощения для n = привел пользователь riabininos:
Алгоритм описал пользователь kinshik:
Для начала представим все n в таблице с 6ю колонками, записав их последовательно. В первой строке 1,2,3,4,5,6. Во второй 7,8,9,10,11,12. И т.д.
Для n=1 число клеток не делится на 3. Методом индукции можно убедиться, что, если для n число клеток пирамиды не делится на 3, то и для (n+3) число клеток не будет делиться на 3. Действительно, если к пирамиде для n добавить 3 ряда в основание, то число клеток всей пирамиды увеличится на число, делящееся на 3. В итоге результат не будет делится на 3. Из этого правила вытекает, что n в 1м и 4м столбцах не имеют решений. Легко убедиться, что нет решений для чисел 3 и 5, но есть решения для 2, 6, 9 и 11.
Можно убедиться, что если есть решение для некоторого n, то есть решение для (n+6). Действительно, добавим к пирамиде для n в основание 6 рядов. Добавку можно разделить на 2 фигуры: пирамиду для 6 слева (которая имеет решение) и прямоугольник 6m. Очевидно, что эта вторая фигура хорошо делится на прямоугольники 2×3, которые имеют решение. Таблицу чисел, для которых могут быть найдены решения можно представить в виде: х 2 х х х 6 х 8 9 х 11 12 х 14 15 х 17 18 х 20 22 х 23 24 И т.д. Итого ответ: n=a+b*6, где a=, b=
Источник: proglib.io
Как пройти собеседование: каверзные вопросы и задачи при приеме на работу в крупных компаниях и их решение
Вы думали, что после получения диплома решать задачи больше не придется? Не тут-то было! Работодатели очень любят задавать разные задачки и головоломки. Так что не расслабляемся! Вопрос приема на работу – самый важный вопрос после получения диплома. Конечно, все стремятся найти работу по душе. Готовитесь решать вопрос трудоустройства?
Давайте посмотрим, с какими задачами могут столкнуться кандидаты, проходя собеседование в топовых крупных компаниях. А заодно и потренируем логическое мышление.
На случай, если Вам скоро предстоит собеседование: о том, что надеть и как вести себя при разговоре с HR-ом, читайте в нашей статье.
Какие задачи Вам могут задать на собеседовании
Логические задачи на собеседовании. Такие задачи встречаются на собеседованиях часто и могут предлагаться как в текстовом формате, так и в виде теста. Работодатели часто подбирают разные задачи в зависимости от специальности, на которую принимают работника. Очень часто с логическими задачами при приеме на работу сталкиваются специалисты из сферы IT и продаж.
Математические задачи на собеседовании. Как правило, такие задачи требуют базовых знаний математики. В большинстве математических задач на собеседовании не нужно брать тройной интеграл или решать дифференциальное уравнение в частных производных. Хотя бывают и редкие исключения.
Кстати, о том, как решать системы линейных уравнений методом Гаусса, читайте в нашей отдельной статье.
Аналитические задачи. Эти задачи – своеобразный синтез математических и логических задач. Испытуемому предлагают рассмотреть кейс, оценить все обстоятельства, выявить сильные и слабые стороны, а потом принять решение касательно описываемой ситуации.
Нестандартные задачи и вопросы. Такие задачи требуют логического мышления, но не только! Для их решения придется применить нестандартный подход и посмотреть на ситуацию под разными углами.
Задачи на собеседовании
А теперь Вашему вниманию 5 логических задач, которые требуют нестандартного подхода и логического мышления. Попробуйте решить их сами, а потом загляните в ответы.
Задача на собеседовании в Google
В Гугл любят проверить способность мыслить нестандартно. Вот одна из задач, которую задавали при приеме на работу в гугл.
Есть рычажные весы и 8 шариков одинакового вида и размера. Один из них тяжелее остальных. Найдите тот шар, который тяжелее. Взвешивание можно проводить только 2 раза.
Ответ: Сначала нужно разделить все шары на три группы. В двух группах – по 3 шара, а в одной – 2. Сначала кладем три шара на одну чашу весов, и три – на другую. Группа с тяжелым шаром перевесит. Потом взвешиваем любые два шара из этой группы.
Если шары весят одинаково, то тяжелый – тот, что остался.
Если же группы по 3 шара весили одинаково, то нужно взвесить оставшиеся два шара и найти тяжелый.
Задача на собеседовании в Adobe
Чтобы устроиться в Аdobe, проявите способность к логическому мышлению.
Шелдон Купер стоит перед двумя дверями. Одна дверь ведет к сокровищам, а вторая – к лабиринту, в котором он, Шелдон, обязательно заблудится и пропадет. У каждой двери стоит стражник. Каждый стражник знает, куда ведет его дверь, но один из них всегда говорит правду, а второй – постоянно врет. Что спросить Шелдону у стражников, чтобы узнать, какая дверь ведет к сокровищам?
Можно задать только один вопрос одному стражнику.
Ответ: Шелдон может спросить у любого стражника: какая дверь, по мнению другого, правильная, то есть ведет к сокровищам? Если спросить у правдивого стражника, то он укажет на нужную дверь. Другой стражник соврет о двери, на которую укажет правдивый стражник, тем самым тоже указав на нужную дверь.
Кстати! Для наших читателей сейчас действует скидка 10% на любой вид работы
Задача на собеседовании в Майкрософт
Представьте: есть неограниченный запас воды и два ведра объемом 5 и 3 литра. Как с их помощью отмерить 4 литра?
Ответ: Такую же задачу задали Боюсу Уиллису в Крепком Орешке 3. Только на кону там была жизнь, а не прием на работу.
Берем и наполняем ведро в пять литров. Из него наполняем трехлитровое ведро. В большом ведре остается 2 литра. Потом опустошаем маленькое ведро и выливаем в него два литра из большого. Снова наполняем большое ведро.
Наполняем из него маленькое ведро, доливая один литр. В большом ведре остается 4 литра.
Просто задача на смекалку
Популярный вопрос на собеседовании: почему канализационный люк круглый?
Ответ: Все очень просто. Крышки делают круглыми, чтобы они не проваливались в люк, когда его открывают. Кстати, круг – самая распространенная форма крышки для люка, но есть еще и треугольные крышки.
Пример нестандартной задачи от Google
Вот еще одна из задач гугл на собеседовании:
Сколько шаров для гольфа поместится в школьный автобус?
Ответ: У этой задачи нет однозначного ответа. Важен именно ход решения и мысли. Для наших реалий можно переформулировать условие и спросить: сколько самоваров поместится в жигули. Суть останется та же.
Нужно примерно представить габариты автобуса, зная радиус мяча для гольфа, вычислить его объем, учесть погрешность при вычислении объема автобуса и дать приблизительный ответ.
Математические задачи на собеседовании
А вот популярная математическая задача, которую можно встретить при приеме на работу:
В 00.00 часов идет дождь. Есть ли вероятность, что через 72 часа будет солнечно?
Ответ: С помощью простых математических действий можно понять, что нет. 72 часа — ровно трое суток. Значит, через это время снова будет полночь и никакой солнечной погоды просто не может быть.
Желаем Вам нестандартного мышления и мощной работы обоих полушарий мозга, которая поможет верно ответить на все нестандартные вопросы на собеседовании. А если вдруг понадобится помощь в решении задач — обращайтесь к нашим авторам, которые всегда находятся в полной боевой готовности.
Источник: zaochnik.ru
Дюжина логических задач с собеседований
Не знаю, как у вас, но у меня любимая часть интервью — логические задачи.
Довелось пройти немало собеседований на вакансию разработчика, поэтому набралась небольшая коллекция.
Спешу поделиться с вами!
Некоторые задачи проще и широкоизвестные, другие заставляют хорошенько задуматься.
Ответы пока что публиковать не буду, надеюсь, вы сами сможете всё решить.
Предлагаю размять свой мозг.
1) Человек построил дом, все стены которого смотрят на юг. К нему в дом забрался медведь. Какого цвета медведь?
2) На столе 12 монет, одна из которых фальшивая. Она отличается от остальных лишь по массе. За какое минимальное число взвешиваний на чашечных весах можно обнаружить фальшивую монету?
3) В первой изолированной комнате — три лампочки, во второй — три переключателя от каждой из них. Разрешается произвольно дёргать переключатели, но перейти из второй комнаты в первую можно лишь один раз. Как узнать, от какой лампочки каждый переключатель, если до потолка можно достать рукой?
4) Даны две веревки и спички. Каждая из верёвок сгорает за 1 час, но горят они неравномерно, поэтому нельзя точно узнать, какая часть веревки за какое время сгорит. Как отмерить при помощи этих веревок интервал в 45 минут?
5) В офис привезли три автомата с напитками. Первый выдаёт чай, второй кофе, а третий случайным образом чай или кофе. Стакан любого напитка стоит одну монету. На каждом автомате есть наклейка с названием продукта, который он выдаёт. Так получилось, что на заводе перепутали местами наклейки и на каждом автомате оказалась неправильная.
Сколько нужно потратить монет, чтобы выяснить, где какой автомат?
6) Есть два абонента A и B, почтальон C и открытый сейф с двумя замками. У каждого абонента есть ключ от одного из замков. Если передавать ключ через почтальона, то он может сделать дубликат. Как передать письмо от одного абонента к другому через почтальона, чтобы тот не смог его прочитать? Как изменится алгоритм, если в сейфе сделать небольшое отверстие для вложения письма?
7) Путник находится в лесу в какой-то случайной точке. Известно, что площадь леса равна S, а форма может быть совершенно произвольная, однако в лесу нет полян. По какой траектории нужно двигаться путнику, чтобы гарантировано выйти из леса затратив минимальный по длине маршрут?
8) Путешественник прошёл один километр на юг, затем один километр на запад, а после один километр на север и вернулся в исходную точку. Сколько существует таких мест на земле? Подсказка: больше одного…
9) Есть огромный файл в несколько гигабайт, в котором записаны целые числа. Нужно записать в другой файл все эти числа в отсортированном порядке. Как это эффективно сделать?
10) Есть огромный файл в несколько гигабайт, в котором записаны целые числа. Известно, что каждое число встречается два раза, но есть единственное число, которое встречается один раз. Предложите эффективный алгоритм для поиска этого числа. Как изменится алгоритм, если каждое число будет встречаться в файле чётное число раз, а единственное из них нечётное число раз?
11) Есть огромный файл, в котором записаны все целые числа из диапазона от 1 до 10^9 в произвольном порядке. То есть в файле есть абсолютно все числа из этого диапазона, и встречаются они лишь по одному разу. Однако одно число встречается два раза. Как найти это число эффективным образом?
12) Сколькими способами можно разложить на 6 целых множителей 1 000 000?
P.S. Любителям геометрии на закуску euclidthegame.org
- логические задачи
- программирование
- Разработка веб-сайтов
- Программирование
Источник: habr.com