1. 计算机产生伪随机数的周期是多少算法是什么
为追求真正的随机序列，人们曾采用很多种原始的物理方法用于生成一定范围内满足精度（位数）的均匀分布序列，其缺点在于：速度慢、效率低、需占用大量存储空间且不可重现等。为满足计算机模拟研究的需求，人们转而研究用算法生成模拟各种概率分布的伪随机序列。伪随机数是指用数学递推公式所产生的随机数。从实用的角度看，获取这种数的最简单和最自然的方法是利用计算机语言的函数库提供的随机数发生器。典型情况下，它会输出一个均匀分布在0和1区间内的伪随机变量的值。其中应用的最为广泛、研究最彻底的一个算法即线性同余法。
线性同余法LCG（Linear Congruence Generator）
选取足够大的正整数M和任意自然数n0，a，b，由递推公式：
ni+1=（af（ni）+b）mod M i=0，1，…，M-1
生成的数值序列称为是同余序列。当函数f（n）为线性函数时，即得到线性同余序列：
ni+1=（a*ni+b）mod M i=0，1，…，M-1
以下是线性同余法生成伪随机数的伪代码：
Random（n，m，seed，a，b）
{
r0 = seed；
for （i = 1；i<=n；i++）
ri = （a*ri-1 + b） mod m
}
其中种子参数seed可以任意选择，常常将它设为计算机当前的日期或者时间；m是一个较大数，可以把它取为2w，w是计算机的字长；a可以是0.01w和0.99w之间的任何整数。
应用递推公式产生均匀分布随机数时，式中参数n0，a，b，M的选取十分重要。
例如，选取M=10，a=b =n0=7，生成的随机序列为{6，9，0，7，6，9，……}，周期为4。
取M=16，a=5，b =3，n0=7，生成的随机序列为{6，1，8，11，10，5，12，15，14，9，0，3，2，13，4，7，6，1……}，周期为16。
取M=8，a=5，b =1，n0=1，生成的随机序列为{6，7，4，5，2，3，0，1，6，7……}，周期为8。
Visual C++中伪随机数生成机制
用VC产生随机数有两个函数，分别为rand（void）和srand（seed）。rand()产生的随机整数是在0~RAND_MAX之间平均分布的，RAND_MAX是一个常量（定义为：#define RAND_MAX 0x7fff）。它是short型数据的最大值，如果要产生一个浮点型的随机数，可以将rand()/1000.0，这样就得到一个0~32.767之间平均分布的随机浮点数。如果要使得范围大一点，那么可以通过产生几个随机数的线性组合来实现任意范围内的平均分布的随机数。
其用法是先调用srand函数，如
srand( (unsigned)time( NULL ) )
这样可以使得每次产生的随机数序列不同。如果计算伪随机序列的初始数值（称为种子）相同，则计算出来的伪随机序列就是完全相同的。要解决这个问题，需要在每次产生随机序列前，先指定不同的种子，这样计算出来的随机序列就不会完全相同了。以time函数值（即当前时间）作为种子数，因为两次调用rand函数的时间通常是不同的，这样就可以保证随机性了。也可以使用srand函数来人为指定种子数分析以下两个程序段，
程序段1：
//包含头文件
void main() {
int count=0;
for (int i=0;i<10;i++){
srand((unsigned)time(NULL));
count++;
cout<<"No"<
//包含头文件
void main() {
int count=0;
srand((unsigned)time(NULL));
for (int i=0;i<10;i++){
count++;
cout<<"No"<
No1=9694 No2=9694 No3=9694 No4=9694 No5=9694
No6=9694 No7=9694 No8=9694 No9=9694 No10=9694
程序段2的运行结果为：
No1=10351 No2=444 No3=11351 No4=3074 No5=21497
No6=30426 No7=6246 No8=24614 No9=22089 No10=21498
可以发现，以上两个程序段由于随机数生成时选择的种子的不同，运行的结果也不一样。rand()函数返回随机数序列中的下一个数(实际上是一个伪随机数序列，序列中的每一个数是由对其前面的数字进行复杂变换得到的)。为了模仿真正的随机性，首先要调用srand()函数给序列设置一个种子。为了更好地满足随机性，使用了时间函数time()，以便取到一个随时间变化的值，使每次运行rand()函数时从srand()函数所得到的种子值不相同。伪随机数生成器将作为"种子"的数当作初始整数传给函数。这粒种子会使这个球（生成伪随机数）一直滚下去。
程序段1中由于将srand（）函数放在循环体内，而程序执行的CPU时间较快，调用time函数获取的时间精度却较低（55ms），这样循环体内每次产生随机数用到的种子数都是一样的，因此产生的随机数也是一样的。而程序段2中第1次产生的随机数要用到随机种子，以后的每次产生随机数都是利用递推关系得到的。 基于MFC的随机校验码生成
Web应用程序中经常要利用到随机校验码，校验码的主要作用是防止黑客利用工具软件在线破译用户登录密码，校验码、用户名、密码三者配合组成了进入Web应用系统的钥匙。在利用VC开发的基于客户机/浏览器（Client/Server）模式的应用软件系统中，为了防止非法用户入侵系统，通常也要运用随机校验码生成技术。
2. 随机算法
相关总结参见 http://www.jianshu.com/p/60ea83ea17cc
一个随机算法的最坏运行时间几乎总是和非随机化算法的最坏情形运行时间相同。重要的区别在于，好的随机化算法没有不好的输入，而只有坏的随机数（相对于特定的输入）。
比如说：对于快速排序，方法A用第一个元素作为枢纽元，方法B使用随机选出的元素作为枢纽元。
通过随机化算法，特定的输入不再重要。重要的是随机数，我们可以山败前得到一个期望的运行时间，此时我们是对所有可能的随机数取平均而不是对所有可能的输入求平均。
随机数有许多已知的统计性质；逗清伪随机数满足这些性质的大枯蔽部分。
真正需要的是随机数的序列。这些数应该独立地出现。
线性同余数发生器
产生随机数的最简单的方法是线性同余数发生器，由Lehmer于1951年提出：
例如：M = 11，x0 = 1
A = 7： 7， 5， 2， 3， 10， 4， 6， 9， 8， 1， 7 ，5 ，2... （周期为10 = M-1）
A = 5： 5， 3， 4， 9， 1， 5， 3， 4...（周期为5 < M -1）
一个有问题的随机数发生器（返回(0,1)开区间值）：乘法溢出
工作在32位机器上的随机数发生器
证明：为什么δ(xi)或者是0，或者是1
为什么仅当余项的值小于0时，δ(xi)=1
说明：因为这里是对M取余，所以是M的倍数则自然消掉；并且δ(xi)两项都是取整函数，因此肯定为整数，另外xi+1总是介于1~M-1之间，因此当余项小于0，则取1
随机化的第一个用途是以O(lgn)期望时间支持查找和插入的数据结构。
每个2^i 结点就有一个指针指向下一个2^i结点，总的指针个数仅仅是加倍，但现在在一次查找中最多考察floor(lgn)个结点。因此总的时间消耗为O(lgn)。
本质上是二分查找：
放松上面数据结构的结构条件，就构成了跳跃表：
如果我们想查找19是否存在？如何查找呢？我们从头结点开始，首先和9进行判断，此时大于9，然后和21进行判断，小于21，此时这个值肯定在9结点和21结点之间，此时，我们和17进行判断，大于17，然后和21进行判断，小于21，此时肯定在17结点和21结点之间，此时和19进行判断，找到了。
1）实现
2）空间大小耗费
3）查找
1-2-3跳跃表的实现特点：
在同一层级的链表（不超过3个结点）中找到首个大于item的结点，然后向下移一层。
4）插入
必须保证当一个高度为h的新结点加入进来时不会产生具有四个高度为h的结点的间隙。
插入采用2-3-4树的自顶向下的方法（保证当前结点不是4-结点）：（参考 http://www.jianshu.com/p/8258ed821859 ）
设在第L层，并要降到下一层。如果下一层的间隙容量是3，则提高该间隙的中间项使其高度为L，从而形成两个容量为1的间隙。由于这使得朝下删除的道路上消除了容量为3的间隙，因此插入式安全的。
5）删除
删除采用2-3-4树的自顶向下的方法（保证当前结点不是2-结点）：（参考 http://www.jianshu.com/p/8258ed821859 ）
确定一个大数是否是素数的问题。
结点包括：
具有最低优先级的结点必然是根。树是根据优先级的N!种可能的排列而不是根据项的N!中排列形成的。
1）插入
插入之后，通过左旋和右旋恢复堆序性质：
2）删除
这个删除方法也可以采用红黑树的删除方法，将删除归结为叶子节点的删除。（使用后继，这样可以节省很多旋转）
3. 随机化算法有哪些应用领域
随机化算法
在我们的生活中，人们经常会去掷色子来看结果，投硬币来决定行动，这就牵涉到一个问题：随机。
计算机为我们提供好了随机方法（部分计算器也提供了），那么对于有些具有瑕疵的算法，如果配上随机化算法的话，又是可以得到一样不到的结果。
定义：随机化算法是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。随机化算法基于随机方法，依赖于概率大小。
这种算法看上去是凭着运气做事，其实，随机化算法是有一定的理论基础的，我们可以想象，在[1,10000]这个闭区间里，随机1000次，随机到2这个数的几率是多大，何况1000次的随机在计算机程序中仅仅是一眨眼的功夫。可以看出，随机化算法有着广阔的前景。只是由于随机化算法比较难于掌控，所以并不是很多人都接触过他，但肯定有很多人都听说过。
下面，我们就随机化问题，举一个例子：
一个长度在4..10的字符串中，需要判定是否可以在字符串中删去若干字符，使得改变后字符串符合以下条件之一：
（1）AAAA；（2）AABB；（3）ABAB；（4）ABBA。
例如：长度为6字符串“POPKDK”，若删除其中的“O”，“D”两个字母，则原串变为：“PPKK”，符合条件（2）AABB。
分析：
这道题很容易想到一种算法：运用排列组合：枚举每4个字母，然后逐一判断。算法是可行的，但是如果需要题目中加上一句话：需要判断n个字符串，且n<=100000，那么这样的耗时是不能让人忍受①的，因为在枚举的过程中，是非常浪费时间的。
(①：这里是指信息学中要求算法的普遍运算时间为：1000ms）
所以这道题有可能可以借助于随机化算法，下面我们来算一下在10个组符中取4个字符一共有多少种取法：C(4,10)=210。那么很容易得知，随机化算法如果随机100次，能都到的结果基本上就正确了，而随机时的时间消耗是O(1)，只需要判断没有随机重复即可，判重的时间复杂度也为O(1)，并且最多随机100次，这样就可以有效地得到答案，最大运算次数为：O(100n)，这是在计算机的承受范围内（1000ms）的。
从这里就能看出，随机化算法是一个很好的概率算法，但是它并不能保证正确，而且它单独使用的情况很少，大部分是与其他的算法：例如贪心、搜索等配合起来运用。
再举一个例子：
排序问题。快速排序是排序方法中较为便捷的方法之一，但是由于它极不稳定，最好的时候时间复杂度为O(n㏒n)，这里的㏒是指以2为底的对数运算。最坏的时候能达到与普通排序方法一样的O(n^2)。
而制约快速排序的有两个：一是数据，越无序的数据，快排的速度越快；二是中间点的枚举。
因为两个制约条件都与随机有着不可分开的关系。
所以，在快速排序中加入随机化算法无疑是十分重要的。
运用在：
（1）数据读入时，随机排放数据位置。
（2）中间点的枚举进行多次随机化后决定。
这样就基本上将快速排序的时间复杂度维持在最好状态