欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

常见面试题:实现微信红包算法

程序员文章站 2022-05-30 22:50:36
关于这个算法问题,由于刚转CS专业大半年,代码能力还是很辣鸡。在面试过程中第一次遇到,结果凉凉。结束后痛定思过,查了一下网上的实现方法。发现很多文章都是相互copy,写的像翔一样,几乎没看到很详细的,经过自己的整理,把自己写的代码记录一下,希望各位大佬下次再遇到此类问题可以轻松应对。代码是基于Python实现先说一下思路众所周知,红包最小值是0.01,我们每次要抢的数额肯定是要在最大值和最小值之间取随机。比如现在是10块钱,分给10个人。那么有一下几个条件:1.每次取值是随机在当前金额范围内...

关于这个算法问题,由于刚转CS专业大半年,代码能力还是很辣鸡。在面试过程中第一次遇到,结果凉凉。
结束后痛定思过,查了一下网上的实现方法。
发现很多文章都是相互copy,写的像翔一样,几乎没看到很详细的,经过自己的整理,把自己写的代码记录一下,希望各位大佬下次再遇到此类问题可以轻松应对。

代码是基于Python实现

先说一下思路

众所周知,红包最小值是0.01,我们每次要抢的数额肯定是要在最大值和最小值之间取随机。比如现在是10块钱,分给10个人。
那么有一下几个条件:
1.每次取值是随机在当前金额范围内
2.每次金额又不能相差太大(比如第一个人抢了9.91,剩下9个人每人0.01,这太虽了)
3.一共抢到的金额加和为总金额

好了,这就是最重要的几点

下面要引入这个算法最关键的点:如何实现每次金额不能相差太大

这里我查了一下资料,真正的发红包算法里面每一次抢到红包金额的数学期望都是相等的,主要核心算法就是每一次红包的金额为当前的(总金额/红包个数*2
比如总金额100元,分10个红包,那么第一个红包的随机区间为(0,20),它的期望为10,同理第二个红包的理论期望值也为10

好了下面上详细的python代码

import random
def randBonus(money,num):
    totalMoney = float(money)
    if num < 1:
        return 
    if num == 1:
        print("第%d个用户,抢到的红包是:%.2f"%(num,money))
        return
    #当最小分割无法满足人数的时候
    if num*0.01>money:
        print("数据非法")
        return
    #当每个人最多只能分到0.01时
    if num*0.01==money:
        for i in range(num):
            print("第%d个用户,抢到的红包是:%.2f"%(i+1,0.01))
        return
    
    #抢到红包的金额范围在(0,(M/N)* 2),最小值是0.01
    i = 0
    while i < num-1:
        #记录本轮随机范围,这里为什么*100,因为rand函数只能生成整数,我想要0.01必须1/100,这里要理解
        max_range = int((totalMoney/(num-i))*2*100)
        get_money = random.randint(1,max_range)
        get_money = float(get_money/100)
        totalMoney = totalMoney-get_money
        print("第%d个用户,抢到的红包是:%.2f"%(i+1,get_money))
        i += 1
    
    print("第%d个用户,抢到的红包是:%.2f"%(num,totalMoney))
    return

代码大家自己测试下吧,如果有问题欢迎指正。

本文地址:https://blog.csdn.net/KeithVV/article/details/107342315