|
|
約瑟夫環(huán)（Josephus）問(wèn)題：古代某法官要判決n個(gè)犯人的死刑，他有一條荒唐的法律，將犯人站成一個(gè)圓圈，從第s個(gè)人開始數(shù)起，每數(shù)到第d個(gè)犯人，就拉出來(lái)處決，然后再數(shù)d個(gè)，數(shù)到的人再處決……直到剩下的最后一個(gè)可赦免。
LinearList:
 package com;
  /** *//**
 * 線性表的存儲(chǔ)結(jié)構(gòu)
* @author zdw
*
 */
public class LinearList
 {
private int table[] ;
private int n;
//為順序表分配n個(gè)存儲(chǔ)單元
public LinearList(int n)
  {
//所占用的存儲(chǔ)單元個(gè)數(shù)this.table.length等于n
table = new int[n];
this.n = 0;
 }
//判斷順序表的是否為空
public boolean isEmpty()
{
return n == 0;
}
//判斷順序表是否為滿
public boolean isFull()
{
return n >= table.length;
}
//返回順序表長(zhǎng)度
public int length()
{
return n;
}
//獲得順序表的第i個(gè)數(shù)據(jù)元素值
public int get(int i)
{
if(i > 0 && i <= n)
{
return table[i-1];
}
else
{
return -1;
}
}
//設(shè)置順序表的第i個(gè)數(shù)據(jù)元素值
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值,找到時(shí)返回位置,找不到返回-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個(gè)位置上插入數(shù)據(jù)元素
public void insert(int i,int k) //插入k值作為第i個(gè)值。
{
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("數(shù)組已滿，無(wú)法插入"+k+"值！");
}
public void insert(int k) //添加k值到順序表最后，重載
{
insert(n+1,k);
}
//刪除順序表的第i個(gè)數(shù)據(jù)元素
public void remove(int k) //刪除k值首次出現(xiàn)的數(shù)據(jù)元素
{
int i=indexof(k); //查找k值的位置
if(i!=-1)
{
for(int j=i;j<n-1;j++) //刪除第i個(gè)值
table[j]=table[j+1];
table[n-1]=0;
n--;
}
else
System.out.println(k+"值未找到，無(wú)法刪除!");
}
}
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個(gè)人依次插入線性表
ring1.insert(i);
// ring1.output();
i = S - 1; // 從第s個(gè)開始計(jì)數(shù)
k = N;
while (k > 1) // n-1個(gè)人依次出環(huán)
{
j = 0;
while (j < D)
{
i = i % N + 1; // 將線性表看成環(huán)形
if (ring1.get(i) != NULL)
j++; // 計(jì)數(shù)
}
System.out.println("out : " + ring1.get(i));
ring1.set(i, NULL); // 第i個(gè)人出環(huán),設(shè)置第i個(gè)位置為空
k--;
// ring1.output();
}
i = 1;
while (i <= N && ring1.get(i) == NULL)
// 尋找最后一個(gè)人
i++;
System.out.println("The final person is " + ring1.get(i));
}
}
輸出結(jié)果如下:
out : 2
out : 4
out : 1
out : 5
The final person is 3
|