[题目描述]给定一个函数Random(5), 它将随机地返回 {1, 2, 3, 4, 5}中的一个数字. 问: 如何实现函数 random(n)?

希望数字分布比较均匀, 有什么比较好的实现方法吗?

google一下，或者直接看java源代码吧如果没有版权问题的话。

这个和分布方式相关。
正态分布，泊松分布和均匀分布的生成算法不一样。
如果要求正态分布的话，可以使用多项式生成，其他两个需要查一下。

他说要均匀分布……

这里有一个线性同余法的：
[url=http://zhidao.baidu.com/question/540840.html?fr=qrl]

直接使用rand()%5+1怎么样？rand()本身就是一个比较均匀的伪随机数。
-----------------------
#include <cstdlib>
#include <ctime>

int rand1_5()
{
return rand()%5+1;
}

int main()
{
srand(clock());//伪随机数使用系统时钟初始化；
int ret_val = rand1_5();
//...
}

楼上貌似都理解错题意了
貌似是算法导论的习题，就是已经有一个均匀分布的int rand_5()
要实现一个int rand(n)

我改一下题目，假设rand_5返回0～4，需要构造一个0～n-1的随机数

我的方法是用k次rand_5()(5^k >= n)得到一个k位的5进制数，当这个数大于等于n时丢弃重新来一次，小于等于n时返回
例如n = 31，则k = 3，那么这个3位5进制数为rand_5() * 25 + rand_5() * 5 + rand_5()

补充一下: k = floor(log(5, n)) + 1, 且5^k > n >= 5^(k-1). 调用k次rand_5(), 得到的数应该是[0, 5^k). 只保留小于n的数, 所得到的[0, n)上的每个数是均匀分布的.

这种做法效率不是很高, 但可以保证均匀分布. 如果不要求均匀分布, 将得到的数直接mod n, 就可以了.

这种方法在概率上有可能运行时间趋向无穷吧，看起来好不可靠

正如版主所说，这个效率不高，这里给出一个效率更好的算法。
设已知Random(0, N) 要求Random(0, M) M > N
假入N=4, M=5, 那么必须至少要生成0～24个随机数才够用,也就是5*Random(0, 4) + Random(0, 4)，但是大于M的直接抛弃又太浪费，于是想到可以mod M+1，但是这样又不均匀。在这种情况下，mod M+1可以如下所示：
0 ~ 5 6 ~ 11 12 ~ 17 18 ~ 23 24
事实上，如果只有位于0 ~ 23之间随机数就正好分为4组，很均匀。这里唯余一个24，mod M+1 = 0，概率空间会多一个0。
所以这里还是可以采用抛弃的思路，但是却是抛弃24的这种情况。一般来说，我们需要抛弃不能整除M+1的那一部分。算法如下:
但是等等，这个算法其实没有直接抛弃不能整除的那部分，假设不能整除的那部分概率空间是{0, 1, ... , K} K < M。
也就是说，如果直接抛弃重来，那么我们又要从0开始获取随机数，而这里可以看出，我们已经有了位于 0 ~ K 之间的均匀随机数，那么如果直接继续迭代一次，
0 -> 0* (N+1) + Random(0, N) -> 0 ~ N
1 -> ... -> N+1 ~ 2N+1
2-> ... -> 2N+2 ~ 3N+2
...
K-> ... -> KN+K ~ KN+N+K
就得到了 0 ～ KN+N+K 之间的均匀随机数，无疑加快了速度。

这个算法的本质就是利用Random(0, N)迭代产生 0 ~ N^X-1 之间的随机数，如果space够用了就mod得到所需的随机数，排除不均匀的那部分，再利用那部分继续产生随机数。如此往复。本质上和直接抛弃是一样的，不过速度要快一些。

PS:算法不是我的，网上抄的，只有分析是自己的，有点罗嗦.....
完整的算法是：
这里注意的是，中间有个误差控制量，如果运气不好老是需要重来，那么一定次数后就直接返回退出，实践中也可以得到相当均匀的随机量。

给一个思路，用一个骰子可以随机获得1到6任何数字，现在用2个骰子，根据乘法原理，可以获得，6x6等于36种不同排列，并且均匀分布，采用6进制数，骰子1的点数-1，乘以6后加上骰子2的点数-1，就可以机会均等表示0-35。因此用k个骰子，就可以均匀表示0到6^k-1的范围。

值得注意的是，并不能用反复掷一个骰子然后将点数相加来获取1到6n之间的随机数，因为这样概率分布不均匀。

但是，如果n不是正好的6^k-1，则严格说，概率并不均匀。例如我希望通过2个dice，获取0到6这7个数字，必然从8到35代表的数字，超出范围，如果仅仅将结果模n,则就会面对鸽笼原理问题（或叫抽屉原则问题），必然某些数字的概率高，令一些概率低。

一个办法是丢弃，我考虑另一个调整办法，从rand ( m ) 生成rand ( n )。不失一般性，假设(m,n)=1。也就是互素。
首先，寻找k使得m^k<=n<m^(k+1)
令n和m^(k+1)-1的最小公倍数为lcm，并且令
n*p=lcm
(m^(k+1)-1)*p=lcm
我们把生成的随机数乘以q再处以p就将0到m^(k+1)-1均匀分布到0到n-1，附带的scheme代码如下，在MIT scheme上测试通过。

你除了之后未必能得到整数。

通常情况下，都不是整数。所以最后一句有floor。

floor 了之后还是均匀分布么？