[!] 讨论: 随机红包算法问题

2019-09-28 10:31:29 +08:00
 zhuzhibin

我相信大家都有自己的看法,所以我也是抱着学习的心态问这个问题

举个例子了呗:

10 人群聊咯,我发了 100 元红包,然后 10 人随机瓜分 100 元红包

方案应该很多,例如随机比例等等 ,嘿嘿 大家畅所欲言哈,想请教下各位

2998 次点击
所在节点    问与答
17 条回复
niknik
2019-09-28 10:37:25 +08:00
一条绳子,九个结,每段长度,然后十段绳子随机分出去(自我猜测应该是这样的,嘻嘻)
Baymaxbowen
2019-09-28 10:38:48 +08:00
<amp-youtube data-videoid="KYd8pSiLFiw" layout="responsive" width="480" height="270"></amp-youtube>
memedahui
2019-09-28 10:40:52 +08:00
import java.util.LinkedList;
import java.util.List;

/**
* Function: 模拟微信红包生成,以分为单位
*
* @author crossoverJie
* Date: 03/01/2018 16:52
* @since JDK 1.8
*/
public class RedPacket {

/**
* 生成红包最小值 1 分
*/
private static final int MIN_MONEY = 1;

/**
* 生成红包最大值 200 人民币
*/
private static final int MAX_MONEY = 200 * 100;

/**
* 小于最小值
*/
private static final int LESS = -1;
/**
* 大于最大值
*/
private static final int MORE = -2;

/**
* 正常值
*/
private static final int OK = 1;

/**
* 最大的红包是平均值的 TIMES 倍,防止某一次分配红包较大
*/
private static final double TIMES = 2.1F;

private int recursiveCount = 0;

public List<Integer> splitRedPacket(int money, int count) {
List<Integer> moneys = new LinkedList<>();

//金额检查,如果最大红包 * 个数 < 总金额;则需要调大最小红包 MAX_MONEY
if (MAX_MONEY * count <= money) {
System.err.println("请调大最小红包金额 MAX_MONEY=[" + MAX_MONEY + "]");
return moneys ;
}


//计算出最大红包
int max = (int) ((money / count) * TIMES);
max = max > MAX_MONEY ? MAX_MONEY : max;

for (int i = 0; i < count; i++) {
//随机获取红包
int redPacket = randomRedPacket(money, MIN_MONEY, max, count - i);
moneys.add(redPacket);
//总金额每次减少
money -= redPacket;
}

return moneys;
}

private int randomRedPacket(int totalMoney, int minMoney, int maxMoney, int count) {
//只有一个红包直接返回
if (count == 1) {
return totalMoney;
}

if (minMoney == maxMoney) {
return minMoney;
}

//如果最大金额大于了剩余金额 则用剩余金额 因为这个 money 每分配一次都会减小
maxMoney = maxMoney > totalMoney ? totalMoney : maxMoney;

//在 minMoney 到 maxMoney 生成一个随机红包
int redPacket = (int) (Math.random() * (maxMoney - minMoney) + minMoney);

int lastMoney = totalMoney - redPacket;

int status = checkMoney(lastMoney, count - 1);

//正常金额
if (OK == status) {
return redPacket;
}

//如果生成的金额不合法 则递归重新生成
if (LESS == status) {
recursiveCount++;
System.out.println("recursiveCount==" + recursiveCount);
return randomRedPacket(totalMoney, minMoney, redPacket, count);
}

if (MORE == status) {
recursiveCount++;
System.out.println("recursiveCount===" + recursiveCount);
return randomRedPacket(totalMoney, redPacket, maxMoney, count);
}

return redPacket;
}

/**
* 校验剩余的金额的平均值是否在 最小值和最大值这个范围内
*
* @param lastMoney
* @param count
* @return
*/
private int checkMoney(int lastMoney, int count) {
double avg = lastMoney / count;
if (avg < MIN_MONEY) {
return LESS;
}

if (avg > MAX_MONEY) {
return MORE;
}

return OK;
}


public static void main(String[] args) {
RedPacket redPacket = new RedPacket();
List<Integer> redPackets = redPacket.splitRedPacket(20000, 100);
System.out.println(redPackets);

int sum = 0;
for (Integer red : redPackets) {
sum += red;
}
System.out.println(sum);
}

}






注 引用至:github.com/crossoverJie
lhx2008
2019-09-28 10:40:53 +08:00
100 元,随机在 0-100 9 个数,加上 0 和 100,相邻的数距离有 10 个,就是 10 个红包
Raymon111111
2019-09-28 10:41:44 +08:00
微信的逻辑是每次要抢的时候去随机生成一个合法的数字
zhuzhibin
2019-09-28 10:43:39 +08:00
@Baymaxbowen 老哥 我 ip 被 ban 了呜呜 解封后我倒回来看看
zhuzhibin
2019-09-28 10:48:48 +08:00
@lhx2008 如果刚好随机的情况是平均分配呢 ?每个人刚好 10 元
lhx2008
2019-09-28 10:53:14 +08:00
@zhuzhibin #7 没问题呀,随机到 0 10 20 30 40 50 60 70 80 90 100 就是平均分配了。要说 bug 就是随机数要去重,如果有重复要重新随机一个。
Cbdy
2019-09-28 11:19:29 +08:00
随手写了一个
wysnylc
2019-09-28 11:57:26 +08:00
红包算法都是预先生成,发红包的时候已经根据红包领取人数随机好了所有金额
任何按照随机数来的都不可避免的可能会出现极大和极小值
这不是算法问题,是业务问题
x86
2019-09-28 11:58:05 +08:00
@Raymon111111 #5 我也感觉是这样每次点的时候拿剩余额度在随机一个
snw
2019-09-28 12:45:51 +08:00
@wysnylc
微信的红.包就不是这样。
geelaw
2019-09-28 15:05:18 +08:00
https://geelaw.blog/entries/red-envelope/

这个问题其实很无聊 - - 从我两个小时就能排版完毕就能看出来。
w292614191
2019-09-28 16:38:06 +08:00
我记得,过年群里:80 元。
我得了 79,另一个人 1 块钱。
简直逆天。
zhuzhibin
2019-09-28 19:02:16 +08:00
@geelaw 老哥 👍 感谢回复
DevRoss
2019-09-28 19:04:24 +08:00
分层抽样减少方差呗
zhuchaowe
2019-09-28 20:25:39 +08:00
微信的逻辑: random(0.01,0.5*restMoney)

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/605033

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX