Creazione di un algoritmo efficiente per "Eliminare il gioco"

Aug 17 2020

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

1 Ekin Aug 17 2020 at 03:21

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.