一圈有100名枪手杀死下一个人

"""

    100 people are standing in a circle with gun in their hands.
    1 kills 2, 3 kills 4, 5 kills 6 and so on till we are
    left with only one person. Who will be the last person alive?
    Write code to implement this ##efficiently.## <-[ Python is not efficient]

"""

persons = list(range(1,101)) # The question asks 1-indexing

while len(persons) > 1:
    for index, person in enumerate(persons):
        del persons[(index + 1) % len(persons)]

print(persons)

#1 楼

1.封装

在模块的顶层编写代码使测试代码和性能变得困难。最好将代码封装在一个函数中。因此，我会写：

def survivor(n):
    """Return the survivor of a circular firing squad of n people."""
    persons = list(range(1, n + 1))
    while len(persons) > 1:
        for index, _ in enumerate(persons):
            del persons[(index + 1) % len(persons)]
    return persons[0]

（变量person不在for循环的主体中使用；为此类变量编写_很方便，这就是我在这里所做的。）

2。效率的含义

问题所要求的代码是否“有效”？通常，在计算中，我们使用“有效”来表示算法效率：即程序使用的资源随输入量增长的速率，通常以big-O表示。

这个问题说：“ Python效率不高”，但是按照效率的通常观点，编程语言并不重要：效率是算法的属性，而不是算法的实现语言。

3。偶然是二次方

survivor函数的运行时间是多少，用\ $ n \ $函数表示？好吧，查看Python Wiki上的时间复杂度页面，我们可以看到列表上的del操作需要\ $ O（n）\ $，其中\ $ n \ $是列表的长度，并且执行一次对于每个被杀死的人，整个运行时间为\ $ O（n ^ 2）\ $。

可以通过实验进行检查：

>>> t = 1
>>> for i in range(8, 17):
...     t, u = timeit(lambda:survivor(2**i), number=1), t
...     print('{:6d} {:.6f} {:.2f}'.format(2**i, t, t / u))
... 
   256 0.000138 0.00
   512 0.000318 2.31
  1024 0.000560 1.76
  2048 0.001363 2.43
  4096 0.006631 4.87
  8192 0.030330 4.57
 16384 0.132857 4.38
 32768 0.534205 4.02
 65536 2.134860 4.00

您可以看到，n的每增加一倍，运行时间就会增加大约四倍，这是我们期望的\ $ O（n ^ 2）\ $算法的结果。



4。使其线性

我们如何加快速度？好吧，我们可以通过列出幸存者列表而不是删除死者来避免昂贵的del操作。考虑一次绕行射击队。如果剩下的人数是偶数，则索引为0、2、4等的人可以生存。但是，如果剩余的人数为奇数，则最后一个幸存者射中索引为0的人，因此幸存者为索引为2、4的人，依此类推。将其放入代码形式：

def survivor2(n):
    """Return the survivor of a circular firing squad of n people."""
    persons = list(range(1, n + 1))
    while len(persons) > 1:
        if len(persons) % 2 == 0:
            persons = persons[::2]
        else:
            persons = persons[2::2]
    return persons[0]

（如果愿意，可以使用persons[(len(persons) % 2) * 2::2]这样的表达式来缩短它，但我认为代码的减少不大长度值得失去清晰度。）

通过将结果与原始实现进行比较，让我们检查这是否正确：

>>> all(survivor(i) == survivor2(i) for i in range(1, 1000))
True

请注意，将代码组织成函数对于测试非常有用。

现在，survivor2的运行时间是多少？再次，查看Python Wiki上的时间复杂度页面，我们可以看到“获取切片”操作花费时间\ $ O（k）\ $，其中\ $ k \ $是切片中的项目数。在这种情况下，每个切片的长度是persons的一半，因此运行时间为$$ O \ left（{n \ over 2} \ right）+ O \ left（{n \ over 4} \ right）+ O \ left（ {n \ over 8} \ right）+ \ dots $$，即\ $ O（n）\ $。再次，我们可以通过实验检查：

>>> t = 1
>>> for i in range(8, 25):
...     t, u = timeit(lambda:survivor2(2**i), number=1), t
...     print('{:8d} {:8.6f} {:.2f}'.format(2**i, t, t / u))
... 
     256 0.000034 0.00
     512 0.000048 1.40
    1024 0.000087 1.79
    2048 0.000142 1.63
    4096 0.000300 2.12
    8192 0.000573 1.91
   16384 0.001227 2.14
   32768 0.002628 2.14
   65536 0.006003 2.28
  131072 0.017954 2.99
  262144 0.043873 2.44
  524288 0.094669 2.16
 1048576 0.180889 1.91
 2097152 0.364302 2.01
 4194304 0.743028 2.04
 8388608 1.497255 2.02
16777216 3.094121 2.07

现在，每增加n一次，运行时间就会增加大约两倍，这是我们期望的\ $ O（n）\ $算法。



5。使它成为对数

我们可以做得更好吗？让我们看看在射击队每次出行后幸存者的实际身份：

from pprint import pprint

def survivors(n):
    """Print survivors after each round of circular firing squad with n people."""
    persons = list(range(1, n + 1))
    while len(persons) > 1:
        if len(persons) % 2 == 0:
            persons = persons[::2]
        else:
            persons = persons[2::2]
        pprint(persons, compact=True)

>>> survivors(100)
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41,
 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 77, 79, 81,
 83, 85, 87, 89, 91, 93, 95, 97, 99]
[1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49, 53, 57, 61, 65, 69, 73, 77,
 81, 85, 89, 93, 97]
[9, 17, 25, 33, 41, 49, 57, 65, 73, 81, 89, 97]
[9, 25, 41, 57, 73, 89]
[9, 41, 73]
[73]

每一轮之后，幸存者之间的距离加倍。因此，经过一轮，幸存者是第二个人。两轮之后，每第4个人，三轮之后，每8个人，依此类推。如果人数是偶数，则第一人仍然是下一轮的第一位幸存者。但是当人数奇数时，第三人称将成为下一轮的第一位幸存者。

因此，要解决此问题，我们无需记住所有幸存者，我们只需要记住第一个幸存者，幸存者之间的差距以及幸存者总数。像这样：

def survivor3(n):
    """Return the survivor of a circular firing squad of n people."""
    first = 1
    gap = 1
    while n > 1:
        gap *= 2
        n, odd = divmod(n, 2)
        if odd:
            first += gap
    return first

再次，我们应该检查一下是否正确：

>>> all(survivor(i) == survivor3(i) for i in range(1, 1000))
True

多快这是？在这里，每次循环时，我们对大小不超过\ $ n \ $的数进行一些算术运算，取\ $ O（\ log n）\ $，并且每次循环时，我们将幸存者的数量相除乘以2，因此循环执行\ $ O（\ log n）\ $次，整体运行时间为\ $ O（（\ log n）^ 2）\ $。

>>> t = 0
>>> for i in range(8, 60, 4):
...     t, u = timeit(lambda:survivor3(2**i), number=1), t
...     print('{:20d} {:8.6f} {:.6f}'.format(2**i, t, t - u))
... 
                 256 0.000014 0.000014
                4096 0.000012 -0.000001
               65536 0.000013 0.000001
             1048576 0.000015 0.000002
            16777216 0.000016 0.000002
           268435456 0.000018 0.000002
          4294967296 0.000022 0.000003
         68719476736 0.000030 0.000008
       1099511627776 0.000026 -0.000003
      17592186044416 0.000027 0.000001
     281474976710656 0.000031 0.000003
    4503599627370496 0.000032 0.000001
   72057594037927936 0.000035 0.000003

您可以看到n每增加16倍，运行时间就会增加一个大致恒定的数量，这是我们期望的对数算法。



请注意，该图显示的运行时缩放比例大致与\ $ \ log n \ $而不是\ $（\ log n）^ 2 \ $成比例。这是因为\ $ n \ $的值很小（小于\ $ 2 ^ {64} \ $），因此在此范围内，算术运算实际上是\ $ O（1）\ $。我们必须使用更大的\ $ n \ $值来显示渐近行为。

6。进一步阅读

这个问题是（一个简单的例子）著名的约瑟夫斯问题。