之前讀資料結構的書,看到有一個關於約瑟夫問題的探討。
規則是這樣,大家圍個圈圈,從1開始報數。
每數到3就自殺,自殺後從下一位開始報數,直到剩下2位。<<已跳過故事大綱
後來自己改寫規則,修改為每數到?就自殺,直到剩下1位。
感覺新規則比較刺激!XDD
以下參考書為:
1. 2015資料結構 by 王致強
2. 2015程式語言 by 金乃傑
結果圖:
程式碼:
import java.util.Scanner;
class Node
{
private int data;
private Node next;
Node(int n,Node link)
{
data=n;
next=link;
}
public void setNext(Node link){next=link;}
public int getData(){return data;}
public Node getNext(){return next;}
}
public class JosephusProblem
{
public static void main(String args[])
{
System.out.print("請輸入人數:");
Scanner sc = new Scanner(System.in);
int people = sc.nextInt();
Node head = null;
Node tail = null;
Node p = null;
for(int i=0;i<people;i++)
{
//前個Node不會知道下個Node位址,所以傳入參數即反向
Node node = new Node(people-i-1,head);
//為了循環串列,因此要做記號,未來要接起頭位址
if(i==0)tail = node;
//頭標準備往前移
head = node;
}
tail.setNext(head);//頭尾接起來!!
//此處是確認有做出循環串列
//System.out.println("頭標在:"+head.getData());
//System.out.println("下一站:"+(head.getNext()).getData());
System.out.println("尾標在:"+tail.getData());
System.out.println("下一站:"+(tail.getNext()).getData());
//顯示成員
p = head;
do{
System.out.print(p.getData()+" ");
p = p.getNext();
}while(p!=head);
System.out.println();
//死亡遊戲開始
while(tail.getNext()!=tail){
//輸入程式可搬出或在此處
System.out.print("請輸入報數:");
Scanner run = new Scanner(System.in);
int point = run.nextInt();
//指向自殺者的前一位人
for(int j=2;j<=point;j++)tail = tail.getNext();
//自殺者大名
System.out.println((tail.getNext()).getData());
//尾標連結指向自殺者的下一位人
tail.setNext((tail.getNext()).getNext());
}
System.out.println("生存者:"+tail.getData());
}
}
留言列表