Java-Math.random（）：选择13×13三角形数组中的一个元素

Question

编辑：这个问题解决了。如果您想在另一个问题上提供帮助，请访问Java偏置三角形数组中的随机数。

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

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

正方形（0x0、1x1、2x2等）的拾取时间为一半（因为1x2与2x1相同）。如何使所有组合以相同的频率拾取？有91种可能的组合（n（n1）/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），然后将其拆分为2个条目（如坐标（x， y）），但我不知道如何拆分它。

Answer 1

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）函数是常量时间-我实际上不确定这一点。}