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

в 11:00, , рубрики: Алгоритмы, Занимательные задачки, собеседование, улитка, школа

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 лет школы.

Автор: sasha1024

Источник

Поделиться новостью

* - обязательные к заполнению поля