Creación de un algoritmo eficaz para "eliminar el juego"
Estaba resolviendo este problema de Elimination Game .
Primero, lo intenté por fuerza bruta;
- números eliminados desde el principio con distancia $2$ (es decir, elemento después del siguiente)
- invirtió la lista
- números eliminados desde el principio con distancia $2$
- invirtió la lista ...
Finalmente, devolvió el último elemento restante. Sin embargo, no es sorprendente que esto planteara "Límite de tiempo excedido".
Aquí está el código de Python para esto:
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]
Luego, busqué una mejor solución y encontré lo siguiente:
def lastRemaining(n: int) -> int:
if n == 1: return 1
return (n//2 - lastRemaining(n//2) + 1) * 2
y funciona. Esto está matemáticamente escrito como$$ 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} $$ He verificado esto para algunos valores de $n$. No obstante, necesito ayuda para demostrar que este algoritmo funciona en todos los casos.
Se agradece cualquier ayuda.
Respuestas
El primer caso $n=1$es obvio. Para el segundo caso, tenga en cuenta que lo que está haciendo es básicamente ejecutar la primera iteración y resolver el problema en el resto (que es$2, 4, 6, ... 2⌊n/2⌋$) - bueno, casi. Lo haces en orden inverso, por eso tienes$⌊n/2⌋-f(⌊n/2⌋)+1$ en vez de $f(⌊n/2⌋)$Aquí, tenga en cuenta que en realidad está devolviendo el orden del "último número" y no su valor, que sería equivalente en el problema original. Por lo tanto, multiplicamos por$2$ al final para obtener el valor del "último número" cuyo orden conocemos.