找出在Python中到达终点的移动次数的程序

假设我们有一辆汽车,正在一维道路上行驶。当前,我们处于位置= 0且速度=1。我们可以执行这两个操作中的任何一个。

  • 加速度:位置:=位置+速度和速度:=速度* 2倒档:速度:= -1(当速度> 0时,否则速度:= 1)。

我们必须找到至少达到目标所需的移动次数。

因此,如果输入类似于target = 10,则输出将为7。

为了解决这个问题,我们将遵循以下步骤-

  • 定义一个功能dfs()。这需要数字,费用,排名,否定目标

    • 返回

    • ans:= ans和tot的最小值

    • 返回

    • 返回

    • tot:=成本+最大值2 *(pos − 1)和2 *(neg − 1)

    • 如果tot> = ans,则

    • 如果目标等于0,则

    • 步骤:=(2 ^ digit)− 1

    • 如果步骤* 2 <| target |,则

    • dfs(数字-1,费用,排名,否定目标)

    • dfs(数字− 1,成本+数字,pos + 1,负数,目标-步骤)

    • dfs(数字-1,费用+数字* 2,pos + 2,负数,目标-步骤* 2)

    • dfs(数字− 1,成本+数字,pos,负+ 1,目标+步长)

    • dfs(数字− 1,成本+数字* 2,pos,负+ 2,目标+步数* 2)

    • 在主要功能中,执行以下操作-

    • ans:=无限

    • 嗨:= 1

    • 而2 ^ hi <目标,做

      • 嗨:=嗨+ 1

    • dfs(hi,0,0,0,目标)

    • 返回ans

    让我们看下面的实现以更好地理解-

    示例

    class Solution:
       def solve(self, target):
          self.ans = int(1e9)
          hi = 1
          while (1 << hi) < target:
             hi += 1
          self.dfs(hi, 0, 0, 0, target)
          return self.ans
       def dfs(self, digit, cost, pos, neg, target):
          tot = cost + max(2 * (pos − 1), 2 * neg − 1)
          if tot >= self.ans:
             return
          if target == 0:
             self.ans = min(self.ans, tot)
             return
          step = (1 << digit) − 1
          if step * 2 < abs(target):
             return
          self.dfs(digit − 1, cost, pos, neg, target)
          self.dfs(digit − 1, cost + digit, pos + 1, neg, target − step)
          self.dfs(digit − 1, cost + digit * 2, pos + 2, neg, target − step * 2)
          self.dfs(digit − 1, cost + digit, pos, neg + 1, target + step)
          self.dfs(digit − 1, cost + digit * 2, pos, neg + 2, target + step * 2)
    ob = Solution()
    print(ob.solve(10))

    输入值

    10
    输出结果
    7