请教抽奖算法奖品是 1-100 元整数

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1528 天前的主题，其中的信息可能已经有所发展或是发生改变。

抽奖算法

奖品是 1-100 元整数

要求金额越大抽中概率越小，可以设置数学期望。

各位有什么思路？

整数

算法

奖品

抽中

25 条回复 • 2020-02-14 22:56:13 +08:00

oIMOo

2020-02-12 14:27:47 +08:00

笨办法：
把 1 - 100 按照你的意愿放入一个 list 里面
假设抽中 1 元的概率是抽中 100 元的 666 倍，那就在 list 里面放 1 个 100 和 666 个 1，其它金额同理。
然后随机选列表里面的一个数字。

没睡好，脑子不太转，等楼下……

shadeofgod

2020-02-12 15:39:21 +08:00

```js
function rand(max) {
const _rand = () => ~~(Math.random() * max);
const a = _rand();
return (Math.random() > a / 100) ? a : _rand();
}
```

shadeofgod

2020-02-12 15:40:21 +08:00

哦上面这个只是 max = 100 的时候的，随便写了一下

hearfish

2020-02-12 15:43:40 +08:00

weighted random, 金额越大权重越小

有兴趣的话可以去看看 Alias Method

ferock

2020-02-12 15:44:16 +08:00

@oIMOo #1

这个方案并不是不可行

st2udio

2020-02-12 15:48:07 +08:00

要有个背景吧。抽奖人数是否可估，奖品总数是否固定。避免没被抽完或提前抽完。

daozhihun

2020-02-12 17:26:12 +08:00

有个简单的办法。
假如 1 的概率是 10 的 10 倍，是 100 的 100 倍
则可以考虑 1 ～ 100 为 1，101 ～ 199 为 2，……，5048 ～ 5049 为 99，5050 为 100。
则生成 1 ～ 5050 区间的随机数，按照上面的算法判断对应的区间表示哪个数，比如生成 145 对应的数字是 2。
这样的话 1 ～ 100 的概率递减，且 1 是 10 的 10 倍，是 100 的 100 倍

daozhihun

2020-02-12 17:28:26 +08:00

@daozhihun 概率算错了，但是思路大致这样。总的来说按照概率大小分成不同区间，再计算生成的随机数所在的区间对应的数字

xupefei

2020-02-12 17:47:59 +08:00

带权重的水塘抽样？

ylsc633

2020-02-12 17:50:50 +08:00

http://interview.wzcu.com/%E8%AE%BE%E8%AE%A1%E9%A2%98/%E5%B8%A6%E6%9C%89%E6%9D%83%E9%87%8D%E7%9A%84%E9%9A%8F%E6%9C%BA%E7%AE%97%E6%B3%95.html

实现很简单不过看需求

这个概率跟奖品数量有没有关系！

比如 2 个奖品！ 100 个人抽！每人一次机会！

跟库存有关的话第一个人没中，第二个人概率就是 2/99
跟库存无关的话第一个人没中，第二个人概率还是 2/100

ipwx

2020-02-12 18:02:55 +08:00

https://docs.scipy.org/doc/numpy-1.15.0/reference/generated/numpy.random.multinomial.html

设好合适的参数，请。

freakxx

2020-02-12 18:03:10 +08:00

看需求，
比如总金额固定，最简单的就是你事先生成数组，你自己按比例配进去；

还有一种比较简单的，就是你划定好区间，随机生成一个数，然后用二分插入的算法做。
x = [1, 100, 300, 400 ... 9990, 10000]
y = [1, 2, 3 ... 100]

index = bisect_search(x)
y[index]

ccoming

2020-02-12 18:07:09 +08:00

会出现全部不中奖的情况么？

ETiV

2020-02-12 19:50:58 +08:00

https://zh.wikipedia.org/wiki/%E6%B3%8A%E6%9D%BE%E5%88%86%E4%BD%88

我首先想到的是泊松分布 lambda=1 的曲线

----
话说这种出真钱的概率不能是前后无关的吧
比如服务器记录一下今天 100 块已经被抽出去了，那今天就不应该再出现 100 块了…

dji38838c

2020-02-12 20:31:26 +08:00

要求金额越大抽中概率越小，并且可以设定期望值，可以用几何分布。
可以设定期待值 expected_value, 和抽奖的次数 n
np.random.geometric(p = 1.0/expected_value, size = n)
注意，如果期待值高的话，随机产生的值可能超出 100。

oIMOo

2020-02-12 21:45:20 +08:00

楼主不要被我 1 楼的回复迷惑，我现在清醒了。
#4 的关键词可以参考，下面这个也可以看看
https://medium.com/@peterkellyonline/weighted-random-selection-3ff222917eb6

kdashl

2020-02-12 21:51:22 +08:00

1 加到 100 是 5050...100 就是 1/5050,99 就是 2/5050.....以此类推到 1 就是 100/5050

CEBBCAT

2020-02-13 02:18:43 +08:00 via Android

这个我写过，网上也是稍微搜下就有。要是明天我还记得就过来贴代码

CEBBCAT

2020-02-13 02:23:05 +08:00 via Android

一个变量存权重之和，random 一个 r 然后对刚才那个 sum 求模。循环加权值，直到加和大于等于得到的模

VDimos

2020-02-13 02:30:53 +08:00 via Android

box muller 算法，不知道行不行

smdbh

2020-02-13 10:55:00 +08:00

最简单的方法，设一个数组，数字越小，重复个数就越多，然后随机函数抽一个。

coderEOS

2020-02-13 15:00:30 +08:00

@rets = [1, 2, 3, 4, 15]
@quan = [10, 30, 50, 70, 100]
@randMax = @quan.inject(:+)
def clacOneRet
randV = rand(@randMax) + 1
@quan.each_index do |i|
randV = randV - @quan[i]
return @rets[i] if randV <= 0
end
return -1
end

nums = {}
@rets.each {|k| nums[k] = 0}
for i in 1..1000
v = clacOneRet
nums[v] = nums[v].to_i + 1
end
puts nums ## {1=>31, 2=>123, 3=>182, 4=>263, 15=>401}

coderEOS

2020-02-13 15:35:17 +08:00

<body class="vscode-light">
<h1 id="%e5%85%b6%e5%ae%9e%e5%b0%b1%e6%98%af%e7%ae%80%e5%8d%95%e7%9a%84%e5%b8%a6%e6%9d%83%e7%ae%97%e6%b3%95">其实就是简单的带权算法</h1>
<pre><code class="language-ruby"><div>@rets = [1, 2, 3, 4, 15]
@quan = [10, 30, 50, 70, 100]
@randMax = @quan.inject(:+)
def clacOneRet
randV = rand(@randMax) + 1
@quan.each_index do |i|
randV = randV - @quan[i]
return @rets[i] if randV <= 0
end
return -1
end

nums = {}
@rets.each {|k| nums[k] = 0}
for i in 1..1000
v = clacOneRet
nums[v] = nums[v].to_i + 1
end
puts nums ## {1=>31, 2=>123, 3=>182, 4=>263, 15=>401}
</div></code></pre>

pmispig

2020-02-13 19:29:37 +08:00

最简单的实现方法 100 元 = 1% 1 元=99%
这个几率太高的化，统一乘以一个比例

Windowsxpplayer

2020-02-14 22:56:13 +08:00 via Android

@st2udio 都是不限，奖品不是现金而且余额

请教抽奖算法 奖品是 1-100 元整数

请教抽奖算法奖品是 1-100 元整数