遇到的问题如下:
猴子排序法是计算机科学中的一个著名的随机算法:对于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)。
如何编程求随机事件的期望,有没有 快捷点 的方法
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- hydirl 2014-12-03 09: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 下的
解决 无用评论 打赏 举报
悬赏问题
- ¥100 Jenkins自动化部署—悬赏100元
- ¥15 关于#python#的问题:求帮写python代码
- ¥20 MATLAB画图图形出现上下震荡的线条
- ¥15 关于#windows#的问题:怎么用WIN 11系统的电脑 克隆WIN NT3.51-4.0系统的硬盘
- ¥15 perl MISA分析p3_in脚本出错
- ¥15 k8s部署jupyterlab,jupyterlab保存不了文件
- ¥15 ubuntu虚拟机打包apk错误
- ¥199 rust编程架构设计的方案 有偿
- ¥15 回答4f系统的像差计算
- ¥15 java如何提取出pdf里的文字?