约瑟夫环问题整理

问题是这样的:

约瑟夫环问题:一圈共有N个人,开始报数,报到M的人自杀,然后重新开始报数,问最后自杀的人是谁?

最简单的解法就是,遍历去查找:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def test(nlist, m):
'''
从0开始的序号,此处为[0,1,2,3,4,5,6]7个人
nlist:[0,1,2,3,4,5,6]

从1开始报数,到m,比如此处的1,2,3,1,2,3
m:3

[0,1,2,3,4,5,6]-->[0,1,3,4,6]-->[0,3,4]-->[0,3]-->[3]
'''
count = 1
idx = 0
while len(nlist) != 1:
if idx == len(nlist):
idx = 0

if count % m == 0:
nlist.pop(idx)
idx -= 1

idx += 1
count += 1
return nlist[0]

这样的解法,时间复杂度是o(N*M),有没有更加合理快速的解决方式呢?

刚才的问题重新表述一下,即为如下:

N个人(编号0~(N-1)),从0开始报数,报到(M-1)的自杀,剩下的人继续从0开始报数。求最后自杀者的编号。

假设N = 10,M=4,则现在的人数编号为0-9,报数为0-3。以下是旧环每个人编号:
旧环 0 1 2 [3] 4 5 6 7 8 9。旧环中的3被剔除后,2-4就不连续了,接下来如果再循环到3的位置上的时候缺失了一个值,所以我们需要建立一个新环编号,且新环和旧环之间需要一个映射关系。

方法:将它与 N-1 个人组成的(0 ~ N-1)环进行一一映射。比如之前的之前,将剩余的 9 人与 9 人环(0~8)一一映射:新环 6 7 8 x 0 1 2 3 4 5,数据映射关系就是如下:

有两个问题需要被解决:
1、如何由新环中的 3 得到旧环中的 7 呢?
2、如何由旧环中的 7 得到新环中的 3 呢?
新环= (旧环中编号-最大报数值)%旧总人数取得,即 new_number = (old_number + value ) % old_sum
旧环= ( 新环中的数字 + 最大报数值 )% 旧总人数取得,即 old_number = ( new_number + value ) % old_sum

以上变化之后,问题由10个变为9个人,报到为3的人自杀,问题规模减小了。这样一直进行下去,最后剩下编号为0的人。用函数表示:F(1)=0。倒数第二个自杀的人,必然倒数第三轮自杀的人后的那个,所以:F(2) = F(1) + M,所以递归公式为:F(i) = F(i-1) + M,因为可能会超出总人数范围,所以要求模F(i) = (F(i-1) + M)%i。

1
2
3
4
5
6
def getNumber(N, M):
result = 0
for i in range(2, N + 1):
print(result)
result = (result + M) % i
return result

为了仔细看下这个出环和入环反查的流程,我们来看下:

注意看最后留下的序号为4的列,最后出环的序号比如为0,这就是上面F(1)=0的原因。这个序号为4的列,1人环中:0,2人环中:0,3人环中:1,4人环中:1,5人环中:0,6人环中:4,7人环中:1,8人环中:5,9人环中:0,10人环中:4。这样就得到了10个人报数4,最后留下的那个人在最初的10人环中的序号。

下面这个例子:一共有三十个人,从1-30依次编号。每次隔9个人就踢出去一个人。求踢出的前十五个人的号码:

1
2
3
4
5
a = [x 	for x in range(30)]
del_number = 8 #该删除的编号
for i in range(15):
del a[del_number]
del_number = (del_number+8)%len(a)

其中,旧环= ( 新环中的数字 + 最大报数值 )% 旧总人数取得,即 old_number = ( new_number + value ) % old_sum

下面这个例子:按递增间隔删数,直到最后只剩下一个数

题目:有数组A,每个元素存放相应的下标,即A[i]=i,要求按照1,2,3,…的规律删除数组中的元素,第一次间隔1个数,第二次间隔2个数,依次类推,到末尾时循环至开头继续进行,求最后一个被删掉的数的原始下标位置

1
2
3
4
5
6
7
8
9
10
11
12
def remove_element(input_list):
idx , num = 0,0
while len(input_list)!=1:
# 控制间隔
num+=1
idx+=num

# 如果范围溢出了,直接对idx取余
if idx>=len(input_list):
idx = idx%len(input_list)
input_list.pop(idx)
return input_list

约瑟夫环问题整理就给大家整理到这,如果大家想看更多的数据结构问题,可以关注一下我的Github,希望有所帮助。

欢迎大家关注我的个人bolg知乎,更多代码内容欢迎follow我的个人Github,如果有任何算法、代码、转行疑问都欢迎通过邮箱发消息给我。

打赏的大佬可以联系我,赠送超赞的算法资料