Chương trình tạo chuỗi hợp lệ lớn nhất về mặt từ vựng trong Python

Giả sử chúng ta có một số n, chúng ta phải tìm một dãy số thỏa mãn tất cả các quy tắc sau -

• 1 xảy ra một lần trong chuỗi.

• Mỗi số từ 2 đến n xảy ra hai lần trong dãy.

• Với mọi i trong phạm vi từ 2 đến n, khoảng cách giữa hai lần xuất hiện của i chính xác là i.

Khoảng cách giữa hai số trên dãy, a [i] và a [j], là | j - i |. Chúng ta phải tìm ra chuỗi lớn nhất về mặt kỹ thuật.

Vì vậy, nếu đầu vào là n =4, thì đầu ra sẽ là [4, 2, 3, 2, 4, 3, 1]

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

• Xác định hàm backtrack (). Điều này sẽ mất elems, res, start:=0
• nếu kích thước của elems <=0, thì
  • trả về True
• if start> =size of res, then
  • trả về Sai
• nếu res [start] không giống -1, thì
  • trả lại nhạc nền (elems, res, start + 1)
• đối với tôi trong phạm vi từ 0 đến kích thước của elems - 1, thực hiện
  • num:=elems [i]
  • dist:=0 khi num giống với 1 nếu không là num
  • if (start + dist)
  • res [start]:=num
  • res [start + dist]:=num
  • xóa phần tử thứ i khỏi elems
  • nếu backtrack (elems, res, start) là false, thì
    • res [start]:=-1
    • res [start + dist]:=-1
    • chèn num vào cao độ ở vị trí i
    • chuyển sang lần lặp tiếp theo
  • nếu không,
    • trả về True

Ví dụ

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

def backtrack(elems, res, start = 0):
   if len(elems) <= 0:
      return True

   if start >= len(res):
      return False

   if res[start] != -1:
      return backtrack(elems, res, start + 1)

   for i in range(len(elems)):
      num = elems[i]
      dist = 0 if num == 1 else num

      if (start + dist) < len(res) and res[start + dist] == -1:
         res[start] = num
         res[start + dist] = num
         elems.pop(i)

         if not backtrack(elems, res, start):
            res[start] = -1
            res[start + dist] = -1
            elems.insert(i, num)
            continue
         else:
            return True
def solve(n):
   elems = [ i for i in range(n,0,-1)]
   res = [ -1 for i in range(n*2 - 1)]
   backtrack(elems, res)
   return res

n = 4
print(solve(n))

Đầu vào

4

Đầu ra

[4, 2, 3, 2, 4, 3, 1]