Skip to content

Latest commit

 

History

History
71 lines (45 loc) · 1.61 KB

3.1 FrogJmp.md

File metadata and controls

71 lines (45 loc) · 1.61 KB
Raw

Lesson_3 Time Complexity 时间复杂度

P3.1 FrogJump

Count minimal number of jumps from position X to Y.

  • P3.1 青蛙跳

从位置X跳到位置Y的最少次数

一只小青蛙想跳到路的另一边。青蛙目前位于位置X，想要到达大于或等于Y的位置。小青蛙每次总是跳跃一个固定的距离D。

计算小青蛙为了达到目标需要的最少跳跃次数。

编写函数：

def solution(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处

假定：

  1. X、Y和D是[1，100000000]内的整数；
  2. X小于Y；

  • 解题思路

    简单的数学除法计算。

  • Python3代码

# -*- coding：utf-8 -*-
# &Author  AnFany
# Lesson 3：Time Complexity
# P 3.1 FrogJump


def solution(X, Y, D):
    """
    每次跳跃D，从位置X到位置Y的最少的跳跃次数
    :param X: 起始位置
    :param Y: 目标位置
    :param D: 每次跳跃的距离
    :return: 最少次数
    """
    length = Y - X
    float_times = length / D
    int_times = int(float_times)
    if float_times > int_times:
        return int_times + 1
    else:
        return int_times

  • 结果

image