# 約瑟夫問題

December 5, 2021

## 解法思路

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

g(1, k) = 0
g(n, k) = (g(n - 1, k) + k) % n

## 程式實作

``````#include <stdio.h>
#include <stdlib.h>
#define LEN 41
#define STEP 3

void josephus(int*, int, int);
int next(int*, int, int, int);
int winner(int, int);

int main(void) {
int man[LEN] = {0};
josephus(man, LEN, STEP);

printf("約琴夫排列：");
int i;
for(i = 0; i < LEN; i++) {
printf("%d ", man[i]);
}
printf("\nWinner: %d", winner(LEN, STEP));

return 0;
}

void josephus(int* man, int len, int k) {
int i, n;
for(i = 1, n = -1; i <= len; i++) {
n = next(man, len, k, n);
man[n] = i;
}
}

int next(int* man, int len, int k, int n) {
int count = 0;
while(count < k) {
n = (n + 1) % len;
if(man[n] == 0) { count++; }
}
return n;
}

int winner(int len, int k) {
int g, n;
for(g = 0, n = 1; n <= len; n++) {
g = (g + k) % n;
}
return g + 1;
}
``````
``````import java.util.*;
import static java.lang.System.out;

public class Josephus {
public static List<Integer> awayOrder(int len, int k) {
for(int i = 1; i <= len; i++) { numbers.add(i); }

List<Integer> awayOrder = new ArrayList<>(len);
for(int i = 2;;) {
if(numbers.isEmpty()) { break; }
i = (i + k - 1) % numbers.size();
}

return awayOrder;
}

public static List<Integer> josephus(List<Integer> awayOrder) {
List<Integer> josephus = new ArrayList<>(awayOrder.size());
for(int i = 1; i <= awayOrder.size(); i++) {
}
return josephus;
}

public static List<Integer> josephus(int len, int k) {
return josephus(awayOrder(len, k));
}

public static void main(String[] args) {
List<Integer> awayOrder = awayOrder(41, 3);
out.print("自殺順序：");
for(Integer number : awayOrder) {
out.printf("%3d", number);
}
out.print("\n約瑟夫環：");
for(Integer number : josephus(awayOrder)) {
out.printf("%3d", number);
}
}
}
``````
``````def remove(list, i):
return list[0:i] + list[i + 1:]

def awayOrder(l, k):
def suicide(numbers, awayOrder, i):
awayOrd = awayOrder + [numbers[i]]
nums = remove(numbers, i)
return awayOrd if len(nums) == 0 \
else suicide(nums, awayOrd, (i + k - 1) % len(nums))

return suicide([i for i in range(1, l + 1)], [], 2)

def josephus(awayOrder):
return [awayOrder.index(i) + 1 for i in range(1, len(awayOrder) + 1)]

awayOrd = awayOrder(41, 3)
print("自殺順序：" + str(awayOrd))
print("約瑟夫環：" + str(josephus(awayOrd)))
``````
``````def awayOrder(len: Int, k: Int) = {
def suicide(numbers: List[Int],
awayOrder: List[Int], i: Int): List[Int] = {
val awayOrd = numbers(i) :: awayOrder
val nums = numbers.filterNot(numbers.indexOf(_) == i)
if(nums.isEmpty) awayOrd.reverse
else suicide(nums, awayOrd, (i + k - 1) % nums.size)
}
suicide((1 to len).toList, Nil, 2)
}

def josephus(awayOrder: List[Int]) = {
(for(i <- 1 to awayOrder.size) yield awayOrder.indexOf(i) + 1).toList
}

def josephus(len: Int, k: Int): List[Int] = josephus(awayOrder(len, k))

println("自殺順序：" + awayOrder(41, 3).toString.drop(4))
println("約瑟夫環：" + josephus(41, 3).toString.drop(4))
``````
``````# encoding: UTF-8
def awayOrder(l, k)
suicide = ->(numbers, awayOrder, i) {
awayOrd = awayOrder + [numbers[i]]
nums = numbers.select {|e| numbers.find_index(e) != i }
nums.empty? ? awayOrd :
suicide.call(nums, awayOrd, (i + k - 1) % nums.size)
}
suicide.call((1..l).to_a, [], 2)
end

def josephus(awayOrder)
(1..awayOrder.size).map {|i| awayOrder.find_index(i) + 1}
end

awayOrd = awayOrder(41, 3)
puts("自殺順序：" + awayOrd.to_s)
puts("約瑟夫環：" + josephus(awayOrd).to_s)
``````
``````function awayOrder(len, k) {
var numbers = [];
for(var i = 1; i <= len; i++) { numbers.push(i); }

var awayOrder = [];
for(var i = 2;;) {
awayOrder.push(numbers.splice(i, 1)[0]);
if(numbers.length === 0) { break; }
i = (i + k - 1) % numbers.length;
}

return awayOrder;
}

function josephus(awayOrder) {
var jp = [];
for(var i = 1; i <= awayOrder.length; i++) {
jp.push(awayOrder.indexOf(i) + 1);
}
return jp;
}

var awayOrd = awayOrder(41, 3);
print('自殺順序：' + awayOrd);
print('約瑟夫環：' + josephus(awayOrd));
``````
``````import Data.List

remove lt i = (take i lt) ++ (drop (i + 1) lt)

indexOf elem list = a
where (Just a) = elem `elemIndex` list

awayOrder l k = suicide [1..l] [] 2
where suicide numbers awayOrder i =
if length nums == 0 then reverse awayOrd
else suicide nums awayOrd ((i + k - 1) `mod` (length nums))
where awayOrd = (numbers !! i) : awayOrder
nums = remove numbers i

josephus awayOrder =
[(indexOf i awayOrder) + 1 | i <- [1..(length awayOrder)]]

main = do
putStrLn \$ "Away order    : " ++ show awayOrd
putStrLn \$ "Josephus order: " ++ show (josephus awayOrd)
where awayOrd = awayOrder 41 3
``````