Computer >> Máy Tính >  >> Lập trình >> Python

Chương trình tìm các bước nhảy tối thiểu để về đến nhà bằng Python

Giả sử có một mảng được gọi là bị cấm, trong đó cấm [i] chỉ ra rằng lỗi không thể nhảy đến vị trí bị cấm [i], và chúng ta cũng có ba giá trị a, b và x. Nhà của một con bọ ở vị trí x trên trục số. Ban đầu nó ở vị trí 0. nó có thể nhảy theo các quy tắc -

  • Con bọ có thể nhảy chính xác một vị trí sang bên phải.

  • Con bọ có thể nhảy chính xác b vị trí sang trái.

  • Lỗi không thể nhảy lùi hai lần liên tiếp.

  • Lỗi không thể nhảy đến bất kỳ vị trí bị cấm nào được cung cấp trong mảng.

  • Con bọ có thể nhảy về phía trước ra khỏi nhà của nó, nhưng nó không thể nhảy đến các vị trí được đánh số bằng các giá trị âm.

Chúng ta phải tìm số lần nhảy tối thiểu cần thiết để con bọ có thể đến đích. Nếu không có trình tự nào có thể xảy ra như vậy, hãy trả về -1.

Vì vậy, nếu đầu vào giống như bị cấm =[2,3,7,9, 12], a =4, b =2, x =16, thì đầu ra sẽ là 7 vì, bắt đầu từ 0, nhảy a =4 về phía trước hai lần để đạt 4 và 8, nhưng không thể nhảy đến 12 vì điều này bị cấm, sau đó lùi lại b =2 tại 6, sau đó nhảy đến 10, 14, 18 và sau đó quay lại hai để đạt 16, như vậy có 7 bước.

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

  • queue:=một hàng đợi với một tuple (x, 0, True), Cấm:=một tập hợp mới và chèn các phần tử từ danh sách bị cấm

  • lim:=a + b + (giá trị lớn nhất của x và giá trị lớn nhất của tập bị cấm)

  • trong khi hàng đợi không trống, hãy làm

    • (curr, jumps, is_b):=phần tử đầu tiên từ hàng đợi và xóa nó khỏi hàng đợi

    • nếu curr bị cấm hoặc (0 <=curr <=lim) là false, thì

      • chuyển sang lần lặp tiếp theo

    • chèn lề đường vào cấm

    • nếu curr giống 0 thì

      • các bước nhảy trở lại

    • nếu is_b là true, thì

      • insert (curr + b, jumps + 1, False) vào hàng đợi

    • insert (curr-a, jumps + 1, True) vào hàng đợi

  • trả về -1

Ví dụ

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

def solve(forbidden, a, b, x):
   queue, forbidden = [(x,0,True)], set(forbidden)
   lim = max(max(forbidden),x)+a+b
   while queue:
      curr,jumps,is_b = queue.pop(0)
      if curr in forbidden or not 0 <= curr <= lim:
         continue
      forbidden.add(curr)
      if curr==0:
         return jumps
      if is_b:
         queue.append((curr+b,jumps+1,False))
      queue.append((curr-a,jumps+1,True))
   return -1

forbidden = [2,3,7,9, 12]
a = 4
b = 2
x = 16
print(solve(forbidden, a, b, x))

Đầu vào 

[2,3,7,9, 12], 4, 2, 16

Đầu ra 

7