โปรแกรมค้นหาสตริงที่เล็กที่สุดตามลำดับพจนานุกรมเพื่อเคลื่อนที่จากจุดเริ่มต้นไปยังจุดหมายใน Python

สมมติว่าเราอยู่ที่ตำแหน่ง (0, 0) บนระนาบคาร์ทีเซียน เราต้องการไปยังจุด (x, y) โดยใช้การเคลื่อนที่แนวนอน (H) และแนวตั้ง (V) ทีละหน่วยเดียว มีหลายวิธีในการไปถึงจุดหมาย แต่ละวิธีประกอบด้วยการเคลื่อนที่ H และ V จำนวนหนึ่ง (เช่น หากต้องการไปจาก (0,0) ไป (2,2) แล้ว HVVH เป็นหนึ่งในวิธีที่เป็นไปได้) หากมีค่า k เพิ่มเติม เราต้องหาวิธีการที่เป็นลำดับที่ k ตามลำดับพจนานุกรม

ตัวอย่าง: หากอินพุตคือ (x, y) = (3, 3) และ k = 3 ผลลัพธ์จะเป็น "HHVVVH"

ขั้นตอนการแก้ปัญหา

1. กำหนดฟังก์ชัน paths(x, y) เพื่อคำนวณจำนวนเส้นทางทั้งหมดจาก (0,0) ไป (x,y) โดยใช้สูตรจัดหมู่: factorial(x+y) / (factorial(x) * factorial(y)) หาก x หรือ y เป็นค่าติดลบ ให้คืนค่า 0
2. ในฟังก์ชันหลัก solve(x, y, k):
   • สร้างลิสต์ res เพื่อเก็บลำดับการเคลื่อนที่
   • กำหนดตัวแปร p, q = 0, 0 เป็นตำแหน่งปัจจุบัน
   • วนลูปจนกว่า (p, q) จะเท่ากับ (x, y):
     • คำนวณ n = paths(x - p - 1, y - q) (จำนวนเส้นทางหากเลือก H ต่อไป)
     • หาก p + 1 <= x และ k < n ให้เพิ่ม 'H' ลงใน res และเพิ่ม p ขึ้น 1
     • มิฉะนั้น ให้ลบ n ออกจาก k เพิ่ม 'V' ลงใน res และเพิ่ม q ขึ้น 1
   • คืนค่าสตริงจากการรวมสมาชิกใน res

ตัวอย่างโค้ด Python

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))  # ผลลัพธ์: HHVVVH

อินพุตตัวอย่าง

(3, 3), 3

เอาต์พุตตัวอย่าง

HHVVVH