约瑟夫环问题的递归解法

题源:2017蓝桥杯国赛

基本问题描述:
已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为1的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。而问题一般是判断第k个出列或最后出列的人的编号.

有些人在解决这类问题时会把编号视为0~n-1,最后将结果+1而得原问题的解,但在此我就不这样做了.

解题思路:

此题最简单的做法可以使用模拟法完成,但不论是用数组模拟还是链表模拟,复杂度都比较高(链表模拟法每次删人需要迭代n次,总复杂度为O(mn),而数组模拟法复杂度甚至更高).

该题问题的关键在于当有人被T出后队列中剩余的编号列表就不再连续了,此时再想使用数值计算的方法难以得到下一个位置,不得已才需要使用模拟的办法得到位置.

另一种办法是每次去除人后将新环的编号重排,这样编号顺序就再次连续了,而我们所要做的就是得到新编号与旧编号之间的对应关系计算方法(以便最后能够回推得到最终的答案).这样的话寻找第k次删除人的编号问题就变成了从其第k-1次重排的编号中回推得到它在原始队列中的…编号,复杂度只有O(k)/O(n)(但是这有一个问题,如果要按顺序得出每个出列的人的编号,这样做的复杂度就没有什么优势了).

举例来说:

起始n=10,m=6

初始情况为:

1   2   3   4   5   6   7   8   9   10

删除一人后:

1 2 3 4 5 ① 7 8 9 10

队列重排:

5 6 7 8 9 ① 1 2 3 4

再删一人:

5 ② 7 8 9 ① 1 2 3 4

我们现在要找到②处在原始序列中对应的编号,首先发现它在新队列中编号为6,而计算首次删除的①在队列中编号也为6,即新队列的编号是在前队列的基础上+6,那么将其相加后再对前队列的总人数求余即可得到他在前队列中的编号了((6+6)%10).

以此类推我们也可以从第k次删除后的情况反推出其在初始时的位置.

递归版代码:

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据