分钱问题
x 元分给 y 个人,每个人可以分到的金额为 m 到 n 元,且 m < x/y < n。
思路很多,但都有缺陷。对于上述问题,除了实现明面上的分配问题,还需要考虑:
- 是否实时性分配、而不是预分配
- 是否需要符合某种分布方案
- 伯努利分布
- 二项式分布
- 几何分布
- 负二项式分布
- 超几何分布
- 泊松分布
- 均匀分布
- 正态分布
- 伽马分布
- 指数分布
这里面牵扯到不少概率论的问题,想清楚算法再去想实现。
方案一:快速预分配
使用预分配的方案,在初次分配后随即给随机用户分钱,只要用户可持有的金额没超过最大值即成立,否则这次划转失效。
package main
import (
"fmt"
"math/rand"
"time"
)
var (
totalMoney = 100.00
person = 10
min = 9.5
max = 10.5
)
func main() {
// 假设精确到分,即不使用浮点数
var resultOut [10]float64
var result [10]int
totalMoneyInt := int(totalMoney * 100)
minInt := int(min * 100)
maxInt := int(max * 100)
// 预分配 9.5 元,实现第一个条件
for index := range result {
result[index] = minInt
}
remainMoney := totalMoneyInt - minInt*person
rand.Seed(time.Now().Unix())
oneAlloct := 0
randomUser := 0
cycleCount := 0
for {
// 每次循环获得一个随机值,然后随机分配给一个用户
cycleCount++
if remainMoney == 0 {
break
} else if remainMoney < maxInt-minInt {
oneAlloct = remainMoney
} else {
oneAlloct = rand.Intn(maxInt - minInt)
}
randomUser = rand.Intn(person)
if result[randomUser]+oneAlloct > maxInt {
continue
}
result[randomUser] = result[randomUser] + oneAlloct
remainMoney = remainMoney - oneAlloct
}
for index := range result {
resultOut[index] = float64(result[index]) / 100
}
fmt.Printf("总共循环了:%d次\n每个人可以分配的金额为:%v", cycleCount, resultOut)
}
方案二:即时分配
参考微信发送红包机制:每个人可以抢到的金额为 [0.01, 平均值*2]。
package main
import (
"fmt"
"math/rand"
"time"
)
var (
totalMoney = 100.00
person = 10
min = 9.5
max = 10.5
)
func main() {
// 假设精确到分,即不使用浮点数
totalMoneyInt := int(totalMoney * 100)
minInt := int(min * 100)
// 预分配 9.5 元,实现第一个条件
remainMoney := totalMoneyInt - minInt*person
remainMoneyAvg := remainMoney / person
rand.Seed(time.Now().Unix())
oneAlloct := 0
cycleCount := 0
for i := 0; i < person; i++ {
// 最多循环10次,每次可随机的金额为 [0, 平均可分配*2]
// 最后一次直接赋值
cycleCount++
if i < (person - 1) {
oneAlloct = rand.Intn(remainMoneyAvg * 2)
remainMoney -= oneAlloct
remainMoneyAvg = remainMoney / (person - i - 1)
} else {
oneAlloct = remainMoney
}
fmt.Printf("第%d个人分到了%.2f元\n", i+1, float64(950+oneAlloct)/100)
}
fmt.Printf("总共循环了:%d次\n", cycleCount)
}