Créer un algorithme efficace pour «Eliminating Game»

Question

Je résolvais ce problème de jeu d'élimination .

Tout d'abord, j'ai essayé par force brute;

• numéros éliminés du début à la distance $2$ (ie élément après le suivant)
• inversé la liste
• nombres éliminés de début par avec la distance $2$
• inversé la liste ...

Enfin, a renvoyé le dernier élément restant. Cependant, il n'est pas surprenant que cela ait augmenté le «délai dépassé».

Voici le code Python pour cela:

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]

Ensuite, j'ai cherché une meilleure solution et j'ai trouvé ce qui suit:

def lastRemaining(n: int) -> int:
        if n == 1: return 1
        return (n//2 - lastRemaining(n//2) + 1) * 2

et il fonctionne. Ceci est mathématiquement écrit comme$$ 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} $$ J'ai vérifié cela pour certaines valeurs de $n$. Néanmoins, j'ai besoin d'aide pour prouver que cet algorithme fonctionne pour chaque cas.

Toute aide est appréciée.

Answer 1

Le premier cas $n=1$est évident. Pour le deuxième cas, notez que ce que vous faites consiste essentiellement à exécuter la première itération et à résoudre le problème sur le reste (qui est$2, 4, 6, ... 2⌊n/2⌋$) - enfin, presque. Vous le faites dans l'ordre inverse, c'est pourquoi vous avez$⌊n/2⌋-f(⌊n/2⌋)+1$ au lieu de $f(⌊n/2⌋)$Ici, notez que vous retournez en fait l'ordre du "dernier nombre" et non sa valeur, ce qui serait équivalent dans le problème d'origine. Par conséquent, nous multiplions par$2$ à la fin afin d'obtenir la valeur du "dernier nombre" dont nous connaissons l'ordre.