今天的主题是使用循环链表来完成约瑟夫问题的求解。那么首先让我们先了解下,什么是约瑟夫问题。 据说著名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始,越过k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。问题是,给定了和,一开始要站在什么地方才能避免被处决。Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏。下图是约瑟夫问题的图例。
我们将数据规模调小一点,假定数据规模为8,[1,2,3,4,5,6,7,8]
。按照约瑟夫的算法:(ps:其中current指的是出局后重新开始的位置)
出局 | 链表调整 | current指向 |
---|---|---|
3 | [1,2,4,5,6,7,8] | 4 |
6 | [1,2,4,5,7,8] | 7 |
1 | [2,4,5,7,8] | 2 |
5 | [2,4,7,8] | 7 |
2 | [4,7,8] | 4 |
8 | [4,7] | 4 |
[1,2,4,5,6,7,8]
,current
指向4[1,2,4,5,7,8]
,current
指向7[2,4,5,7,8]
,current
指向2[2,4,7,8]
,current
指向7[4,7,8]
, current
指向4[4,7]
,current
指向4[4,7]
这个数据模型就是循环链表,为了便于大家理解,我做了一张图:
3号出局后,如下图所示:
本文使用的编码语言为swift,读者朋友们可以有自己熟悉的语言来进行编码实现。重要的是理解原理和解题思路。我想你们肯定是懂得这个道理的。
编码思路:
current走2步,然后删掉该结点,最后将current指向下一个结点。
循环第一步,直到链表为空
let list = CircleList<Int>()
for index in 1..<9 {
list.add(index)//构造约瑟夫数据
}
while !list.isEmpty() {
//走两步-->删结点-->继续执行
list.next()
list.next()
print( list.remove())
}