文章目录

实例说明

运行时间O(N min(M, N))
Josephus问题（Josephus problem）是下面的游戏：

  1. <mstyle mathcolor="&#35;00ff11"> N </mstyle> \color{#00ff11}{N} N个人编号 <mstyle mathcolor="&#35;001111"> 从 1 到 N </mstyle> \color{#001111}{从1到N} 从1到N，围坐成一个圈。
  2. 号码1的人有一个“土豆”，向后传递“土豆”。
  3. 经过 <mstyle mathcolor="&#35;005ff5"> M </mstyle> \color{#005ff5}{M} M次传递后，手拿“土豆”的人被清理出场。
  4. “土豆”交给下一个人，继续往后传递 <mstyle mathcolor="&#35;005ff5"> M </mstyle> \color{#005ff5}{M} M次。
  5. 一直重复，直到剩下最后一个。
  6. 最后剩下的人获得胜利。

e.g.
M=0 N=5 5号胜利
M=1 N=5 被清除的顺序2 4 1 5 ，3号胜利

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

实例代码

/** * Josephus问题 * “死亡轮盘” */
	@Test
	public void testChapter3_6() {
		//N>=2
		//人数
		int N = 5 ; 
		//传几次才杀人
		int M = 1 ; 
		/* * 创建N个人，环 */
		Node<Integer> first = new Node<Integer>(1, null);
		Node<Integer> last ; 
		Node<Integer> currentNode = first;
		//开始创建2号
		int number = 2; 
		while(true) {
			//连接N号之后,N号连接first退出
			if(number>N) {
				last = currentNode;
				currentNode.next = first; 
				break;
			}
			Node<Integer> insNext = new Node<Integer>(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<Integer> 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<T>{
		private Node<T> next ;
		private T elementDate  ;
		public  Node(T e ,  Node<T> nex) {
			this.elementDate = e ; 
			this.next = nex;
		}
	}

测试