找出在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