模拟中的无限循环

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);

如果你们都遇到同样的错误，请告诉我。另外，请告诉我我是否违反了任何规则，因为这是我发布的第一个问题。如果看起来太长，请告诉我。

本来应该是这样的…… 在这种情况下，代码在以下 mods 下确实可以正常工作：

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-乘客和飞机座位/

Answer 1

递归虽然允许，但并不是您的最佳首选。

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 之后的三引号字符串。

Answer 2

您也许可以使用动态规划找到精确的解决方案
http://en.wikipedia.org/wiki/Dynamic_programming
为此，您需要将记忆添加到递归函数中：
什么是记忆以及如何在 Python 中使用它？

如果您只想使用模拟来估计概率使用随机数，那么我建议您在一定深度后，当概率变得非常小时，突破递归函数，因为这只会改变一些较小的小数位（很可能......您可能想将结果的变化绘制为你改变深度）。

要测量深度，您可以在参数中添加一个整数：
f（深度）：
如果深度>10：
返回一些东西
else: f(深度+1)

默认情况下允许的最大递归深度是 1000，尽管您可以更改此设置，但在得到答案之前您将耗尽内存