本文共 1762 字，大约阅读时间需要 5 分钟。

实例说明

运行时间O(N min(M, N))

1. $N$个人编号$从1到N$，围坐成一个圈。
2. 号码1的人有一个“土豆”，向后传递“土豆”。
3. 经过$M$次传递后，手拿“土豆”的人被清理出场。
4. “土豆”交给下一个人，继续往后传递$M$次。
5. 一直重复，直到剩下最后一个。
6. 最后剩下的人获得胜利。

e.g.

问题：N个人，M次传递后，谁会胜利

实例代码

/**	 * Josephus问题	 * “死亡轮盘”	 */	@Test	public void testChapter3_6() {
   		//N>=2		//人数		int N = 5 ; 		//传几次才杀人		int M = 1 ; 		/*		 * 创建N个人，环		 */		Node
   
     first = new Node
    
     (1, null);		Node
     
       last ; 		Node
      
        currentNode = first;		//开始创建2号		int number = 2; 		while(true) {
   			//连接N号之后,N号连接first退出			if(number>N) {
   				last = currentNode;				currentNode.next = first; 				break;			}			Node
       
         insNext = new Node
        
         (number, null); //连接下一个 currentNode.next = insNext; //下一个 currentNode = currentNode.next; number ++ ; } /* * 检查 */ System.out.print("围坐情况："); currentNode = first ; for(int i=0 ; i<= N ; i++) { System.out.print(currentNode.elementDate+", "); currentNode = currentNode.next; } /* * 开始M循环 */ currentNode = first ; Node
         
           previousNode = last ; int index = 0 ; while(true) { if(previousNode == currentNode) { //跳出的条件 break; } //处决 if(index == M) { //前一个 previousNode.next = currentNode.next; //重新计数 index = 0 ; }else { //处决计数 index ++ ; //更新上位置 previousNode = currentNode; } //当前位置往后移 currentNode = currentNode.next ; } System.out.println("\r\n"+M+"步杀一人"); System.out.print("死剩种:"+currentNode.elementDate+"号"); }
         
        
       
      
     
    
   

Node类代码

private static class Node
   
    {
   		private Node
    
      next ;		private T elementDate  ;		public  Node(T e ,  Node
     
       nex) {
   			this.elementDate = e ; 			this.next = nex;		}	}
     
    
   

测试

转载地址：https://lawsssscat.blog.csdn.net/article/details/103001802 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！