Welcome

约瑟夫环

约瑟夫环

前言: 貌似高中老师讲过,但是数学课被我睡过去了,罪孽深重啊,现在补过来

已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1,最后[1] 结果+1即为原问题的解

这个是约瑟夫环的问题的大概题目

看到这个题目,我的脑海中闪过的是最直接的方式,就是仿照这个游戏过程来做

模拟法

如果是按照这个游戏规则来模拟,那么,我可以建立一个首尾相连的链表,然后不断地循环这个链表,每次数到m的时候,被选中的单元就从链表中去掉,然后接着从下一个开始重新数到m的时候把该项去掉,不断的循环下去,直到最后剩下的唯一的一个单元,因为现在这边是从0~n-1,所以最后的结果是需要加1的,按照这种方法,编写出以下的代码,最近比较少写python,有点生疏了,不要介意,有什么问题可以和我讨论下 :P

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Ysf:
def __init__(self, step_size, amount):
self.step_size = step_size
self.amount = amount
self.items = []
for each in range(0, amount):
self.items.insert(0, each)
self.items.reverse()
def run(self):
while len(self.items) > 1:
for each in range(0, self.step_size):
if (each + 1) == self.step_size:
self.items.pop()
else:
self.items.insert(0, self.items.pop())
return self.items.pop()
ysf = Ysf(2, 5)
print ysf.run() + 1

虽然解决了问题,但是也可以看到,这个时间复杂度可是nm,如果是数值稍微带点的mn的话,那就变得相当糟糕了

数学方法

两个变量决定一个输出,这个过程很符合函数的思想,所以马上就会觉得,是不是有什么通用的公式可以直接用,不需要自己去模拟这个过程就可以快捷的获取最终的答案,毕竟采用模拟的方法也可以看到,时间复杂度是O(nm),如果是人数很多的或者m值很大的话将会很呛人,所以现在来寻找一下通用的方法吧。

每次循环m次,然后去掉一个单元的结果是同上一次循环m次去除单元这个动作是相关的是吧,如果是这种情况,可以想到的应该马上就是递归了,

1
F(n) = F(n-1) + m

同时又有

1
F(n-1) = F(n-2) + m

因为在加上m的时候可能大于总数(现在是i),所以修改成这样子

1
F(n) = (F(n-1) + m) % i

按照上边的方法,如果是按照递归的算法也可以写出来,但是我现在是采用了循环的写法来写

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class YSF:
def __init__(self, step_size, amount):
self.step_size = step_size
self.amount = amount
self.items = []
for each in range(0, amount):
self.items.insert(0, each)
self.items.reverse()
def run(self):
result = 0
for each in range(2, self.amount + 1):
result = (result + self.step_size) % each
return result
ysf = YSF(2, 5)
print ysf.run() + 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class YSF:
def __init__(self, step_size, amount):
self.step_size = step_size
self.amount = amount
self.items = []
for each in range(0, amount):
self.items.insert(0, each)
self.items.reverse()
def run(self, step_size, amount):
if amount == 1:
return 0
else:
return (self.run(step_size, amount - 1) + step_size) % amount
ysf = YSF(2, 5)
print ysf.run(2, 5) + 1

从上面的代码可以看到,现在的时间复杂度已经变成了O(n)了,和O(nm)相比好了一些