4

编辑：这个问题解决了。如果您想帮助解决另一个问题，请访问Java Biasing Random Numbers in a Triangular Array。

我正在做一个乘法游戏，所以我选择了 0 到 12 之间的 2 个数字。如果我这样做：

int num1 = (int)(Math.random() * 13);
int num2 = (int)(Math.random() * 13);

方块（0x0、1x1、2x2 等）被挑选了一半（因为 1x2 与 2x1 相同）。如何以相同的频率挑选所有组合？有 91 种可能的组合 (n(n+1)/2)。如果有帮助，这里有一个 13 x 13 的三角形数组：

{{0},
 {0,0},
 {0,0,0},
 {0,0,0,0},
 {0,0,0,0,0},
 {0,0,0,0,0,0},
 {0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0}};

我试过选择第一个数字，并给第二个数字 50% 的机会成为第一个数字。这没有用。我试着给第二个数字 1/91 的机会成为第一个。这导致较小的数字被选择的次数要多得多（大约 7/91 的时间；这是一个平滑的曲线增加）。我想过有一个随机数：int roll = random.next(91)然后将其拆分为 2 个条目（如坐标 (x,y)），但我不知道如何拆分它。

4

1 回答 1

6

该int roll = random.next(91)策略将正常工作。由于您只选择 1 个随机数，因此您将获得有保证、无忧的均匀分布和更好的启动性能。您只需要找到一个公式来确定一个“行”在哪里结束而另一个“行”从哪里开始。寻找模式：

0, 1, 3, 6, 10, 15, ...

它们被称为“三角数……”是有原因的

让我们再充实一点。您实际上希望找到比您选择的随机数更小roll的最近的三角形数：这会让您找到正确的行，以及该三角形数的差异并roll让您获得该行的偏移量。

鉴于n第 th 个三角形数由 给出n*(n+1)/2，你如何找到小于 的最大一个roll？考虑到数组的小尺寸，一个简单的实现应该足够快：

int largestTriangleNumberSmallerThan(int x) {
    int i = 0;
    int last = 0;
    while (true) {
        int triangle = i*(i+1)/2;
        if (triangle > x) return last;
        last = triangle;
        i++;
    }
}

http://ideone.com/vzQEBz

当然，这很无聊，没有考虑任何想法。我们可以做得更好！无论输入有多大，我们都可以在恒定的时间内完成！从反转函数开始（当然，我们只关心正根）：

n = (Math.sqrt(8y + 1) - 1)/2

然后截断小数部分，并通过以下方式运行：

int largestTriangleNumberSmallerThan(int x) {
    int n = (int) (Math.sqrt(8*x + 1) - 1)/2;
    return n*(n+1)/2;
}

http://ideone.com/1qBHfX

把它们放在一起：

int roll = random.nextInt(91);
int num1 = (int) (Math.sqrt(8*roll + 1) - 1)/2;
int num2 = roll - num1*(num1+1)/2;

就是这样！

*假设本机StrictMath#sqrt(double)函数是常数时间 -我实际上对此不确定。

于 2013-04-02T02:53:34.517 回答