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;
}
}
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/198810.html
標籤：其他