Chương trình tìm số bước tối ưu cần thiết để đến đích bằng các bước nhỏ và bước khổng lồ bằng Python

Giả sử chúng ta có một danh sách các truy vấn Q, trong đó mỗi truy vấn Q [i] chứa một bộ ba [a_i, b_i và d_i]. Coi ban đầu chúng ta đang ở vị trí (0, 0), sau đó trong một bước chúng ta có thể chuyển từ vị trí (x1, y1) nào đó đến (x2, y2) trong đó khoảng cách Euclide giữa hai điểm này ít nhất là a và nhiều nhất là b. Bây giờ đối với mỗi truy vấn, chúng tôi phải tìm số bước tối thiểu cần thiết để đạt được (d_i, 0) từ (0, 0).

Vì vậy, nếu đầu vào giống như Q =[(2,3,1), (1,2,0), (3,4,11)], thì đầu ra sẽ là [2, 0, 3] vì đối với truy vấn đầu tiên từ (0, 0) với a =2, chúng ta có thể chuyển sang $ \ left (\ frac {1} {2}, \ frac {\ sqrt {15}} {2} \ right) $ rồi đến (1, 0) vì vậy chúng ta cần hai bước, do đó đầu ra là 2, đối với truy vấn tiếp theo d là 0, vì vậy chúng ta không cần di chuyển bất kỳ bước nào nên đầu ra là 0. Và đối với bước thứ ba, b =4 và a =3 di chuyển (0, 0 ) đến (4, 0) rồi đến (8, 0) rồi đến (11, 0).

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định các bước hàm (). Điều này sẽ mất a, b, d
• mmin:=tối thiểu a, b
• mmax:=tối đa là a, b
• nếu d là 0, thì
  • trả về 0
• nếu d là mmin hoặc mmax, thì
  • trả lại 1
• nếu d
• trả về 2

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

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

Đầu ra

[2, 0, 2.0]