# 約瑟夫問題（Josephus Problem）

## 解法

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

• C
``#include <stdio.h> #include <stdlib.h> #define LEN 41#define STEP 3void 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;}``

• Java
``import java.util.*;import static java.lang.System.out;public class Josephus {    public static List<Integer> awayOrder(int len, int k) {        List<Integer> numbers = new LinkedList<>();        for(int i = 1; i <= len; i++) { numbers.add(i); }                List<Integer> awayOrder = new ArrayList<>(len);        for(int i = 2;;) {            awayOrder.add(numbers.remove(i));            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++) {            josephus.add(awayOrder.indexOf(i) + 1);        }        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);         }    }}``

• Python
``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)))``

• Scala
``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))``

• Ruby
``# encoding: Big5def 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)enddef 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)``

• JavaScript
``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.Listremove lt i = (take i lt) ++ (drop (i + 1) lt)indexOf elem list = a    where (Just a) = elem `elemIndex` listawayOrder 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 ijosephus 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``