智游城

 找回密码
 注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 2601|回复: 3

追车问题

[复制链接]
老陈 发表于 2020-4-11 17:26:35 来自手机 | 显示全部楼层 |阅读模式
在一条单线无线长的公路上,有100辆汽车以不同的速度同一方向行驶,初始汽车的前后距离15米,每辆汽车的速度都不变,如果发生追尾后面的车退出,前面的车继续。问达到稳定状态时剩余汽车的期望值多少?
ahthwl 发表于 2020-4-12 14:09:48 | 显示全部楼层
假设N辆车的速度是从1~N的随机排序数组。比如4辆车的速度分别为[1,2,3,4],某一个随机数组为[3,1,2,4]
那么针对单个随机数组求最终车辆的数量等价于:求以数组最后一位为终点的严格单调递增子序列的长度。
例如[3,1,2,4]以4为终点的单调递增子序列:从4往前第一个小于4的是2,子序列为[4,2],再往前小于2的是1,子序列为[4,2,1],最终是三辆车。
[2,3,1,4]以4为终点的单调递增子序列为[4,1],最终有两辆车剩下来。
针对速度列表的所有随机数组都进行单调递增子序列的计算,总和除以全排列中数组的数量,就是最终的期望值。
我没有去求全排列然后计算期望值,简单随机排序了10000次,最终期望值是5.1左右。
ahthwl 发表于 2020-4-12 14:24:30 | 显示全部楼层
又想到了用动态规划的方式去精确求解,思路就不赘述了。代码如下:
dp=[0 for i in range(100)]
dp[0]=1
dp[1]=2
for i in range(2,100):
    dp[i]=sum(dp[:i])/i+1
print(sum(dp)/100)

最终期望值是5.187377517639617
 楼主| 老陈 发表于 2020-5-9 18:37:54 来自手机 | 显示全部楼层
结果:Σ(1/k){k=1,100}
您需要登录后才可以回帖 登录 | 注册

本版积分规则

手机版|Archiver|智游城论坛

GMT+8, 2024-3-29 21:27 , Processed in 0.039968 second(s), 6 queries , Redis On.

Powered by Discuz! X3.2

© 2001-2012 Comsenz Inc.

返回顶部