约瑟夫环问题 Python3实现

2024-01-07 01:37| 来源: 网络整理| 查看: 265

Python学习笔记

尝试用Python3实现约瑟夫环问题。

约瑟夫环问题的描述：

约瑟夫斯问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程的算法中，类似问题又称为约瑟夫环。有 n个囚犯站成一个圆圈，准备处决。首先从一个人开始，越过 k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过 k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了n和 k，一开始要站在什么地方才能避免被处决？

假定n=100;k=3。

则正确的答案是：

总共有100个人，每3个人必须被处死一个，则整个被处死的队列是： 3 6 9 12 15 18 21 24 27 30 33 36 39 42 45 48 51 54 57 60 63 66 69 72 75 78 81 84 87 90 93 96 99 2 7 11 16 20 25 29 34 38 43 47 52 56 61 65 70 74 79 83 88 92 97 1 8 14 22 28 35 41 49 55 62 68 76 82 89 95 4 13 23 32 44 53 64 73 85 94 5 19 37 50 67 80 98 17 40 59 86 10 46 77 26 71 31 100 58 91 如果最后一个可以存活，那么你应该站在第91个的位置。

现在自己做个程序来验证：

1 #!/usr/local/bin/python3 2 #! version 3.0.7 3 #! encode utf-8 4 n = 100 5 survive_person = list(range(1,n+1)) 6 count = 3 7 temp = 1 8 round = 0 9 kill_person = [] 10 while(round < 10): 11 for i in survive_person : 12 print('now it\'s:',i,'turn',end='\n') 13 if temp == count : 14 kill_person.append(i) 15 survive_person.remove(i) 16 temp = 1 17 print('kill person:',i,'lenth of survive:',len(survive_person),end='\n') 18 temp += 1 19 print('the first turn is ',i,end='\n') 20 round += 1 21 print(kill_person) 22 print(survive_person)

但是答案不对：

$./josephloop.py now it's: 1 turn the first turn is 1 now it's: 2 turn the first turn is 2 now it's: 3 turn kill person: 3 lenth of survive: 99 the first turn is 3 now it's: 5 turn the first turn is 5 now it's: 6 turn kill person: 6 lenth of survive: 98 the first turn is 6 now it's: 8 turn the first turn is 8 now it's: 9 turn kill person: 9 lenth of survive: 97 the first turn is 9 now it's: 11 turn the first turn is 11 now it's: 12 turn kill person: 12 lenth of survive: 96 the first turn is 12 now it's: 14 turn the first turn is 14 now it's: 15 turn kill person: 15 lenth of survive: 95 the first turn is 15 now it's: 17 turn the first turn is 17 now it's: 18 turn kill person: 18 lenth of survive: 94 the first turn is 18 now it's: 20 turn the first turn is 20 now it's: 21 turn kill person: 21 lenth of survive: 93 the first turn is 21 now it's: 23 turn the first turn is 23 now it's: 24 turn kill person: 24 lenth of survive: 92 the first turn is 24 now it's: 26 turn the first turn is 26 now it's: 27 turn kill person: 27 lenth of survive: 91 the first turn is 27 now it's: 29 turn the first turn is 29 now it's: 30 turn kill person: 30 lenth of survive: 90 the first turn is 30 now it's: 32 turn the first turn is 32 now it's: 33 turn kill person: 33 lenth of survive: 89 the first turn is 33 now it's: 35 turn the first turn is 35 now it's: 36 turn kill person: 36 lenth of survive: 88 the first turn is 36 now it's: 38 turn the first turn is 38 now it's: 39 turn kill person: 39 lenth of survive: 87 the first turn is 39 now it's: 41 turn the first turn is 41 now it's: 42 turn kill person: 42 lenth of survive: 86 the first turn is 42 now it's: 44 turn the first turn is 44 now it's: 45 turn kill person: 45 lenth of survive: 85 the first turn is 45 now it's: 47 turn the first turn is 47 now it's: 48 turn kill person: 48 lenth of survive: 84 the first turn is 48 now it's: 50 turn the first turn is 50 now it's: 51 turn kill person: 51 lenth of survive: 83 the first turn is 51 now it's: 53 turn the first turn is 53 now it's: 54 turn kill person: 54 lenth of survive: 82 the first turn is 54 now it's: 56 turn the first turn is 56 now it's: 57 turn kill person: 57 lenth of survive: 81 the first turn is 57 now it's: 59 turn the first turn is 59 now it's: 60 turn kill person: 60 lenth of survive: 80 the first turn is 60 now it's: 62 turn the first turn is 62 now it's: 63 turn kill person: 63 lenth of survive: 79 the first turn is 63 now it's: 65 turn the first turn is 65 now it's: 66 turn kill person: 66 lenth of survive: 78 the first turn is 66 now it's: 68 turn the first turn is 68 now it's: 69 turn kill person: 69 lenth of survive: 77 the first turn is 69 now it's: 71 turn the first turn is 71 now it's: 72 turn kill person: 72 lenth of survive: 76 the first turn is 72 now it's: 74 turn the first turn is 74 now it's: 75 turn kill person: 75 lenth of survive: 75 the first turn is 75 now it's: 77 turn the first turn is 77 now it's: 78 turn kill person: 78 lenth of survive: 74 the first turn is 78 now it's: 80 turn the first turn is 80 now it's: 81 turn kill person: 81 lenth of survive: 73 the first turn is 81 now it's: 83 turn the first turn is 83 now it's: 84 turn kill person: 84 lenth of survive: 72 the first turn is 84 now it's: 86 turn the first turn is 86 now it's: 87 turn kill person: 87 lenth of survive: 71 the first turn is 87 now it's: 89 turn the first turn is 89 now it's: 90 turn kill person: 90 lenth of survive: 70 the first turn is 90 now it's: 92 turn the first turn is 92 now it's: 93 turn kill person: 93 lenth of survive: 69 the first turn is 93 now it's: 95 turn the first turn is 95 now it's: 96 turn kill person: 96 lenth of survive: 68 the first turn is 96 now it's: 98 turn the first turn is 98 now it's: 99 turn kill person: 99 lenth of survive: 67 the first turn is 99 now it's: 1 turn the first turn is 1 now it's: 2 turn kill person: 2 lenth of survive: 66 the first turn is 2 now it's: 5 turn the first turn is 5 now it's: 7 turn kill person: 7 lenth of survive: 65 the first turn is 7 now it's: 10 turn the first turn is 10 now it's: 11 turn kill person: 11 lenth of survive: 64 the first turn is 11 now it's: 14 turn the first turn is 14 now it's: 16 turn kill person: 16 lenth of survive: 63 the first turn is 16 now it's: 19 turn the first turn is 19 now it's: 20 turn kill person: 20 lenth of survive: 62 the first turn is 20 now it's: 23 turn the first turn is 23 now it's: 25 turn kill person: 25 lenth of survive: 61 the first turn is 25 now it's: 28 turn the first turn is 28 now it's: 29 turn kill person: 29 lenth of survive: 60 the first turn is 29 now it's: 32 turn the first turn is 32 now it's: 34 turn kill person: 34 lenth of survive: 59 the first turn is 34 now it's: 37 turn the first turn is 37 now it's: 38 turn kill person: 38 lenth of survive: 58 the first turn is 38 now it's: 41 turn the first turn is 41 now it's: 43 turn kill person: 43 lenth of survive: 57 the first turn is 43 now it's: 46 turn the first turn is 46 now it's: 47 turn kill person: 47 lenth of survive: 56 the first turn is 47 now it's: 50 turn the first turn is 50 now it's: 52 turn kill person: 52 lenth of survive: 55 the first turn is 52 now it's: 55 turn the first turn is 55 now it's: 56 turn kill person: 56 lenth of survive: 54 the first turn is 56 now it's: 59 turn the first turn is 59 now it's: 61 turn kill person: 61 lenth of survive: 53 the first turn is 61 now it's: 64 turn the first turn is 64 now it's: 65 turn kill person: 65 lenth of survive: 52 the first turn is 65 now it's: 68 turn the first turn is 68 now it's: 70 turn kill person: 70 lenth of survive: 51 the first turn is 70 now it's: 73 turn the first turn is 73 now it's: 74 turn kill person: 74 lenth of survive: 50 the first turn is 74 now it's: 77 turn the first turn is 77 now it's: 79 turn kill person: 79 lenth of survive: 49 the first turn is 79 now it's: 82 turn the first turn is 82 now it's: 83 turn kill person: 83 lenth of survive: 48 the first turn is 83 now it's: 86 turn the first turn is 86 now it's: 88 turn kill person: 88 lenth of survive: 47 the first turn is 88 now it's: 91 turn the first turn is 91 now it's: 92 turn kill person: 92 lenth of survive: 46 the first turn is 92 now it's: 95 turn the first turn is 95 now it's: 97 turn kill person: 97 lenth of survive: 45 the first turn is 97 now it's: 100 turn the first turn is 100 now it's: 1 turn kill person: 1 lenth of survive: 44 the first turn is 1 now it's: 5 turn the first turn is 5 now it's: 8 turn kill person: 8 lenth of survive: 43 the first turn is 8 now it's: 13 turn the first turn is 13 now it's: 14 turn kill person: 14 lenth of survive: 42 the first turn is 14 now it's: 19 turn the first turn is 19 now it's: 22 turn kill person: 22 lenth of survive: 41 the first turn is 22 now it's: 26 turn the first turn is 26 now it's: 28 turn kill person: 28 lenth of survive: 40 the first turn is 28 now it's: 32 turn the first turn is 32 now it's: 35 turn kill person: 35 lenth of survive: 39 the first turn is 35 now it's: 40 turn the first turn is 40 now it's: 41 turn kill person: 41 lenth of survive: 38 the first turn is 41 now it's: 46 turn the first turn is 46 now it's: 49 turn kill person: 49 lenth of survive: 37 the first turn is 49 now it's: 53 turn the first turn is 53 now it's: 55 turn kill person: 55 lenth of survive: 36 the first turn is 55 now it's: 59 turn the first turn is 59 now it's: 62 turn kill person: 62 lenth of survive: 35 the first turn is 62 now it's: 67 turn the first turn is 67 now it's: 68 turn kill person: 68 lenth of survive: 34 the first turn is 68 now it's: 73 turn the first turn is 73 now it's: 76 turn kill person: 76 lenth of survive: 33 the first turn is 76 now it's: 80 turn the first turn is 80 now it's: 82 turn kill person: 82 lenth of survive: 32 the first turn is 82 now it's: 86 turn the first turn is 86 now it's: 89 turn kill person: 89 lenth of survive: 31 the first turn is 89 now it's: 94 turn the first turn is 94 now it's: 95 turn kill person: 95 lenth of survive: 30 the first turn is 95 now it's: 100 turn the first turn is 100 now it's: 4 turn kill person: 4 lenth of survive: 29 the first turn is 4 now it's: 10 turn the first turn is 10 now it's: 13 turn kill person: 13 lenth of survive: 28 the first turn is 13 now it's: 19 turn the first turn is 19 now it's: 23 turn kill person: 23 lenth of survive: 27 the first turn is 23 now it's: 31 turn the first turn is 31 now it's: 32 turn kill person: 32 lenth of survive: 26 the first turn is 32 now it's: 40 turn the first turn is 40 now it's: 44 turn kill person: 44 lenth of survive: 25 the first turn is 44 now it's: 50 turn the first turn is 50 now it's: 53 turn kill person: 53 lenth of survive: 24 the first turn is 53 now it's: 59 turn the first turn is 59 now it's: 64 turn kill person: 64 lenth of survive: 23 the first turn is 64 now it's: 71 turn the first turn is 71 now it's: 73 turn kill person: 73 lenth of survive: 22 the first turn is 73 now it's: 80 turn the first turn is 80 now it's: 85 turn kill person: 85 lenth of survive: 21 the first turn is 85 now it's: 91 turn the first turn is 91 now it's: 94 turn kill person: 94 lenth of survive: 20 the first turn is 94 now it's: 100 turn the first turn is 100 now it's: 5 turn kill person: 5 lenth of survive: 19 the first turn is 5 now it's: 17 turn the first turn is 17 now it's: 19 turn kill person: 19 lenth of survive: 18 the first turn is 19 now it's: 31 turn the first turn is 31 now it's: 37 turn kill person: 37 lenth of survive: 17 the first turn is 37 now it's: 46 turn the first turn is 46 now it's: 50 turn kill person: 50 lenth of survive: 16 the first turn is 50 now it's: 59 turn the first turn is 59 now it's: 67 turn kill person: 67 lenth of survive: 15 the first turn is 67 now it's: 77 turn the first turn is 77 now it's: 80 turn kill person: 80 lenth of survive: 14 the first turn is 80 now it's: 91 turn the first turn is 91 now it's: 98 turn kill person: 98 lenth of survive: 13 the first turn is 98 now it's: 10 turn the first turn is 10 now it's: 17 turn kill person: 17 lenth of survive: 12 the first turn is 17 now it's: 31 turn the first turn is 31 now it's: 40 turn kill person: 40 lenth of survive: 11 the first turn is 40 now it's: 58 turn the first turn is 58 now it's: 59 turn kill person: 59 lenth of survive: 10 the first turn is 59 now it's: 77 turn the first turn is 77 now it's: 86 turn kill person: 86 lenth of survive: 9 the first turn is 86 now it's: 100 turn the first turn is 100 now it's: 10 turn kill person: 10 lenth of survive: 8 the first turn is 10 now it's: 31 turn the first turn is 31 now it's: 46 turn kill person: 46 lenth of survive: 7 the first turn is 46 now it's: 71 turn the first turn is 71 now it's: 77 turn kill person: 77 lenth of survive: 6 the first turn is 77 now it's: 100 turn the first turn is 100 now it's: 26 turn kill person: 26 lenth of survive: 5 the first turn is 26 now it's: 58 turn the first turn is 58 now it's: 71 turn kill person: 71 lenth of survive: 4 the first turn is 71 now it's: 100 turn the first turn is 100 now it's: 31 turn kill person: 31 lenth of survive: 3 the first turn is 31 now it's: 91 turn the first turn is 91 now it's: 100 turn kill person: 100 lenth of survive: 2 the first turn is 100 now it's: 58 turn the first turn is 58 now it's: 91 turn kill person: 91 lenth of survive: 1 the first turn is 91 [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60, 63, 66, 69, 72, 75, 78, 81, 84, 87, 90, 93, 96, 99, 2, 7, 11, 16, 20, 25, 29, 34, 38, 43, 47, 52, 56, 61, 65, 70, 74, 79, 83, 88, 92, 97, 1, 8, 14, 22, 28, 35, 41, 49, 55, 62, 68, 76, 82, 89, 95, 4, 13, 23, 32, 44, 53, 64, 73, 85, 94, 5, 19, 37, 50, 67, 80, 98, 17, 40, 59, 86, 10, 46, 77, 26, 71, 31, 100, 91] [58]

程序应该逻辑上是正确的。但是第一次Kill了3以后，4就不显示了呢？

排查下发现survive_person.remove(i)这个动作导致了问题。CSDN还是有大神的，https://blog.csdn.net/guan666/article/details/71511948 就描述了这个问题。

重新修改如下：

1 #!/usr/local/bin/python3 2 #! version 3.0.7 3 #! encode utf-8 4 import copy 5 import sys 6 def joseph(n,count): 7 n = 100 8 survive_person = list(range(1,n+1)) 9 count = 3 10 temp = 1 11 round = 0 12 kill_person = [] 13 while len(survive_person)>1 : 14 for i in survive_person : 15 print('now it\'s:',i,'turn','count is ',temp,end='\n') 16 if temp == count : 17 print('kill person:',i,'lenth of survive:',len(survive_person)-1,end='\n') 18 print('the first turn is ',i,end='\n') 19 kill_person.append(i) 20 cache = copy.deepcopy(survive_person) 21 cache.remove(i) 22 survive_person = copy.deepcopy(cache) 23 cache = [] 24 temp = 0 25 temp += 1 26 round += 1 27 print(kill_person) 28 print(survive_person) 29 if __name__ == '__main__': 30 amount=input('please input amount:') 31 step=input('please input step:') 32 joseph(amount,step)

完美解决！！！

【本文地址】

公司简介

联系我们