1 约瑟夫问题描述

  1.    在古罗马人占领乔塔帕特后，39个犹太人与约瑟夫和他的朋友躲到一个洞中。39个犹太人决定宁死也不被敌人抓到，于是商定以一种特殊的方式自杀: 41个人排成一个圆图，由第一个人开始报数，每报数到3的人就必须自杀，直到所有人都自杀身亡为止。但是约瑟夫及其朋友并不想死，那么请问约瑟夫及其朋友应该怎样安排自己的位置才能逃过一劫?

2 问题分析

  1.     如果约瑟夫及其朋友不想死，那么他们将是最后剩下的两个人，因此，问题的关键在于如何安排他们的位置才能将他们留到最后。

3 Python程序模拟

下面我们用程序模拟这个自杀过程，找出最后两个人的位置，这两个位置就是约瑟夫及其朋友的位置。

  1. def move(man,sep):
  2.     """
  3.     将man列表向左移动sep单位，最左边的元素向列表后面添加，相当于队列顺时针移动
  4.     """
  5.     for i in range(sep):
  6.         item = man.pop(0)
  7.         man.append(item)
  8. def play(man=41,sep=3,rest=2):
  9.     """
  10.     man:玩家个数
  11.     sep:杀死数到的第几个人
  12.     rest:幸存者数量
  13.     """
  14.     print('总共%d个人，每报数到第%d的人自杀，最后剩余%d个人'%(man,sep,rest))
  15.     man=[i for i in range(1,man+1)]      #初始化玩家队列
  16.     print("玩家队列：",man)
  17.     sep-=1                               #数两个数，到第3个人时就自杀
  18.     while len(man)>rest:
  19.         move(man,sep)
  20.         print('kill',man.pop(0))
  21.     return man
  22. servive=play()
  23. print("最后逃生的人编号是：",servive)

测试及运行结果如下：

  1. 总共41个人，每报数到第3的人自杀，最后剩余2个人
  2. 玩家队列： [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41]
  3. kill 3
  4. kill 6
  5. kill 9
  6. kill 12
  7. kill 15
  8. kill 18
  9. kill 21
  10. kill 24
  11. kill 27
  12. kill 30
  13. kill 33
  14. kill 36
  15. kill 39
  16. kill 1
  17. kill 5
  18. kill 10
  19. kill 14
  20. kill 19
  21. kill 23
  22. kill 28
  23. kill 32
  24. kill 37
  25. kill 41
  26. kill 7
  27. kill 13
  28. kill 20
  29. kill 26
  30. kill 34
  31. kill 40
  32. kill 8
  33. kill 17
  34. kill 29
  35. kill 38
  36. kill 11
  37. kill 25
  38. kill 2
  39. kill 22
  40. kill 4
  41. kill 35
  42. 最后逃生的人编号是： [16, 31]
  44. Process finished with exit code 0

因此，约瑟夫和他朋友如果想要逃生的话，就得把他自己和朋友放到第16和31个位置上，以保证他们是最后的两个玩家。