|
|
约瑟夫环（Josephus）问题：古代某法官要判决n个犯人的死刑，他有一条荒唐的法律，将犯人站成一个圆圈，从第s个人开始数起，每数到第d个犯人，就拉出来处决，然后再数d个，数到的人再处决……直到剩下的最后一个可赦免。
LinearList:
 package com;
  /** *//**
 * 线性表的存储结构
* @author zdw
*
 */
public class LinearList
 {
private int table[] ;
private int n;
//为顺序表分配n个存储单元
public LinearList(int n)
  {
//所占用的存储单元个数this.table.length等于n
table = new int[n];
this.n = 0;
 }
//判断顺序表的是否为空
public boolean isEmpty()
{
return n == 0;
}
//判断顺序表是否为满
public boolean isFull()
{
return n >= table.length;
}
//返回顺序表长度
public int length()
{
return n;
}
//获得顺序表的第i个数据元素值
public int get(int i)
{
if(i > 0 && i <= n)
{
return table[i-1];
}
else
{
return -1;
}
}
//设置顺序表的第i个数据元素值
public void set(int i ,int k)
{
if(i > 0 && i <= n + 1)
{
table[i - 1] = k;
if(i == n + 1)
{
n ++;
}
}
}
//查找线性表是否包含k值
public boolean contains(int k)
{
int j = indexof(k);
if(j != -1)
return true;
else
return false;
}
//查找k值,找到时返回位置,找不到返回-1
private int indexof(int k)
{
int j = 0;
while(j < n && table[j] != k)
{
j ++;
}
if(j >= 0 && j < n)
{
return j;
}
else
{
return -1;
}
}
//在顺序表的第i个位置上插入数据元素
public void insert(int i,int k) //插入k值作为第i个值。
{
int j;
if(!isFull())
{
if(i<=0) i=1;
if(i>n) i=n+1;
for(j=n-1;j>=i-1;j--)
table[j+1]=table[j];
table[i-1]=k;
n++;
}
else
System.out.println("数组已满，无法插入"+k+"值！");
}
public void insert(int k) //添加k值到顺序表最后，重载
{
insert(n+1,k);
}
//删除顺序表的第i个数据元素
public void remove(int k) //删除k值首次出现的数据元素
{
int i=indexof(k); //查找k值的位置
if(i!=-1)
{
for(int j=i;j<n-1;j++) //删除第i个值
table[j]=table[j+1];
table[n-1]=0;
n--;
}
else
System.out.println(k+"值未找到，无法删除!");
}
}
package com;
public class Josephus
{
public static void main(String args[])
{
(new Josephus()).display(5, 1, 2);
}
public void display(int N, int S, int D)
{
final int NULL = 0;
LinearList ring1 = new LinearList(N);
int i, j, k;
for (i = 1; i <= N; i++)
// n个人依次插入线性表
ring1.insert(i);
// ring1.output();
i = S - 1; // 从第s个开始计数
k = N;
while (k > 1) // n-1个人依次出环
{
j = 0;
while (j < D)
{
i = i % N + 1; // 将线性表看成环形
if (ring1.get(i) != NULL)
j++; // 计数
}
System.out.println("out : " + ring1.get(i));
ring1.set(i, NULL); // 第i个人出环,设置第i个位置为空
k--;
// ring1.output();
}
i = 1;
while (i <= N && ring1.get(i) == NULL)
// 寻找最后一个人
i++;
System.out.println("The final person is " + ring1.get(i));
}
}
输出结果如下:
out : 2
out : 4
out : 1
out : 5
The final person is 3
|