Задачи с собеседований. Три адекватные задачки на «подумать» / Habr
И снова про собеседования. Некоторые простые задачи порой вызывают затруднение. В этом посте я хочу рассмотреть три задачки с собеседований, которые мне понравились, потому что к их решению можно прийти самим, но чуток подумать все равно придется.Задача 1. Проверьте, насколько вы избалованный программист
Дана упорядоченная последовательность чисел от 1 до N. Из нее удалили одно число, а оставшиеся перемешали. Найти удаленное число.
С толку сбивает только одна фраза «упорядоченная последовательность», она-то и может натолкнуть на использование сортировки для решения данной задачи. Программисты довольно часто пользуются готовыми библиотеками и фреймворками, поэтому при решении задач автоматом обдумываешь, что будешь использовать из библиотеки. Для многих программистов единственным очевидным решением является сортировка полученной последовательности и далее поэлементное сравнение исходной и отсортированной последовательностей до первого несовпадения. Можно подсчитать сложность такого решения: сложность сортировки плюс линейная сложность поиска. Хм, может подойти к решению как-то иначе?Есть более простое решениеДавайте забудем о том, что последовательность упорядочена. Обе последовательности различаются всего одним числом, а значит, чтобы его найти нужно из суммы элементов исходной последовательности вычесть сумму полученной. И кстати, если все элементы уникальны, то в исходном массиве у нас арифметическая прогрессия и первую сумму можно вычислить как .
Задача 2. Жонглирование числами
У вас есть пятилитровый и трехлитровый кувшины и неограниченное количество воды. Как отмерить ровно 4 литра воды? Кувшины имеют неправильную форму, поэтому точно отмерить половину кувшина не получится.
Это моя любимая задачка из разряда «головоломок». С одной стороны нужно немного подумать, а с другой – она действительно проста и адекватна.РешениеЗдесь придется немного пожонглировать с простыми числами 5 и 3.
1. Заполняем трехлитровый кувшин. Переливаем эти 3 литра в пятилитровый кувшин.
2. Снова заполняем трехлитровый кувшин и переливаем из него в пятилитровый. Помним, что в пятилитровом кувшине сейчас 3 литра, до полного его заполнения из другого кувшина выливается 2 литра. В трехлитровом кувшине остался один литр.
Задача 3. Без посредников
Имеется два числа. Можно ли поменять их местами без использования дополнительной переменной?
Как потом оказалось, это довольно популярная задачка. Но я решила со значительным недочетом.
Решить задачу можно, используя арифметические или побитовые операции. Поскольку арифметические показались проще, то я решила использовать их.
РешениеПусть у нас есть A и B.A = A + B
B = A – B // После этого B становится A, т.к. в действительности получаем (A + B) – B = A
A = A – B
В этом решении есть большой минус: возможность переполнения. Поэтому лучше использовать поразрядную операцию XOR.
A = A ^ B
B = A ^ B
A = A ^ B
Как это работает: в первой строке мы получаем маску на различающиеся биты, в этих разрядах будут стоять единички. Далее производится сброс и выставление нужных бит для обмена значений.
На примере будет наглядней. Рассмотрим обмен чисел 5 и 9.
A = 0101 ^ 1001 = 1100
B = 1100 ^ 1001 = 0101
A = 1100 ^ 0101 = 1001
Осталось только пожелать всем успешных собеседований!
А в комментариях можете написать, какие задачи встречались вам.
habr.com
Задачи с красивыми решениями / Habr
Существует класс задачек, которые в основном передаются из уст в уста, можно сказать входят в математический фольклор. Иногда встречаются задачи с очень красивыми решениями. Ты смотришь на решение, вроде понимаешь каждый шаг в рассуждениях, но чувствуешь себя как будто обманутым. Ты все понимаешь и одновременно ничего не понимаешь. Аналогию, наверное, можно провести, например, с этой оптической иллюзией:Тут видишь то большой куб с выпиленным куском, то маленький кубик, стоящий в углу.
В этом посте я собрал некоторые мои любимые задачи, решения которых, как мне кажется, вызывают этот неуловимый дуализм чувств: «понимаю — не понимаю».
Окружность и линейка
Доказать, что при помощи только одной линейки нельзя найти центр нарисованной на плоскости окружности (считается, что линейка имеет бесконечную длину; ею можно соединять любые заданные точки на плоскости; на линейке нет никакой шкалы, и ничего нельзя на ней отмечать).Решение Рассмотрим наклонный конус, основанием которого является некая окружность . Так как конус наклонный, то существует некая не параллельная основанию плоскость, которая высекает из конуса вторую окружность, назовем ее .
Поместим на вершине конуса лампочку. Эта лампочка будет бросать тень каждой прямой, лежащей на плоскости «верхней» окружности , на плоскость «нижней» окружности . Притом тенью любой прямой будет тоже прямая. Заметим, что эта тень настолько хитрая, что несмотря на то, что отображает «верхнюю» окружность в «нижнюю» , тень центра «верхней» окружности не попадает в центр «нижней».
Теперь на минутку представим, что существует такой чудесный алгоритм, который говорит, как при помощи одной линейки найти центр любой окружности. Этот алгоритм, читай компьютерная программа, должен состоять из последовательности действий типа: проведи произвольную прямую, проведи вторую произвольную прямую, соедини такую-то точку пересечения с такой-то точкой, потом точку пересечения вот этой прямой и окружности соедини с другой какой-то точкой, и так далее… Заметим, что если мы будем применять этот чудо-алгоритм на «верхней» плоскости для нахождения центра окружности , то «тень» этого алгоритма будет выполнять точно такие же команды на «нижней» плоскости. И так как мы предположили, что наш алгоритм (набор команд) находит центр любой окружности, то «тень» алгоритма, выполняющая точно такие же команды, обязана найти центр нижней окружности. Мы немедленно приходим к противоречию, потому что, как мы отмечали ранее, тень найденного центра «верхней» окружности не попадает в центр «нижней».
Задача московского метро
В московском метро есть правило, которое запрещает проносить предметы, сумма высоты, ширины и глубины которых больше см. Давайте условимся, что речь идет о прямоугольных ящиках. Доказать, что нельзя обмануть систему и полностью засунуть ящик, сумма измерений которого больше см, в ящик с суммой измерений меньше см. Ящик можно пытаться укладывать как угодно криво-косо, но мять нельзя.
Для нашего доказательства нам понадобится понятие -вздутия над телом. Возьмем произвольное тело в пространстве, ее -вздутием назовем множество точек, которые находятся на теле или на расстоянии меньше чем от него. Скажем, -вздутием точки в пространстве будет шар радиуса , а -вздутием отрезка будет тело, похожее на сосиску.
Теперь возьмем наш параллелепипед (ящик плюс ее внутренняя часть) размерами , и , и объемом, соответственно, . Попытаемся посчитать объем ее -вздутия. В это -вздутие входят:
Мы получаем, что объем -вздутия ящика будет равняться
Пусть теперь в ящике с размерами сторон , и находится второй ящик , и . Ясно, что какое бы число мы не взяли, -вздутие внутреннего ящика будет лежать в -вздутии внешнего ящика, поэтому ее объем будет меньше:
Подставляем в неравенство выражения для объемов, сокращаем одинаковые члены и делим все на :
Заметим, что последнее неравенство обязано выполнятся для любого , как для маленького, так и для большого. Поэтому мы всегда можем перейти к пределу , получим:
Вот мы и доказали, что если один ящик находится во втором, то сумма ее размерностей не может быть больше.
Кирпичная стена
Представьте себе, что у нас есть очень много разных прямоугольников (двухмерных кирпичей) таких, что у каждого кирпича хотя бы одна сторона имеет целую длину. Из таких кирпичей построили ровную прямоугольную стену, без наложений и дыр, кирпичи не наклонены. Доказать, что у получившейся стены хотя бы одна сторона имеет целую длину.
РешениеПеред тем как решать задачу, давайте вспомним одно замечательное свойство функции : ее интеграл по любому отрезку, длина которого кратна числу , равен нулю. Действительно
Более того, если интеграл функции от нуля до какого-то числа равен нулю, то смело можно считать, что число кратно .
Аналогично показывается, что для «сжатой» по горизонтали функции , интеграл по любому отрезку, длина которого кратна единице (целое число), равен нулю:
Теперь рассмотрим функцию (начало координат поместим в левом нижнем углу стены). Эта функция обладает таким замечательным свойством, что ее интеграл по любому кирпичу на стене равен нулю:
Действительно, ведь один из интегралов справа берется по отрезку длиной в целое число, и поэтому равен нулю.
Мы видим, что интеграл от нашей замечательной функции по любому из кирпичей на стене равен нулю, поэтому этот интеграл равен нулю и на всей стене, построенной этими кирпичами, так как попросту является суммой интегралов по каждому из кирпичей. Получаем:
Значит или , или должен равняться нулю. Из чего немедленно следует, что или горизонтальная, или вертикальная сторона стены имеет целую длину.
(upd: как мне подсказывают читатели, задача имеет по крайней мере 14 решений)
Задача про колодец
На поле вырыт круглый колодец. У нас есть очень много разных бесконечно длинных досок. Каждая доска имеет какую-то свою ширину. И мы этими досками полностью закрыли колодец так, что не осталось никаких щелей (доски необязательно все параллельны друг другу). Доказать, что сумма ширин досок всегда будет не меньше диаметра колодца.Решение Решение, если я не ошибаюсь, принадлежит Александру Карабегову.
Давайте накроем колодец полусферой, как показано на рисунке, а в колодец установим огромный прожектор, который светит параллельными вертикальными лучами наверх. И рассмотрим очень-очень тонкую доску, шириной , которая лежит на колодце.
Заметим что, чем дальше расстояние доски от центра колодца, тем меньше становится длина , которую занимает доска непосредственно над колодцем, но вместе с этим тем круче становится угол наклона тени от этой доски на полусфере. Оказывается, что эти два процесса компенсируют друг друга, и площадь тени не зависит от расстояния доски от центра колодца. Действительно, длина доски над колодцем , а тангенс угла наклона тени равен . Получаем формулу для площади тени от доски, которая равна длине тени умноженной на ее ширину:
Мы видим, что, действительно, где бы над колодцем не находилась очень тонкая доска шириной , площадь ее тени на полусфере будет всегда равняться , то есть будет зависеть только от ширины доски . Это свойство «независимости» выполняется и для досок любой ширины, ведь их можно представить как множество скрепленных между собой тоненьких досок. В итоге мы получаем замечательный результат: если ширина доски над колодцем равна , то площадь ее тени равна .
Пусть теперь множество досок ширинами полностью закрывают наш колодец. Некоторые из досок могут, конечно же, не всей своей шириной располагаться над колодцем. Поэтому площадь тени каждой из досок . Разные доски могут накладываться друг на друга, поэтому площадь общей тени
Но так как доски закрывают колодец без щелей, то их общая тень заполняет всю полусферу, а значит имеет площадь. В итоге получаем, что
Что и требовалось доказать.
habr.com
задача — это… Что такое задача?
ЗАДАЧА — может быть определена, по крайней мере, тремя различными способами: 1) как цель, поставленная перед решателем; 2) как ситуация, которая включает в себя и цель, и условия, в которых она должна быть достигнута; 3)как словесная формулировка (знаковая модель) проблемной ситуации ( Г. А. Балл). Наибольшее распространение получил 2-й способ формулировки (А.Н. Леонтьев).
3. служит для мышления «спусковым крючком», приводя в движение мыслительный процесс. При этом она выступает формой взаимодействия с неопределенностью: до нахождения окончательного решения искомое в значительной степени не известно. Именно 3. представляет человеку эту неопределенность, причем способом, допускающим поиск решения.
3. обладает объективной и психологической структурой (В.В. Петухов). Первая существует независимо от процесса решения, а вторая — только в его ходе. Объективная структура 3. включает в себя ее условия и требование. В психологической структуре требованию соответствует цель, а условиям — средства ее достижения.
Процесс решения начинается с преобразования требования в цель. В итоге 3. оказывается представленной человеку и принятой к решению. Это значит, что у него появляется представление о 3.: она притягивает к себе его внимание и вследствие наличия цели «заставляет» себя решать. Именно в этот момент 3. целиком соответствует определению: цель, поставленная в определенных условиях.Структуру 3. можно описать и иначе. В ней выделяется известное (условия и требование) и неизвестное (искомое), связанные между собой определенными отношениями (СЛ. Рубинштейн), опираясь на которые решатель и находит ответ.
3. можно классифицировать по следующим параметрам.
I. Содержание требования.
1.3. на преобразование, на систематизацию, на выведение структуры, на оценку дедуктивных аргументов (Дж. Грино).
3. на преобразование представляют собой описание наличного и целевого состояний и требуют последовательности операций, переводящих первое во второе; 3. на систематизацию включают в себя массу материала, структурирование и систематизация которого и обеспечивает достижение цели; задачи на выведение структуры предполагают отыскание общего принципа; 3. на оценку дедуктивных аргументов, наоборот, направлены на применение общих положений к конкретным примерам.
II. Организация и полнота условий.
2. Подлинные 3. и З.-описания (Л.М. Фридман). Подлинная 3. сформулирована на языке той области знаний, средствами которой она может быть решена. Все остальные — 3.- описания.
3.3. с полными, неполными или избыточными условиями.
4. Правильно и неправильно поставленные 3. (Л.М. Фридман).
В правильно поставленной 3. указанные в ней отношения определены для тех элементов предметной области, для которых эти отношения заданы в условии, и все утверждения в условиях являются истинными. Неправильно поставленными оказываются 3.: а) в которых используются неопределенные элементы или отношения между ними и б) в которых имеются ложные утверждения.
III. Параметры цели.
5. Открытые и закрытые 3. (Дж. Гилфорд).
Открытыми называют 3., имеющие большое (в пределе — бесконечное) количество правильных решений; закрытыми — с ограниченным количеством ответов.
6. Хорошо определенные и плохо определенные 3. (М. Минский).
Хорошо определенными являются 3., для которых сформулированы критерии правильности полученных решений. Для плохо определенных 3. они отсутствуют.
7. Теоретические и практические 3. (Б.М. Теплов).
Теоретические 3. предполагают объяснение и предсказание явлений на основании общих закономерностей. Практические 3. связаны с реализацией каких-то замыслов в конкретных условиях, включающих нехватку ресурсов и противодействие. Они хуже определены и их условия могут подвергаться сомнению.
IV. Наличие средств.
8. Творческие и репродуктивные 3.
Для репродуктивных 3. у решателя есть готовые способы решения, ведущие к успеху. В случае творческих 3. такие средства либо отсутствуют, либо по каким-то причинам не могут быть использованы.
9. Решаемые и нерешаемые 3. Решаемая 3. имеет какое-либо решение. Нерешаемые
задачи бывают двух видов: формальные и реальные. Формальные отличаются противоречивой формулировкой; реальные — это недостижимые при заданных условиях цели.
Не попадают в общую схему следующие классификации:
10. Действенные, образные и пропозициональные (вербальные) 3. (Дж. Брунер).
Существуют три основные формы представления реальности человеком: действие, образ и знак. В соответствии с этим можно различить действенные, образные и пропозициональные 3.11. «Инсайтные» и «регулярные» 3. Эти 3. противопоставлены друг другу на основании
характера обнаружения ответа. Инсайтные 3. предполагают наличие в процессе решения ключевого этапа, когда скачкообразно происходит понимание основных отношений проблемной ситуации и формулируется ответ. В другом случае процесс решения постепенно приближает человека к цели.
12. Предзаданные и формулируемые по ходу решения 3.
Обычно человек получает задачу, уже имеющую какую-то формулировку. В более сложном случае он вынужден сам ее формулировать по ходу решения проблем (см. Проблема).В.Ф. Спиридонов
Решение комплексных 3. (англ. complex problem solving) — решение систем взаимосвязанных 3., относящихся сразу ко многим областям, которые ранее в такую систему не объединялись. Подзадачи, входящие в систему, характеризуются разнородностью представляемых ими предметных областей, а также разными уровнями формализации и разработанности: от стандартных, корректно поставленных и алгоритмически разрешимых 3. до совершенно новых и еще нечетко сформулированных. (Примером комплексной 3. может служить реализация инновационного проекта, в котором одновременно во взаимосвязи решаются научно-технические, технологические, экологические, социальные и др. 3.)
Объектом деятельности субъектов, решающих комплексные 3., являются динамически изменяющиеся среды (технологические, природные, социальные), содержащие большое число компонентов с заранее неизвестными и неочевидными («непрозрачными») множественными связями между ними. Эти связи организованы по принципу целостных сетей взаимодействий, а не отдельных, изолированных друг от друга цепей. Поэтому, делая, казалось бы, что-то одно, решающий на самом деле воздействует на множество самых разных объектов, связанных между собой. Такие системы часто характеризуются внутренней динамикой — изменениями собственных системообразующих свойств, связей и зависимостей, т.е. изменениями не только на уровне конкретных проявлений, но и на уровне своей сущности (со временем система становится качественно иной). В поведении и развитии этих систем всегда есть значимая доля принципиально неустранимой неопределенности и непредсказуемости. В силу названных причин субъекты, решающие комплексную 3., могут сталкиваться с побочными и отдаленными следствиями своих действий, которые прямо противоположны их целям.
Следствием непредсказуемости результатов поисковых проб при решении являются: а) неожиданные открытия ранее не известного и не предполагавшегося; б) ошибки разной степени тяжести (в ряде случаев — фатальные).
Решение комплексных 3. требует комплекса способностей высокого уровня: познавательных (способности собирать разнообразную информацию из множества источников, обрабатывать ее в условиях ограниченного времени и принимать несколько решений одновременно), личностных и эмоциональных (способности действовать в условиях новизны и неопределенности, внутренней готовности к различным результатам действий, в том числе неожиданным, — как положительным, так и отрицательным), социальных способностей, связанных с пониманием и учетом намерений и действий множества людей — партнеров, союзников и противников.
А.Н. Поддьяков
Факторы успешности решения 3. делятся на личностные и ситуативные. К личностным относятся черты личности и ее отношение к познавательной сфере, которые влияют на особенности мышления, определяя степень его восприимчивости к ситуативным факторам. Ситуативные факторы непосредственно связаны с 3. или проблемой (ее содержанием, формулировкой, способом предъявления и т.д.) и с ситуацией решения. Факторы делятся также на приближающие к решению («подсказки») и мешающие его достижению («барьеры»).
Ситуативные факторы:
1. Количество материала, составляющего 3.
2. Структурированность материала — чем лучше исходно организован материал 3. или проблемы, тем она легче.
3. Сложность формулировки — чем сложнее сформулированы условия 3., тем она труднее.
4. Контринтуитивность условий — если условия противоречат здравому смыслу или прошлому опыту человека, 3. оказывается для него трудной.
5. «Функциональная фиксированность» (К. Дункер) — функции предметов, составляющих 3., бывают жестко фиксированными для испытуемого, что затрудняет нахождение решения.
6. Психологическая «доступность» (К. Дункер) — возможность испытуемого использовать те или иные свойства предметов.
7. «Оптимум мотивации» ( Р. Йеркс — Дж. Додсон) — различные по трудности 3. требуют разного уровня стимуляции для успешного решения.
8. Противоречие между общими принципами решения и особенностями проблемной ситуации.
9. «Маскировка» условий формулировкой 3.
10. Перенос способов решения — использование уже известных способов для решения новых проблемных ситуаций. Перенос может служить не только помощью, но и серьезным затруднением в ходе решения (см. Перенос способов решения).Личностные факторы:
1. Структура и свойства интеллекта. Структурные факторы: чем выше развита какая-либо интеллектуальная способность (общая или специальная), тем лучше решаются соответствующие задачи.
Уровень интеллекта: люди с более высокими показателями по интеллектуальным тестам лучше выдвигают и проверяют гипотезы, менее подвержены негативному влиянию интеллектуальных установок, шаблонов и привычек.
Роль эвристик — мыслительных средств, предназначенных для самонаведения человека на решение, интенсифицируя решение; однако существуют и «минус-эвристики», которые приводят к ошибкам (см. Эвристика).2. Личностные особенности. Описан ряд черт, свойственных творческой личности:
более эффективное восприятие реальности, центрированность на проблеме, «свежесть» восприятия, отсутствие предубеждений, чувство юмора, креативность, сопротивление окультуриванию и др.
Выявлены также характеристики, выступающие помехами в ходе решения:
а) конформизм;
б) внутренняя цензура — неспособность снять внутренние запреты по поводу содержания и формы собственных идей;
в) ригидность;
г) низкая самоэффективность (А. Бандура): недоверие к собственным возможностям и недостаток настойчивости в ходе решения.
Мотивационные характеристики: ряд постоянно действующих мотивов, которые удовлетворяются за счет достижений в интеллектуальной сфере — мотивация достижения, познавательная мотивация, ориентация на действие. Они определяют выбор человеком 3. и проблем в долгосрочной перспективе и количество усилий, которое затрачивается на решение.
Ситуативные переменные — уровень притязаний и самооценка — позволяют человеку соотнести оценку своих возможностей с достигнутыми результатами и выработать стратегию поведения, сохраняющую сложившееся самоотношение.
3. Организация знаний.
Эксперты в различных сферах деятельности отличаются от новичков количеством «единиц» профессионального опыта — чанков; наличием четких схем предметных областей, в которых возникают проблемы; связью между этими схемами и стратегиями решения и др.
В.Ф. Спиридонов
Энциклопедия эпистемологии и философии науки. М.: «Канон+», РООИ «Реабилитация». И.Т. Касавин. 2009.
epistemology_of_science.academic.ru