|
约瑟夫环(Josephus)问题:古代某法官要判决n个犯人的死刑,他有一条荒唐的法律,将犯人站成一个圆圈,从第s个人开始数起,每数到第d个犯人,就拉出来处决,然后再数d个,数到的人再处决……直到剩下的最后一个可赦免.
结点类:OneLinkNode:
package com;
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) /** *//**
* 结点类
* @author zdw
*
*/
public class OneLinkNode
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
public int data;
public OneLinkNode next;
public OneLinkNode(int k)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
data = k;
next = null;
}
public OneLinkNode()
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
this(0);
}
}
![](/Images/OutliningIndicators/None.gif)
链表类:
OneLink:
package com;
![](/Images/OutliningIndicators/None.gif)
public class OneLink
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
//头结点
protected OneLinkNode head;
//构造一个空的单向链表
public OneLink()
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
head = null;
}
//只有一个结点的单向链表
public OneLink(OneLinkNode h1)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
head = h1;
}
//判断链表是否为空
public boolean isEmpty()
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
return head == null;
}
//用随机数构造n个数的链表
public OneLink(int n)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
OneLinkNode rear,q;
if(n > 0)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int k = (int) (Math.random()*100);
head = new OneLinkNode(k);
rear = head;
for(int i = 1; i < n ;i++)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
k = (int) (Math.random()*100);
q = new OneLinkNode(k);
rear.next = q;
rear = q;
}
}
}
}
![](/Images/OutliningIndicators/None.gif)
Josephus类:
package com;
![](/Images/OutliningIndicators/None.gif)
public class Josephus2 extends OneLink
![](/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](/Images/OutliningIndicators/ContractedBlock.gif) {
Josephus2() // 构造空的单向循环链表
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
super();
}
![](/Images/OutliningIndicators/InBlock.gif)
Josephus2(int n) // 建立n个结点的单向循环链表
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) { // 链表结点值为1到n
this();
int i = 1;
//q新结点,rear尾结点
OneLinkNode q, rear;
if (n > 0)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
//先创建只有一个结点的单向循环链表
head = new OneLinkNode(i);
//指向自己
head.next = head;
rear = head;
while (i < n)
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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) // 解约瑟夫环
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int j = 0;
OneLinkNode p = head;
while (j < s - 1) // 指针步进到计数起始点
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
j++;
p = p.next;
}
while (p.next != p) // 多于一个结点时循环
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
j = 0;
while (j < d ) // 计数
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
j++;
p = p.next;
}
delete(p); // 删除p的后继结点
p = p.next;
this.output();
}
}
![](/Images/OutliningIndicators/InBlock.gif)
public void delete(OneLinkNode p) // 删除p的后继结点
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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
}
![](/Images/OutliningIndicators/InBlock.gif)
public void output() // 输出单向链表的各个结点值
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
OneLinkNode p = head;
System.out.print(this.getClass().getName() + ": ");
do
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
System.out.print(p.data + " -> ");
p = p.next;
} while (p != head);
System.out.println();
}
//测试
public static void main(String args[])
![](/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
int n = 5, s = 2, d = 1;
Josephus2 h1 = new Josephus2(n);
h1.output();
h1.display(s, d);
}
![](/Images/OutliningIndicators/InBlock.gif)
![](/Images/OutliningIndicators/InBlock.gif)
}
![](/Images/OutliningIndicators/None.gif)
测试输出结果没有任何问题:
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 ->
|