約瑟夫環

Java陣列解決約瑟夫環問題（附源代碼）

什么是約瑟夫環？

? 據說著名猶太歷史學家 Josephus有過以下的故事：在羅馬人占領喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止，然而Josephus 和他的朋友并不想遵從，首先從一個人開始，越過k-2個人（因為第一個人已經被越過），并殺掉第k個人，接著，再越過k-1個人，并殺掉第k個人，這個程序沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著，問題是，給定了和，一開始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲，

可以在圖片中看到，最后出列的兩位就是站在16與31位置的人，那么如何算出最后出列的人站在原始的位置呢？

我們可以把這個游戲想成一個問題：

? 假設有n個人參與游戲，這n個人排成一個圓圈、回圈從1到m報數，報到m的人則出局、求最后一個出局的人站在圓圈的什么位置？

如何使用陣列來解決這個問題？

? 可以先看看下圖來模擬一下這個問題（報到3的人出局）：

? 假設只有六個人參與這個游戲（用不同的顏色標注了六個方塊代表六個參與者，如下圖：）

第一輪（第一個報到3的人出局，我用黑色框代表）：

第二輪：

第三輪：

第四輪：

第五輪：

由上圖可看出最后出局的人是站在1位置上的人

那么如何用陣列來解決這個問題呢：

? 我們可以把這個陣列想象成他自己無限的拼接起來，像這樣（如圖）：

如何使用代碼來實作這個程序呢：

• 首先獲取游戲的資料和規則（多少人參與，報到多少的人出局）：

  //獲取參與游戲的人數，以及報到多少出列：
  		Scanner scanner =new Scanner(System.in);
  		System.out.println("請輸入參與游戲的人數：");
  		int n=scanner.nextInt();
  		System.out.println("請輸入報到多少的人出局：");
  		int m=scanner.nextInt();
  		System.out.println("請輸入從第幾個人開始報數：");
  		int p=scanner.nextInt();
  
  

• 定義一個布爾型別陣列有參與者人數大小，并且初始化全部為true：

  //定義陣列，并且全部初始化
  		boolean[] player=new boolean[n];
  		for(int i=0;i<player.length;i++) {
  			player[i]=true;
  		}
  
  

• 定義計數和剩下人數的變數和出局的常量，

		//定義
		int count=0;//計數
		int outNumber=m;//出局數
		int human=n;//參與數
		int k=p-1;//開始的人，在陣列中下標要-1

• 回圈這個陣列，將出局的人定義為false并輸出，

  while(human>=1) {
  			//回圈遍歷陣列
  			for(int index=k;index<player.length;index++) {
  				//判斷是true計數就加1
  				if(player[index]) {
  					count++;
  				}
  				//判斷到出局數，陣列中這個位置就變成了false,人數減1
  				if(count==outNumber) {
  					System.out.println(index+1);
  					player[index]=false;
  					human--;//人數減一
  					count=0;//計數歸0,重新開始計數
  				}
  				//判斷回圈到末尾，則陣列最后下標后一位歸0
  				if(index==player.length) {
  					index=0;
  				}
  				
  			}
  		}
  
  
  

運行這段代碼

? 將參與人數和出局數還有開始位置都定義成猶太歷史學家 Josephus故事中的資料：

? 可以看到結果（如下圖）：

? 最后兩位出局的正是位置16和位置31

原始碼：

package com;

import java.util.Scanner;

public class YueSeFuGame {

	public static void main(String[] args) {
		
		
		//獲取參與游戲的人數，以及報到多少出列：
		Scanner scanner =new Scanner(System.in);
		System.out.println("請輸入參與游戲的人數：");
		int n=scanner.nextInt();
		System.out.println("請輸入報到多少的人出局：");
		int m=scanner.nextInt();
		System.out.println("請輸入從第幾個人開始報數：");
		int p=scanner.nextInt();
		
		//定義陣列，并且全部初始化
		boolean[] player=new boolean[n];
		for(int i=0;i<player.length;i++) {
			player[i]=true;
		}
		
		//定義
		int count=0;//計數
		int outNumber=m;//出局數
		int human=n;//參與數
		int k=p-1;//開始的人，在陣列中下標要-1
		
		//回圈
		while(human>=1) {
			//回圈遍歷陣列
			for(int index=k;index<player.length;index++) {
				//判斷是true計數就加1
				if(player[index]) {
					count++;
				}
				//判斷到出局數，陣列中這個位置就變成了false,人數減1
				if(count==outNumber) {
					System.out.println(index+1);//下標在陣列中從0開始所以要+1
					player[index]=false;
					human--;//人數減一
					count=0;//計數歸0,重新開始計數
				}
				//判斷回圈到末尾，則陣列最后下標后一位歸0
				if(index==player.length) {
					index=0;
				}
				
			}
		}
		

	}

}