|
|
約瑟夫環（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
|