首页 > 试题广场 >

牛客网在一周年纪念系列活动中，其中有一个抽奖的环节，在1亿会

[问答题]

牛客网在一周年纪念系列活动中，其中有一个抽奖的环节，在1亿会员中随机抽出100万幸运会员，并发送相应礼品。
请帮助牛客网设计一个抽奖算法。要求：
1）不能重复中奖
2）个位数为6的用户中奖概率是其他用户的2倍
3）rand()生成的最大值不超过2的10次方-1

牛客145121328号

int Rand(int N)
{
    return rand() % N;
}

void good_luck_choose()
{
    // 尾号为6的几率翻倍，因为每10个里面有一个6，所以总数多1.1倍即可；
    const int N = 110'000'000;

    set<int> choosed;
    while (true)
    {
        int r = Rand(110) * 1'000'000 + Rand(1000) * 1'000 + Rand(1000);
        if (r >= 100'000'000) {
            r = (r - 100'000'000) * 10 + 6;
        }

        if (choosed.find(r) == choosed.end()) {
            choosed.insert(r);
        }

        if (choosed.size() == 1'000'000) {
            break;
        }
    }
    return;
}

发表于 2021-11-13 16:12:27 回复(0)

Heap

有个简单的思路。

概率抽取比较方便的是《蓄水池抽样方法》

那么该题其实可以分为两部分：

从尾数为6的数后面抽取的概率比从其他中抽取的概率大6倍。

那么可以列公式得到

10（百万人） * 6 * p + 90（百万人) * p = 1（百万人）

那么可得结果是

从尾数为6的1000万人中抽取 40万，从其他9000万人中抽取60万

所以：

（m-k）/ (n-i-1) k表示已经抽取的数量。m表示需要抽取的总数。n表示总人数，i表示第几个人。

本题完毕。

发表于 2015-08-19 17:26:55 回复(1)

咔嚓

//1亿会员中个位数为6的有1e8个，所以我们将总数设为1.1e9个，
//如果抽中的数x大于1e9，相当于抽中个位数为6的数y=((x-1e9-1)*10+6)。
//抽中每个人的概率为1/1.1e9，

//rand()取值为0～1023，如果取值超过1000则重新取值，所以可以随机取值0～999.
//用3个rand()，然后1.1e6*rand()+1e3*rand()+rand()，
//可以得到0~1.1e9之间的随机值。


int Rand(void) {
    int ret;
    return (ret = rand()) >= 1000 ? Rand() : ret;
}
//抽取一次
int ExtraceOnce(void) {
    int num;
    num = 1.1e6*Rand()+1e3*Rand()+Rand();
    if(num > 1e9)
         num = (num - 1e9 - 1) * 10 + 6;
    return num;
}
void foo (void) {
    //set保存找到的值
    hash_set<int> set;
    for(int i = 0; i < 1e6； ++i) {
        int num = ExtraceOnce();
        //避免重复
        while(set.find(num) != set.end())
            num = ExtraceOnce();
        set.insert(num);
    }    
}

发表于 2015-08-12 10:42:32 回复(0)

提交观点

问题信息

阿里巴巴系统设计

上传者：小耀

难度：

3条回答 25收藏 13230浏览

牛客网在一周年纪念系列活动中，其中有一个抽奖的环节，在1亿会

问题信息

热门推荐

相关试题