python - 如何找到从 1 到达 A 的最小合法跳跃次数?

标签 python python-3.x algorithm

我在制定算法来解决这个问题时遇到了麻烦。怎么做到呢?

给定一个整数 A 表示目标位置。 Jack 最初站在位置 1。在任何时候,如果 Jack 在位置 X,那么他可以一步:

  • 移动到 2 *X 位置。
  • 移动到 3 *X 位置。
  • 移动到 4 *X 位置。
  • 移动到 5 *X 位置。

  • 帮助 jack (和我😭)找到到达目的地位置的最少步数。

    如果使用任意数量的移动都无法到达目标位置,则返回 -1。

    我的尝试

    def solve(A):
        currentpos=1
        jump=5
        Jno=0
        while currentpos<A:
            currentpos=currentpos*jump
            Jno+=1
            if currentpos==A:
                break
            elif currentpos>A:
                if jump==2:
                    break
                else:
                    jump-=1
            else:
                continue
        return Jno
    

    最佳答案

    已经发布了很多好的答案。无论如何,您可以尝试动态编程方法。该范例侧重于保存较小子问题的答案以供以后使用。我附上了一个示例代码:

    A = 100
    infinity = 2**32
    dp = [infinity]*(A+1)
    dp[1] = 0
    for i in range(2, A+1):
        if i%5 == 0:
            dp[i] = min(dp[int(i/5)]+1, dp[i])
        if i%4 == 0:
            dp[i] = min(dp[int(i/4)]+1, dp[i])
        if i%3 == 0:
            dp[i] = min(dp[int(i/3)]+1, dp[i])
        if i%2 == 0:
            dp[i] = min(dp[int(i/2)]+1, dp[i])
    
    print(dp[A])
    

    解释 :A是目的地——对于这个例子,我刚刚将它设置为 100。

    我创建了一个名为 infinity 的 int =2^32 我将用它填充数组dp .我认为这个问题不会让您找到大于 infinity 的目的地。 .
    dp[i]将存储到达 i 所需的步数.因此,dp[1]设置为 0,因为它是我们的初始位置。

    我将大小设为 dp成为 A+1这样dp将包含从 0...A 的索引。 (从 0 开始计数)

    现在我们迭代 i从 2 到 A .在每一步,我们检查是否 i可被 2、3、4 或 5 整除。如果是,我们查看 dpi除以其中一个数字:
        if i%5 == 0:
            dp[i] = min(dp[int(i/5)]+1, dp[i])
        if i%4 == 0:
            dp[i] = min(dp[int(i/4)]+1, dp[i])
        if i%3 == 0:
            dp[i] = min(dp[int(i/3)]+1, dp[i])
        if i%2 == 0:
            dp[i] = min(dp[int(i/2)]+1, dp[i])
    

    在每一步,为了找到达到i的最小步数,我们检查是否保留了 dp[i] 的原始值或将其替换为以前的值 dp+1因为需要一步才能到达i从以前的值。

    示例:dp[1] = 0 .假设我们现在在 i=5 . i能被 5 整除。i/5=1 .目前,dp[5]=infinity .但是如果我们从 1 到 5 一步(这是合法的),我们将总共采取 dp[1]+1=1步。 1 小于 infinity .因此我们替换dp[5]与 1。

    这一直持续到我们迭代到 i=A .现在,dp[A]将保持到达 A 的最小步数.如果我们无法访问 A , dp[A]将等于 infinity .

    该算法的运行时间是线性的,O(N)。

    抱歉解释冗长,如果有人愿意,我可以编辑。

    关于python - 如何找到从 1 到达 A 的最小合法跳跃次数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/57240753/

    相关文章:

    python - FFT没有返回正确的幅度

    python - Python使用'ascii'编解码器进行解码,而应该使用'UTF-8'

    python-3.x - Python3 asyncio "Task was destroyed but it is pending"具有某些特定条件

    python-3.x - 如何在 OpenCV 中获取 VideoCapture 对象的 4 字符编解码器代码?

    c++ - 制表哈希和 N3980

    algorithm - 在 O(V + E) 中验证 Dijkstras 算法

    algorithm - 算法:如何找到最接近的元素,具有坐标和尺寸

    python - 使用Python将照片或视频上传到Facebook

    python - 简单的正则表达式从字符串获取Twitter用户名

    python - Tensorflow:导入错误:libcudnn.so.7:无法打开共享对象文件:没有这样的文件或目录