list - 删除n-1个顶点后查找n边多边形的最后一个剩余顶点

Question

问题描述： 考虑到我们有一个 n 边多边形。它具有以顺时针方式编号为 1 到 n 的顶点。
我们从任何顶点开始，比如说 1，我们必须删除顶点，然后移动到下一个顶点。
下一个顶点必须始终与当前顶点相距 2 个顶点，并且必须沿顺时针方向到达。也就是在删除 1 号顶点之后，我要访问的下一个顶点是 3，即顺时针距离 1 两个顶点。

目标：- 以上述方式执行删除，直到只剩下一个顶点。

示例：如果我有一个顶点为 1、2、3、4 和 5 的 5 边多边形。我从顶点 3 开始，删除顶点。我将两个顶点从它移到顶点 5，删除它，然后移动到顶点 2，删除它，然后到顶点 1（2 和 3 已经删除）删除它，最后我留下了顶点 4。

代码：

    n=5
    start_vertex=2 #Vertices are considered 0 indexed for the sake of modulo operation
    vert_status=[]
    deletionCount=0
    while(deletionCount<n-1):
        vert_status.append(start_vertex)
        next_vertex=start_vertex
        count=0
        while(count!=2):
            next_vertex=(next_vertex+1)%n
            if(next_vertex not in vert_status):
                count+=1            
        start_vertex=next_vertex
        explosionCount+=1

    print("End",start_vertex+1)

代码说明： 以上是我的尝试。我实际上正在运行一个while循环，并将已删除的顶点添加到列表中，然后通过检查我的列表以查看它是否尚未被删除来导航到下一个。while 循环一直执行，直到删除了 n-1 个顶点。

我目前的方法存在问题，我认为可能是通往更好解决方案的道路： 虽然它是正确的，但我的代码对于非常大的边多边形效果不佳。所以我不禁想知道在给定值'n'和下一个顶点距离当前顶点2个顶点的条件下，开始和结束顶点之间是否存在一些简单的关系。

标签： listalgorithm

Answer 1

需要注意的一点是，起始位置的移动会在结束位置产生相同的移动，因为它与仅将所有顶点旋转该量没有什么不同。因此，我们可以专注于解决您从顶点编号 1（对于每个n）开始的情况，但请记住，您必须应用适当的转变来获得其他每个解决方案。

另一件需要注意的是，从 1 开始，我们首先点击所有奇数（因为我们每次都增加 2）。在下一次通过时，我们有效地增加了 4（因为我们增加了 2，但删除了一半的数字），然后在下一次通过时，我们有效地增加了 8，然后在之后的通过中，我们'实际上增加了 16 等。

这产生了一个明显的模式：

n =  3:  result =  2; sequence = 1, 3, 2
n =  4:  result =  4; sequence = 1, 3, 2, 4
n =  5:  result =  2; sequence = 1, 3, 5, 4, 2
n =  6:  result =  4; sequence = 1, 3, 5, 2, 6, 4
n =  7:  result =  6; sequence = 1, 3, 5, 7, 4, 2, 6
n =  8:  result =  8; sequence = 1, 3, 5, 7, 2, 6, 4, 8
n =  9:  result =  2; sequence = 1, 3, 5, 7, 9, 4, 8, 6, 2
n = 10:  result =  4; sequence = 1, 3, 5, 7, 9, 2, 6,10, 8, 4
n = 11:  result =  6; sequence = 1, 3, 5, 7, 9,11, 4, 8, 2,10, 6
n = 12:  result =  8; sequence = 1, 3, 5, 7, 9,11, 2, 6,10, 4,12, 8
n = 13:  result = 10; sequence = 1, 3, 5, 7, 9,11,13, 4, 8,12, 6, 2,10
n = 14:  result = 12; sequence = 1, 3, 5, 7, 9,11,13, 2, 6,10,14, 8, 4,12
n = 15:  result = 14; sequence = 1, 3, 5, 7, 9,11,13,15, 4, 8,12, 2,10, 6,14
n = 16:  result = 16; sequence = 1, 3, 5, 7, 9,11,13,15, 2, 6,10,14, 4,12, 8,16
n = 17:  result =  2; sequence = 1, 3, 5, 7, 9,11,13,15,17, 4, 8,12,16, 6,14,10, 2
n = 18:  result =  4; sequence = 1, 3, 5, 7, 9,11,13,15,17, 2, 6,10,14,18, 8,16,12, 4
n = 19:  result =  6; sequence = 1, 3, 5, 7, 9,11,13,15,17,19, 4, 8,12,16, 2,10,18,14, 6
n = 20:  result =  8; sequence = 1, 3, 5, 7, 9,11,13,15,17,19, 2, 6,10,14,18, 4,12,16,20, 8

显然，结果是增加偶数到 2 的幂，然后重置并计数到 2 的下一个幂，等等。（如果我包含n=1and n=2，它们实际上不是多边形，你会得到2^0and2^1作为前两个解决方案。）

n正如教科书作者喜欢说的那样，“作为练习给读者”留下了对所有人都适用的证明。:)