Chương trình tìm chuỗi nhỏ nhất về mặt từ vựng để di chuyển từ đầu đến đích bằng Python

Giả sử chúng ta đang ở vị trí (0, 0) trong mặt phẳng Descartes. Chúng ta muốn đi đến điểm (x, y) chỉ sử dụng các bước di chuyển ngang (H) và dọc (V) của một đơn vị. Có nhiều cách có thể để đến đích. Mỗi cách bao gồm một vài lần di chuyển H và một vài bước di chuyển V. (Ví dụ, nếu chúng ta muốn đi đến điểm (2,2) từ điểm (0,0), thì HVVH là một trong những cách khả thi.) Nếu chúng ta có một giá trị k khác, chúng ta phải tìm cách nhỏ nhất về mặt từ vựng thứ k của đi đến đích.

Vì vậy, nếu đầu vào là (x, y) =(3, 3) k =3, thì đầu ra sẽ là "HHVVVH"

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

• Xác định một đường dẫn hàm (). Điều này sẽ mất x, y
• nếu min (x, y) <0, thì
  • trả về 0
• trả về giai thừa (x + y) / giai thừa (x) / giai thừa (y)
• Từ phương pháp chính, hãy thực hiện như sau -
• res:=một danh sách mới
• (p, q):=(0, 0)
• while (p, q) không giống với (x, y), do
  • n:=đường dẫn (x - p - 1, y - q)
  • nếu p + 1 <=x và k
  • chèn 'H' vào cuối res
  • p:=p + 1
• nếu không,
  • k:=k - n
  • chèn 'V' vào cuối res
  • q:=q + 1

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

Đầu vào

(3, 3), 3

Đầu ra

HHVVVH