約瑟夫問題

package test.oracle;

import java.util.LinkedList;
import java.util.List;

/**
 * Algorithm Gossip: 約瑟夫問題（Josephus Problem） -- 从网上搜了一些实现
 * http://www.java3z.com/cwbwebhome/article/article3/AlgorithmGossip/JosephusProblem.htm
 */
public class Josephus {
	public static int removeNM0(int n, int m) {
		int s = 0;
		for (int i = 2; i <= n; i++) {
			s = (s + m) % i;
		}
		return s + 1;
	}

	public static int removeNM1(int n, int m) {
		LinkedList<Integer> list = new LinkedList<Integer>();
		for (int i = 0; i < n; i++) {
			list.add(new Integer(i + 1));
		}
		int i = -1;
		while (list.size() > 1) {
			i = (i + m) % list.size();
			list.remove(i--);
		}
		return list.get(0).intValue();
	}

	public static int removeNM2(int n, int m) {
		List<Integer> list = new LinkedList<Integer>();
		for (int i = 0; i < n; i++) {
			list.add(i);
		}
		int i = -1;
		while (n > 1) {
			i += m;
			list.remove(i % n);
			i = (i % n) - 1;
			n--;
		}
		return list.get(0) + 1;
	}

	public static int removeNM3(int n, int m) {
		int a = 0, b = 1;
		LinkedList<Integer> list = new LinkedList<Integer>();
		for (int i = 0; i < n; i++) {
			list.add(i + 1);
		}
		while (list.size() > 1) {
			if (b % m == 0) {
				list.remove(a);
				a--;
			}
			a++; b++;
			if (a > list.size() - 1) {
				a = 0;
			}
		}
		return list.get(0);
	}

	public static int removeNM4(int n, int m) {
		int a[] = new int[n];
		for (int i = 0; i < n; i++) {
			a[i] = i + 1;
		}
		int k = 1, i = -1;
		while (true) {
			for (int j = 0; j < m;) {
				i = (i + 1) % n;
				if (a[i] > 0) j++;
			}
			if (k == n) break;
			a[i] = -1;
			k++;
		}
		return a[i];
	}

	public static int removeNM5(int n, int m) {
		int[] child = new int[n + 1];
		int[] flag = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			child[i] = i;
			flag[i] = 1;
		}
		int k = 0, i = 1, j = 1;
		boolean noEnd = true;
		while (noEnd) {
			while (j < m) {
				i = (i + 1 > n ? 1 : i + 1);
				j += flag[i];
			}
			flag[i] = 0;
			k++;
			if (k == n) noEnd = false;
			else j = 0;
		}
		return i;
	}

	public static int[] arrayOfJosephus(int n, int m) {
		int[] man = new int[n];
		for (int count = 1, i = 0, pos = -1; count <= n; count++) {
			do {
				pos = (pos + 1) % n;
				if (man[pos] == 0) i++;
				if (i == m) {
					i = 0; break;
				}
			} while (true);
			man[pos] = count;
		}
		return man;
	}

	public static void main(String[] args) {
		int n = 1000, m = 3;
		int[] man = Josephus.arrayOfJosephus(n, m);
		for (int i = 0; i < n; i++) {
			System.out.print(man[i] + " ");
		}
		System.out.println();
		System.out.println(removeNM0(n, m));
		System.out.println(removeNM1(n, m));
		System.out.println(removeNM2(n, m));
		System.out.println(removeNM3(n, m));
		System.out.println(removeNM4(n, m));
		System.out.println(removeNM5(n, m));
	}
}