http://
Question:随机播放音乐（随机数相关。带权重）
如果张三的mp3里有1000首歌，如今希望设计一种随机算法来随机播放。与普通随机模式不同的是，张三希望每首歌被随机到的改了吧是与一首歌的豆瓣评分（0~10分）成正比的。如item0评分为8.9分，item1评分为9.5分。则希望听item0的概率与item1的概率比为89:95,。如今我们已知这1000首歌的豆瓣评分。 解决方式： 一、
def randomSelect(item_list): ''' 随机选择带权重的list中的某个item,并返回其下标（item_list权重和能够不为1） :param item_list: :return: ''' accu_item_list = add.accumulate(item_list) # print(type(accu_item_list)) random_select = random.random() * accu_item_list[-1] for accu_item_id, accu_item in enumerate(accu_item_list): if accu_item > random_select: return accu_item_iddef cal_ratio(item_list): ''' 计算每一个item在item_list中的比重 :param item_list: :return: ''' all_sum = sum(item_list) for i in item_list: print(i / all_sum)if __name__ == '__main__': item_list = [0.1, 0.4, 0.6, 0.8, 0.3] cal_ratio(item_list) item_list_all = [] item_list_cnt = [] for i in range(100000): selected_item_id = randomSelect(item_list) item_list_all.append(selected_item_id) for i in range(len(item_list)): item_list_cnt.append(item_list_all.count(i)) cal_ratio(item_list_cnt)Note： 原理全部比重加和为accu_item_list[-1](可看成一维上的长度。 是全部item长度的和，且大比重的item长度相对更长)， 在这个总长度上掷骰子，长度长的item选中概率大。
二、
（1）1000首歌曲编号。从1至1000
（2）随机选择一首歌：产生一个1至1000的随机数。表示要播放的歌曲。这时，全部的歌曲被选中播放的概率是同样的 （3）选定的歌播放与否：假设选定的歌曲是54号。它的豆瓣评分是9.5分。那么此时再随机生成一个1至100的随机数，假设随机数小于等于95。那么就播放这首歌曲，假设随机数大于95，则反复1,2,3的步骤，直至找到一首能够播放的歌曲 备注：两首歌曲，评分分别为8.0,9.5，他们被选中的概率为1/1000,选中后还要产生一次随机数。被播放的概率分别为80%，95%。选中概率同样。播放概率比恰好是分数比值
详解：
重述算法本身：
1、以[1,N]均匀分布产生随机数s； 2、以[0,1]均与分布产生随机数q，若q<ps，则选择第s首歌。算法结束；否则，跳转到第1步。 以下的研究对象。都是仅考察第i首音乐： 如果它第n次被选中的概率为f(n)，前n次被选中的概率为s(n)，即s(n)=f(1)+f(2)+...+f(n)。 显然有：f(n) = s(n) - s(n-1) 第n+1次被选中的概率为： f(n+1) = (1-s(n))(1/N) * pi当中，1-s(n)表示前n次都没有被选中。 从而：s(n)= 1 - (f(n+1) N/pi) 令a = -N/pi,则： s(n) = af(n+1) + 1 从而：s(n-1)=af(n) + 1 两式相减，得到： f(n) = af(n+1) - af(n) 从而：q = f(n+1) / f(n) = (1+a)/a = (N-1)/N 而f(1)=pi/N 从而，s(n) = f(1) / (1 - q) = pi 结论仍然是：这样的做法是对的。 此外，尽管啰嗦了这么多，再说两点： 1、通过上面的式子：f(n+1) / f(n) = (N-1)/N能够看出，事实上第n+1次的概率比第n次的概率，是等比数列的。 2、以上不过高中“等比数列”“通项公式和前n项和公式”的简单运算。
复杂度分析：
须要多少次才干成功选中一首歌的期望值
- 定义一个大小1000的数组A[1000]。 这个数组的每一个元素分别存放第0~i首歌的打分之和，设数组最后一个元素为A[999]为M。
- 随机生成一个0~M间的随机数R；
- 利用折半查找。找到第一个大于等于R的元素的下标，则该下标即为选中的歌曲编号。
算法的时间复杂度即为折半查找的时间复杂度O(lgn)，n是列表中歌曲的数目
在未知个数的链表中均匀随机选一个元素
比如：list: node1 -> node2 -> node3 -> node4 -> node5 -> node6 -> NULL 这个链表有6元素，每一个node可能被选到的概率为1/6。但普通情况下，node的个数是未知的（没有链表头没有记录个数的状态变量）。
写一个函数。怎样在这样的情况下，能均匀的概率选取出链表当中一个node?解决方式：
遍历链表 对第i个节点 （i从1開始）。均匀产生随机数 x
若x % i == 0 则临时保留这个节点 （换掉之前保留的节点） （1） 假设仅仅有1个节点 选择第1个节点的概率是1 （2） 假设仅仅有2个节点 第一步先选择第1个节点 然后再以1/2的概率换掉， 所以每一个节点选择的概率是1/2 （3） 如果遍历到链表第n个节点的时候 选择眼下保留的n个节点的概率都是1/n 则对第(n + 1)个节点， 我们有1/(n + 1)的概率选择它，有n / (n + 1)的概率保留原来保存的节点，所以保留前n个节点中每一个的概率是(这是个条件概率） 1/n * (n / (n + 1)) = 1 / (n + 1) ，可见终于保留每一个节点的概率都是1/(n + 1) 这样的抽样方法叫水库抽样，能够扩展到要保留k个的情况。 from:ref:http://ask.julyedu.com/question/127
http://ask.julyedu.com/question/315