一.单向链表模拟
class Node: def __init__(self, num, next): self.num = num self.next = next a = [] # n个人 n = 3 # 数到k的人死去 k = 2 for i in range(0, n): a.append(Node(i, (i + 1) % n)) # 计数器 counter = 1 # 现在的人 now = a[0] while True: next = a[now.next] if next == now:#就剩下一个人了,游戏结束 break else: counter += 1 if counter == k:#计数器为k,要死人了 counter = 0 now.next = next.next print(str(next.num)+" has died",end=' ') else:#不死人,now=next,向后走一格 now=next #打印唯一的幸存者 print(now.num)
二.递推公式法
f(n)=[f(n-1)+k]%n
编号从0开始,f(n)表示n个人数到k的死去最后的幸存者,显而易见第一个死去的人是(k-1)%n,死者后面一人编号为0,再后面为1,以此类推,构成一个新的f(n-1).所以f(n)中的幸存者就是f(n)=[f(n-1)+k]%n.
#n个人 n=100 a=[0]*n #数到k的人死去 k=2 a[1]=0 for i in range(1,len(a)): a[i]=(a[i-1]+k)%i for i in range(1,len(a)): print(a[i],end=' ')
输出为
0 0 2 0 2 4 6 0 2 4 6 8 10 12 14 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42 44 46 48 50 52 54 56 58 60 62 64 66 68 70
很显然可以找到规律,数字周期为第0个周期长度为1,第1个周期长度为2,第2个周期长度为4,第三个周期长度为8....对于数字n,它所在的周期为log2(n),数字n在周期中的列数为n-2^log2(n).
当k=2时,f(n)=[n-2^log2(n)]*2
验证上述结论:
from math import * for i in range(1,100): print((i-2**int(log2(i)))<<1)
在上述表述中,一切计数都从0开始.从0开始,你会发现问题的表达形式会简单很多,从0开始计数确实应该成为一种习惯.
三.k=2时的另一种递推公式
f(2n)=2*f(n)
f(2n+1)=f(n)+1
下标一律从0开始,当有2n个人,数完一圈之后,奇数号人全跪了.给剩下的人重新编号,原来的0号还是0号,原来的2号变成1号,原来4号变成2号....即原来的2n号变成了现在的n号.剩下n个人的幸存者为第f(n)号,这个人对应原来的f(n)*2号.所以f(2n)=2f(n).
当有2n+1个人,数完一圈之后,奇数号人全跪了,最后一个人2n号没有跪,下一个跪的是0号.这样第一圈算跪了n+1个人.对剩下的n个人重新编号,原来的2号变成0号,原来的4号变成1号,原来的6号变成2号,原来的8号变成3号....即原来的2n号变成了现在的n-1号.剩下n个人的幸存者为f(n)号,对应原来的(f(n)+1)*2号,所以f(2n+1)=2f(n)+2.
对于这种问题,关键在于重新编号.
四.比较快的递推公式法
递推公式f(n)=(f(n-1)+k)%n,复杂度为O(n).有一个更快的递推式:
f(n)=[f(n-n/k)+n-n%k+f(n-n/k)/(k-1)]%n
f(n-n/k)第一轮输完之后,n/k个人死了,就剩下n-n/k个人.剩下的任务就是找到f(n-n/k)这个人对应f(n)中的哪个人.f(n-n/k)每(k-1)个人中可以插入一个死者,这些死者是要算数的.最后一个死者是n-n%k,他的下一个为0号,这是偏移量.这个递推公式复杂度
f(n)=常数*f(n-n/k)
复杂度为log(n)级别.
五.关于约瑟夫环
约瑟夫环花样繁多,比如给定一个数组
1 4 当第一个人死去,下一个死去的人是第一个人左边的第4个人
2 3 当2号人死去,下一个死去的人是第二个人左边第3个人
3 4 当3号人死去,下一个死的人是他左边的第4个人
...
给定一个数组,问最后的幸存者是谁.
这个问题可以用线段树来求解.