演算法面試題:音樂播放器的隨機播放
題目描述:
假設張三的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
更多面試題,請微信搜「七月在線實驗室」
畢業季福利
原價800元的Python入門課程
現在限時免費!沒有任何要求,直接領取就可以!