这个问题是以弗拉维奥·约瑟夫斯命名的,它是1世纪的一名犹太历史学家。他在自己的日记中写道,他和他的40个战友被罗马军队包围在洞中。他们讨论是自杀还是被俘,最终决定自杀,并以抽签的方式决定谁杀掉谁。约瑟夫斯和另外一个人是最后两个留下的人。约瑟夫斯说服了那个人,他们将向罗马军队投降,不再自杀。约瑟夫斯把他的存活归因于运气或天意,他不知道是哪一个。 – https://zh.wikipedia.org/wiki/约瑟夫斯问题

这是一个比较简单的问题,n个人围成圆圈,越过k-1个人,杀掉第k个人,如此反复直到只剩下最后一个人。可以用数学推导给出答案,问题本身已经足够简单,用链表可以模拟整个过程。实现起来比较直观。这里在初始化这个链表的时候,需要注意,到了最后一人的时候,他应该指向第一个人,这样才能形成一个环状的链表,然后问题就非常简单了,从第一人开始,后面就无所谓头和尾了,按照规则来,每次杀掉一个人,直到只剩下最后一人,就是结果。从维基的解释可以看出,最后两个人没死,这没节操的事情被拿来说,如果你数学好,你就可以救自己一命(站在合适的位置,让自己是最后一个)。

Continue reading

Author's picture

Guangchuang Yu

Bioinformatics Professor @ SMU

Bioinformatics Professor

Guangzhou