给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
package CareerCup;
public class RangeTransform {
static int counter = (int)(Math.random() * 5 + 1);
private int func() {
return (int) (Math.random() * 5 + 1);
}
private int getMultiplier() {
return counter % 5 + 1;
}
public int rangeTransform() {
counter++;
int count = getMultiplier();
int mult = func() + 5 * count;
System.out.println("Mult is : " + 5 * count);
return (mult) % 7 + 1;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
RangeTransform rangeTransform = new RangeTransform();
for (int i = 0; i < 35; i++)
System.out.println("Val is : " + rangeTransform.rangeTransform());
}
}
其他回答
我玩了一下,我为这个Rand(7)算法写了“测试环境”。例如,如果你想尝试哪种分布给你的算法,或者需要多少次迭代才能生成所有不同的随机值(对于Rand(7) 1-7),你可以使用它。
我的核心算法是:
return (Rand5() + Rand5()) % 7 + 1;
和亚当·罗森菲尔德的分布一样均匀。(我将其包含在代码片段中)
private static int Rand7WithRand5()
{
//PUT YOU FAVOURITE ALGORITHM HERE//
//1. Stackoverflow winner
int i;
do
{
i = 5 * (Rand5() - 1) + Rand5(); // i is now uniformly random between 1 and 25
} while (i > 21);
// i is now uniformly random between 1 and 21
return i % 7 + 1;
//My 2 cents
//return (Rand5() + Rand5()) % 7 + 1;
}
这个“测试环境”可以采用任何Rand(n)算法并测试和评估它(分布和速度)。只需将代码放入“Rand7WithRand5”方法并运行代码片段。
一些观察:
亚当·罗森菲尔德(Adam Rosenfield)的算法并不比我的算法分布得更好。不管怎样,两种算法的分布都很糟糕。 本机Rand7(随机的。Next(1,8))完成,因为它在大约200+迭代中生成了给定间隔内的所有成员,Rand7WithRand5算法的顺序为10k(约30-70k) 真正的挑战不是编写从Rand(5)生成Rand(7)的方法,而是生成几乎均匀分布的值。
我知道它已经被回答了,但这似乎是可以工作的,但我不能告诉你它是否有偏见。我的“测试”表明,这至少是合理的。
也许亚当·罗森菲尔德会好心地评论一下?
我(天真?)的想法是这样的:
积累rand5,直到有足够的随机位形成rand7。这最多需要2兰特。为了得到rand7,我使用累计值mod 7。
为了避免累加器溢出,由于累加器是mod 7,那么我取累加器的mod 7:
(5a + rand5) % 7 = (k*7 + (5a%7) + rand5) % 7 = ( (5a%7) + rand5) % 7
rand7()函数如下:
(我让rand5的范围是0-4,rand7也是0-6。)
int rand7(){
static int a=0;
static int e=0;
int r;
a = a * 5 + rand5();
e = e + 5; // added 5/7ths of a rand7 number
if ( e<7 ){
a = a * 5 + rand5();
e = e + 5; // another 5/7ths
}
r = a % 7;
e = e - 7; // removed a rand7 number
a = a % 7;
return r;
}
编辑:增加了1亿次试验的结果。
'Real' rand函数mod 5或7
rand5 : 平均=1.999802 0:20003944 1:19999889 2:20003690 3:19996938 4:19995539 Rand7 : 平均=3.000111 0:14282851 1:14282879 2:14284554 3:14288546 4:14292388 5:14288736 6:14280046
我的边缘7
平均数看起来不错,数字分布也不错。
Randt : 平均=3.000080 0:14288793 1:14280135 2:14287848 3:14285277 4:14286341 5:14278663 6:14292943
面对这么复杂的答案,我觉得自己很蠢。
为什么不能:
int random1_to_7()
{
return (random1_to_5() * 7) / 5;
}
?
(我剽窃了亚当·罗森菲尔德的答案,使其运行速度提高了7%左右。)
假设rand5()返回分布相等的{0,1,2,3,4}中的一个,目标是返回分布相等的{0,1,2,3,4,5,6}。
int rand7() {
i = 5 * rand5() + rand5();
max = 25;
//i is uniform among {0 ... max-1}
while(i < max%7) {
//i is uniform among {0 ... (max%7 - 1)}
i *= 5;
i += rand5(); //i is uniform {0 ... (((max%7)*5) - 1)}
max %= 7;
max *= 5; //once again, i is uniform among {0 ... max-1}
}
return(i%7);
}
我们在跟踪这个循环在变量max中所能产生的最大值。如果到目前为止的结果在max%7和max-1之间,那么结果将均匀分布在该范围内。如果不是,则使用余数,余数是0到max%7-1之间的随机数,然后再次调用rand()来生成一个新的数字和一个新的max。然后我们重新开始。
编辑:在这个方程中,期望调用rand5()的次数是x:
x = 2 * 21/25
+ 3 * 4/25 * 14/20
+ 4 * 4/25 * 6/20 * 28/30
+ 5 * 4/25 * 6/20 * 2/30 * 7/10
+ 6 * 4/25 * 6/20 * 2/30 * 3/10 * 14/15
+ (6+x) * 4/25 * 6/20 * 2/30 * 3/10 * 1/15
x = about 2.21 calls to rand5()
这个答案更像是一个从Rand5函数中获得最大熵的实验。因此,T有点不清楚,几乎可以肯定比其他实现慢得多。
假设0-4为均匀分布,0-6为均匀分布:
public class SevenFromFive
{
public SevenFromFive()
{
// this outputs a uniform ditribution but for some reason including it
// screws up the output distribution
// open question Why?
this.fifth = new ProbabilityCondensor(5, b => {});
this.eigth = new ProbabilityCondensor(8, AddEntropy);
}
private static Random r = new Random();
private static uint Rand5()
{
return (uint)r.Next(0,5);
}
private class ProbabilityCondensor
{
private readonly int samples;
private int counter;
private int store;
private readonly Action<bool> output;
public ProbabilityCondensor(int chanceOfTrueReciprocal,
Action<bool> output)
{
this.output = output;
this.samples = chanceOfTrueReciprocal - 1;
}
public void Add(bool bit)
{
this.counter++;
if (bit)
this.store++;
if (counter == samples)
{
bool? e;
if (store == 0)
e = false;
else if (store == 1)
e = true;
else
e = null;// discard for now
counter = 0;
store = 0;
if (e.HasValue)
output(e.Value);
}
}
}
ulong buffer = 0;
const ulong Mask = 7UL;
int bitsAvail = 0;
private readonly ProbabilityCondensor fifth;
private readonly ProbabilityCondensor eigth;
private void AddEntropy(bool bit)
{
buffer <<= 1;
if (bit)
buffer |= 1;
bitsAvail++;
}
private void AddTwoBitsEntropy(uint u)
{
buffer <<= 2;
buffer |= (u & 3UL);
bitsAvail += 2;
}
public uint Rand7()
{
uint selection;
do
{
while (bitsAvail < 3)
{
var x = Rand5();
if (x < 4)
{
// put the two low order bits straight in
AddTwoBitsEntropy(x);
fifth.Add(false);
}
else
{
fifth.Add(true);
}
}
// read 3 bits
selection = (uint)((buffer & Mask));
bitsAvail -= 3;
buffer >>= 3;
if (selection == 7)
eigth.Add(true);
else
eigth.Add(false);
}
while (selection == 7);
return selection;
}
}
每次调用Rand5添加到缓冲区的比特数目前是4/5 * 2,所以是1.6。 如果包括1/5的概率值,则增加0.05,因此增加1.65,但请参阅代码中的注释,我不得不禁用它。
调用Rand7消耗的比特数= 3 + 1/8 *(3 + 1/8 *(3 + 1/8 *(… 这是3 + 3/8 + 3/64 + 3/512…大约是3.42
通过从7中提取信息,我每次调用回收1/8*1/7位,大约0.018
这使得每次调用的净消耗为3.4比特,这意味着每一次Rand7调用到Rand5的比率为2.125。最优值应该是2.1。
我可以想象这种方法比这里的许多其他方法都要慢得多,除非调用Rand5的代价非常昂贵(比如调用一些外部熵源)。