Python程式：計算嬰兒步和巨人步到達目的地的最優步數

假設我們有一系列查詢Q，每個查詢Q[i]包含一個三元組[a_i, b_i和d_i]。考慮我們最初位於(0, 0)位置，那麼一步內我們可以從某個位置(x1, y1)移動到(x2, y2)，這兩個點之間的歐幾里得距離至少為a，最多為b。現在對於每個查詢，我們必須找到從(0, 0)到達(d_i, 0)所需的最小步數。

因此，如果輸入類似於Q = [(2,3,1), (1,2,0), (3,4,11)]，則輸出將為[2, 0, 3]，因為對於第一個查詢，從(0, 0)出發，a = 2，我們可以先移動到$\left(\frac{1}{2},\frac{\sqrt{15}}{2}\right)$，然後到(1, 0)，所以我們需要兩步，因此輸出為2；對於下一個查詢，d為0，所以我們不需要移動任何步，因此輸出為0；對於第三個查詢，b = 4，a = 3，從(0, 0)移動到(4, 0)，然後到(8, 0)，最後到(11, 0)。

為了解決這個問題，我們將遵循以下步驟：

• 定義一個函式steps()。它將接收a、b、d作為引數。
• mmin := a和b的最小值
• mmax := a和b的最大值
• 如果d為0，則
  • 返回0
• 如果d等於mmin或mmax，則
  • 返回1
• 如果d < mmax，則
  • 返回2
• 返回(d / mmax)的上取整
• 在主方法中，執行以下操作：
• res := 新建一個列表
• 對Q中的每個q執行以下操作：
  • (a, b, d) := q
  • 將steps(a, b, d)的結果插入到res的末尾
• 返回res

示例

讓我們看下面的實現，以便更好地理解：

from math import ceil

def steps(a, b, d):
   mmin = min(a, b)
   mmax = max(a, b)
   if d is 0:
      return 0
   if d in [mmin, mmax]:
      return 1
   if d < mmax:
      return 2
   return ceil(d / mmax)

def solve(Q):
   res = []
   for q in Q:
      a, b, d = q
      res.append(steps(a, b, d))
   return res

Q = [(2,3,1), (1,2,0), (3,4,11)]
print(solve(Q))

輸入

[(2,3,1), (1,2,0), (3,4,11)]

輸出

[2, 0, 2.0]

作者：Arnab Chakraborty

更新於：2021年10月11日

瀏覽量：319

開啟你的職業生涯

完成課程獲得認證

開始學習