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