给定一个函数,它产生的是1到5之间的随机整数,写一个函数,它产生的是1到7之间的随机整数。
当前回答
下面是一个利用c++ 11特性的答案
#include <functional>
#include <iostream>
#include <ostream>
#include <random>
int main()
{
std::random_device rd;
unsigned long seed = rd();
std::cout << "seed = " << seed << std::endl;
std::mt19937 engine(seed);
std::uniform_int_distribution<> dist(1, 5);
auto rand5 = std::bind(dist, engine);
const int n = 20;
for (int i = 0; i != n; ++i)
{
std::cout << rand5() << " ";
}
std::cout << std::endl;
// Use a lambda expression to define rand7
auto rand7 = [&rand5]()->int
{
for (int result = 0; ; result = 0)
{
// Take advantage of the fact that
// 5**6 = 15625 = 15624 + 1 = 7 * (2232) + 1.
// So we only have to discard one out of every 15625 numbers generated.
// Generate a 6-digit number in base 5
for (int i = 0; i != 6; ++i)
{
result = 5 * result + (rand5() - 1);
}
// result is in the range [0, 15625)
if (result == 15625 - 1)
{
// Discard this number
continue;
}
// We now know that result is in the range [0, 15624), a range that can
// be divided evenly into 7 buckets guaranteeing uniformity
result /= 2232;
return 1 + result;
}
};
for (int i = 0; i != n; ++i)
{
std::cout << rand7() << " ";
}
std::cout << std::endl;
return 0;
}
其他回答
这个怎么样
rand5 () % + rand5 (2) + 2 (2) % + rand5 rand5 () (2) % + rand5 % + rand5 (2) 2
不确定这是均匀分布的。有什么建议吗?
下面使用随机数发生器在{1,2,3,4,5,6,7}上产生均匀分布,在{1,2,3,4,5}上产生均匀分布。代码很混乱,但逻辑很清晰。
public static int random_7(Random rg) {
int returnValue = 0;
while (returnValue == 0) {
for (int i = 1; i <= 3; i++) {
returnValue = (returnValue << 1) + SimulateFairCoin(rg);
}
}
return returnValue;
}
private static int SimulateFairCoin(Random rg) {
while (true) {
int flipOne = random_5_mod_2(rg);
int flipTwo = random_5_mod_2(rg);
if (flipOne == 0 && flipTwo == 1) {
return 0;
}
else if (flipOne == 1 && flipTwo == 0) {
return 1;
}
}
}
private static int random_5_mod_2(Random rg) {
return random_5(rg) % 2;
}
private static int random_5(Random rg) {
return rg.Next(5) + 1;
}
PHP解决方案
<?php
function random_5(){
return rand(1,5);
}
function random_7(){
$total = 0;
for($i=0;$i<7;$i++){
$total += random_5();
}
return ($total%7)+1;
}
echo random_7();
?>
如果我们考虑尝试给出最有效答案的附加约束,即给定一个长度为m(1-5)的均匀分布整数的输入流I,输出一个长度为m(1-7)的均匀分布整数的流O,长度为L(m)。
最简单的分析方法是将流I和O分别视为5元数和7元数。这是通过主答案的思想来实现的,即取流a1, a2, a3,…- > a1 + a2 + 5 * 5 ^ 2 * a3 + . .流O也是如此。
然后如果我们取长度为m的输入流的一段,选n s.t, 5^m-7^n=c,其中c>0,且尽可能小。然后有一个从长度为m的输入流到1到5^m的整数的统一映射,还有一个从1到7^n的整数到长度为n的输出流的统一映射,当映射的整数超过7^n时,我们可能不得不从输入流中丢失一些情况。
这就给出了L(m)的值约为m (log5/log7)也就是。82米。
上述分析的难点是方程5^m-7^n=c,它不容易精确求解,而在1到5^m的均匀值超过7^n的情况下,我们失去了效率。
问题是如何接近m (log5/log7)的最佳可能值。例如,当这个数字接近一个整数时,我们能否找到一种方法来实现这个精确的整数值输出?
如果5^m-7^n=c,那么从输入流中,我们有效地生成了一个从0到(5^m)-1的均匀随机数,并且不使用任何高于7^n的值。但是,这些值可以被保存并再次使用。它们有效地生成了从1到5^m-7^n的统一数字序列。所以我们可以尝试使用这些,并将它们转换成7位数,这样我们就可以创建更多的输出值。
如果我们让T7(X)是由大小为X的均匀输入导出的随机(1-7)整数的输出序列的平均长度,并假设5^m=7^n0+7^n1+7^n2+…+ 7 ^ nr + s, s < 7。
那么T7(5^m)=n0x7^n0/5^m + ((5^m-7^n0)/5^m) T7(5^m-7^n0)因为我们有一个无长度序列,概率为7^n0/5^m,残差长度为5^m-7^n0,概率为(5^m-7^n0)/5^m)。
如果我们一直代入,我们得到:
T7(5^m) = n0x7^n0/5^m + n1x7^n1/5^m + ... + nrx7^nr/5^m = (n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/5^m
因此
L(m)=T7(5^m)=(n0x7^n0 + n1x7^n1 + ... + nrx7^nr)/(7^n0+7^n1+7^n2+...+7^nr+s)
另一种说法是:
If 5^m has 7-ary representation `a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r
Then L(m) = (a1*7 + 2a2*7^2 + 3a3*7^3+...+rar*7^r)/(a0+a1*7 + a2*7^2 + a3*7^3+...+ar*7^r)
最好的情况是上面的原始情况,即5^m=7^n+s,其中s<7。
然后机械师》(5 ^ m) = nx (7 ^ n) / (7 ^ n + s) = o (n + 1) = m (Log5 / Log7) + o(1)美国之前。
最坏的情况是我们只能找到k和s.t 5^m = kx7+s。
Then T7(5^m) = 1x(k.7)/(k.7+s) = 1+o(1)
其他情况介于两者之间。看看对于很大的m,我们能做得多好,也就是说,我们能多好地得到误差项,这将是很有趣的:
T7(5^m) = m (Log5/Log7)+e(m)
一般来说,似乎不可能实现e(m)=o(1)但希望我们可以证明e(m)=o(m)。
整个问题取决于5^m的7位数字对不同m值的分布。
我相信有很多理论涵盖了这一点,我可能会在某个时候看一看并报告。
我不喜欢从1开始的范围,所以我将从0开始:-)
unsigned rand5()
{
return rand() % 5;
}
unsigned rand7()
{
int r;
do
{
r = rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
r = r * 5 + rand5();
} while (r > 15623);
return r / 2232;
}