步长随机的行走问题

mathe

http://tieba.baidu.com/f?kz=473815763 某人从一点出发，沿直线行走，他每步所走的长度是一个在[0,1)上均匀分布的随机变量。他每走完一步，都会停下来计算一下走过的总路程。如果总路程大于或等于一个特定的正整数n，则任务完成，否则继续行走。试求他完成任务时所用步数的期望。

mathe

大家可以分别从理论公式推导和数值计算俩方面下手，看看各自能够计算到多少

无心人

理论上应该是2n吧 看随机分布的曲线是什么分布？

无心人

1. #include <stdio.h>
2. #include <stdlib.h>
4. void main(void)
5. {
6. double s, total;
7. int i, t, n;
8. int k, m;
10. m = RAND_MAX;
11. printf("Input n:(0 exit)");
12. scanf("%d", &n);
13. printf("\n");
14. if (n == 0) exit(1);
15. srand((int) time(0));
16. total = 0.0;
17. for (i = 0; i < 1000000; i ++)
18. {
19. s = 0.0;
20. t = 0;
22. for (;;)
23. {
24. if (s - (double)n >= 0.000001)
25. {
26. total += (double)t;
27. break;
28. }
29. k = rand();
30. t ++;
31. s += (double)k / (double)m;
32. }
33. }
35. printf("%.6f\n", total / 1000000.0);
36. }

复制代码

无心人

1. Input n(0 exit)1
2. 2.718653
4. Input n(0 exit)2
5. 4.672719
7. Input n(0 exit)3
8. 6.666750
10. Input n(0 exit)4
11. 8.664709
13. Input n(0 exit)10
14. 20.669294
16. Input n(0 exit)12
17. 24.668935
19. Input n(0 exit)100
20. 200.680219

复制代码

[ 本帖最后由 无心人 于 2008-9-4 14:23 编辑 ]

mathe

不错,结果验证了baidu中对于n=1,2的理论结果,分别是e和e(e-1) Monte-carlo方法的优点是算法简单,缺点是精度不够高.

无心人

主要是随机算法不好吧 这种随机达不到0.000001的精度要求 mathe能找个比较好的随机函数产生至少是0.0001精度的随机小数么？ 我回去看我算法手册 应该能找到个

mathe

Linux下面的还可以,你在Linux下面运行吧

mathe

不过实际上即使精度再高,意义也不是很大,后面运算对精度提高有限.

无心人

另外可以看到 n越大 该数值越接近2n 但因为精度不够 只有1/32767的精度 无法准确判定 除非实现个8位精度的随机函数