拉斯維加斯演演算法

void obstinate(Object x, Object y) {// 反覆調用拉斯維加斯演演算法LV(x,y)，直到找到問題的一個解y bool success= false; while (!success) success=lv(x,y); }

設p(x)是對輸入x調用拉斯維加斯演演算法獲得問題的一個解的概率。一個正確的拉斯維加斯演演算法應該對所有輸入x均有。設t(x)是演演算法obstinate找到具體實例x的一個解所需的平均時間,s(x)和e(x)分別是演演算法對於具體實例x求解成功或求解失敗所需的平均時間，則有：解此方程可得：n后問題

對於n后問題的任何一個解而言，每一個皇后在棋盤上的位置無任何規律，不具有系統性，而更象是隨機放置的。由此容易想到下面的拉斯維加斯演演算法。

在棋盤上相繼的各行中隨機地放置皇后，並注意使新放置的皇后與已放置的皇后互不攻擊，直至n個皇后已相容地放置好，或已沒有下一個皇后的可放置位置時為止。

如果將上述隨機放置策略與回溯法相結合，可能會獲得更好的效果。可以先在棋盤的若干行中隨機地放置皇后，然後在後繼行中用回溯法繼續放置，直至找到一個解或宣告失敗。隨機放置的皇后越多，後繼回溯搜索所需的時間就越少，但失敗的概率也就越大。

設是一個整數。關於整數n的因子分解問題是找出n的如下形式的唯一分解式：其中，是k個素數，是k個正整數。如果n是一個合數，則n必有一個非平凡因子x，，使得x可以整除n。給定一個合數n，求n的一個非平凡因子的問題稱為整數n的因子分割問題。

int Split(int n){ int m = floor(sqrt(double(n))); for (int; ; i++) if (n%i==0) return i; return 1;}

事實上，演演算法split(n)是對範圍在1～x的所有整數進行了試除而得到範圍在的任一整數的因子分割。

在開始時選取範圍內的隨機數，然後遞歸地由

產生無窮序列

對於

以及，演演算法計算出與n的最大公因子。如果d是n的非平凡因子，則實現對n的一次分割，演演算法輸出n的因子d。

void Pollard(int n){// 求整數n因子分割的拉斯維加斯演演算法 RandomNumber rnd; int ; int .Random(n); // 隨機整數 // 求n的非平凡因子 >

對Pollard演演算法更深入的分析可知，執行演演算法的while循環約次后，Pollard演演算法會輸出n的一個因子p。由於n的最小素因子，故Pollard演演算法可在時間內找到n的一個素因子。