已知一个函数f可以得到1-5间的随机数，问怎么得到1-7的随机数

jerryz920

这个其实和算法导论上的一个题很像么：已知random等概率返回0或者1，那么试写一个函数等概率返回[a,b]之间的整数。思路就是2进制表示[0, b-a]之间的数，先计算出至少需要多少位，按位生成一个二进制数，一旦大于b-a就重新生成。放到这里的话，表示成5进制就可以了~

推广一下：对于等概率可以生成k个连续整数函数的函数randomk，设计生成[a,b]之间的整数的算法：
令n = b - a;则等概率生成[0，n]上的一个整数即可。于是用k进制表示生成的整数，设m=ceiling(logk(n)),

1. int randN() {
   
2.   while (res > n) {
   
3.      for (i = 0; i < m; i++)  
   
4.          gen bit i for res with randomk
   
5.   }
   
6.   return res;
   
7. }

复制代码

期望的运行时间为t*m* i * (1 - (n+1)/k^m)^(i-1) * ((n+1)/k^m)，i从1加到无穷，t表示randomk的运行时间，那么计算这个级数的值为t*m*k^m/(n+1).
带入到这个题目，期望运行时间为50*t/7，还是很快的。

goldenfort

讨厌讨论  各种 面试题， 这些题目 在某国 好象 都是 类似 于  唐 jun  ,这些能吹会拍的 人出的，能有什么水平。  可惜呀， 好资源一半让狗占了。

奶茶dsk

回复 42# jerryz920


    高论

goubao198562

回复 40# churchmice


    照这种理论 我是不是可以认为 如果一个函数能随机生成[1,N] 那这个函数不用改变只要舍弃某些值也就能随机生成[1,M] (其中M < N)

bruceteen

题目是从CU上看到的，我的算法是：
int rand7()
{
    int a;
    while( (a=rand5()*5+rand5()) > 26 );
    return (a-3)/3;
}
可惜没办法验证，不知道这个算法是否正确？（问题一）。
（验证方法是通过双循环将两个rand5()分别换成1 2 3 4 5，但剔除掉(5,2)(5,3)(5,4)(5,5)这四个组合）

算法思路是：
1. 通过 rand5()*5+rand5() 产生 6 7 8 9 10 11 …… 26，27 28 29 30 这25个数，每个数的出现机率相等
2. 只需要前面 3*7 个数，所以舍弃后面的4个数
3. 将 6 7 8 转化为 1，9 10 11 转化为 2，……，24 25 26 转化为 7。公式是 (a-3)/3

注：
我觉得不能将 while( (a=rand5()*5+rand5()) > 26 ) 其中一个rand5()移到while之外，即不能写成
int b = rand5();
int a;
while( (a=b*5+rand5()) > 26 ); 或 while( (a=rand5()*5+b) > 26 );
因为出现 >26 的情况，说明 b 有很大机率很大，从而又导致while之后的a有很大机率很大，破坏了平衡性。
这个备注中的看法对么？（问题二）

但，令人惋惜的是，这不是一个严格意义上的算法，因为“计算机算法”比“数学上的算法”多两个限定，是“有限时间有限步骤内……”，而while( (a=rand5()*5+rand5()) > 26 )可能会循环超过可忍耐次数，即某次运行这段代码可能到地球灭亡时还没结束，虽然几率很低，但有可能发生。

------------------------------------------------------------------------------------

google了一下，找到另一种方法：（本质和上面的算法相同，但要使得第二步不产生多余的数）
找到一个五进制的数 444…4，这个数正好能被7整除
于是他找到444444（五进制）这个数，也就是15624
产生nnnnnn（五进制）的方法很简单，就是每位都通过rand5-1来产生
然后将nnnnnn%7+1就得到了均匀分布于1到7的算法。

这个算法是错误的，因为 444444（五进制）内包含有15625个数，不是15624个数，前者不是7的整数倍。
用我的变形算法来描述就是：
通过 r*5^0 + r*5^1 + r*5^2 + r*5^3 + r*5^4 + r*5^5 产生 3906 到 19530 共15625个数的均匀分布，可惜15625不是7的整数倍，还是需要舍弃掉最后一位。作者错误在于马虎的认为 0至n 内有n个数，其实是n+1个数。

虽然作者的结果是错误的，但思路是正确的，只要能找到一个数n，使得 4 + 4*5 + 4*25 + 4*125 + 4*625 + 4*3125 + …… 的结果加一后是7的整数倍。
我用代码暴力求解，在数据溢出之前都没找到这个数。于是从理论上分析，444…4（五进制）+1 也就是 5的x次方，永远不可能是7的倍数。

还google到其它一些巧妙的算法，但可惜作者并没有真正理解“随机”的概念。

------------------------------------------------------------------------------------

思考一下 rand5()+rand5()，将产生 1/25个2，2/25个3，3/25个4，4/25个5，5/25个6，4/25个7，3/25个8，2/25个9，1/25个10。
如果能找到一个公式，使之产生一系列不同几率的数，将这些数分成7组，使得每组数的几率总和为1/7就可以了。
假设这个公式f需要n个rand5()为自变量，则最多产生5^n个数，不是“最多”的情况说明不同参数组合产生了相同的数，无论是不是“最多”的情况，都可以证明每个数的几率都必然是 1/(5^n) 的整数倍。
那么无论怎么分组，每组数的几率总和都应该是 m * 1/(5^n)。
求 m/(5^n) = 1/7 的整数解，即求 5^n = 7m 的整数解，很显然是无解的。（前者的个位数不是0就是5，而后者的个位数不可能是0或5）
因此自此证明这个问题是无解的。

churchmice

回复 45# goubao198562

当然可以

klyh305

17楼：
是不是可以这样理解呢：随便从这25个二元组中选出七个，这七个每个出现的概率是1/25，将这七个数字分别对应到1-7，然后重复的执行(rand(), rand())，直到出现前面7个二元组中的一个，这时就产生了一个1-7之间的随机数，这些随机数是等概率的

churchmice

回复 48# klyh305

是的，只要是7的倍数个就可以了，所以要舍弃掉一些值

但是从效率方面来考虑的话还是舍弃尽可能少的值

guoruimin

回复 17# churchmice
17楼的算法，确实是真正随机的，却不是严格的算法。
致命的漏洞是当出现的组合不符合条件时，重新生成！
从概率上来讲：重新生成符合条件的组合需要一万年，也是可能的。
所以是不可靠的算法！

有 1 - 5 之间的随机数 n1, n2, ... n7
则有 7 - 35 之间的随机数 m = n1 + n2 + ... + n7
则有 1 - 7 之间的随机数 k = m / 5

该算法始终稳定在 rand 7 次！

但该算法似乎不是真正随机的。
中间的几个数出现的概率比较高吧？

churchmice

回复 50# guoruimin

侬说的对，凡事讲概率，那你可以计算一下，由于是25种情况种舍弃了4种，所以舍弃的概率是4/25

那么我连续舍弃100次的概率是多少？ (4/25)^100
连续舍弃1000次呢？这概率是多么的小啊， 舍弃这么多次对于现代的计算机来说只是瞬间的事情，所以不存在性能的问题
如果恰如你所说，这个算法不幸的连续舍弃了n次，导致需要运行个1万年才能出结果，你可以去算算这个时候的n值是多大，对应的概率是多小？
这世界上没有100%会发生的事情，计算机中硬盘挂掉，cpu计算出现错误都有一个概率，就连寄存器（硬件）也会有一个meantime to work,也就是能够正常工作的概率。

照你这么说密码学都不用搞了，比如密钥是128位，那我随便猜一个也有1/(2^12的概率命中
但实际中的情况时，如果一个事件发生的概率很小（究竟多小算小要根据实际应用场景确定），我们就认为它不会发生，就可以放心的去用


反观你这个算法

有 1 - 5 之间的随机数 n1, n2, ... n7
则有 1 - 35 之间的随机数 m = n1 + n2 + ... + n7
则有 1 - 7 之间的随机数 k = m % 7 + 1

要证明k是等概率的有两种情况：
1. m是等概率分布在1-35之间，这个是不可能的
   因为根本没有任何可能使得m=1
2.m在1-35之间的分布不是等概率的，但是经过m%7 + 1的操作后成为了等概率，那可以算一下
   k=1要求: m=0,7,14,21,18,35
   m=0 的概率为0
   m=35的概率为 (1/5)^7
   其余几种我没算过，但是你要这玩意加起来等于1/7，我认为很悬