ลำดับ Connell ใน Python

ภาพรวม

ลำดับ Connell สร้างโดยสลับกลุ่มเลขคี่-คู่ ขนาดกลุ่มเพิ่มทีละ 1:

1. 1 เลขคี่: 1
2. 2 เลขคู่: 2, 4
3. 3 เลขคี่: 5, 7, 9
4. 4 เลขคู่: 10, 12, 14, 16
5. ...

ลำดับ: 1, 2, 4, 5, 7, 9, 10, 12, 14, 16, 17, 19, 21, ...

สูตรคำนวณพจน์ที่ n

1. หา i ที่ทำให้ i(i+1)/2 ≥ n+1 (ขนาดกลุ่มที่ครอบคลุม n)
2. idx = i(i+1)/2 (ตำแหน่งสุดท้ายของกลุ่ม i)
3. num = i² (ค่าสุดท้ายของกลุ่ม i)
4. คำตอบ = num - 2×(idx - n - 1)

ตัวอย่าง n=12

• i=5: 5×6/2=15 ≥ 13 ✓
• idx=15, num=25
• ans = 25 - 2×(15-12-1) = 25 - 2×2 = 21

โค้ด Python

class Solution:
    def solve(self, n):
        i = 1
        while (i * (i + 1) // 2) < n + 1:
            i += 1
        idx = i * (i + 1) // 2
        num = i**2
        return num - 2 * (idx - n - 1)

ob = Solution()
print(ob.solve(12))

ผลลัพธ์

21