|
|
約瑟夫環（Josephus）問題：古代某法官要判決n個犯人的死刑，他有一條荒唐的法律，將犯人站成一個圓圈，從第s個人開始數起，每數到第d個犯人，就拉出來處決，然后再數d個，數到的人再處決……直到剩下的最后一個可赦免.
結點類:OneLinkNode:
 package com;
  /** *//**
 * 結點類
* @author zdw
*
 */
public class OneLinkNode
 {
public int data;
public OneLinkNode next;
public OneLinkNode(int k)
  {
data = k;
next = null;
 }
public OneLinkNode()
{
this(0);
}
}
OneLink:
package com;
public class OneLink
{
//頭結點
protected OneLinkNode head;
//構造一個空的單向鏈表
public OneLink()
{
head = null;
}
//只有一個結點的單向鏈表
public OneLink(OneLinkNode h1)
{
head = h1;
}
//判斷鏈表是否為空
public boolean isEmpty()
{
return head == null;
}
//用隨機數構造n個數的鏈表
public OneLink(int n)
{
OneLinkNode rear,q;
if(n > 0)
{
int k = (int) (Math.random()*100);
head = new OneLinkNode(k);
rear = head;
for(int i = 1; i < n ;i++)
{
k = (int) (Math.random()*100);
q = new OneLinkNode(k);
rear.next = q;
rear = q;
}
}
}
}
Josephus類:
package com;
public class Josephus2 extends OneLink
{
Josephus2() // 構造空的單向循環鏈表
{
super();
}
Josephus2(int n) // 建立n個結點的單向循環鏈表
{ // 鏈表結點值為1到n
this();
int i = 1;
//q新結點,rear尾結點
OneLinkNode q, rear;
if (n > 0)
{
//先創建只有一個結點的單向循環鏈表
head = new OneLinkNode(i);
//指向自己
head.next = head;
rear = head;
while (i < n)
{
i++;
//新結點
q = new OneLinkNode(i);
//新結點的next字段指向head
q.next = head;
//這里的near是尾結點(第一次就是head)的next字段指向新結點
rear.next = q;
//保存新節點的地址,以便下次循環使用
rear = q;
}
}
}
//計數起點s,d要跳過的個數
public void display(int s, int d) // 解約瑟夫環
{
int j = 0;
OneLinkNode p = head;
while (j < s - 1) // 指針步進到計數起始點
{
j++;
p = p.next;
}
while (p.next != p) // 多于一個結點時循環
{
j = 0;
while (j < d ) // 計數
{
j++;
p = p.next;
}
delete(p); // 刪除p的后繼結點
p = p.next;
this.output();
}
}
public void delete(OneLinkNode p) // 刪除p的后繼結點
{
OneLinkNode q = p.next; // q是p的后繼結點
System.out.print("delete: " + q.data + " ");
if (q == head) // 欲刪除head指向結點時，
head = q.next; // 要將head向后移動
p.next = q.next; // 刪除q
}
public void output() // 輸出單向鏈表的各個結點值
{
OneLinkNode p = head;
System.out.print(this.getClass().getName() + ": ");
do
{
System.out.print(p.data + " -> ");
p = p.next;
} while (p != head);
System.out.println();
}
//測試
public static void main(String args[])
{
int n = 5, s = 2, d = 1;
Josephus2 h1 = new Josephus2(n);
h1.output();
h1.display(s, d);
}
}
測試輸出結果沒有任何問題:
com.Josephus2: 1 -> 2 -> 3 -> 4 -> 5 ->
delete: 4 com.Josephus2: 1 -> 2 -> 3 -> 5 ->
delete: 2 com.Josephus2: 1 -> 3 -> 5 ->
delete: 1 com.Josephus2: 3 -> 5 ->
delete: 3 com.Josephus2: 5 ->
|