2 wm64195135 wm64195135 于 2014.11.29 12:25 提问

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

遇到的问题如下:
猴子排序法是计算机科学中的一个著名的随机算法:对于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)。

1个回答

hydirl
hydirl   2014.12.03 17:23

我写了个程序去执行这个操作,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 下的
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!