- 论坛徽章:
- 14
|
题目是从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）
因此自此证明这个问题是无解的。 |
|
免费注册
楼主: glq2000
发表于 2010-07-07 23:35