数学研发论坛

 找回密码
 欢迎注册
查看: 21697|回复: 96

[转载] 步长随机的行走问题

[复制链接]
发表于 2008-9-4 10:11:48 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
http://tieba.baidu.com/f?kz=473815763

某人从一点出发,沿直线行走,他每步所走的长度是一个在[0,1)上均匀分布的随机变量。他每走完一步,都会停下来计算一下走过的总路程。如果总路程大于或等于一个特定的正整数n,则任务完成,否则继续行走。试求他完成任务时所用步数的期望。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-4 10:13:25 | 显示全部楼层
大家可以分别从理论公式推导和数值计算俩方面下手,看看各自能够计算到多少
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-4 13:55:47 | 显示全部楼层
理论上应该是2n吧

看随机分布的曲线是什么分布?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-4 14:20:49 | 显示全部楼层
  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. void main(void)
  4. {
  5.   double s, total;
  6.   int i, t, n;
  7.   int k, m;

  8.   m = RAND_MAX;
  9.   printf("Input n:(0 exit)");
  10.   scanf("%d", &n);
  11.   printf("\n");
  12.   if (n == 0) exit(1);
  13.   srand((int) time(0));
  14.   total = 0.0;
  15.   for (i = 0; i < 1000000; i ++)
  16.   {
  17.     s = 0.0;
  18.     t = 0;

  19.     for (;;)
  20.     {
  21.       if (s - (double)n >= 0.000001)
  22.       {
  23.       total += (double)t;
  24.       break;
  25.       }
  26.       k = rand();
  27.       t ++;
  28.       s += (double)k / (double)m;
  29.     }
  30.   }
  31.   
  32.   printf("%.6f\n", total / 1000000.0);
  33. }
复制代码
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-4 14:21:49 | 显示全部楼层
  1. Input n(0 exit)1
  2. 2.718653

  3. Input n(0 exit)2
  4. 4.672719

  5. Input n(0 exit)3
  6. 6.666750

  7. Input n(0 exit)4
  8. 8.664709

  9. Input n(0 exit)10
  10. 20.669294

  11. Input n(0 exit)12
  12. 24.668935

  13. Input n(0 exit)100
  14. 200.680219
复制代码

[ 本帖最后由 无心人 于 2008-9-4 14:23 编辑 ]
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-4 15:35:40 | 显示全部楼层
不错,结果验证了baidu中对于n=1,2的理论结果,分别是e和e(e-1)
Monte-carlo方法的优点是算法简单,缺点是精度不够高.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-4 17:56:43 | 显示全部楼层


主要是随机算法不好吧
这种随机达不到0.000001的精度要求

mathe能找个比较好的随机函数产生至少是0.0001精度的随机小数么?

我回去看我算法手册
应该能找到个
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-4 17:57:42 | 显示全部楼层
Linux下面的还可以,你在Linux下面运行吧
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2008-9-4 17:58:41 | 显示全部楼层
不过实际上即使精度再高,意义也不是很大,后面运算对精度提高有限.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2008-9-4 18:00:46 | 显示全部楼层
另外可以看到
n越大
该数值越接近2n

但因为精度不够
只有1/32767的精度
无法准确判定

除非实现个8位精度的随机函数
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-1-16 12:28 , Processed in 0.054617 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表