สมมติว่าเรามีตัวเลข n เราต้องหาลำดับที่สอดคล้องกับกฎทั้งหมดต่อไปนี้:
- 1 ปรากฏในลำดับเพียงครั้งเดียว
- แต่ละตัวเลขระหว่าง 2 ถึง n ปรากฏในลำดับสองครั้ง
- สำหรับทุก i ในช่วง 2 ถึง n ระยะห่างระหว่างสองครั้งที่ i ปรากฏ ต้องเท่ากับ i อย่างแน่นอน
ระยะห่างระหว่างสองตัวเลขในลำดับ a[i] และ a[j] คือ |j - i| เราต้องหาลำดับที่ใหญ่ที่สุดในลำดับเลขโครงรัง (lexicographically largest)
เช่น ถ้าอินพุตคือ n = 4 ผลลัพธ์จะเป็น [4, 2, 3, 2, 4, 3, 1]
วิธีแก้ปัญหา
ทำตามขั้นตอนต่อไปนี้:
- กำหนดฟังก์ชัน backtrack() รับพารามิเตอร์ elems, res, start := 0
- ถ้าขนาดของ elems <= 0 แล้ว return True
- ถ้า start >= ขนาดของ res แล้ว return False
- ถ้า res[start] ไม่เท่ากับ -1 แล้ว return backtrack(elems, res, start + 1)
- สำหรับ i ในช่วง 0 ถึงขนาดของ elems - 1:
- num := elems[i]
- dist := 0 ถ้า num เท่ากับ 1 มิฉะนั้น num
- ถ้า (start + dist) < ขนาดของ res และ res[start + dist] เท่ากับ -1:
- res[start] := num
- res[start + dist] := num
- ลบองค์ประกอบที่ i ออกจาก elems
- ถ้า backtrack(elems, res, start) เป็น false:
- res[start] := -1
- res[start + dist] := -1
- แทรก num กลับเข้า elems ที่ตำแหน่ง i
- ไปรอบถัดไป
- มิฉะนั้น return True
- จากเมธอดหลัก:
- elems := รายการที่มี n องค์ประกอบจาก n ลงมา 1
- res := รายการขนาด n*2-1 เติมด้วย -1
- backtrack(elems, res)
- return res
ตัวอย่าง
ดูการนำไปใช้ดังต่อไปนี้:
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))
อินพุต
4
เอาต์พุต
[4, 2, 3, 2, 4, 3, 1]
