Creazione di un algoritmo efficiente per "Eliminare il gioco"
Stavo risolvendo questo problema del gioco ad eliminazione .
In primo luogo, ho provato con la forza bruta;
- numeri eliminati dall'inizio con la distanza $2$ (cioè elemento dopo quello successivo)
- ha invertito l'elenco
- numeri eliminati dall'inizio con la distanza $2$
- ha invertito la lista ...
Infine, restituito l'ultimo elemento rimanente. Tuttavia, non sorprendentemente, questo ha generato "Time Limit Exceeded".
Ecco il codice Python per questo:
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]
Quindi, ho cercato una soluzione migliore e ho trovato quanto segue:
def lastRemaining(n: int) -> int:
if n == 1: return 1
return (n//2 - lastRemaining(n//2) + 1) * 2
e funziona. Questo è matematicamente scritto come$$ 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} $$ L'ho verificato per alcuni valori di $n$. Tuttavia, ho bisogno di aiuto per dimostrare che questo algoritmo funziona per ogni caso.
Qualsiasi aiuto è apprezzato.
Risposte
Il primo caso $n=1$è ovvio. Per il secondo caso, nota che quello che stai facendo è fondamentalmente eseguire la prima iterazione e risolvere il problema sul rimanente (che è$2, 4, 6, ... 2⌊n/2⌋$) - be 'quasi. Lo fai in ordine inverso, ecco perché lo hai fatto$⌊n/2⌋-f(⌊n/2⌋)+1$ invece di $f(⌊n/2⌋)$Tieni presente che stai effettivamente restituendo l'ordine dell '"ultimo numero" e non il suo valore, che sarebbe equivalente nel problema originale. Quindi moltiplichiamo per$2$ alla fine per ottenere il valore dell '"ultimo numero" di cui conosciamo l'ordine.