设计一种随机算法来随机播放歌曲。

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);



	}