การสร้างอัลกอริทึมที่มีประสิทธิภาพสำหรับ "เกมกำจัด"
ฉันกำลังแก้ปัญหาเกมกำจัดนี้
อันดับแรกฉันพยายามด้วยพลังเดรัจฉาน
- กำจัดตัวเลขจากจุดเริ่มต้นด้วยระยะทาง $2$ (เช่นองค์ประกอบหลังจากที่ถัดไป)
- กลับรายการ
- กำจัดตัวเลขจากจุดเริ่มต้นด้วยระยะทาง $2$
- กลับรายการ ...
สุดท้ายส่งคืนองค์ประกอบสุดท้ายที่เหลือ อย่างไรก็ตามไม่น่าแปลกใจที่สิ่งนี้ทำให้เกิด "Time Limit Exceeded"
นี่คือรหัส Python สำหรับสิ่งนี้:
def lastRemaining(n: int) -> int:
nums = [i for i in range(1, n + 1)]
l = len(nums)
while l != 1:
for i in range(0, len(nums), 1):
if i < len(nums):
nums.remove(nums[i])
l -= 1
nums.reverse()
return nums[0]
จากนั้นฉันค้นหาวิธีแก้ปัญหาที่ดีกว่าและพบสิ่งต่อไปนี้:
def lastRemaining(n: int) -> int:
if n == 1: return 1
return (n//2 - lastRemaining(n//2) + 1) * 2
และมันได้ผล นี่คือการเขียนทางคณิตศาสตร์เป็น$$ f(n) = \begin{cases} 1, \text{ if } n=1, \\ 2\left(\bigg\lfloor\cfrac{n}{2}\bigg\rfloor - f\left(\bigg\lfloor\cfrac{n}{2}\bigg\rfloor\right) + 1\right), \text{ otherwise } \end{cases} $$ ฉันได้ตรวจสอบแล้วสำหรับค่าบางอย่างของ $n$. อย่างไรก็ตามฉันต้องการความช่วยเหลือในการพิสูจน์ว่าอัลกอริทึมนี้ใช้ได้กับทุกกรณี
ขอความช่วยเหลือใด ๆ
คำตอบ
กรณีแรก $n=1$ชัดเจน สำหรับกรณีที่สองโปรดทราบว่าโดยพื้นฐานแล้วสิ่งที่คุณกำลังทำคือการรันการย้ำครั้งแรกและการแก้ปัญหาในส่วนที่เหลือ (ซึ่งก็คือ$2, 4, 6, ... 2⌊n/2⌋$) - ดีเกือบ คุณทำในลำดับย้อนกลับซึ่งเป็นเหตุผลที่คุณมี$⌊n/2⌋-f(⌊n/2⌋)+1$ แทน $f(⌊n/2⌋)$ที่นี่โปรดทราบว่าคุณส่งคืนลำดับของ "หมายเลขสุดท้าย" จริง ๆ แล้วไม่ใช่ค่าของมันซึ่งจะเทียบเท่ากับปัญหาเดิม ดังนั้นเราจึงคูณด้วย$2$ ในตอนท้ายเพื่อให้ได้ค่าของ "ตัวเลขสุดท้าย" ซึ่งเราทราบลำดับของ