囚徒问题解答

前天提出了一个关于囚犯排队报数，谁能留到最后的问题：

有人看出来，这是“约瑟夫环”问题的改编版，在网上可以搜到原版的问题，和很多种解法。

这里说一下我的解法：

大体思路就是，用一个列表表示所有囚犯，用循环去模拟报数的过程，如果报到奇数，就把当前值从列表中移除。循环一次之后，如果剩下的人超过 1 个，就对剩下的列表再进行循环。如此反复，直到剩下 1 个为止。代码如下：

def lucky(n):

    lst = range(1, n + 1)

    count = 0

    while len(lst) > 1:

        lst2 = lst[:]

        for i in lst:

            count += 1

            if count % 2 != 0:

                lst2.remove(i)

        lst = lst2

    return lst[0]

lst 是表示从 1 开始所有位置的列表。

count 表示报数，每次加 1。

count % 2 != 0 就是报到奇数。

lst2.remove(i) 移除对应元素。

最后剩下 1 个元素时，lst[0]就是最终结果。

这里有一个特别提出的地方，就是每次循环中，我都创建了一个新列表 lst2，作为 lst 的备份。删除元素时，是从 lst2 中删除。到循环结束后，再将 lst2 赋值给 lst。

思考题：

1. 如果直接在 lst 中删除行不行？

2. 如果写成 lst2 = lst 行不行？ 

测试几个 lucky 的输出结果，然后自己在纸上验证一下是否正确。

有同学留言说，最终结果就是队列中最大的 2 的次方数。如果是所有人站成一排，报完一轮之后，从第一个重新报数，的确是这个结果。但站成一圈循环报数就不对了。

上面我的方法只是一种可行解法。在留言中，有人给出了更好的解答，比如：

def lucky(n):

    lst = range(1,n + 1)

    while len(lst) > 1: 

        lst.append(lst[1]) 

        del lst[0:2] 

    return lst[0] 

解释一下：每次把队列中的第 2 个元素加到队尾，然后把前两个元素都删掉。一直循环，直到剩下最后一个。

关于思考题：

1.

试下这段代码：

lst = [1, 2, 3, 4, 5, 6]

for i in lst:

    if i < 5:

        lst.remove(i)

print lst

结果似乎应该是 [5, 6]？但实际输出却是 [2, 4, 5, 6]。这是因为 for 循环中每一次执行完毕后，都会去找下一个元素，进行下一次循环。但如果删除当前元素，当前元素位置的下一个元素就变成了原本的下下一个元素，因而跳过了一个元素。这是在遍历列表删除元素时常会遇到的问题。在遇到这种情况时，切记不要直接删除正在遍历的列表，而且通过其他方式来处理，比如另开一个列表，或者把待删除的元素记录下来，遍历完之后再统一删除。

2.

lst2 = lst，并没有产生一个新列表，只是相当于给 lst 起了个别名叫 lst2，所以结果会和直接操作 lst 一样。当你想对一个列表进行拷贝时，需要用 [:]。

---

Crossin的编程教室

微信ID：crossincode

论坛：http://bbs.crossincode.com

QQ群：465369080

点击左下角“阅读原文”，查看更多学习资源