给定一个函数，它产生的是1到5之间的随机整数，写一个函数，它产生的是1到7之间的随机整数。
当前回答
如果有人能就这一点给我反馈，那就太酷了，我使用了没有assert模式的JUNIT，因为在Eclipse中运行它很容易，也很快速，我也可以只定义一个主方法。顺便说一下，我假设rand5给出的值为0-4，加上1将得到1-5,rand7也是如此……所以讨论应该是解决方案，它的分布，而不是它是从0-4还是1-5…
package random;
import java.util.Random;
import org.junit.Test;
public class RandomTest {
@Test
public void testName() throws Exception {
long times = 100000000;
int indexes[] = new int[7];
for(int i = 0; i < times; i++) {
int rand7 = rand7();
indexes[rand7]++;
}
for(int i = 0; i < 7; i++)
System.out.println("Value " + i + ": " + indexes[i]);
}
public int rand7() {
return (rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5()) % 7;
}
public int rand5() {
return new Random().nextInt(5);
}
}
当我运行它时，我得到这样的结果:
Value 0: 14308087
Value 1: 14298303
Value 2: 14279731
Value 3: 14262533
Value 4: 14269749
Value 5: 14277560
Value 6: 14304037
这似乎是一个非常公平的分配，不是吗?
如果我将rand5()添加更少或更多次(其中次数不能被7整除)，分布会清楚地显示偏移量。例如，将rand5()相加3次:
Value 0: 15199685
Value 1: 14402429
Value 2: 12795649
Value 3: 12796957
Value 4: 14402252
Value 5: 15202778
Value 6: 15200250
因此，这将导致以下结果:
public int rand(int range) {
int randomValue = 0;
for(int i = 0; i < range; i++) {
randomValue += rand5();
}
return randomValue % range;
}
然后，我可以更进一步:
public static final int ORIGN_RANGE = 5;
public static final int DEST_RANGE = 7;
@Test
public void testName() throws Exception {
long times = 100000000;
int indexes[] = new int[DEST_RANGE];
for(int i = 0; i < times; i++) {
int rand7 = convertRand(DEST_RANGE, ORIGN_RANGE);
indexes[rand7]++;
}
for(int i = 0; i < DEST_RANGE; i++)
System.out.println("Value " + i + ": " + indexes[i]);
}
public int convertRand(int destRange, int originRange) {
int randomValue = 0;
for(int i = 0; i < destRange; i++) {
randomValue += rand(originRange);
}
return randomValue % destRange;
}
public int rand(int range) {
return new Random().nextInt(range);
}
我尝试用不同的值替换destRange和originRange(甚至ORIGIN为7,DEST为13)，我得到了这样的分布:
Value 0: 7713763
Value 1: 7706552
Value 2: 7694697
Value 3: 7695319
Value 4: 7688617
Value 5: 7681691
Value 6: 7674798
Value 7: 7680348
Value 8: 7685286
Value 9: 7683943
Value 10: 7690283
Value 11: 7699142
Value 12: 7705561
从这里我可以得出的结论是，你可以通过求和起始随机“目的地”时间来将任意随机改变为任意随机。这将得到一种高斯分布(中间值更有可能，边缘值更不常见)。然而，目标模量似乎均匀地分布在这个高斯分布中…如果能得到数学家的反馈就太好了……
最酷的是，成本是100%可预测的和恒定的，而其他解决方案导致无限循环的概率很小……
其他回答
我觉得你们都想多了。难道这个简单的解决方案行不通吗?
int rand7(void)
{
static int startpos = 0;
startpos = (startpos+5) % (5*7);
return (((startpos + rand5()-1)%7)+1);
}
int rand7() {
int value = rand5()
+ rand5() * 2
+ rand5() * 3
+ rand5() * 4
+ rand5() * 5
+ rand5() * 6;
return value%7;
}
与选定的解决方案不同，该算法将在常数时间内运行。然而，它对rand5的调用比所选解决方案的平均运行时间多2次。
请注意，这个生成器并不完美(数字0比任何其他数字都有0.0064%的可能性)，但对于大多数实际目的，保证恒定的时间可能比这种不准确性更重要。
解释
这个解源于数字15624能被7整除的事实，因此，如果我们可以随机且均匀地生成从0到15624的数字，然后对7取余，我们就可以得到一个近乎均匀的rand7生成器。将rand5滚动6次，将0到15624之间的数字统一生成，并使用这些数字组成以5为基数的数字，如下所示:
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
mod 7的属性允许我们稍微简化一下方程:
5^5 = 3 mod 7
5^4 = 2 mod 7
5^3 = 6 mod 7
5^2 = 4 mod 7
5^1 = 5 mod 7
So
rand5 * 5^5 + rand5 * 5^4 + rand5 * 5^3 + rand5 * 5^2 + rand5 * 5 + rand5
就变成了
rand5 * 3 + rand5 * 2 + rand5 * 6 + rand5 * 4 + rand5 * 5 + rand5
理论
15624这个数字不是随机选择的，而是可以用费马小定理来发现的，该定理指出，如果p是质数，那么
a^(p-1) = 1 mod p
这就得到，
(5^6)-1 = 0 mod 7
(5^6)-1等于
4 * 5^5 + 4 * 5^4 + 4 * 5^3 + 4 * 5^2 + 4 * 5 + 4
这是一个以5为底的数，因此我们可以看到，这种方法可以用于从任何随机数发生器到任何其他随机数发生器。尽管在使用指数p-1时总是会引入对0的小偏差。
为了更准确地推广这种方法，我们可以有这样一个函数:
def getRandomconverted(frm, to):
s = 0
for i in range(to):
s += getRandomUniform(frm)*frm**i
mx = 0
for i in range(to):
mx = (to-1)*frm**i
mx = int(mx/to)*to # maximum value till which we can take mod
if s < mx:
return s%to
else:
return getRandomconverted(frm, to)
这里有很多解决方案没有产生均匀分布，许多评论指出了这一点，但这个问题并没有把它作为一个要求。最简单的解决方案是:
int rand_7() { return rand_5(); }
1 - 5范围内的随机整数显然在1 - 7范围内。从技术上讲，最简单的解决方法是返回一个常数，但那太琐碎了。
然而，我认为rand_5函数的存在是一个转移注意力的问题。假设问题是“生成一个均匀分布的伪随机数生成器，输出范围为1 - 7”。这是一个简单的问题(技术上不简单，但已经解决了，所以您可以查阅它)。
另一方面，如果问题被解释为你实际上有一个真正的随机数生成器，用于范围为1 - 5的整数(而不是伪随机)，那么解决方案是:
1) examine the rand_5 function
2) understand how it works
3) profit
如果有人能就这一点给我反馈，那就太酷了，我使用了没有assert模式的JUNIT，因为在Eclipse中运行它很容易，也很快速，我也可以只定义一个主方法。顺便说一下，我假设rand5给出的值为0-4，加上1将得到1-5,rand7也是如此……所以讨论应该是解决方案，它的分布，而不是它是从0-4还是1-5…
package random;
import java.util.Random;
import org.junit.Test;
public class RandomTest {
@Test
public void testName() throws Exception {
long times = 100000000;
int indexes[] = new int[7];
for(int i = 0; i < times; i++) {
int rand7 = rand7();
indexes[rand7]++;
}
for(int i = 0; i < 7; i++)
System.out.println("Value " + i + ": " + indexes[i]);
}
public int rand7() {
return (rand5() + rand5() + rand5() + rand5() + rand5() + rand5() + rand5()) % 7;
}
public int rand5() {
return new Random().nextInt(5);
}
}
当我运行它时，我得到这样的结果:
Value 0: 14308087
Value 1: 14298303
Value 2: 14279731
Value 3: 14262533
Value 4: 14269749
Value 5: 14277560
Value 6: 14304037
这似乎是一个非常公平的分配，不是吗?
如果我将rand5()添加更少或更多次(其中次数不能被7整除)，分布会清楚地显示偏移量。例如，将rand5()相加3次:
Value 0: 15199685
Value 1: 14402429
Value 2: 12795649
Value 3: 12796957
Value 4: 14402252
Value 5: 15202778
Value 6: 15200250
因此，这将导致以下结果:
public int rand(int range) {
int randomValue = 0;
for(int i = 0; i < range; i++) {
randomValue += rand5();
}
return randomValue % range;
}
然后，我可以更进一步:
public static final int ORIGN_RANGE = 5;
public static final int DEST_RANGE = 7;
@Test
public void testName() throws Exception {
long times = 100000000;
int indexes[] = new int[DEST_RANGE];
for(int i = 0; i < times; i++) {
int rand7 = convertRand(DEST_RANGE, ORIGN_RANGE);
indexes[rand7]++;
}
for(int i = 0; i < DEST_RANGE; i++)
System.out.println("Value " + i + ": " + indexes[i]);
}
public int convertRand(int destRange, int originRange) {
int randomValue = 0;
for(int i = 0; i < destRange; i++) {
randomValue += rand(originRange);
}
return randomValue % destRange;
}
public int rand(int range) {
return new Random().nextInt(range);
}
我尝试用不同的值替换destRange和originRange(甚至ORIGIN为7,DEST为13)，我得到了这样的分布:
Value 0: 7713763
Value 1: 7706552
Value 2: 7694697
Value 3: 7695319
Value 4: 7688617
Value 5: 7681691
Value 6: 7674798
Value 7: 7680348
Value 8: 7685286
Value 9: 7683943
Value 10: 7690283
Value 11: 7699142
Value 12: 7705561
从这里我可以得出的结论是，你可以通过求和起始随机“目的地”时间来将任意随机改变为任意随机。这将得到一种高斯分布(中间值更有可能，边缘值更不常见)。然而，目标模量似乎均匀地分布在这个高斯分布中…如果能得到数学家的反馈就太好了……
最酷的是，成本是100%可预测的和恒定的，而其他解决方案导致无限循环的概率很小……
//返回0-5之间概率相等的随机数 函数rand5() { return Math.floor(Math.random() * 6); ｝ //返回0-7之间概率相等的随机数 函数rand7() { If (rand5() % 2 == 0 && rand5() % 2 == 0) { 返回6 + rand5() % 2; }其他{ 返回rand5 (); ｝ ｝ console.log (rand7 ());
