假设张三的mp3里有1000首歌,现在希望设计一种随机算法来随机播放。与普通随机模式不同的是,张三希望每首歌被随机抽到的概率是与一首歌的豆瓣评分(0~10分)成正比的,如朴树的《平凡之路》评分为8.9分,逃跑计划的《夜空中最亮的星》评分为9.5分,则希望听《平凡之路》的概率与《夜空中最亮的星》的概率比为89:95,。现在我们已知这1000首歌的豆瓣评分:
(1)请设计一种随机算法来满足张三的需求。
(2)请写代码实现自己的算法。
public class RandomSongs {//JAVA public int randomSong(double[] grades){ //grades 是输入参数,表明每一首歌的评分,共1000个;返回值是歌曲的编号 while(true){ int x=(int)(Math.random()*(grades.length));//首先是平等地选歌 double y=(Math.random()*10);//然后进行评分验证: if(grades[x]>=y){ return x; } }//其实这种方法,对于那两首歌并不是完全的89:95,但是在歌曲总数 很多的情况下,很接近原始评分比例了 } //可以用下面的测试方法来验证,我们举一个7首歌曲的歌单 public static void main(String[] args){ RandomSongs rs=new RandomSongs(); double[] grades={8.9, 9.0, 8.0, 6, 2, 5.1, 9.5}; int[] prob=new int[grades.length]; for(int i=0;i<prob.length;i++){prob[i]=0;} for(int i=0;i<10000;i++){ int x=rs.randomSong(grades); prob[x]++; } for(int i=0;i<prob.length;i++){ System.out.print(prob[i]+"\t"); } } }
import random musics = [ {'name': '平凡之路', 'score': 8.9}, {'name': '夜空中最亮的星', 'score': 9.5}, ] # score * 1000 避免整数离散带来的误差 total = int(sum(x['score'] * 1000 for x in musics)) def play(): r = random.randint(0, total) index = 0 value = musics[0]['score'] * 1000 while r > value: index += 1 value += musics[index]['score'] * 1000 return musics[index] if __name__ == '__main__': n = 0 for i in range(1000000): if play()['name'] == '平凡之路': n += 1 print(musics[0]['score'] / musics[1]['score']) # 0.9368421052631579 print(n / (1000000 - n)) # 0.9366821149343368
#coding:utf-8 import random class RanPlay: # music is a list which contains name of music and its score def __init__(self,musics): self.musics = musics self.region = {} self.counter = 0 for music in musics: self.counter += music['score'] self.region[self.counter] = music['name'] def play(self): key = random.randint(0,int(self.counter * 10) )/ 10.0 temp = filter(lambda x:key<x,self.region.keys()) print key,temp if len(temp) !=0: played_music_key = min(temp) else: played_music_key = max(self.region.keys()) return self.region[played_music_key] musics = [ { "name":"平凡之路", "score":8.9 }, { "name":"夜空中最亮的星", "score":9.5, }, ] r = RanPlay(musics) print r.play()
#include <iostream> #include <time.h> #include <stdlib.h> 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<n;i++) sum_scores[i]=sum_scores[i-1]+scores[i]; cout<<"Calculate the probability of each song: "<<endl; int totalScore=sum_scores[n-1]; for(int i=0;i<n;i++) cout<<scores[i]/totalScore<<" "; cout<<endl; int counts[n]; for(int i=0;i<n;i++) counts[i]=0; int i=0; int idx; int MAX_ITER=100000000; while(i<MAX_ITER){ idx=randomPlaySong(sum_scores,n); counts[idx]++; i++; } cout<<"After simulation, probability of each song: "<<endl; for(int i=0;i<n;i++) cout<<1.0*counts[i]/MAX_ITER<<" "; cout<<endl; return 0; }
思想和前面几位差不多,但是要考虑所有歌曲。extern int musicNum; //歌曲数extern float scoreTable[]; //歌曲评分float scoreTotal = 0; //评分总和void init(float *score, int num) {scoreTotal = 0;for( int i=0; i<num; i++) {scoreTotal += score[i];}}int musicSelect(void) {int id = 0;float tmp = ( srand(time()) % ((int)(scoreTotal*10)) )/10.0; //随机数while( (tmp-=scoreTable[id]) > 0 ) {id++;}return id;}int main(void) {int id;init(scoreTable, musicNum);id = musicSelect(void);}