随机数生成算法面试

1. 利用随机函数产生N个随机整数（20000以上），对这些数进行多种方法进行排序。

o ,老师作业吧，虽然想说书上都有的。呵呵不自己做一下真的学不到东西。呵呵虽然可能你以后的志向不想做程序员。都是基础算法。面试保证问你。

2. 随机数算法是什么

在计算机中并没有一个真正的随机数发生器，但是可以做到使产生的数字重复率很低，这样看起来好象是真正的随机数，实现这一功能的程序叫伪随机数发生器。有关如何产生随机数的理论有许多如果要详细地讨论，需要厚厚的一本书的篇幅。不管用什么方法实现随机数发生器，都必须给它提供一个名为“种子”的初始值。而且这个值最好是随机的，或者至少这个值是伪随机的。“种子”的值通常是用快速计数寄存器或移位寄存器来生成的。下面讲一讲在C语言里所提供的随机数发生器的用法。现在的C编译器都提供了一个基于ANSI标准的伪随机数发生器函数，用来生成随机数。它们就是rand（）和srand（）函数。这二个函数的工作过程如下：”）首先给srand（）提供一个种子，它是一个unsignedint类型，其取值范围从0～65535；2）然后调用rand（），它会根据提供给srand（）的种子值返回一个随机数（在0到32767之间）3）根据需要多次调用rand（），从而不间断地得到新的随机数；4）无论什么时候，都可以给srand（）提供一个新的种子，从而进一步“随机化”rand（）的输出结果。这个过程看起来很简单，问题是如果你每次调用srand（）时都提供相同的种子值，那么，你将会得到相同的随机数序列，这时看到的现象是没有随机数，而每一次的数都是一样的了。例如，在以17为种子值调用srand（）之后，在首次调用rand（）时，得到随机数94。在第二次和第三次调用rand（）时将分别得到26602和30017，这些数看上去是很随机的（尽管这只是一个很小的数据点集合），但是，在你再次以17为种子值调用srand（）后，在对于rand（）的前三次调用中，所得的返回值仍然是在对94，26602，30017，并且此后得到的返回值仍然是在对rand（）的第一批调用中所得到的其余的返回值。因此只有再次给srand（）提供一个随机的种子值，才能再次得到一个随机数。下面的例子用一种简单而有效的方法来产生一个相当随机的“种子”值－－－－当天的时间值：g＃椋睿悖欤酰洌澹Γ欤簦唬螅簦洌椋铮瑁Γ纾簦弧。＃椋睿悖欤酰洌澹Γ欤簦唬螅簦洌欤椋猓瑁Γ纾簦弧。＃椋睿悖欤酰洌澹Γ欤簦唬螅螅Γ＃矗罚唬簦穑澹螅瑁Γ纾簦弧。＃椋睿悖欤酰洌澹Γ欤簦唬螅螅Γ＃矗罚唬簦椋恚澹猓瑁Γ纾簦弧。觯铮椋洹。恚幔椋睿ǎ觯铮椋洌。。椋睿簟。椋弧。酰睿螅椋纾睿澹洹。椋睿簟。螅澹澹洌郑幔欤弧。螅簦颍酰悖簟。簦椋恚澹狻。簦椋恚澹拢酰妫弧。妫簦椋恚澹ǎΓ幔恚穑唬簦椋恚澹拢酰妫弧。螅澹澹洌郑幔欤剑ǎǎǎǎ酰睿螅椋纾睿澹洹。椋睿簦簦椋恚澹拢酰妫簦椋恚澹Γ幔恚穑唬埃疲疲疲疲。ǎ酰睿螅椋纾睿澹洹。椋睿簦簦椋恚澹拢酰妫恚椋欤欤椋簦恚蕖。ǎ酰睿螅椋纾睿澹洹。椋睿簦簦椋恚澹拢酰妫恚椋欤欤椋簦恚弧。螅颍幔睿洌ǎǎ酰睿螅椋纾睿澹洹。椋睿簦螅澹澹洌郑幔欤弧。妫铮颍ǎ椋剑埃唬椋Γ欤簦唬保埃唬椋。穑颍椋睿簦妫ǎΓ瘢酰铮簦唬ィ叮洌Γ＃梗玻唬睿Γ瘢酰铮簦籦egjrand（））；｝上面的程序先是调用＿ftime（）来检查当前时间yc并把它的值存入结构成员timeBuf．time中wae当前时间的值从1970年1月1日开始以秒计算aeh在调用了＿ftime（）之后在结构timeBuf的成员millitm中还存入了当前那一秒已经度过的毫秒数，但在DOS中这个数字实际上是以百分之一秒来计算的。然后，把毫秒数和秒数相加，再和毫秒数进行异或运算。当然也可以对这两个结构成员进行更多的计算，以控制se．．．．．．余下全文＞＞

3. 随机数生成方案（计算方法）

诺依曼的平方数取中法。
先通过求关键码的平方值，从而扩大相近数的差别，然后根据表长度取中间的几位数（往往取二进制的比特位）

4. 电脑中的随机数是怎么生成的（硬件方面的原理）

http://ke..com/view/1127.htm

伪随机数的生成方法
一般地，伪随机数的生成方法主要有以下3种[6]：
（1） 直接法（Direct Method），根据分布函数的物理意义生成。缺点是仅适用于某些具有特殊分布的随机数，如二项式分布、泊松分布。
（2） 逆转法（Inversion Method），假设U服从[0，1]区间上的均匀分布，令X=F-1（U），则X的累计分布函数（CDF）为F。该方法原理简单、编程方便、适用性广。
（3）接受拒绝法（Acceptance-Rejection Method）：假设希望生成的随机数的概率密度函数（PDF）为f，则首先找到一个PDF为g的随机数发生器与常数c，使得f
[伪随机数发生器]

伪随机数发生器
（x）≤cg（x），然后根据接收拒绝算法求解。由于算法平均运算c次才能得到一个希望生成的随机数，因此c的取值必须尽可能小。显然，该算法的缺点是较难确定g与c。 因此，伪随机数生成器（PRNG）一般采用逆转法，其基础是均匀分布，均匀分布PRNG的优劣决定了整个随机数体系的优劣[7]。下文研究均匀分布的 PRNG。
随机数的“庐山真面目”
首先需要声明的是，计算机不会产生绝对随机的随机数，计算机只能产生“伪随机数”。其实绝对随机的随机数只是一种理想的随机数，即使计算机怎样发展，它也不会产生一串绝对随机的随机数。计算机只能生成相对的随机数，即伪随机数。
伪随机数并不是假随机数，这里的“伪”是有规律的意思，就是计算机产生的伪随机数既是随机的又是有规律的。怎样理解呢？产生的伪随机数有时遵守一定的规律，有时不遵守任何规律；伪随机数有一部分遵守一定的规律；另一部分不遵守任何规律。比如“世上没有两片形状完全相同的树叶”，这正是点到了事物的特性，即随机性，但是每种树的叶子都有近似的形状，这正是事物的共性，即规律性。从这个角度讲，你大概就会接受这样的事实了：计算机只能产生伪随机数而不能产生绝对随机的随机数。（严格地说，这里的计算机是指由冯诺依曼思想发展起来的电子计算机。而未来的量子计算机有可能产生基于自然规律的不可重现的“真”随机数）。

5. 求各种产生随机数的算法

多的很呀！别撤消呀，千万！ 不过几乎都是伪随机数。 随机序列的算法 找到了两个算法, 第一个很简单, 但可惜不是随机的, 第二个是典型的伪随机数算法, 可惜要用到2的几百万次方这样巨大的整数, 真痛苦 要是有UNIX上计算密码的源代码就好了 第一种做法: f(k) = (k*F(N-1)) mod F(N)其中, k是一个序列号, 就是要取的那个数的顺序号 F(N)是这样一个序列 F(0) = 0, F(1) = 1, F(N+2) = F(N+1)+F(N) (for N>=0)第二种做法V = ( ( V * 2 ) + B .xor. B ... )(Mod 2^n)N+1 N 0 2V是要取的随机数, B是个种子, n是随机数的最大个数 原来这个问题, 很高难, 不少数学高手都为解决这个问题写了论文, 咳咳, 偶真是个白痴 呵呵, 效果肯定是不错啦, 因为用不到很大的表. 至于应用是这样的, 比如, 你要给每个用户在注册的时候一个ID但有不希望用户在看到自己的ID的时候能知道其他用户的ID, 如果用SEQUENCE来生成ID的话, 一个用户只要把自己的ID减1就能得到其它用户的ID了. 所以要用随机数来做ID, 这样用户很难猜到其他用户的ID了. 当然主要的问题是, 随机数可能重复. 因此希望使用一个随机数做种子用它来确定一组"无规律"的自然数序列, 并且在这个序列中不会出现重复的自然数. 在这里使用的方法生成的序列并不是没有规律的, 只不过这个轨律很难被发现就是了. Xn+1 = (aXn + b) mod c (其中, abc通常是质数)是一种被广泛使用的最简单的随机数发生算法, 有研究表表明这个算法生成的随机数基本上符合统计规律, java, BORLAND C等用的都是这个方法, 一般只要保证第一个种子是真正的随机数就行了, 下面来说一下重复的问题, 上述方法会有可能出现重复, 因为当(aXn + b)有可能是同样的数或者说余数相同的数, 因此要想不重复就得变形 偶想到的方法是 Xn=(a*n + b) mod c n是一个在1到c之间的整数, a*n + b就是一个线性公式了, 且若n不同则a*n + b也不同, 它们除上质数c得到的余数也肯定不同, 因为 若不考虑a和b而只有n的时候, 每次的结果都是n,而线性公式, 只不过移动了这条直线的位置和斜率而已, 每个结果仍然不会相同的, 为了增加不可预计性, 偶又为上面那个公式设计了, 随机数种子, 于是就变成了这个样子 F(N)=(随机数*(N+随机数))MOD 一个质数 这样就能够产生 1到选定质数之间的一个"无规律"的自然数序列了, 只要改变随机数就能改变序列的次序 在应用的时候, 要把随机数种子和最后用到的序列号保存到一个表里, 每此使用的时候取出来算好, 再把序列号更新一下就可以了 具体地说, 就是可以建一个表来保存每个序列的随机数种子, 然后再为这个序列建一个SEQUENCE就行了然后就SELECT MOD(序列控制表.随机数*(SEQ.NEXTVAL+序列控制表.随机数)),序列控制表.质数) FROM 序列控制表 WHERE 序列控制表.序列ID=XX就OK了注意 序列控制表.质数 决定了序列的范围

6. 昨天面试，面试官问了我一题关于伪随机数的问题。问题大概如下： 通过编程方法实现5个伪随机数

我在网上查看过一些关于random函数的资料，random函数是跟randimze函数一起使用的。作用跟rand函数和srand函数一样。
我在linux下，把你的程序该了一下，运行是可以的。我猜random函数是Linux C下的函数，而不是标准C，所以运行会报错。
下面是修改后的程序：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
// int randomize(); //播种子
srand((unsigned)time(NULL));
int a=0,b=100,t=0,i=0;
a=random()%90; //生成第一个随机数
t=t+a;
int c=b-a; //限制随机数的范围
printf("t=%d ",t);
printf("random1:%2d\n",a);
for(i=2;i<5;i++) //循环为了生成3个的随机数
{
a=rand()%c;
c=c-a;
t=t+a;
printf("t=%d ",t);
printf("random%d:%2d\n",i,a);
}

a=100-t; //生成最后一个随机数
printf("t=100 ");
printf("random5:%2d\n",a);

return 0;
}
上面程序虽然能够执行，但是如果使用"int randomize(); "初始化的时候，运行结果都是一样的，也就是说没有达到真正上的随机。但是用"srand((unsigned)time(NULL));”，结果就是真正上的随机了。

回答如果可以给点分呗。

7. java怎么进行随机数生成算法

要产生随机数，可以使用Java api中java.lang包中的Math类.Math类以静态方法的方式提供常用的数学方法，
其中Math.random()方法是一个可以产生[0.0,1.0]区间内的一个双精度浮点数的方法
如：
产生一个100以内的整数：int x=(int)(Math.random()*100);
又如：
产生一个1-50之间的随机数：int x=1+(int)(Math.random()*50)
也可以使用通用创建对象来获取：
Random random = new Random();
random.nextInt(x);
产生一个0到x-1的正数，如果想产生浮点数有Random类的nextFloat方法，总之nextXXX方法是用来产生随机数的。

8. 关于数据结构的面试题

有a~z,0~9共36个字符组成的字符串，尤其从中任取两个字符组成一个新的字符串，不得重复，这样的字符串一共有：36*35=1260，照你那么说，即使他让你写1000个也应该能够写出来。算法复杂度最小的不好找，这种题能够写出来就OK了。别人给我10个数让我排序，我也不一定就用快速排序啊？

9. c语言中如何生成1个0到1的随机数

C语言中生成1个0到1的随机数可以执行语句：float b=rand()/(RAND_MAX+1.0);

解析：

标准C库中函数rand（）可以生成0~RAND_MAX之间的一个随机数，其中RAND_MAX 是stdlib.h 中定义的一个整数，它与系统有关。rand（）函数没有输入参数，直接通过表达式rand（）来引用；

用函数rand取得的随机数除以(RAND_MAX+1.0)，即可确保得到的结果在0到1之间。ISO IEC 9899 2011 (C11)标准中未规定 RAND_MAX 的具体数值。但该标准规定了RAND_MAX 的值应至少为32767。编程的时候，不应该对 RAND_MAX 的具体数值做任何假设。

(9)随机数生成算法面试扩展阅读：

相关说明：

1、因为rand（）函数是按指定的顺序来产生整数，因此每次执行上面的语句都打印相同的两个值，所以说C语言的随机并不是真正意义上的随机。

2、为了使程序在每次执行时都能生成一个新序列的随机值，我们通常通过为随机数生成器提供一粒新的随机种子。函数 srand()(来自stdlib.h)可以为随机数生成器播散种子。只要种子不同rand()函数就会产生不同的随机数序列。srand()称为随机数生成器的初始化器。

3、随机种子（Random Seed）是计算机专业术语，一种以随机数作为对象的以真随机数（种子）为初始条件的随机数。一般计算机的随机数都是伪随机数，以一个真随机数（种子）作为初始条件，然后用一定的算法不停迭代产生随机数。