說明
據說著名猶太歷史學家 Josephus有過以下的故事：在羅馬人佔領喬塔帕特後，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧願死也不要被敵人抓到，於是決定了一個自殺方式，41個人排成一個圓圈，由第1個人 開始報數，每報數到第3人該人就必須自殺，然後再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus 和他的朋友並不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，於是逃過了這場死亡遊戲。
解法
約瑟夫問題可用代數分析來求解，將這個問題擴大好了，假設現在您與m個朋友不幸參與了這個遊戲，您要如何保護您與您的朋友？只要畫兩個圓圈就可以讓自己與朋友免於死亡遊戲，這兩個圓圈內圈是排列順序，而外圈是自殺順序，如下圖所示：
14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23
由上可知，最後一個自殺的是在第31個位置，而倒數第二個自殺的要排在第16個位置，之前的人都死光了，所以他們也就不知道約琴夫與他的朋友並沒有遵守遊戲規則了。
實作
- C
#include <stdio.h>
#include <stdlib.h>
#define N 41
#define M 3
int main(void) {
int man[N] = {0};
int count = 1;
int i = 0, pos = -1;
int alive = 0;
while(count <= N) {
do {
pos = (pos+1) % N; // 環狀處理
if(man[pos] == 0)
i++;
if(i == M) { // 報數為3了
i = 0;
break;
}
} while(1);
man[pos] = count;
count++;
}
printf("\n約琴夫排列：");
for(i = 0; i < N; i++)
printf("%d ", man[i]);
printf("\n\n您想要救多少人？");
scanf("%d", &alive);
printf("\nL表示這%d人要放的位置：\n", alive);
for(i = 0; i < N; i++) {
if(man[i] > alive)
printf("D");
else
printf("L");
if((i+1) % 5 == 0)
printf(" ");
}
printf("\n");
return 0;
}
- Java
public class Josephus {
public static int[] arrayOfJosephus(
int number, int per) {
int[] man = new int[number];
for(int count = 1, i = 0, pos = -1;
count <= number; count++) {
do {
pos = (pos+1) % number; // 環狀處理
if(man[pos] == 0)
i++;
if(i == per) { // 報數為3了
i = 0;
break;
}
} while(true);
man[pos] = count;
}
return man;
}
public static void main(String[] args) {
int[] man = Josephus.arrayOfJosephus(41, 3);
int alive = 3;
System.out.println("約琴夫排列：");
for(int i = 0; i < 41; i++)
System.out.print(man[i] + " ");
System.out.println("\nL表示3個存活的人要放的位置：");
for(int i = 0; i < 41; i++) {
if(man[i] > alive)
System.out.print("D");
else
System.out.print("L");
if((i+1) % 5 == 0)
System.out.print(" ");
}
System.out.println();
}
}