仿真中的无限循环

Question

我刚开始学习Python，下面是我写的细节。我的代码进入了一个无限循环，当我尝试在函数内部调用它自己时出现了错误。这种递归方式是不允许的吗？

我把代码贴在下面，谢谢大家的帮助 :)

这个程序假设有100名乘客登机。假设第一个乘客丢失了登机牌，他随机找了个座位坐下。接下来的乘客如果自己的座位空着就坐自己的座位，如果被占了就随机找个座位坐下。最终的目标是找出最后一名乘客不坐自己座位的概率。我还没有添加循环部分，这样才能做一个完整的模拟。上面的问题实际上是一个概率谜题。我想验证一下答案，因为我不太理解这个推理。

import random
from numpy import zeros

rand = zeros((100,3))
# The rows are : Passenger number , The seat he is occupying and if his designated     seat is occupied. I am assuming that the passengers have seats which are same as the order in which they enter. so the 1st passenger enter has a designated seat number 1, 2nd to enter has no. 2 etc.

def cio(r):  # Says if the seat is occupied ( 1 if occupied, 0 if not)
    if rand[r][2]==1:
        return 1
    if rand[r][2]==0:
        return 0

def assign(ini,mov):    # The first is passenger no. and the second is the final seat he gets. So I keep on chaning the mov variable if the seat that he randomly picked was occupied too. 
    if cio(rand[mov][2])== 0 :
        rand[mov][2] = 1
        rand[mov][1] = ini
    elif cio(rand[mov][2])== 1 :
        mov2 = random.randint(0,99)
 #       print(mov2)            Was used to debug.. didn't really help
        assign(ini,mov2)        # I get the error pointing to this line :(

# Defining the first passenger's stats.
rand[0][0] = 1
rand[0][1] = random.randint(1,100)
m = rand[0][1]
rand[m][2]= 1

for x in range(99):
    rand[x+1][0] = x + 2

for x in range(99):
    assign(x+1,x+1)

if rand[99][0]==rand[99][1] :
    print(1);
else :
    print(0);

请告诉我你们是否遇到同样的错误。如果我违反了什么规则，请告诉我，因为这是我第一次发问。如果内容太长我很抱歉。

这应该是正确的做法……在进行以下修改后，代码在这种情况下运行得很好：

def assign(ini,mov):
if cio(mov)== 0 :     """Changed here"""
    rand[mov][2] = 1
    rand[mov][1] = ini
elif cio(mov)== 1 :    """And here"""
    mov2 = random.randint(0,99)
    assign(ini,mov2)  

我在Windows 7上使用Python 2.6.6，使用的是Enthought的学术版Python软件。http://www.enthought.com/products/getepd.php

这个谜题的答案是0.5，实际上我运行10000次后得到的结果也差不多是这个。

我没有在这里看到，但它应该在网上有……http://www.brightbubble.net/2010/07/10/100-passengers-and-plane-seats/

Answer 1

你可以尝试用动态规划来找到确切的解决方案。动态规划是一种解决问题的方法，具体可以参考这个链接：http://en.wikipedia.org/wiki/Dynamic_programming。为了实现这个，你需要在你的递归函数中加入记忆化（memoization）技术。想了解记忆化是什么以及如何在Python中使用，可以看看这个链接：什么是记忆化，我该如何在Python中使用它？

如果你只是想用随机数模拟来估算概率，我建议你在递归函数达到一定深度后就停止，因为当概率变得非常小的时候，继续计算只会改变一些小数位（大概率是这样……你可能想要绘制一下随着深度变化结果的变化）。

为了测量深度，你可以在参数中添加一个整数，比如这样：

f(depth):
   if depth>10:
       return something
   else: f(depth+1)

默认情况下，允许的最大递归深度是1000，虽然你可以更改这个限制，但在得到答案之前，你可能会耗尽内存。

Answer 2

递归虽然可以用，但这并不是你最好的选择。

在Python中，递归函数有一个上限。看起来你的循环超过了这个上限。

你其实想在赋值的时候使用某种while循环。

def assign(ini,mov):    
   """The first is passenger no. and the second is the final seat he gets. So I keep on chaning the mov variable if the seat that he randomly picked was occupied too. 
   """
   while cio(rand[mov][2])== 1:
      mov = random.randint(0,99)

   assert cio(rand[mov][2])== 0
   rand[mov][2] = 1
   rand[mov][1] = ini

这可能更接近你想要做的事情。

注意你注释的变化。在def后面用三重引号的字符串。