##问题
假设张三的mp3里有1000首歌，现在希望设计一种随机算法来随机播放。与普通随机模式不同的是，张三希望每首歌被随机到的改了吧是与一首歌的豆瓣评分（0~10分）成正比的，如朴树的《平凡之路》评分为8.9分，逃跑计划的《夜空中最亮的星》评分为9.5分，则希望听《平凡之路》的概率与《夜空中最亮的星》的概率比为89:95,。现在我们已知这1000首歌的豆瓣评分：
- 请设计一种随机算法来满足张三的需求。
- 请写代码实现自己的算法。
##思路解答
- 1000首歌曲编号，从1至1000
- 产生一个1至1000的随机数，表示要播放的歌曲，这时，所有的歌曲被选中播放的概率是相同的
- 假设选定的歌曲是54号，它的豆瓣评分是9.5分，那么此时再随机生成一个1至100的随机数，如果随机数小于等于95，那么就播放这首歌曲，如果随机数大于95，则重复1,2,3的步骤，直至找到一首可以播放的歌曲
备注：两首歌曲，评分分别为8.0,9.5，他们被选中的概率为1/1000,选中后还要产生一次随机数，被播放的概率分别为80%，95%，选中概率相同，播放概率比恰好是分数比值
##证明
假定歌曲总数为N，第i个歌曲的评分为pi(预处理一下：评分值除以满分，使得评分取值范围是0到1)
重述具体方法：
- 以[1,N]均匀分布产生随机数s；
- 以[0,1]均与分布产生随机数q，若q<ps，则选择第s首歌，算法结束；否则，跳转到第1步。
下面分析这种算法的正确性：
- 歌曲i第一次即被选中的概率：(1/N) pi
简要说明：
即第一个随机数s=i，概率为1/N；第二个随机数q要小于pi。
因此，第一次被选中的概率是：(1/N) pi - 歌曲i第二次即被选中的概率：((N-1)/N) (1/N) pi；
- 歌曲i第三次即被选中的概率：((N-1)/N) (N-1)/N) (1/N) * pi；
- 歌曲i第四次即被选中的概率：((N-1)/N) (N-1)/N) (N-1)/N) (1/N) pi；
依次类推…
第i首歌被选中的概率为上述概率的和。大家会发现，提取公因子(1/N) * pi后，剩下的是个首项为1，公比为(N-1)/N)的递减数列，所有项的和是1/(1-(N-1)/N))=1/N，和公因子相乘后，结论恰好为pi。