0

我的目标是独立计算敌人被杀死后会掉落的物品数量。例如，假设有 50 种药水，每种药水都有 50% 的几率掉落，我想根据独立试验随机返回一个从 0 到 50 的数字。

目前，这是我正在使用的代码：

int droppedItems(int n, float probability) {
    int count = 0;
    for (int x = 1; x <= n; ++x) {
        if (random() <= probability) {
            ++count;
        }
    }
    return count;
}

其中probability 是从0.0 到1.0 的数字，random() 返回0.0 到1.0，n 是要丢弃的最大项目数。这是在 C++ 代码中，但是，我实际上使用的是 Visual Basic 6 - 所以没有库可以帮助解决这个问题。

这段代码完美无缺。但是，我想对此进行优化，以便如果 n 恰好是 999999，它不会永远花费（它目前确实如此）。

4

2 回答 2

2

Use the binomial distribution. Wiki - Binomial Distribution

Ideally, use the libraries for whatever language this pseudocode will be written in. There's no sense in reinventing the wheel unless of course you are trying to learn how to invent a wheel.

Specifically, you'll want something that will let you generate random values given a binomial distribution with a probability of success in any given trial and a number of trials.

EDIT :

I went ahead and did this (in python, since that's where I live these days). It relies on the very nice numpy library (hooray, abstraction!):

>>>import numpy
>>>numpy.random.binomial(99999,0.5)
49853
>>>numpy.random.binomial(99999,0.5)
50077

And, using timeit.Timer to check execution time:

# timing it across 10,000 iterations for 99,999 items per iteration
>>>timeit.Timer(stmt="numpy.random.binomial(99999,0.5)", setup="import numpy").timeit(10000) 
0.00927[... seconds]

EDIT 2 :

As it turns out, there isn't a simple way to implement a random number generator based off of the binomial distribution.

There is an algorithm you can implement without library support which will generate random variables from the binomial distribution. You can view it here as a PDF

My guess is that given what you want to use it for (having monsters drop loot in a game), implementing the algorithm is not worth your time. There's room for fudge factor here!

I would change your code like this (note: this is not a binomial distribution):

  1. Use your current code for small values, say n up to 100.
  2. For n greater than one hundred, calculate the value of count for 100 using your current algorithm and then multiply the result by n/100.

Again, if you really want to figure out how to implement the BTPE algorithm yourself, you can - I think the method I give above wins in the trade off between effort to write and getting "close enough".

于 2012-09-20T17:56:54.470 回答
0

正如@IamChuckB 已经指出的那样，关键词是二项分布。当伯努利试验的数量（您的示例中的项目数量）足够大时，泊松分布是一个很好的近似值，它的计算和绘制数字要简单得多（确切的算法在链接的维基百科文章中有详细说明）。

于 2012-09-20T19:46:06.020 回答