演算法面试题：音乐播放器的随机播放

题目描述：

假设张三的mp3里有1000首歌，现在希望设计一种随机演算法来随机播放。

与普通随机模式不同的是，张三希望每首歌被随机到的概率是与一首歌的豆瓣评分（0~10分）成正比的，如朴树的《平凡之路》评分为8.9分，逃跑计划的《夜空中最亮的星》评分为9.5分，则希望听《平凡之路》的概率与《夜空中最亮的星》的概率比为89:95。

现在我们已知这1000首歌的豆瓣评分：

（1）请设计一种随机演算法来满足张三的需求。（2）写代码实现自己的演算法。

分析与解法：

#include #include #include 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;
else
left=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

更多面试题，请微信搜「七月在线实验室」