n个人从1开始报数，报到m的退出，剩下的人继续从1开始报...

老夏

       n个人从1开始报数，报到m的退出，剩下的人继续从1开始报数，计算最后留下的是第几个人

    此题是道典型的约瑟夫环问题，解决该问题的思路有2种：
    一种是常规方式，即创建环形链表，这种方式比较容易了解，即对环形链表进行循环，每次将报到m的节点删除，最后终止的条件为环形链表中的当前节点等于下一个节点指向其本身，那么这个节点就是最后留下人。
    解析代码如下：

1. # 链表节点
   
2. class LinkedNode:
   
3.     def __init__(self, value):
   
4.         self.value = value
   
5.         self.next = None
   
6. # 环形链表
   
7. def create_linkList(n):
   
8.     # 创建头节点
   
9.     head = LinkedNode(1)
   
10.     pre = head
    
11.     for i in range(2, n + 1):
    
12.         # 创建节点
    
13.         newNode = LinkedNode(i)
    
14.         pre.next = newNode
    
15.         pre = newNode
    
16.     # 形成环形
    
17.     pre.next = head
    
18.     return head
    
19. # 总人数
    
20. n = 6
    
21. # 报到的数
    
22. m = 4
    
23. # 如果报的数为1，则最后留下的人就是n
    
24. if m == 1:
    
25.     print(n)
    
26. else:
    
27.     # 获得环形链表
    
28.     head = create_linkList(n)
    
29.     pre = None
    
30.     cur = head
    
31.     # 终止条件是环形链表中的当前节点等于下一个节点指向其本身
    
32.     while cur.next != cur:
    
33.         # 模拟报数，获得报到数的节点
    
34.         for i in range(m - 1):
    
35.             pre = cur
    
36.             cur = cur.next
    
37.         # 删除报到数的节点
    
38.         pre.next = cur.next
    
39.         cur.next = None
    
40.         cur = pre.next
    
41.     print(f'最终留下的是第{cur.value}个人')

复制代码

    第二种方式非常巧妙，可以通过使用递归的方式来解决该问题，即每次删除某一个报到m的人后，就对剩下的n-1个人重新编号，直到留下最后一个人，所以现在的重点就是找出删除前和删除后仍然留下人的编号的映射关系，经过分析，其映射关系如图1-1所示。

图1-1 映射关系

    通过上图，很容易得出删除前和删除后仍然留下人的编号的的映射关系，假设删除前的编号为beforedel，删除后的编号为afterdel，则beforedel=(afterdel+m)%n，但是由于编号是从1开始，所以需要将beforedel加1，此外还需要保持等式两边相等，所以需要将afterdel+m减1，则最终删除前编号和删除后仍然留下的人的编号的的映射关系为beforedel=(afterdel+m-1)%n+1。
    解析代码如下：

1. def JosephRing(n, m):
   
2.     return n if n == 1 else (JosephRing(n - 1, m) + m - 1) % n + 1
   
3. print(f'最终留下的是第{JosephRing(6, 4)}个人')

复制代码