第一题：
假设张三的mp3里有1000首歌，现在希望设计一种随机算法来随机播放。与普通随机模式不同的是，张三希望每首歌被随机抽到的概率是与一首歌的豆瓣评分（0~10分）成正比的，如朴树的《平凡之路》评分为8.9分，逃跑计划的《夜空中最亮的星》评分为9.5分，则希望听《平凡之路》的概率与《夜空中最亮的星》的概率比为89:95,。现在我们已知这1000首歌的豆瓣评分：
（1）请设计一种随机算法来满足张三的需求。
（2）请写代码实现自己的算法。
思路：
把所有歌的评分叠加起来，特定的区间属于特定的歌，然后在这个区间上随机采样（服从均匀分布），采样得到的值落在哪个区间上，就播哪首歌。例如8.9+9.5=18.4，if(8.9 < rand(0~18.4) <= 18.4)则播《夜空中最亮的星》。Boosting中就会用到这种技巧。
代码：
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);
}
第二题：
假设有一个数组，里面有10个元素 int a[10]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9}。请写一个算法，得到a数组的一个随机排列。要求时间复杂度尽量小，可以使用random函数。例如输出的随机序列可以是：3 6 2 4 5 1 9 8 0
思路：
在数组中随机取一个数，跟第一个交换，
然后在从第二个开始的子序列中随机取一个数，跟第二个交换。。。
代码：
public class Test {
public static void main(String[] args) {
int a[]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9
};
int tmp;
for(
int i=0;i<a.length;i++
){
int random=getRandom(10-i);
//获取小于10-i的随机整数
tmp=
a[i];
a[i]=
a[random];
a[random]=
tmp;
}
for(
int i=0;i<a.length;i++
){
System.out.print(a[i]);
}
}
static int getRandom(
int max){
int k=(
int)(Math.random()*max*10)/max;
//0到max随机数
return k;
}
}
转载于:https://www.cnblogs.com/jasonkent27/p/5093525.html
