请实现如下这个函数: String getRandomPri

#include <iostream>
#include <map>
#include <string>
#include <ctime>

using namespace std;

string getRandomPrize(map<string, double> hm)
{
	double all = 0.0;

	map<double, string> mp;
	map<string, double>::iterator it = hm.begin();
	while (it != hm.end())
	{
		all += (*it).second;
		mp.insert(pair<double, string>(all, (*it).first));
		++it;
	}

	srand((unsigned)time(NULL));
	double total = rand() / double(RAND_MAX) * all;

	map<double, string>::iterator mpit = mp.begin();
	while (mpit != mp.end())
	{
		if (total < (*mpit).first)
			return (*mpit).second;
		++mpit;
	}

	return "";
}

int main(void)
{
	map<string, double> hm;
	hm.insert(pair<string, double>("1", 0.5));
	hm.insert(pair<string, double>("2", 0.3));
	hm.insert(pair<string, double>("3", 0.1));
	hm.insert(pair<string, double>("4", 0.95));
	hm.insert(pair<string, double>("5", 0.05));

	while (1)
		cout << getRandomPrize(hm);

	return 0;
}

详细分析请见我的博客：http://blog.csdn.net/BillCYJ/article/details/79018918

分析

法1：直接从左到右一次相加。每次相加都记录相加后的结果：0.5 0.8 0.9 1.85 1.9，if(产生的随机数<=0.5)则说明选到了物品1,else if(产生的随机数<=0.8)则说明选到了物品2，以此类推。
法2：将0.5 0.3 0.1 0.95 0.05按照比例映射为[0,1]之间的数，再将映射后的五个数从左到右相加。剩余步骤同法1后半部分。

我用的法1

所用数据结构： map和string

代码

#include 
#include 
#include //map由红黑树实现，其中的关键字有序
using namespace std;
string getRandomPrize(map prizeMap)
{
    double sum=0;
    map::iterator iter=prizeMap.begin();
    map tempMap;
    while(iter!=prizeMap.end())
    {
        sum+=iter->second;
        tempMap.insert(pair(iter->first,sum));
        ++iter;
    }
    //计时器原理实现种子，若每次调用时都重新设置种子，那多次调用的结果相同
    //srand((unsigned)time(NULL));
    //产生[a，b]上的随机数 ((double)rand()/RAND_MAX)*(b-a) + a ,其中
    //(double)rand()/RAND_MAX)得一个0~1的随机数
    double total = (double(rand()) / RAND_MAX) * sum;//0到sum间的浮点数
    map::iterator it=tempMap.begin();
    while(it!=tempMap.end())
    {
        if(total<(*it).second)
            return (*it).first;
        ++it;
    }
}
int main()
{
    map prizeMap = {{"1",0.5},{"2",0.3},{"3",0.1},{"4",0.95},
{"5",0.05}};
    int i=5000;
    srand((unsigned)time(NULL));//应在这设种子，这样每次调用结果才随机。
    while(i--)
        cout << getRandomPrize(prizeMap) << endl;
    return 0;
}

}