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）中間點的枚舉進行多次隨機化後決定。
這樣就基本上將快速排序的時間復雜度維持在最好狀態