В этом топике я предлагаю 3 довольно базовые задачи на сообразительность. Для начинающих программистов (вероятно, для совсем начинающих, а-ля школа, потому что для настоящего программиста слишком банально). Или, возможно, для собеседования, но для проверки конкретно одного узкого аспекта: насколько человек может вообще принимать решения самостоятельно, а не передирать и подправлять под себя.База
В качестве базы выбрана довольно известная задача про улитку для младших классов школы. «Улитка ползёт вверх по столбу высотой 5 метров. Каждый день она проползает вверх на 3 метра, а каждую ночь съезжает вниз на 2 метра. За сколько дней она доползёт до вершины столба.»
Как известно, многие школьники срезаются на том, что просто делят 5 на (3?2) и получают 5 дней, не учитывая того, что в конце третьего дня улитка уже? достигла вершины.
Задача 1
Вводятся действительные? неотрицательные числа: сколько проползает за день вверх; сколько съезжает за ночь вниз; высота столба. Должен вывестись ответ — минимальное необходимое целое число суток.
- Если высота столба 0 — возвращаем 0.
- Если дневной пробег 0 — возвращаем бесконечность/никогда?.
- Вычисляем разность высоты столба и дневного пробега (
РВСДП); если она неположительна — возвращаем 1. - Вычисляем пробег за целые сутки (
ПЗЦС); если он неположителен — возвращаем бесконечность/никогда?. - Возвращаем
1 + ceil(РВСДП / ПЗЦС).
? Под действительными я имел в виду с плавающей точкой. Можно взять и целые. Суть в том, что в общем случае разность высоты столба и дневного пробега может быть не кратна пробегу за целые сутки.
? Эти варианты, так и быть, можно простить (или задать в условии, что так не будет).
Суть в том, чтобы решающий обработал хотя бы: (1) классический случай (вершина достигается не в первый день, но ровно к концу какого-то из дней); (2) некратную длину (вершина достигается не в первый день и не ровно к концу какого-то дня); (3) короткую длину (вершина достигается ещё до конца первого дня).
Задача 2
То же самое. Только вернуть уже нужно не минимальное необходимое целое число суток, а «время» относительно длины суток (возможно нецелое число). Предполагается, что каждый день и ночь длится ровно по 0.5 (и процесс начинается ровно в начале дня). А улитка и днём, и ночью двигается с постоянной скоростью.
Задача 3
То же самое. Только процесс начинается в произвольное время, а не ровно в начале дня. Пользователь вводит произвольное действительное число — «время» начала процесса. Ответ — произвольное действительное число — «время» конца процесса.
Задача 1
Вася с силой 100 H тянет за ручку динамометра, вторая ручка которого нерастяжимой верёвкой привязана к неподвижной стене.
Вопрос: Какую силу покажет динамометр?
Задача 2
Вася и Федя, каждый с силой по 100 H, тянут за противоположные ручки динамометра.
Вопрос: Какую силу покажет динамометр?
Задача 3
Вася тянет за ручку динамометра с силой 80 Н, а Федя, будучи послабее, тянет за противоположную ручку с силой 70 Н.
Вопрос: Какую силу покажет динамометр?
Комментарии (42)
Sirion
04.10.2016 15:46+3По сложности — уровень внутришкольной олимпиады. По интересности — уровень сферического учебника в вакууме.
peck_wtf
04.10.2016 16:20в классическом решении задачи 1, в пункте 5, вы даёте неверный ответ.
Lelik13a
04.10.2016 17:13+1Вот отличная задачка про улиток:
Ползут три улитки.
Улитки ползут в одном направлении и по одной прямой.
Первая говорит:
— Впереди меня одна улитка и сзади одна.
Вторая говорит:
— Я ползу впереди, и две улитки позади.
Третья говорит:
— Впереди меня одна улитка и сзади одна.
Вопрос: Как такое может быть?
ОтветКакая-то улитка3,14здитврёт.
playermet
06.10.2016 20:15Третья улитка сидит на первой (и она не ползет, что не противоречит условию), а сзади ползет четвертая.
lifecom
04.10.2016 17:41+3Они ползут по кольцу и автор задачи врет, что они ползут по прямой
sasha1024
04.10.2016 18:16Или они ползут «по прямой» на неплоской поверхности (сфера, циллиндр и т.п.). Конечно, это не совсем прямая, но идя «прямо» по Земле, Вы ж не говорите «я иду по дуге». То, что они видят именно так (1-я и 3-я видят по штуке спереди и сзади, а 2-я — двух сзади), обеспечивается рельефом поверхности (не идеальная сфера/циллиндр/т.п.) и тем, что они дают отчёт в разное время.
marenkov
04.10.2016 17:47+1Старая школьная задачка на сообразительность:
Расстояние между двумя параллельными стенами 10 м.
В какой-то момент стены начитают сближаться со скоростью 1 м/с каждая.
Одновременно с этим от одной стены по направлению к другой вылетает мяч со скоростью 10 м/с. Какое расстояние пролетит мяч до того как стены столкнуться? Считать что отскок идеален и сила тяжести отсутствует.sasha1024
04.10.2016 18:33Интересен такой момент.
Я когда-то решал домашнее задание по математике; от скуки заглянул вперёд учёбника (места в учебнике до и после всегда интереснее именно того места, которое тебе задали); наткнулся на эту задачу (она была со звёздочкой); быстро решил в уме (удивился, почему звёздочка); почти забыл об этом (точнее, забыл решение).
Потом позже, через сколько-то недель мне уже задали эту задачу в составе домашнего задания; как не пытался, не смог решить (и вспомнить); домашние тоже помочь не смогли (точнее, не смогли решить методами, приемлемыми для моего возраста, без сумм рядов).
Вот так.WebSun
04.10.2016 19:03+2а что не так? стены сближаются со скоросью 2 м/с, значит столкнуться через 5 секунд. за 5 секунд мяч пролелит 50 метров.
sasha1024
04.10.2016 19:28+1Всё верно. Коммент о том, как у людей то включается, то выключается сообразительность.
Некоторые пытаются считать в лоб, типа:
1. Начальное расстояние между стен 10м.
При этом скорость сближения мяча и противоположной стены 10м/с+1м/с=11м/с.
Значит мяч долетит до противоположной стены за (10м) / (11м/с) = (10/11)c.
При этом он пройдёт (10/11)c*10м/с=(100/11)м.
При этом стены сближались со скоростью 1м/с+1м/с = 2м/с и соответственно прошли (10/11)c * 2м/с = (20/11)м, и соответственно расстояние между ними стало 10м-(20/11)м = (90/11)м.
2. Расстояние между стенами (90/11)м.
Значит мяч долетит до противоположной стены за (90/11)м / (11м/с) = (90/121)с и при этом пройдёт (90/121)с*10м/с = (900/121)м.
При этом стены прошли (90/121)с*2м/с = (180/121)м, и соответственно расстояние между ними стало (90/11)м-(180/121)м = (810/121)м.
3. …
Итого: (100/11)м + (900/121)м + (8100/1331)м + … = формула суммы бесконечной геометрической прогрессии = (100/11)м / (1 — 9/11) = (100/11)м / (2/11) = 50м.
Т.е. ответ тот же, но гораздо муторнее и не подходит для 2 класса :).
ukhegg
04.10.2016 23:27хм… насколько я помню из школьной физики, при абсолютно упругом ударе(так я понимаю идеальный отскок) относительная скорость стены и мяча не меняется, только направление, а значит его скорость относительно второй стены станет уже 13 м/с(относительно земли 12). После второго удара 15 м/с(земля-14), далее 17 м/с (земля 16) и т.д.(здесь указывается скорость относительно стены, о которую ударился мяч)
Прикинув на бумаге, получилось, что мяч довольно быстро наберет скорость света и… тут много вариантов развития событий) Попровьте, если неправ, зря значит золотая медаль физмата досталась
EndUser
05.10.2016 08:25Поэтому правильная задача про муху — в ней нет артефактов с изменением скоростей.
sasha1024
05.10.2016 11:20Да, Вы правы.
EndUser, я читал аналогичную про собаку (2 друга идут на встречу и собака бегает между ними).
Но я думаю, что автора этой задачи подразумевали как раз не абсолютно упругий удар, а настолько упругий, насколько необходимо для того, чтобы скорость мяча сохранилась.
(И ещё один момент: в момент удара о стену мяч должен вминаться в стену ровно на 50% своего размера, иначе путь мяча будет каждый раз меньше.)marenkov
05.10.2016 12:36Ну да, правильнее было бы написать, что скорость мяча не изменяется. И что размером мяча можно пренебречь.
marenkov
05.10.2016 14:06Прикинув на бумаге, получилось, что мяч довольно быстро наберет скорость света и… тут много вариантов развития событий
С увеличением скорости к около световой его масса начнет бесконечно увеличиваться и, если стены такое выдержат, образуется черная дыра, которая поглотит стены и улетит в бесконечность имея запредельный импульс сметая и поглощая все на своем пути. (Из инструкции «Как из шарика для пинг-понга создать Звезду Смерти»).
marenkov
05.10.2016 12:41Именно поэтому такие задачи хорошо подходят для программистов. Она из тех, которые, грубо говоря, можно решить задействовав сложные вычисления заняв половину ОЗУ и 99% процессора, а можно за 4 процессорных такта использую только регистры.
MacIn
04.10.2016 20:11Это «детское» решение задачи. Помню, в «Кванте» писали про эту особенность — что дети, не знающие сложного аппарата, быстро решают задачу (там было про поезда или автомобили и муху, которая летала между ними), а взрослые начинают прикидывать интегралы, ряды и в конце концов ошибаются.
hdfan2
05.10.2016 08:06+1Про эту задачку есть забавная байка. Её задали какому-то известному математику (кажется, фон Нейману). Тот задумался на секунду и выдал ответ. Спрашивающий разочарованно сказал:
— Я так и думал, что вы быстро догадаетесь.
— Догадаюсь до чего? — удивился математик. — Я просто просуммировал ряд.
LynXzp
05.10.2016 21:08Из занимательной математики: http://rubooks.org/book.php?book=7061&page=15 (задача шмель)
Как раз и про фон Неймана и про то что не математики решают ее быстро.
P.S. как-то оказавшись на олимпиаде по математике я не понял смысла этой задачи и написал правильный ответ сразу :) получил замечание: задача решена с точки зрения физики.
Mendel
06.10.2016 11:38В шею надо гнать таких «замечателей»)
Помню в классе втором или третьем я решил школьную задачку из домашнего задания — не тем способом что подразумевался в учебнике. Со мной это часто бывало, и учителя с этим мирились. Но тут у меня результат не сошелся с учебником. А у всего класса сошелся. Я бы может быть и сдался, если бы не характер моей бабушки, и тот факт что когда у меня ответ не сошелся я попросил перепроверить решение у деда, который был доцентом на кафедре ВОЛС. Тогда я еще не понимал что такое ВОЛС, но то что мнение деда по школьной задачке это приговор, я понимал.
Я достал всю школу, включая директора (школа была гуманитарная) и старшеклассников, которые помогали учителям понять почему же так получилось, что оба ответа правильные.
Часто задумываюсь — как бы сложилась моя жизнь, если бы учителя таки дожали бы меня, и не стали бы разбираться.
С тех пор я не понимаю когда говорят о правильном решении. Численное решение лучше с точки зрения того, что в нем сложнее ошибиться, да и нужно меньше думать. Ты решаешь, и сразу проверяешь. Аналитическое решение лучше с точки зрения производительности. Так какое решение более правильное?)vlivyur
06.10.2016 15:30У меня на вступительном в универ была задача с мутным условием. Мне повезло, одна из экзаменаторов решала тот же вариант, и предложила сверить ответы. В одной задаче ответ не сошёлся, она — почему так? я — ну потому что вот так. она — ну да, так тоже можно, но составители наверняка так не думали. тебе точно охота на апелляцию? Потому я сдался и переделал как думали составители и не пошёл на апелляцию.
Mendel
04.10.2016 18:26Решал бы задачу численно. В случае дробных расстояний/времен ввел бы «квант» времени.
Задача хорошая, но скорее для домашнего решения а не для собеса.
Время ограничено, машины часто под рукой нет, а качественное решение без отладки затруднено.
Не невозможно, но это не так важно на практике — уметь отлаживать алгоритмы на бумажке.
Хотя да, некоторый уровень умения работать в режиме «виртуальная машина в голове, виртуальная память на бумажке» нужно. Тут я погорячился.
nerudo
Скучно. Предлагаю:
Как обычно вечером пятницы Джон хорошо выпил в баре и собрался домой. От двери бара до двери дома Джона ровно L метров по прямой, однако прямолинейно двигаться он сейчас не способен. В связи с алкогольной интоксикацией он движется строго по синусоиде периодом T и амплитудой A. Посчитайте какое расстояние придется пройти Джону до дома, если принять, что на пути ему не встретися препятсвий, а отношение L к T является целым числом.
izzholtik
Учитываем ли мы, что амплитуда А может быть существенно больше ширины двери, и Джону придётся решать сложную задачу достижения двери по k отрезкам синусоиды, когда он достигнет стены своего дома?
nerudo
Мы же договорились, что L mod T = 0. Самого Джона для простоты можно считать материальной точкой.
izzholtik
Каюсь, был неправ :)
alexvoz
главное дойти до дома — а там уже по стеночке можно и в дверь попасть )
sasha1024
Ну, если отношение L к T является целым числом, то никаких загвоздок нету. В смысле, никаких corner cases, которые нужно не забыть учесть. Всё сводится к банальному длина_стандартной_синусоиды_в_периоде * A * L / (2?).
Тут скорее алгебра/геометрия проверяется (длина стандартной синусоиды в периоде). Хотя так-то да, звучит гораздо веселее.
А моей мыслью как бы было внушить новичку (ну или проверить это понимание у собеседуемого), что программирование — это во многом работа с corner cases.
sasha1024
Вру, это получается 4 H E(A/H) L/T, где H = vA???+?(?T?/?2???)??? и E(…) — полный нормальный эллиптический интеграл Лежандра 2-го рода.