В этом посте рассматривается решение для урока 3 с уменьшением временной сложности. Чтобы получить доступ к проблеме, нажмите следующую ссылку.
Описание задания
Маленькая лягушка хочет перебраться на другую сторону дороги. Лягушка в данный момент находится в позиции X и хочет попасть в позицию, большую или равную Y. Маленькая лягушка всегда прыгает на фиксированное расстояние D.
Подсчитайте минимальное количество прыжков, которое должна совершить маленькая лягушка, чтобы достичь своей цели.
Напишите функцию:
решение по определению (X, Y, D)
что, учитывая три целых числа X, Y и D, возвращает минимальное количество прыжков из позиции X в позицию, равную или большую, чем Y.
Например, учитывая:
X = 10
Y = 85
D = 30
функция должна вернуть 3, потому что лягушка будет располагаться следующим образом:
- после первого прыжка, в позиции 10+30=40
- после второго прыжка, в позиции 10 + 30 + 30 = 70
- после третьего прыжка, в позиции 10 + 30 + 30 + 30 = 100
Напишите эффективный алгоритм для следующих предположений:
- X, Y и D — целые числа в диапазоне [1..1 000 000 000];
- X ≤ Y.
Авторские права, 2009–2020 гг., принадлежат Codility Limited. Все права защищены. Несанкционированное копирование, публикация или разглашение запрещено.
Ключевой момент
- Когда вход X равен или больше Y, вычисление количества переходов не требуется. Просто верните 0.
- Если нет, то нужное количество переходов можно просто подсчитать и через цикл while или for, но это неэффективно.
Решение (с использованием Python)
def solution(X, Y, D):
if(X >= Y): return 0
else: return (Y - X) // D + int((Y - X) % D > 0)
Используйте приведенное выше решение для справки.
Я рекомендую вам написать собственный исходный код.
