求通项公式

aimisiyou

@282842712474   能不能再演算下\(m=4\)时\(b_n=?\)的推导过程。

初步模拟你的演算过程，似乎得到$$\beta\left(\frac{4}{3}\right)^n<b_n<\beta\left(\frac{4}{3}\right)^n+2$$,怎么判断$$b_n=？$$

aimisiyou

@kastin   就是不想用递归啊！所以想找到通用递归公式$$b_{n+1}=b_n+\left[\frac{b_n}{m-1}\right]$$的一般解析式（像那种取整函数）,当然对于不同的\(m\)，初始值的个数不同。

aimisiyou

故而推广到一般情况，对于N个人，按1~m循环报数，抱1的出圈，最后出圈的人开始标号为\(m*N-b_n\),其中\(n\)为满足\[\frac{b_n}{m-1}\ge N\]时取得最小自然数。现在是如何根据 \(\D b_{n+1}=b_n+\left[\frac{b_n}{m-1}\right]\) (\(n\ge k;\ b_2,\dots,b_k\)为初始值），求\(b_n\)

aimisiyou

初步写了个笔算方法：$$b_2=2m-2$$ $$b_3=3m-2-(3m-2-b_2)mod2$$ $$b_4=4m-2-(4m-2-b_3)mod3$$ $$……直至满足b_{k+1}=b_k+[\frac{b_k}{m-1}]为止（通常k不到m就能满足）$$   然后采用$$b_{n+1}=b_n+[\frac{b_n}{m-1}]$$来循环运算（对m很小时可大大缩小循环次数），$$当[\frac{b_n}{m-1}]>=N,即b_n>=(m-1)N$$时停止循环，最后结果为$$m*N-b_n$$举个例子吧，取$$N=100，m=6$$,$$b_2=2m-2=2*6-2=10$$$$b_3=3m-2-(3m-2-b_2)mod2=3*6-2-(3*6-2-10)mod2=16$$$$b_4=4m-2-(4m-2-b_3)mod3=4*6-2-(4*6-2-16)mod3=22$$$$b_5=5m-2-(5m-2-b_4)mod4=5*6-2-(5*6-2-22)mod4=26,此时满足b_5=b_4+[\frac{b_4}{m-1}]$$于是$$b_6=b_5+[\frac{b_5}{m-1}]=26+[\frac{26}{5}]=31……$$可算得$$b_{21}=448$$$$b_{22}=537>5*100$$,故$$m*N-b_n=6*100-537=63$$

kastin

aimisiyou 发表于 2015-4-21 09:59
@kastin   就是不想用递归啊！所以想找到通用递归公式$$b_{n+1}=b_n+\left[\frac{b_n}{m-1}\right]$$的一般 ...

原来是这样，但是这种类型的大多是得不到有限的解析表达式的，事实上我用matlab测试过，类似的问题（无论是留报数为1还是报数为m的情形），当固定m，但是总人数变化时，最后一个报数或者剩余存活的人的原始编号是有规律的：

排除N较小时候的特殊情况，比如m=4，那么就排除总人数N=4~8的情形，剩下N>8的情况中，最后一个报数的原始编号则存在一种分段线性同余的关系，如下图所示

结果

其中蓝色的点形成一条条倾斜的直线段（其差分值为m），这些线段的平移距离（上图中红色圆圈之间的间距）大概是5~6次多项式规律（拟合优度等于1，但RSME不为零）。因此用表达式来给出通解释比较困难的，困难之处在于分段界定以及每段直线段内含点的个数。
并且这些蓝色点是上的出现顺序是先沿着直线上升走完直线段，然后下降到新的直线段再上升。而在N较小的时候，这种规律会出被打破，出现一些意外，故即使有符合后面图像规律的表达式，前面的点却不会满足。

aimisiyou

kastin 发表于 2015-4-25 13:50
原来是这样，但是这种类型的大多是得不到有限的解析表达式的，事实上我用matlab测试过，类似的问题（无论 ...

$$m*N-b_n正好反应你图上所表现的$$，$$当N在[N_1,N_2]区间时，b_n为一定值，在此区间内，出圈者编号以m等差递增$$$$随着区间的推移，b_n在下一区间，为另一定值……$$
通过分析可得，$$若N在[N_1,N_2]区间时取b_n，则N在[N_2+1,N_3]上b_{n+1}=b_n+N_2,且N_3=[\frac{b_{n+1}}{m-1}]$$