算法面试题：音乐播放器的随机播放
音乐播放器的随机播放
题目描述：
假设张三的mp3里有1000首歌，现在希望设计一种随机算法来随机播放。
与普通随机模式不同的是，张三希望每首歌被随机到的概率是与一首歌的豆瓣评分（0~10分）成正比的，如朴树的《平凡之路》评分为8.9分，逃跑计划的《夜空中最亮的星》评分为9.5分，则希望听《平凡之路》的概率与《夜空中最亮的星》的概率比为89:95。
现在我们已知这1000首歌的豆瓣评分：
（1）请设计一种随机算法来满足张三的需求。
（2）写代码实现自己的算法。
分析与解法：
using namespace std;int findIdx(double songs[],int n,double rnd){int left=0;int right=n-1;int mid;while(left<=right){mid=(left+right)/2;if((songs[mid-1]<=rnd) && (songs[mid]>=rnd))return mid;if(songs[mid]>rnd)right=mid-1;elseleft=mid+1;}// return mid;}int randomPlaySong(double sum_scores[],int n){double mx=sum_scores[n-1];double rnd= rand()*mx/(double)(RAND_MAX);return findIdx(sum_scores,n,rnd);}int main(){srand(time(0));double scores[]={5.5,6.5,4.5,8.5,9.5,7.5,3.5,5.0,8.0,2.0};int n=sizeof(scores)/sizeof(scores[0]);double sum_scores[n];sum_scores[0]=scores[0];for(int i=1;i
大量学员拿到近30-40万年薪
应届生秋招记录52万年薪
多位名校博士+BAT专家手把手教学
现在报名
送18VIP会员
[包2018全年在线课程和全年GPU]
原价18000元
前30人专属特惠价
仅剩5个名额
扫码查看详情
还能直接领红包
只限今日有效，快扫它↓
登录查看更多
相关内容
Arxiv
8+阅读 · 2018年5月6日
Arxiv
9+阅读 · 2018年3月22日
Arxiv
9+阅读 · 2018年2月3日
相关VIP内容
相关资讯
相关论文
Arxiv
8+阅读 · 2018年5月6日
Arxiv
9+阅读 · 2018年3月22日
Arxiv
9+阅读 · 2018年2月3日
微信扫码咨询专知VIP会员