zgg___
发表于 2012-3-29 14:43:35
da := Module[{n = Length}, Append Range, 0] + s Range];
rr := Prepend, 0];
gg := Module[{s = Table, ds, i},If, 1]]];
Do]] Binomial; If;]; s += ds;, {i, k}];
If] Binomial; If;]; s += ds;, {i, 0, k}]];
Append];
m = 30;
s1 = {{0, 0, 1}, {0, 2, 0}, {1, 0, 0}}; ss = {{1, 0}}; n = 2;
Do, {i, 0, n}]; AppendTo]];, {m - 2}]; // Timing
sk = Map[#/Apply &, ss]; // Timing
ans = {0, 1}; Do]];, {k, m - 1}]; // Timing
ans // ListPlot
把代码贴出来吧。
的确是分2步，其中sk就是第2步的输入（例如：用{1, 0}表示2人射击后剩余0人和1人的几率, {1/4, 3/4, 0}表示3人射击后剩余0、1、2人的几率），ans的那行去做10层说的工作。ss是用状态数表示的sk（例如：{1, 0}对应2人时共有1种射击方式的分布，{2, 6, 0}对应3人时所有的8种射击方式的分布），看，初始时n=2，只有一个ss为{1, 0}。
对于要计算ss的第1步，主要由gg来实现，gg表示有n个人时，其中k个人开枪（其余人不开枪）的状态结果（s0参数只是为了递推存数使的），我们想要的ss就是gg。看，初始时s1 = {{0, 0, 1}, {0, 2, 0}, {1, 0, 0}}，分别表示gg，gg和gg。可以看到，4个gg都是可以用这3个已知的gg来算出的，然后就递推吧。这个算法求的是精确值，如果改为数值计算或许效率更高些。
计算结果在0.5上下震荡，还是比较有趣的。
KeyTo9_Fans
发表于 2012-3-30 21:08:50
“计算结果在0.5上下震荡，还是比较有趣的。”
是的，很有趣的结果。
猜想：计算结果不收敛，上极限大于$0.5$，下极限小于$0.5$。
zeroieme
发表于 2012-3-30 23:37:09
但波动好象在衰减
wayne
发表于 2012-4-3 10:44:09
我算的结果好像不太一样，不知道是不是我问题理解的有误。
设p(n)表示n个人经过足够多次数的 敲钟互杀(无自杀情况) 之后，幸存1人的概率，则算得
p(3)=3/4
p(4)=32/43
p(5)=15/22
思路如下：
wayne
发表于 2012-4-3 10:59:09
n个人，一次敲钟后，有m 个人立刻死亡.
如果2<=m<=n-1 ，所有可能的情况有 C(n,m)*(m-1)^m*m^(n-m) 种
如果m=n，即全部死了，这个情况就相当于错位排列的个数了。
编程序如下：f=1;f=0;
ans=Table=Sum(m-1)^m m^(n-m)*f,{m,2,n-1}]/(Sum(m-1)^m m^(n-m),{m,2,n-1}]+Subfactorial),{n,3,200}];图像跟6楼 倒是极其相似的：
mathe
发表于 2012-4-3 12:27:28
n个人，一次敲钟后，有m 个人立刻死亡.
如果2
wayne 发表于 2012-4-3 10:59 http://bbs.emath.ac.cn/images/common/back.gif
你没有考虑包含了大于m个人死去情况
wayne
发表于 2012-4-4 11:25:28
18# mathe
如果2<=m<=n-1 ，所有可能的情况有 C(n,m)*(m-1)^m*m^(n-m) 种
嗯 ，这个计数有问题
wayne
发表于 2012-4-4 12:38:09
终于和zgg的答案完全一致了。
n个人敲一次钟，互相射击，共有(n-1)^n种情况，其中死掉m个人的情况，计数个数设为g(n,m),这个可利用容斥原理，
$g(n,m) = C_{n}^{m} \sum _{j=0}^m (j-1)^j (-1)^{j+m} j^{n-j} C_{m}^{j}$
于是程序为：g := Binomial Sum[(-1)^(m + j) Binomial j^(n - j) (j - 1)^j, {j, 0, m}];
f = 1; f = 0;ans = Table = Sum*f, {m, 2, n - 1}]/((n - 1)^n), {n, 3, 50}]f(3)=3/4,
f(4)=16/27,
f(5)=15/32,
f(6)=11704/28125
wayne
发表于 2012-4-4 12:59:42
6# zgg___
计算式子算是找到了，可似乎并不能明显的提高速度。
很好奇zgg是怎么算到300多的
mathe
发表于 2012-4-4 17:22:36
n个人一次射击有$(n-1)^n$种等概率情况。
设其中1～k号死亡,k+1~n号存活的方案总数为$u(n,k),k>=2$,于是一轮射击正好死亡k个人的方案总数为$C_n^ku(n,k)$
由于我们知道所有k+1~n号存活的方案总数为$k^{n-k}(k-1)^k$
于是我们得出
$k^{n-k}(k-1)^k=\sum_{h=0}^{k-2} C_k^h u(n,k-h)$
或者说，我们得出递推公式$u(n,k)=k^{n-k}(k-1)^k-\sum_{h=1}^{k-2}C_k^h u(n,k-h)$
特别的，$u(n,2)=2^{n-2}$