"Oyunu Ortadan Kaldırmak" için verimli bir algoritma oluşturma

Aug 17 2020

Bu Eleme Oyunu problemini çözüyordum .

Önce kaba kuvvetle denedim;

  • mesafe ile baştan ortadan kaldırılan sayılar $2$ (yani bir sonraki öğeden sonraki öğe)
  • listeyi tersine çevirdi
  • mesafe ile baştan ortadan kaldırılan sayılar $2$
  • listeyi tersine çevirdi ...

Son olarak, kalan son öğeyi döndürdü. Ancak, şaşırtıcı olmayan bir şekilde, bu "Zaman Sınırı Aşıldı" yı yükseltti.

İşte bunun için Python kodu:

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]

Sonra daha iyi bir çözüm aradım ve şunları buldum:

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

ve çalışıyor. Bu matematiksel olarak şöyle yazılmıştır$$ 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} $$ Bunu bazı değerler için doğruladım $n$. Yine de, bu algoritmanın her durumda işe yaradığını kanıtlamak için yardıma ihtiyacım var.

Herhangi bir yardım takdir edilmektedir.

Yanıtlar

1 Ekin Aug 17 2020 at 03:21

İlk durum $n=1$açıktır. İkinci durum için, yaptığınız şeyin temelde ilk yinelemeyi çalıştırmak ve kalan sorun üzerinde sorunu çözmek olduğunu unutmayın ($2, 4, 6, ... 2⌊n/2⌋$) - iyi, neredeyse. Ters sırayla yaparsınız, bu yüzden$⌊n/2⌋-f(⌊n/2⌋)+1$ onun yerine $f(⌊n/2⌋)$Burada, orijinal soruna eşdeğer olacak şekilde, değerini değil, "son sayı" nın sırasını döndürdüğünüzü unutmayın. Bu nedenle ile çarpıyoruz$2$ sonunda sırasını bildiğimiz "son sayı" nın değerini almak için.