常见面试题:实现微信红包算法
程序员文章站
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
上一篇: 喧嚣之下的机器人实务:坚守工匠精神