给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
这里允许作业题吗?
这个函数进行粗略的“以5为基数”的数学运算,生成0到6之间的数字。
function rnd7() {
do {
r1 = rnd5() - 1;
do {
r2=rnd5() - 1;
} while (r2 > 1);
result = r2 * 5 + r1;
} while (result > 6);
return result + 1;
}
其他回答
我首先想到的是这个。但我不知道它是否均匀分布。 在python中实现
进口随机 def rand5 (): 返回random.randint(1、5) def rand7 (): 返回((rand5() -1) * rand5()) %7)+1
这里有很多解决方案没有产生均匀分布,许多评论指出了这一点,但这个问题并没有把它作为一个要求。最简单的解决方案是:
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
Python:有一个简单的两行答案,它使用空间代数和模量的组合。这不是直观的。我对它的解释令人困惑,但却是正确的。
知道5*7=35 7/5 = 1余数为2。如何保证余数之和始终为0?5*[7/5 = 1余数2]——> 35/5 = 7余数0
想象一下,我们有一条丝带,缠在一根周长为7的杆子上。丝带需要35个单位才能均匀地缠绕。随机选择7个色带片段len=[1…5]。忽略换行的有效长度与将rand5()转换为rand7()的方法相同。
import numpy as np
import pandas as pd
# display is a notebook function FYI
def rand5(): ## random uniform int [1...5]
return np.random.randint(1,6)
n_trials = 1000
samples = [rand5() for _ in range(n_trials)]
display(pd.Series(samples).value_counts(normalize=True))
# 4 0.2042
# 5 0.2041
# 2 0.2010
# 1 0.1981
# 3 0.1926
# dtype: float64
def rand7(): # magic algebra
x = sum(rand5() for _ in range(7))
return x%7 + 1
samples = [rand7() for _ in range(n_trials)]
display(pd.Series(samples).value_counts(normalize=False))
# 6 1475
# 2 1475
# 3 1456
# 1 1423
# 7 1419
# 4 1393
# 5 1359
# dtype: int64
df = pd.DataFrame([
pd.Series([rand7() for _ in range(n_trials)]).value_counts(normalize=True)
for _ in range(1000)
])
df.describe()
# 1 2 3 4 5 6 7
# count 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000 1000.000000
# mean 0.142885 0.142928 0.142523 0.142266 0.142704 0.143048 0.143646
# std 0.010807 0.011526 0.010966 0.011223 0.011052 0.010983 0.011153
# min 0.112000 0.108000 0.101000 0.110000 0.100000 0.109000 0.110000
# 25% 0.135000 0.135000 0.135000 0.135000 0.135000 0.135000 0.136000
# 50% 0.143000 0.142000 0.143000 0.142000 0.143000 0.142000 0.143000
# 75% 0.151000 0.151000 0.150000 0.150000 0.150000 0.150000 0.151000
# max 0.174000 0.181000 0.175000 0.178000 0.189000 0.176000 0.179000
从一个扩大浮动范围的链接来到这里。这个更有趣。而不是我是如何得出结论的,我突然想到,对于一个给定的随机整数生成函数f,以“基数”b(在这种情况下是4,我会告诉为什么),它可以展开如下:
(b^0 * f() + b^1 * f() + b^2 * f() .... b^p * f()) / (b^(p+1) - 1) * (b-1)
这将把随机生成器转换为FLOAT生成器。我将在这里定义2个参数b和p。虽然这里的“基数”是4,但b实际上可以是任何东西,它也可以是无理数等p,我称之为精度是你想要的浮点生成器的良好粒度的程度。可以把这看作是对rand7的每次调用对rand5的调用数。
但我意识到,如果你把b设为底数+1(在这种情况下是4+1 = 5),这是一个最佳点,你会得到均匀的分布。首先摆脱这个1-5生成器,它实际上是rand4() + 1:
function rand4(){
return Math.random() * 5 | 0;
}
为了达到这个目的,你可以用rand5()-1替换rand4
接下来是将rand4从整数生成器转换为浮点生成器
function toFloat(f,b,p){
b = b || 2;
p = p || 3;
return (Array.apply(null,Array(p))
.map(function(d,i){return f()})
.map(function(d,i){return Math.pow(b,i)*d})
.reduce(function(ac,d,i){return ac += d;}))
/
(
(Math.pow(b,p) - 1)
/(b-1)
)
}
这将把我写的第一个函数应用到一个给定的rand函数。试一试:
toFloat(rand4) //1.4285714285714286 base = 2, precision = 3
toFloat(rand4,3,4) //0.75 base = 3, precision = 4
toFloat(rand4,4,5) //3.7507331378299122 base = 4, precision = 5
toFloat(rand4,5,6) //0.2012288786482335 base = 5, precision =6
...
现在,您可以将这个浮动范围(0-4 include)转换为任何其他浮动范围,然后将其降级为整数。这里我们的底是4,因为我们处理的是rand4,因此b=5的值会给你一个均匀分布。当b增长超过4时,你将开始在分布中引入周期性间隙。我测试了从2到8的b值,每个值都有3000分,并与原生数学进行了比较。随机的javascript,在我看来甚至比本机本身更好:
http://jsfiddle.net/ibowankenobi/r57v432t/
对于上面的链接,单击分布顶部的“bin”按钮以减小分箱大小。最后一个图表是原生数学。随机的,第四个d=5是均匀的。
在你得到浮动范围后,要么与7相乘并抛出小数部分,要么与7相乘,减去0.5并四舍五入:
((toFloat(rand4,5,6)/4 * 7) | 0) + 1 ---> occasionally you'll get 8 with 1/4^6 probability.
Math.round((toFloat(rand4,5,6)/4 * 7) - 0.5) + 1 --> between 1 and 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%可预测的和恒定的,而其他解决方案导致无限循环的概率很小……