面试题总结

1.洗牌算法：

洗牌算法：
给n个拍，一个随即函数。求洗牌算法。

for i in range(1,n+1):

           random pick a number j in range(1,i)

           swap i,j

证明：数学归纳法：n=k时候成立，对于n=k+1只需要证明1.最后一个放到k+1位置的概率是1/(k+1)

                                                                                          2.前面k个放到k+1的位置的概率是1/(k+1) 3.前面k个放到前面k个位置时候的每一个方法也是1/(k+1)