|
|
约瑟夫环（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 ->
|