n个数字平均随机抽取多少次能使得每个数字都出现过m次以上？包括m次

jjkkt · 发表于 2014-12-3 14:00:07

您需要登录才可以下载或查看，没有账号？欢迎注册

×

BeerRabbit · 发表于 2014-12-4 10:32:40

这问题我曾经考虑过，有一些初步的结论，但我现在无法添加附件（可能是我IE的问题）

KeyTo9_Fans · 发表于 2014-12-4 11:00:59

当$m=1$时，次数为$n\cdot H_n$。

其中$H_n=\sum_{i=1}^n 1/i$。

$m>1$比较难解。不知道是否有现成的结论。

BeerRabbit · 发表于 2014-12-9 17:38:06

本帖最后由 BeerRabbit 于 2014-12-9 17:59 编辑

压缩包里的PDF是问题解决方法的分析过程，其实思路很简单，归根结底就是递归，主要还是算法的设计优化。

其中的Collect.m文件是文档内收录的那个。对这个函数我用VB做过一个小小的计算工具。例如这个例子：

MultiCollect.m是后来对一个更复杂一点的模型的实现，这个模型的表述是这样的：
“进入一个房间后，同时开启房间内的N个盒子，每个盒子都独立进行原来简化模型的掉落判定，求各个箱子的各个掉落物品达到一定数目时，进入房间的次数期望。”

算法分析与Matlab实现.rar (481.22 KB, 下载次数: 4)

KeyTo9_Fans · 发表于 2014-12-9 21:22:21

不错。

将该算法应用到楼主的问题，

时间复杂度为$O((n+m)^m/((m-1)!))$，

空间复杂度为$O((n+m)^m/(m!))$。

$m$小的时候还能接受，

$m$大了就不行了。

不知道是否有复杂度更低的算法。

账号		自动登录	找回密码
密码			欢迎注册

[求助] n个数字 平均随机抽取多少次能使得每个数字都出现过m次以上？包括m次