Java数学。random（）：选择13×13三角形阵列的元素

Question

编辑：此问题已解决。如果您想在另一个问题上提供帮助，请访问Java Biasing Random Numbers in a Triangular Array

---

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

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

正方形（0x0、1x1、2x2等）的拾取时间为一半（因为1x2与2x1相同）。如何使所有组合以相同频率拾取？有91种可能的组合（n（n+1）/2）。如果有帮助，下面是一个13乘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)，然后把它分成两个条目（比如坐标（x，y）），但我不知道如何把它分开

Answer 1

{}策略会很好地工作。您可以得到有保证的、无需担心的均匀分布，以及更好的引导性能，因为您只需选择1个随机数。你只需要找到一个公式来确定一行的结束和另一行的开始。寻找模式：

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

它们被称为"triangular numbers..."是有原因的

让我们再充实一点。实际上，你想要找到比随机选取的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

当然，这很无聊，而且没有考虑任何问题。我们可以做得更好！无论输入量有多大，我们都可以在恒定的时间内完成！从inverting the function开始（当然，我们只关心正根）：

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;

That's it!

---

_{*假设本机^{}函数是常数时间-I'm actually not sure about this.}