約瑟夫死亡遊戲（迴圈單連結串列）
2020-10-22 13:00:15
約瑟夫死亡遊戲（迴圈單連結串列）
遊戲內容大致描述為：n個遊客同乘一條船，因為嚴重超載，加上風浪大作，危險萬分。因此，船長告訴乘客，只有將全船的safeNumber個旅客投入大海，其餘人才能倖免於難。無奈，大家只得同意，並議定30人圍成一圈，由第一個人數起，依次報數，數到第k人，便把他投入大海，然後再從他的下一個數起，數到k人，再將他扔入大海，如此重複直到剩下safeNumber個乘客為之。結果列印出生者和死者的位置序號。
實現提示
死者的選擇和將遊客投入大海的模擬過程，可以視為：首先從由n個結點構成的迴圈單連結串列的第一個結點開始沿著next指標一次數數，當數到到第k-1個結點，就將這個結點的後繼結點從迴圈單連結串列種刪除，然後從刪除結點的下一個結點開始數數，數到第k-1個結點，又將其後繼結點刪除，如此重複。
- main方法，使用者自主輸入船客原始人數、間隔人數、剩餘人數；
- throwSea方法，扔海主要程式碼塊
- SNode結點, 兩個屬性，一個是int型別的data資料域，一個是next的指標域；
- CircularLinkedList 迴圈單連結串列，將SNode結點連線
程式碼實現
1.生死遊戲實現類
package expriment2.circularSingleList;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/**
* @author auther
*/
public class SY4_lifeGame {
public static void main(String[] args) throws Exception {
// 建立一個有n個結點的單連結串列迴圈儲存結構
System.out.println("請輸入船上有多少個遊客：");
Scanner sc = new Scanner(System.in);
int passengerNumber = sc.nextInt();
// 單向迴圈連結串列裡面儲存的資料，是船客的位置序號，為 1，2，3...n。
CircularLinkedList list = new CircularLinkedList();
for (int i = 1; i <= passengerNumber; i++) {
list.addTail(i);
}
System.out.println("列印原始狀態：");
list.display();
System.out.println("報數到k者為死者，k=？");
int k = sc.nextInt();
System.out.println("船上最多剩多少人才安全？");
int safeNumber = sc.nextInt();
// 呼叫扔海函數，列印生者和死者的位置
throwToSea(list, k,safeNumber);
}
public static void throwToSea(CircularLinkedList originL, int intervalNum,int safeNum) throws Exception {
/*// 當船上的乘客人數為原來的一半時，其餘人安全
int effectiveNum = originL.length() / 2;*/
// deads列表存放 死者的位置
List<Integer> deads = new ArrayList<>();
// 將p結點 初始化為 頭結點
SNode p = originL.getHead();
// 當船上人數達到安全標準之後，結束迴圈
while (originL.length() != safeNum) {
// 此處檢驗連結串列是否為空 為空，則丟擲異常。
if (p == null) {
throw new Exception("連結串列資料為空");
}
// 此迴圈裡面的count僅用來數數（1-8），每次數到8時，跳出此迴圈。
// p結點隨著count的變化，而等於它的下一個結點
int count = 1;
while (count < intervalNum - 1) {
++count;
p = p.getNext();
}
// 將要刪除的，是當前結點的後繼結點，所以死者是後繼結點中儲存的位置序號。
deads.add(p.getNext().getData());
// 傳入當前結點的位置序號，將下一位置上的船客扔入海中。
originL.remove(originL.indexOf(p.getData()));
// 此處實現 從刪除結點的下一結點開始數數
p = p.getNext();
}
/*****************************************************/
System.out.println("船上生者的位置序號：");
// 列印生者的位置序號
SNode nd = originL.getHead();
while (nd != originL.getTail()) {
System.out.print(nd.getData() + " ");
nd = nd.getNext();
}
System.out.println(nd.getData());
/*****************************************************/
System.out.println("船上死者的位置序號：");
// 列印死者的位置序號
for (int i = 0; i < deads.size(); i++) {
System.out.print(deads.get(i) + " ");
}
}
}
2.SNode結點
此結點根據位置序號使用int型別即可，並未使用泛型。
package expriment2.circularSingleList;
public class SNode {
/**
* 資料 區
*/
private int data;
/**
* 指標 區
*/
private SNode next;
public SNode() {
this(0, null);
}
public SNode(int data) {
this(data, null);
}
public SNode(int data, SNode next) {
this.data = data;
this.next = next;
}
public int getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public SNode getNext() {
return next;
}
public void setNext(SNode next) {
this.next = next;
}
}
3.迴圈單連結串列連線結點成圈
CircularLinkedList列表
package expriment2.circularSingleList;
public class CircularLinkedList {
/**
* 頭結點
*/
private SNode head;
/**
* 尾結點
*/
private SNode tail;
/**
* 記錄結點的長度
*/
private int count;
/**
* 構造方法，建一個空連結串列
*/
public CircularLinkedList() {
tail = head = null;
count = 0;
}
/**
* 在連結串列尾部新增結點
*/
public void addTail(int i) {
if (tail == null) {
tail = new SNode(i);
head = tail;
head.setNext(tail);
tail.setNext(head);
count++;
} else {
tail.setNext(new SNode(i));
tail = tail.getNext();
tail.setNext(head);
count++;
}
}
/** 扔海了嘍。。*/
public void remove(int i) throws Exception {
SNode p = head;
int j = 1;
while (p != tail && j < i) {
p = p.getNext();
++j;
}
if (j > i) {
throw new Exception("刪除出錯！");
}
if (p.getNext() == tail) {
// 尾結點特殊處理
tail = p;
tail.setNext(p.getNext().getNext());
} else {
p.setNext(p.getNext().getNext());
}
count--;
}
/** 獲取元素的位置序號*/
public int indexOf(Integer i) {
// 初始化，p指向首結點， j為計數器
SNode p = head;
int j = 1;
// 下面從迴圈單連結串列中的首結點開始查詢，直到p.getData()為i
while (p.getData() != i) {
p = p.getNext();
++j;
}
return j;
}
/** 獲取連結串列長度 */
public int length() {
// 初始化，p指向首結點，length為計數器
SNode p = head;
int length = 1;
while (p != tail) {
// 從結點開始向後查詢，直到p為空 指向後繼結點 長度自增
p = p.getNext();
++length;
}
return length;
}
/**
* 列印全部結點
*/
public void display() {
SNode nd = head;
try {
while (nd.getNext() != head) {
System.out.print(nd.getData());
System.out.print("-->");
nd = nd.getNext();
}
System.out.print(nd.getData());
System.out.print("-->");
System.out.println(head.getData());
} catch (Exception e) {
e.printStackTrace();
}
}
public SNode getHead() {
return head;
}
public void setHead(SNode head) {
this.head = head;
}
public SNode getTail() {
return tail;
}
public void setTail(SNode tail) {
this.tail = tail;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
}
程式碼執行結果：
程式碼不夠完美，還請包含。個人第一篇csdn部落格