สมมติว่าเราอยู่ที่ตำแหน่ง (0, 0) ในระนาบคาร์ทีเซียน เราต้องการไปยังจุด (x, y) โดยใช้การเคลื่อนไหวในแนวนอน (H) และแนวตั้ง (V) ของหน่วยเดียวเท่านั้น มีหลายวิธีที่จะไปถึงจุดหมายได้ แต่ละวิธีประกอบด้วยท่า H ไม่กี่ท่าและท่า V ไม่กี่ท่า (ตัวอย่างเช่น หากเราต้องการไปที่จุด (2,2) จากจุด (0,0) ดังนั้น HVVH ก็เป็นหนึ่งในวิธีที่เป็นไปได้) หากเรามีค่าอื่น k เราจะต้องหาค่า kth ที่เล็กที่สุดของ lexicographically ไปสู่ที่หมาย
ดังนั้น หากอินพุตเป็นแบบ (x, y) =(3, 3) k =3 เอาต์พุตจะเป็น "HHVVVH"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน path() นี่จะใช้เวลา x, y
- ถ้า min(x, y) <0 แล้ว
- คืน 0
- คืนค่า factorial(x+y)/factorial(x)/factorial(y)
- จากวิธีหลัก ให้ทำดังนี้ -
- res :=รายการใหม่
- (p, q) :=(0, 0)
- ในขณะที่ (p, q) ไม่เหมือนกับ (x, y) do
- n :=เส้นทาง(x - p - 1, y - q)
- ถ้า p + 1 <=x และ k
- ใส่ 'H' ต่อท้าย res
- p :=p + 1
- มิฉะนั้น
- k :=k - n
- ใส่ 'V' ต่อท้าย res
- q :=q + 1
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
from math import factorial
def paths(x, y):
if min(x, y) < 0:
return 0
return factorial(x+y) / factorial(x) / factorial(y)
def solve(x, y, k):
res = []
p, q = 0, 0
while (p, q) != (x, y):
n = paths(x - p - 1, y - q)
if p + 1 <= x and k < n:
res.append('H')
p += 1
else:
k -= n
res.append('V')
q += 1
return ''.join(res)
(x, y) = (3, 3)
k = 3
print(solve(x, y, k)) อินพุต
(3, 3), 3
ผลลัพธ์
HHVVVH
