5.1-1

我是看的中文版本, 我觉得这个翻译的不对, 应该是说满足全序关系. 首先要理解什么是全序关系的集合, 这是一个严格的数学定义. 参考https://zh.wikipedia.org/wiki/全序关系

全序关系即集合 X 上的反对称的、传递的和完全的二元关系

还有一点就是, ‘在第四行的代码中, 总能决定哪一个应聘者最佳’, 不是说’运行一次这个代码, 第四行的代码都可以决定哪个最佳’ , 而是说不管如何随机, 不管如何打乱应聘者顺序, 运行多次, 乃至无数次, 第四行的代码都可以决定哪个最佳. 如果不这么理解, 全序关系就正明不了.

我不知道怎么算是严格的数学意义上的证明, 简单说一下吧.

反对称性, 若 a>=b && b>=a, 则 a==b . 关于反对称性, 我觉得, 还有另外一个翻译不准确的地方, ‘总能决定哪一个应聘者最佳’, 是说两两比较总能区分哪一个更好, 不能出现一样好的情况. 如果单看代码的话, 是有可能出现 a == b 的. 如果所有应聘者都是能力相同, 那么反对称性就满足不了了. 按自我纠正后的理解呢, 可以用反证法证明: 如果不满足反对称, 则A和B就不是’总能区分哪一个更好’, 所以一定满足反对称性.

传递性, 这个真不知道怎么算’证明’, A比B好, B比C好, A’明显’比C好, 这个需要证明吗?

完全性, a<=b, 或者 b<=a . 既然’总能区分哪一个更好’, 说明a和b总有一个比另外一个好. 用反证更好理解: 如果不满足完全性, 就是说a和b不能比较哪个更好, 这样就不能保证’总能区分哪一个更好’, 所以一定要满足完全性.

5.1-2

这个问题我想了好几天, 终于没想出来一个可靠的好办法, 网上搜索了别人的回答, 和我的一样不算可靠, 看来只能这样了.

先说下我的思路.

  1. 假设已有 rand(1, n), 返回 1-n 之间随机一个数字. 这里的n是所有2的整数次方, 2, 4, 8, 16 … 1024 …
  2. 求 rand(1, x), 只需要按下面这样, 先找一个比x大的n r = rand(1, n) while r > x: r = rand(1, n) return r
  3. 现在的问题就是假设1 能不能实现, 怎么实现. 这个很简单. rand(1, 2*n) = rand(1, n) * rand(1, 2)

网上看到的回答, 基本原理是一样的, 但合在一步里面了, 并不需要先求 rand(1, n)

对于 rand(1, x), 先找一个最小的n,使 pow(2,n) >= x, 比如求 rand(1,5), 则取 n=3 , 然后

r = x + 1
while r > n {
	r = 0
	for i = 1; i <= n; i++ {
		r = 2*r + rand(0,1)
	}
}
return n

我说他不可靠, 是因为这个 while r > x 的条件可能永远达成不了, 最坏时间复杂度应该是无限大吧, 但还是可以计算一下平均时间复杂度. 我算下来, 平均时间复杂度是 O(n), 这里的n不是x, 就是上面描述里面的n. 精确的说, 平均运行时间是2n

计算方式如下:

首先呢, 如果x正好是2的某整数次方, 那么不会死循环, 一次过! 坏情况是x正好是2的某整数次方+1, 这种情况下, 一次过的概率只有1/2, 还有1/2的概率需要重新再来一次.

设期望运行时间, 也就是 r = 2*r + rand(0,1) 这行代码的运行次数的期望, 为 f(n), 那么 f(n) = 1/2 * n + 1/2 * (1+f(n)) , 求得 f(n) = 2n

写了个程序验证了一下运行时间

# -*- coding: utf-8 -*-

import random
import time
import sys
import math

count = 0

def f(x, n):
    global count
    r = x + 1
    while r >= x:
        r = 0
        for _ in range(n):
            count += 1
            r = 2*r + random.randint(0, 1)
    return r

if __name__ == '__main__':
    x = int(eval(sys.argv[1]))
    n = int(math.ceil(math.log(x, 2)))
    print x,n

    for _ in range(10000):
        f(x, n)

    print count/10000.0

运行结果

% python a.py "2**9+1"
513 10
20.14

% python a.py "2**19+1"
524289 20
40.038

5.1-3

# -*- coding: utf-8 -*-

import sys
import random

count = 0


def fp(p=float(sys.argv[1])):
    if random.random() <= p:
        return 0
    return 1


def f2():
    global count
    while True:
        count += 1
        x = fp() - fp()
        if x == 1:
            return 0
        if x == -1:
            return 1


if __name__ == '__main__':
    for _ in range(100000):
        f2()
    print count / 100000.0

运行结果:

% python a.py 0.3
2.36684

% python a.py 0.5
2.00161

% python a.py 0.1
5.56982

% python a.py 0.9
5.56247

运行时间期望分析. 函数f2中不能返回的概率是 p**2 + (1-p)**2 , 记为x, 能返回的概率则是 1-x

设运行时间的期望是 E , 也就是代码中count的期望值(平均值).

E = 1-x + x(1+E), 得到 E = 1/(1-x)

另外一种计算方式

前面提到的这种计算方式, 总觉得有些怪怪(应该是还没有形成这种思维), 有种无限递归的感觉. 所以再用另外一种方法来算一次, 拿第三个题目做例子.

p和x的意义见上面, 记期望为E

  1. 一次就得到结果的概率是 1-x , 两次得到结果的概率是 (1-x)*x , 三次得到结果的概率是 (1-x)*x**2 , … , n次得到结果的概率是 (1-x)*x**n

  2. 所以期望 E = (1-x) + 2(1-x)x + 3(1-x)*x**2 + ... + n(1-x)*x**(n-1)

  3. 把 (1-x) 去掉, 记 S = 1 + 2x + 3x**2 + ... + n*x**(n-1) ,

  4. 两边乘x, 得 xS = x + 2x**2 + 3x**3 + n*x**n ,

  5. 两个等式想减, 得到 S-xS = 1 + x + x**2 + x**3 + ... + x**(n-1) - n*x**n

  6. 记 f = 1 + x + x**2 + x**3 + ... + x**(n-1), 两边各乘 x, 得 xf = x + x**2 + x**3 + ... + x**n , 两个等式两边相减, 得到 f-xf = 1-x**n , 所以 f=(1-x**n)/(1-x) . 因为 x < 1, 而且 n 趋向于无穷大, 所以 x**n = 0 , 所以 f=1/(1-x)

  7. 根据5和6, 得到 S-xS = 1/(1-x) - n*x**n = 1/(1-x) 所以 `S = 1/(1-x)**2’

  8. 将7代入2, 得到期望 E = 1/(1-x)