Задача про улитку

image В этом топике я предлагаю 3 довольно базовые задачи на сообразительность. Для начинающих программистов (вероятно, для совсем начинающих, а-ля школа, потому что для настоящего программиста слишком банально). Или, возможно, для собеседования, но для проверки конкретно одного узкого аспекта: насколько человек может вообще принимать решения самостоятельно, а не передирать и подправлять под себя.

База


В качестве базы выбрана довольно известная задача про улитку для младших классов школы. «Улитка ползёт вверх по столбу высотой 5 метров. Каждый день она проползает вверх на 3 метра, а каждую ночь съезжает вниз на 2 метра. За сколько дней она доползёт до вершины столба.»

Как известно, многие школьники срезаются на том, что просто делят 5 на (3−2) и получают 5 дней, не учитывая того, что в конце третьего дня улитка уже́ достигла вершины.

Для педантов
Весь процесс начинается строго в начале светлой части суток, когда улитка может ползти вверх (а не посреди дня). Сверху столба горизонтальная площадка, достигнув которой улитка уже не съезжает вниз. Затраты времени по перемещению с вертикальной части поверхности столба на финальную горизонтальную считаем нулевыми.

Задача 1


Вводятся действительные¹ неотрицательные числа: сколько проползает за день вверх; сколько съезжает за ночь вниз; высота столба. Должен вывестись ответ — минимальное необходимое целое число суток.

Классическое решение
  1. Если высота столба 0 — возвращаем 0.
  2. Если дневной пробег 0 — возвращаем бесконечность/никогда².
  3. Вычисляем разность высоты столба и дневного пробега (РВСДП); если она неположительна — возвращаем 1.
  4. Вычисляем пробег за целые сутки (ПЗЦС); если он неположителен — возвращаем бесконечность/никогда².
  5. Возвращаем 1 + ceil(РВСДП / ПЗЦС).

¹ Под действительными я имел в виду с плавающей точкой. Можно взять и целые. Суть в том, что в общем случае разность высоты столба и дневного пробега может быть не кратна пробегу за целые сутки.
² Эти варианты, так и быть, можно простить (или задать в условии, что так не будет).


Суть в том, чтобы решающий обработал хотя бы: (1) классический случай (вершина достигается не в первый день, но ровно к концу какого-то из дней); (2) некратную длину (вершина достигается не в первый день и не ровно к концу какого-то дня); (3) короткую длину (вершина достигается ещё до конца первого дня).

Задача 2


То же самое. Только вернуть уже нужно не минимальное необходимое целое число суток, а «время» относительно длины суток (возможно нецелое число). Предполагается, что каждый день и ночь длится ровно по 0.5 (и процесс начинается ровно в начале дня). А улитка и днём, и ночью двигается с постоянной скоростью.

Задача 3


То же самое. Только процесс начинается в произвольное время, а не ровно в начале дня. Пользователь вводит произвольное действительное число — «время» начала процесса. Ответ — произвольное действительное число — «время» конца процесса.

Inspired by
Очуменными задачами по физике, которые когда-то показал потрясающий препод на ФДП.

Задача 1
Вася с силой 100 H тянет за ручку динамометра, вторая ручка которого нерастяжимой верёвкой привязана к неподвижной стене.
Вопрос: Какую силу покажет динамометр?

Задача 2
Вася и Федя, каждый с силой по 100 H, тянут за противоположные ручки динамометра.
Вопрос: Какую силу покажет динамометр?

Задача 3
Вася тянет за ручку динамометра с силой 80 Н, а Федя, будучи послабее, тянет за противоположную ручку с силой 70 Н.
Вопрос: Какую силу покажет динамометр?

Скрытый текст
Вроде бы банально, но многие даже студенты срезаются уже́ на второй задаче. Особенно именно если в таком порядке (первая — success, вторая — фейл, третья — о_О). И понимание этих задач позволяет глубже понять базовые принципы, которые студент мог прощёлкать за все N лет школы.

Similar posts

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 42

    +11
    Скучно. Предлагаю:
    Как обычно вечером пятницы Джон хорошо выпил в баре и собрался домой. От двери бара до двери дома Джона ровно L метров по прямой, однако прямолинейно двигаться он сейчас не способен. В связи с алкогольной интоксикацией он движется строго по синусоиде периодом T и амплитудой A. Посчитайте какое расстояние придется пройти Джону до дома, если принять, что на пути ему не встретися препятсвий, а отношение L к T является целым числом.
    • UFO just landed and posted this here
        0
        Мы же договорились, что L mod T = 0. Самого Джона для простоты можно считать материальной точкой.
        • UFO just landed and posted this here
          0
          главное дойти до дома — а там уже по стеночке можно и в дверь попасть )
          0
          Ну, если отношение L к T является целым числом, то никаких загвоздок нету. В смысле, никаких corner cases, которые нужно не забыть учесть. Всё сводится к банальному длина_стандартной_синусоиды_в_периоде * A * L / (2π).

          Тут скорее алгебра/геометрия проверяется (длина стандартной синусоиды в периоде). Хотя так-то да, звучит гораздо веселее.

          А моей мыслью как бы было внушить новичку (ну или проверить это понимание у собеседуемого), что программирование — это во многом работа с corner cases.
            –1
            Вру, это получается 4 H E(A/H) L/T, где H = √A̅²̅+̅(̅T̅/̅2̅π̅)̅²̅ и E(…) — полный нормальный эллиптический интеграл Лежандра 2-го рода.
          +3
          По сложности — уровень внутришкольной олимпиады. По интересности — уровень сферического учебника в вакууме.
            0
            в классическом решении задачи 1, в пункте 5, вы даёте неверный ответ.
            Заголовок спойлера
            нужно ещё добавить единицу
              –1
              Вы правы.
              +1
              Вот отличная задачка про улиток:

              Ползут три улитки.
              Улитки ползут в одном направлении и по одной прямой.
              Первая говорит:
              — Впереди меня одна улитка и сзади одна.
              Вторая говорит:
              — Я ползу впереди, и две улитки позади.
              Третья говорит:
              — Впереди меня одна улитка и сзади одна.

              Вопрос: Как такое может быть?

              Ответ
              Какая-то улитка 3,14здитврёт.
                +2

                Улитки находятся на одной прямой и ползут боком.

                  +1
                  Пока вторая отвечала, третья переползла через первую.
                    0
                    Лучший ответ, кстати, по-моему.
                    0
                    Они в нееклидовом пространстве.
                      0
                      Третья улитка сидит на первой (и она не ползет, что не противоречит условию), а сзади ползет четвертая.
                      +3
                      Они ползут по кольцу и автор задачи врет, что они ползут по прямой
                        0
                        Или они ползут «по прямой» на неплоской поверхности (сфера, циллиндр и т.п.). Конечно, это не совсем прямая, но идя «прямо» по Земле, Вы ж не говорите «я иду по дуге». То, что они видят именно так (1-я и 3-я видят по штуке спереди и сзади, а 2-я — двух сзади), обеспечивается рельефом поверхности (не идеальная сфера/циллиндр/т.п.) и тем, что они дают отчёт в разное время.
                          0
                          Не исключено.
                          +1
                          Старая школьная задачка на сообразительность:
                          Расстояние между двумя параллельными стенами 10 м.
                          В какой-то момент стены начитают сближаться со скоростью 1 м/с каждая.
                          Одновременно с этим от одной стены по направлению к другой вылетает мяч со скоростью 10 м/с. Какое расстояние пролетит мяч до того как стены столкнуться? Считать что отскок идеален и сила тяжести отсутствует.
                            0
                            Интересен такой момент.
                            Я когда-то решал домашнее задание по математике; от скуки заглянул вперёд учёбника (места в учебнике до и после всегда интереснее именно того места, которое тебе задали); наткнулся на эту задачу (она была со звёздочкой); быстро решил в уме (удивился, почему звёздочка); почти забыл об этом (точнее, забыл решение).
                            Потом позже, через сколько-то недель мне уже задали эту задачу в составе домашнего задания; как не пытался, не смог решить (и вспомнить); домашние тоже помочь не смогли (точнее, не смогли решить методами, приемлемыми для моего возраста, без сумм рядов).
                            Вот так.
                              +2
                              а что не так? стены сближаются со скоросью 2 м/с, значит столкнуться через 5 секунд. за 5 секунд мяч пролелит 50 метров.
                                +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 класса :).
                                  0
                                  хм… насколько я помню из школьной физики, при абсолютно упругом ударе(так я понимаю идеальный отскок) относительная скорость стены и мяча не меняется, только направление, а значит его скорость относительно второй стены станет уже 13 м/с(относительно земли 12). После второго удара 15 м/с(земля-14), далее 17 м/с (земля 16) и т.д.(здесь указывается скорость относительно стены, о которую ударился мяч)
                                  Прикинув на бумаге, получилось, что мяч довольно быстро наберет скорость света и… тут много вариантов развития событий) Попровьте, если неправ, зря значит золотая медаль физмата досталась
                                    0
                                    Поэтому правильная задача про муху — в ней нет артефактов с изменением скоростей.
                                      0
                                      Да, Вы правы.
                                      EndUser, я читал аналогичную про собаку (2 друга идут на встречу и собака бегает между ними).
                                      Но я думаю, что автора этой задачи подразумевали как раз не абсолютно упругий удар, а настолько упругий, насколько необходимо для того, чтобы скорость мяча сохранилась.
                                      (И ещё один момент: в момент удара о стену мяч должен вминаться в стену ровно на 50% своего размера, иначе путь мяча будет каждый раз меньше.)
                                        0
                                        Ну да, правильнее было бы написать, что скорость мяча не изменяется. И что размером мяча можно пренебречь.
                                        0
                                        Прикинув на бумаге, получилось, что мяч довольно быстро наберет скорость света и… тут много вариантов развития событий

                                        С увеличением скорости к около световой его масса начнет бесконечно увеличиваться и, если стены такое выдержат, образуется черная дыра, которая поглотит стены и улетит в бесконечность имея запредельный импульс сметая и поглощая все на своем пути. (Из инструкции «Как из шарика для пинг-понга создать Звезду Смерти»).
                                        0
                                        Именно поэтому такие задачи хорошо подходят для программистов. Она из тех, которые, грубо говоря, можно решить задействовав сложные вычисления заняв половину ОЗУ и 99% процессора, а можно за 4 процессорных такта использую только регистры.
                                        0
                                        Это «детское» решение задачи. Помню, в «Кванте» писали про эту особенность — что дети, не знающие сложного аппарата, быстро решают задачу (там было про поезда или автомобили и муху, которая летала между ними), а взрослые начинают прикидывать интегралы, ряды и в конце концов ошибаются.
                                          +1
                                          Про эту задачку есть забавная байка. Её задали какому-то известному математику (кажется, фон Нейману). Тот задумался на секунду и выдал ответ. Спрашивающий разочарованно сказал:
                                          — Я так и думал, что вы быстро догадаетесь.
                                          — Догадаюсь до чего? — удивился математик. — Я просто просуммировал ряд.
                                            0
                                            Из занимательной математики: http://rubooks.org/book.php?book=7061&page=15 (задача шмель)
                                            Как раз и про фон Неймана и про то что не математики решают ее быстро.
                                            P.S. как-то оказавшись на олимпиаде по математике я не понял смысла этой задачи и написал правильный ответ сразу :) получил замечание: задача решена с точки зрения физики.
                                              0
                                              В шею надо гнать таких «замечателей»)
                                              Помню в классе втором или третьем я решил школьную задачку из домашнего задания — не тем способом что подразумевался в учебнике. Со мной это часто бывало, и учителя с этим мирились. Но тут у меня результат не сошелся с учебником. А у всего класса сошелся. Я бы может быть и сдался, если бы не характер моей бабушки, и тот факт что когда у меня ответ не сошелся я попросил перепроверить решение у деда, который был доцентом на кафедре ВОЛС. Тогда я еще не понимал что такое ВОЛС, но то что мнение деда по школьной задачке это приговор, я понимал.
                                              Я достал всю школу, включая директора (школа была гуманитарная) и старшеклассников, которые помогали учителям понять почему же так получилось, что оба ответа правильные.
                                              Часто задумываюсь — как бы сложилась моя жизнь, если бы учителя таки дожали бы меня, и не стали бы разбираться.

                                              С тех пор я не понимаю когда говорят о правильном решении. Численное решение лучше с точки зрения того, что в нем сложнее ошибиться, да и нужно меньше думать. Ты решаешь, и сразу проверяешь. Аналитическое решение лучше с точки зрения производительности. Так какое решение более правильное?)
                                                0
                                                А что такое ВОЛС?
                                                И можна саму задачу?
                                                  0
                                                  Задачу к сожалению не помню.
                                                  ВОЛС — Волоконно-оптическая линия связи. И да, именно так называлась кафедра. И у нас в академии, в другом ВУЗе, уже в этом веке был предмет который тоже назывался ВОЛС. Спасибо за вопрос, загуглил, и узнал что оказывается это неканоническое, хоть и распространенное название, а правильно ВОЛП.
                                                  0
                                                  У меня на вступительном в универ была задача с мутным условием. Мне повезло, одна из экзаменаторов решала тот же вариант, и предложила сверить ответы. В одной задаче ответ не сошёлся, она — почему так? я — ну потому что вот так. она — ну да, так тоже можно, но составители наверняка так не думали. тебе точно охота на апелляцию? Потому я сдался и переделал как думали составители и не пошёл на апелляцию.
                                        0
                                        Решал бы задачу численно. В случае дробных расстояний/времен ввел бы «квант» времени.
                                        Задача хорошая, но скорее для домашнего решения а не для собеса.
                                        Время ограничено, машины часто под рукой нет, а качественное решение без отладки затруднено.
                                        Не невозможно, но это не так важно на практике — уметь отлаживать алгоритмы на бумажке.
                                        Хотя да, некоторый уровень умения работать в режиме «виртуальная машина в голове, виртуальная память на бумажке» нужно. Тут я погорячился.
                                          –1
                                          Вы сейчас про улитку?
                                          Или про другие задачи (в комментах постят).
                                          –1
                                          я один начал через интегралы решать? xD
                                            0
                                            Что именно?
                                              0
                                              если бы я говорил про задачу в комментариях, то там бы и написал.
                                                0
                                                Т.е. интеграл кусочно-постоянной функции (днем +v₁, ночью −v₂)?

                                                Некоторые иногда отвечают на комментарий в корень (#comment_9841536), что поделать.

                                          Only users with full accounts can post comments. Log in, please.