Java- Math.random():选择13 x 13三角形数组的元素 [英] Java- Math.random(): Selecting an element of a 13 by 13 triangular array

问题描述

编辑:此问题已解决.如果您想在其他问题上提供帮助，请访问 Java有偏向随机数在三角形阵列中.

This problem is solved. If you would like to help on another problem, please visit Java Biasing Random Numbers in a Triangular Array.

我正在做一个乘法游戏，所以我选择2个介于0和12之间(含0和12)的数字.如果我这样做是这样的:

I'm doing a multiplication game, so I pick 2 numbers between 0 and 12 inclusive. If I do that like this:

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的三角形数组:

the squares (0x0,1x1,2x2,etc) are picked half the time (because 1x2 is the same as 2x1). How can I make all combinations picked at the same frequency? There are 91 possible combinations (n(n+1)/2). If it helps, here is a 13 by 13 triangular array:

{{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))，但我不知道如何拆分它.

I've tried picking the first number and giving the second number a 50% chance of being the first one. This did not work. I tried giving the second number a 1/91 chance of being the first one. This resulted in the smaller numbers being picked a far greater number of times (around 7/91 of the time; it is a smooth, curved increase). I thought about having a single random number: int roll = random.next(91) and then splitting it into 2 entries (like a coordinate (x,y)) but I could not figure out how to split it.

推荐答案

int roll = random.next(91)策略可以正常工作.由于您只选择1个随机数，因此可以确保获得无忧的均匀分布，并具有更好的启动性能.您只需要找到一个公式来标识一个行"在哪里结束而另一个在哪里开始.寻找模式:

The int roll = random.next(91) strategy will work just fine. You get guaranteed, worry-free uniform distribution, and better performance to boot, since you're only picking 1 random number. You simply need to find a formula that identifies where one "row" ends and another begins. Look for the pattern:

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

将它们称为三角数..."

让我们多补充一点.您实际上想找到比所选择的随机roll更近的三角形数 :将您带到右行，而该三角形数与roll的差将使您获得偏移量进入那一行.

Let's flesh this out a bit more. You want to actually find the nearest triangle number smaller than the random roll that you picked: that gets you to the right row, and the difference of that triangle number and roll gets you the offset into that row.

鉴于n ^th 三角数由n*(n+1)/2给出，您如何找到小于roll的最大三角数?考虑到数组的大小，天真的实现应该足够快速:

Given that the n^th triangle number is given by n*(n+1)/2, how do you find the largest one smaller than roll? Given the small size of the array, a naïve implementation should be plenty fast:

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

当然，这很无聊，没有考虑.我们可以做得更好！无论输入多大，我们都可以在固定的时间内完成！由

Of course, that's boring and didn't take any thought. We can do better! We can do it in constant* time, regardless of how big the input is! Start by inverting the function (we only care about the positive root, of course):

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

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

Then truncate the decimal part, and run it back through:

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;

就是这样！

_{*假设原生 函数是恒定时间-}

_{*assuming that the native StrictMath#sqrt(double) function is constant time - I'm actually not sure about this.}

这篇关于Java- Math.random():选择13 x 13三角形数组的元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！