选择最大数的策略

stats_bestchoice.py

本习题的程序文件

假设有N个值都不相同的随机数,每次给你一个数进行选择,你如果选择接受,则游戏结束,如果选择不,则选择下一个数,直到所有的数选择完毕,你不能反悔去选择之前的数。你可以采取如下的策略:

  1. 观察前k个数,记录下其中的最大值。
  2. 在后续的数中只要出现比记录下的最大值更大的数,则选择它。
  3. 如果到了最后一个数,仍然没有做出选择,则选择它。

问题是当k为多大时选择出最大的数的概率最高?

编写选择函数

为了找到选择最大数的概率和k值之间的关系,请编写一个函数choices(data),它返回一个长度与data相同的数组,其中的每个下标index的值为当k=index时,根据前面的策略所选择的数:

import numpy as np
np.random.seed(0)
data = np.arange(1,101)
np.random.shuffle(data)

def choices(data):
    """返回一个长度与data相同的数组,其中的每个下标index的值为
    当k=index时,所选择的数
    """
    【你的程序】

print "data:"
print data
print "best choices:"
print choices(data)
可能用到的函数有:numpy.maximum.accumulate()和numpy.where()。

程序的输出为:

data:
[ 27  87   3  56  76  94  17  74  55  96  54  93  79  14   8  31  23  25
  34   9  44  63   4  72  46  49   7 100  83  77  61  81  91  69  52  28
  19  57  64  75   2  62  43  42   5  16  18  41  39   6  92  60   1  35
  29  51  12  36  24  53  11  32  67  58  80  86  33  85  15  90  20  30
  50  98  99  70  21  95  73  78  26  38  82  47  40  66  59  13  89  71
  88  37  22  84  10  97  68  65  48  45]
best choices:
[ 27  87  94  94  94  94  96  96  96  96 100 100 100 100 100 100 100 100
 100 100 100 100 100 100 100 100 100 100  45  45  45  45  45  45  45  45
  45  45  45  45  45  45  45  45  45  45  45  45  45  45  45  45  45  45
  45  45  45  45  45  45  45  45  45  45  45  45  45  45  45  45  45  45
  45  45  45  45  45  45  45  45  45  45  45  45  45  45  45  45  45  45
  45  45  45  45  45  45  45  45  45  45]
请评价你所编写的choices()的时间复杂度,如果为O(n^{2}),那么你能将它优化为O(n)的吗?请仔细思考这个问题,否则下一节的程序将执行很长很长时间。

统计选择最大数的概率

有了复杂度为O(n)的choices(),我们就可以用它计算对多组不同顺序的候选数的选择结果。请编写程序:

results = np.zeros((10000, len(data)), np.int)
【你的程序】将data的顺序打乱,调用10000次choices(),并将结果保存进results

results数组的形状为(10000,100),沿第0轴统计100出现的次数,即可求出选择最大数的概率。此外为了比较,我们还计算所选数的平均值,请编写程序:

【你的程序】计算选择最大值的概率p1和所选值的平均值p2

import pylab as pl
pl.subplot(211)
pl.plot(p1, lw=2)
pl.ylabel(u"选择最大值的概率")
pl.subplot(212)
pl.plot(p2, lw=2)
pl.ylabel(u"所选数的平均值")
pl.xlabel("k")
pl.show()

运行结果如【图:最大值的概率和所选数的平均值】所示。由图可知为了选择最大值,k值的最优取值因为33到40之间,理论上这个值应为N/e,约为36.8。而为让所选择的数尽可能的大,k值则约为9。这是因为当k为37时,虽然得到最大数的概率最大,然而也有37%的概率只能选择最后一个数。

/tech/static/books/scipyex/_images//stats_bestchoice_01.png

最大值的概率和所选数的平均值

內容目录

上一个主题

验证中心极限定理

下一个主题

PID控制

本页

loading...