数学上的约瑟夫问题怎么解

 我来答
匿名用户
2013-07-20
展开全部
在M比较小的时候 ,可以用笔算的方法求解,
M=2
即N个人围成一圈,1,2,1,2的报数,报到2就去死,直到只剩下一个人为止。
当N=2^k的时候,第一个报数的人就是最后一个死的,
对于任意的自然数N 都可以表示为N=2^k+t,其中t<n/2
于是当有t个人去死的时候,就只剩下2^k个人 ,这2^k个人中第一个报数的就是最后去死的。这2^k个人中第一个报数的人就是2t+1
于是就求出了当M=2时约瑟夫问题的解:
求出不大于N的最大的2的整数次幂,记为2^k,最后一个去死的人是2(N-2^k)+1
M=3
即N个人围成一圈,1,2,3,1,2,3的报数,报到3就去死,直到只剩下一个人为止。
此时要比M=2时要复杂的多
我们以N=2009为例计算
N=2009,M=3时最后被杀死的人记为F(2009,3),或者可以简单的记为F(2009)
假设现在还剩下n个人,则下一轮将杀死[n/3]个人,[]表示取整,还剩下n-[n/3]个人
设这n个人为a1,a2,...,a(n-1),an
从a1开始报数,一圈之后,剩下的人为a1,a2,a4,a5,...a(n-n mod 3-1),a(n-n mod 3+1),..,an
于是可得:
1、这一轮中最后一个死的是a(n-n mod 3),下一轮第一个报数的是a(n-n mod 3+1)
2、若3|n,则最后死的人为新一轮的第F(n-[n/3])个人
若n mod 3≠0 且f(n-[n/3])<=n mod 3则最后死的人为新一轮的第n-[n/3]+F(n-[n/3])-(n mod 3)人
若n mod 3≠0 且f(n-[n/3])>n mod 3则最后死的人为新一轮的第F(n-[n/3])-(n mod 3)人
3、新一轮第k个人对应原来的第 3*[(k-1)/2]+(k-1)mod 2+1个人
综合1,2,3可得:
F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4,F(6)=1,
当f(n-[n/3])<=n mod 3时 k=n-[n/3]+F(n-[n/3])-(n mod 3),F(n)=3*[(k-1)/2]+(k-1)mod 2+1
当f(n-[n/3])>n mod 3时 k=F(n-[n/3])-(n mod 3) ,F(n)=3*[(k-1)/2]+(k-1)mod 2+1
这种算法需要计算 [log(3/2)2009]次 这个数不大于22,可以用笔算了
于是:
第一圈,将杀死669个人,这一圈最后一个被杀死的人是2007,还剩下1340个人,
第二圈,杀死446人,还剩下894人
第三圈,杀死298人,还剩下596人
第四圈,杀死198人,还剩下398人
第五圈,杀死132人,还剩下266人
第六圈,杀死88人,还剩下178人
第七圈,杀死59人,还剩下119人
第八圈,杀死39人,还剩下80人
第九圈,杀死26人,还剩下54人
第十圈,杀死18人,还剩36人
十一圈,杀死12人,还剩24人
十二圈,杀死8人,还剩16人
十三圈,杀死5人,还剩11人
十四圈,杀死3人,还剩8人
十五圈,杀死2人,还剩6人
F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4,F(6)=1,
然后逆推回去
F(8)=7 F(11)=7 F(16)=8 f(24)=11 f(36)=16 f(54)=23 f(80)=31 f(119)=43 f(178)=62 f(266)=89 f(398)=130
F(596)=191 F(894)=286 F(1340)=425 F(2009)=634
-----来自百度
已赞过 已踩过<
你对这个回答的评价是?
评论 收起
推荐律师服务: 若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询

为你推荐:

下载百度知道APP,抢鲜体验
使用百度知道APP,立即抢鲜体验。你的手机镜头里或许有别人想知道的答案。
扫描二维码下载
×

类别

我们会通过消息、邮箱等方式尽快将举报结果通知您。

说明

0/200

提交
取消

辅 助

模 式