什么是约瑟夫斯问题?

易书科技是一家以内容制造、内容创意、内容运营为焦点的多范畴融合型成长的企业。本着内容精品化及跨界融合成长的理念,数字、音频、课程等载体)、影视IP、二维动画、视频等营业。

这是一个陈旧的传说:有64名兵士被仇敌俘虏了,仇敌号令他们排成一个圆圈,编上号码1,2,3,…,64,仇敌把1号杀了,又把3号杀了,他们是隔一个杀一个如许转着圈杀,最初剩下一小我,这小我就是约瑟夫斯,请问约瑟夫斯是几多号?这就是“约瑟夫斯问题”。

这个问题是比力容易解答的:仇敌从1号起头,隔一个杀一个,第一圈把奇数号码的兵士全杀死了。剩下的32名兵士需要从头编号,而仇敌在第二圈杀死的是从头编排的奇数号码。

因为第一圈剩下的全数是偶数号2,4,6,8,…,64。把它们全数用2除,得1,2,3,4,…,32,这是第二圈从头编的号码,第二圈杀过之后,又把奇数号码都杀掉了,还剩下16小我,如斯下去,能够想到最初剩下的必然是64号。

64=26,它能够持续被2整除6次,是从1到64中能被2整除次数最多的数,因而,最初必然把64号剩下,从64=26还能够看到,是转这6圈之后,把约瑟夫斯剩下来的。

若是有65名兵士被俘,仇敌仍是按上述方式残杀兵士,最初剩下的仍是64号约瑟夫斯吗?

不是了,由于第一小我被杀后,也就是1号被杀后,第二个被杀的必然是3号,若是把1号解除在外,那么剩下的仍是64小我,对于剩下这64小我,新1号就该当是本来的3号,如许本来的2号就变成新的64号了,所以剩下的必然是本来的2号。

对于一般环境来说,若是本来有2k小我,最初剩下的必然是2k号;若是本来有2k+1小我,最初剩下的是2号;若是本来有2k+2小我,最初剩下的是4号……若是本来有2k+m小我,最初剩下的是2m号。

下面把问题改一下:不让被俘的兵士站成圆圈,而排成一条直线号起头,隔一个杀一个,然后再从头编号,从新1号起头,再隔一个杀一个,问最初仍是约瑟夫斯吗!

若是战俘人数是65人呢?剩下的仍是约瑟夫斯,只需人数不跨越128人,也就是人数小于27,那么最初剩下的老是约瑟夫斯,由于从1到128两头,能被2整除次数最多的就是64,而仇敌每次都是杀奇数号留偶数号,所以64号老是最初被留下的人。

更多精彩报道,尽在https://www.bwjyxx.com

About the author

发表评论

电子邮件地址不会被公开。 必填项已用*标注