โปรแกรมค้นหาจำนวนก้าวที่เหมาะสมที่สุดที่จำเป็นในการไปถึงจุดหมายโดยทารกและก้าวยักษ์ใน Python

สมมติว่าเรามีรายการข้อความค้นหา Q โดยที่แต่ละข้อความค้นหา Q[i] มี triplet [a_i, b_i และ d_i] พิจารณาว่าเราอยู่ที่ตำแหน่ง (0, 0) ในขั้นต้น จากนั้นในขั้นตอนเดียวเราสามารถย้ายจากตำแหน่งใดตำแหน่งหนึ่ง (x1, y1) ไปยัง (x2, y2) โดยที่ระยะห่างแบบยุคลิดระหว่างจุดสองจุดนี้คืออย่างน้อย a และมากที่สุด b ตอนนี้สำหรับคำค้นหาแต่ละรายการ เราต้องหาจำนวนขั้นตอนขั้นต่ำที่จำเป็นในการเข้าถึง (d_i, 0) จาก (0, 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
• คืน 2

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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]