步长随机的行走问题
http://tieba.baidu.com/f?kz=473815763某人从一点出发，沿直线行走，他每步所走的长度是一个在[0,1)上均匀分布的随机变量。他每走完一步，都会停下来计算一下走过的总路程。如果总路程大于或等于一个特定的正整数n，则任务完成，否则继续行走。试求他完成任务时所用步数的期望。 大家可以分别从理论公式推导和数值计算俩方面下手，看看各自能够计算到多少 理论上应该是2n吧
看随机分布的曲线是什么分布？ #include <stdio.h>
#include <stdlib.h>
void main(void)
{
double s, total;
int i, t, n;
int k, m;
m = RAND_MAX;
printf("Input n:(0 exit)");
scanf("%d", &n);
printf("\n");
if (n == 0) exit(1);
srand((int) time(0));
total = 0.0;
for (i = 0; i < 1000000; i ++)
{
s = 0.0;
t = 0;
for (;;)
{
if (s - (double)n >= 0.000001)
{
total += (double)t;
break;
}
k = rand();
t ++;
s += (double)k / (double)m;
}
}
printf("%.6f\n", total / 1000000.0);
} Input n(0 exit)1
2.718653
Input n(0 exit)2
4.672719
Input n(0 exit)3
6.666750
Input n(0 exit)4
8.664709
Input n(0 exit)10
20.669294
Input n(0 exit)12
24.668935
Input n(0 exit)100
200.680219
[ 本帖最后由 无心人 于 2008-9-4 14:23 编辑 ] 不错,结果验证了baidu中对于n=1,2的理论结果,分别是e和e(e-1)
Monte-carlo方法的优点是算法简单,缺点是精度不够高. :)
主要是随机算法不好吧
这种随机达不到0.000001的精度要求
mathe能找个比较好的随机函数产生至少是0.0001精度的随机小数么？
我回去看我算法手册
应该能找到个 Linux下面的还可以,你在Linux下面运行吧 不过实际上即使精度再高,意义也不是很大,后面运算对精度提高有限. 另外可以看到
n越大
该数值越接近2n
但因为精度不够
只有1/32767的精度
无法准确判定
除非实现个8位精度的随机函数