如何编程求随机事件的期望，有没有 快捷点 的方法

Question

遇到的问题如下：
猴子排序法是计算机科学中的一个著名的随机算法：对于n个数，每次随机一个1..n的排列，按此排列将这n个数重排，直到这n个数有序为止。这个算法期望需要产生n!个排列才能将数列排好序，现在给出了一个改进版的猴子排序算法：假设a[1], a[2], .. a[n] 是1..n的一个排列，每次随机选择三个不同的位置 1 <= i < j < k <= n，随机交换 a[i]，a[j]，a[k]（从六种等可能的情况中等概率选择一种）。假设交换不需要时间，小k想知道期望多少次之后，整个数 组变成有序的（既使得a[i] = i 对于所有i = 1, 2, 3 .. n）。

Answer 1

我写了个程序去执行这个操作，n=5的时候，几百回就完事了，然后把N改成10，执行了100W次也没成功。。。。

代码是这样的，不知道是不是你说的那样。

#include "stdafx.h"
#include
#include
#include

#define N 10
int num[N];

int MyRand()
{
// srand(time(0));
return rand();
}

void Upset()
{
int tmp;
int a,b;
srand(time(0));
for(int j=0; j<N; j++)
{
for(int i=0; i<N; i++)
{
a = MyRand()%N;
b = MyRand()%N;
tmp = num[a];
num[a] = num[b];
num[b] = tmp;
}
}
}

void MonkeySequ()
{
srand(time(0));
int a,b,c,tmp;
a = MyRand()%N;
do{
b=MyRand()%N;
}while(a == b);
do{
c=MyRand()%N;
}while(a==c || b==c);

int type = MyRand()%6;
switch (type)
{
    case 0:
        tmp = num[a];
        num[a] = num[b];
        num[b] = tmp;
        break;
    case 1:
        tmp = num[a];
        num[a] = num[c];
        num[c] = tmp;
        break;
    case 2:
        tmp = num[c];
        num[c] = num[b];
        num[b] = tmp;
        break;
    case 3:
        tmp = num[a];
        num[a] = num[b];
        num[b] = num[c];
        num[c] = tmp;
        break;
    case 4:
        tmp = num[a];
        num[a] = num[c];
        num[c] = num[b];
        num[b] = tmp;
        break;
    case 5:
        break;
}

}

bool isRight()
{
for(int i=0; i<N; i++)
{
if(num[i] != i+1)
{
return false;
}
}

return true;

}
int _tmain(int argc, _TCHAR* argv[])
{

for(int i=0; i<N; i++)
{
    num[i] = i + 1;
}

Upset();
int count = 0;
while(true)
{
    MonkeySequ();

    for(int i=0; i<N; i++)
    {
        printf("%d ",num[i]);
    }
    printf("         (%d)\n",count++);

    if(isRight())
    {
        break;
    }

}
return 0;
}

vs2010 下的