4

这是昨天在 interviewstreet 结束的编程竞赛中的一个问题：

爱丽丝和鲍勃玩游戏。第 i 轮 (i >= 1) 的操作如下：

  • Alice 支付 Bob 2 * i - 1 美元，
  • 爱丽丝扔了一枚有偏见的硬币，
  • 如果硬币的结果是连续k轮正面，则游戏停止，否则游戏继续。

给定 k 和投掷结果为正面 (p) 的概率，您的程序应该找到 Alice 支付给 Bob 的预期美元数，以及预期的回合数。

输入

输入的第一行包含测试用例的数量（T <= 50）。接下来的 T 行中的每一行都包含由单个空格分隔的 p 和 k。p 是一个十进制数，小数点后最多有两位数，这样 0.6 <= p <= 1。k 是一个正整数，这样 0 < k <= 20。

输出

对于每个测试用例，打印两个整数。第一个数字是预期游戏轮数的整数部分，第二个数字是 Alice 支付给 Bob 的预期美元数的整数部分。

样本输入

3

0.6 1

1 20

0.80 8

样本输出

1 3

20 400

24 976

我已经得到了问题的第一部分，即预期的游戏轮数。我用下面的代码得到它

if __name__ == '__main__':
    t = int(raw_input())   
    while t :
        t -= 1
        temp = str(raw_input())
        p,k = temp.split(' ')
        p = float(p)
        k = int(k)

        #print p,k
        ans  = 0.0
        num = k * (p**k)
        den = 1
        q = 1.0 - p
        for N in range(1,k+1):
            den = den - ((p**(N-1))*q)
            num = num + (N*(p**(N-1))*q)
            #print (N*(q**N))

        print int(num/den)

但是问题的第二部分仍然让我感到困惑，即 Alice 支付给 bob 的预期美元数。如何计算预期收益？

4

1 回答 1

3

即使您知道预期的回合数，您也需要对所有可能的支出进行平均。这意味着它比仅在预期停止时间计算支出更复杂。以下是细节：

回想一下期望的技术定义，如果 X 是一个随机变量，那么 X 的期望值是 X(w)*Pr(w) 的所有可能结果 w 的总和。如果 X 取正整数值，我们可以重新表述为 X 的期望值是从 i=1 到 i*Pr(X=i) 的无穷大的总和。在您的情况下，我们处理的随机变量是 T = 游戏停止时间，P = 支出。

期望轮数是 T 的期望，它是从 i=1 到 i*Pr(T=i) 的无穷大的总和。由于他们只要求期望的整数部分，一旦 i*Pr(T=i) 小于 1/2^i，我们就可以停止求和。（当 i*Pr(T=i)<1/2^i 时停止求和的想法是 1/2^i 总和为 1，但您可能需要对此进行调整以避免低估。）

P 的期望稍微复杂一些。如果游戏要进行 j 轮，那么支出将是从 i=1 到 j 的 2i-1 的总和，结果是 j^2。因此，只能发生 j^2 形式的支出，并且 Pr(P=j^2)=Pr(T=j)。所以 P 的期望值是 i=1 到无穷大 i^2 * Pr(P=i^2) 的和，等于 i=1 到无穷大 i^2*Pr(T=一世）。同样，一旦 i^2*Pr(T=i) 小于 1/2^i，我们就可以停止求和。

于 2012-10-09T15:54:21.200 回答