package list; // le problème de Josephus class Josephus { /* construction de la liste circulaire 1,2,...,n; l'élément renvoyé est celui * contenant 1 */ static Doubly circle(int n) { Doubly l1 = new Doubly(1); for (int i = n; i >= 2; i--) { l1.insertAfter(i); if (i == n) { l1.prev = l1.next; l1.next.next = l1; } } return l1; } // n joueurs, on compte de p en p static int josephus(int n, int p) { Doubly c = circle(n); while (c != c.next) { // tant qu'il reste au moins deux joueurs for (int i = 1; i < p; i++) c = c.next; c.remove(); // on élimine le p-ième System.out.println(c.element + " est éliminé"); c = c.next; } System.out.println("le gagnant est " + c.element); return c.element; } public static void main(String args[]) { assert (josephus(7, 5) == 6); assert (josephus(5, 5) == 2); assert (josephus(5, 17) == 4); assert (josephus(13, 2) == 11); System.out.println("Josephus OK"); } } // exercice class JosephusSingly { /* construction de la liste circulaire 1,2,...,n; * l'élément renvoyé est celui contenant n */ static Singly circle(int n) { Singly last = new Singly(n, null); Singly first = last; for (int i = n - 1; i >= 1; i--) first = new Singly(i, first); last.next = first; return last; } static int josephus(int n, int p) { Singly pred = circle(n); Singly c = pred.next; while (c != pred) { // tant qu'il reste au moins deux joueurs for (int i = 1; i < p; i++) { pred = c; c = c.next; } System.out.println(c.element + " est éliminé"); pred.next = c.next; c = c.next; } System.out.println("le gagnant est " + c.element); return c.element; } public static void main(String args[]) { assert (josephus(7, 5) == 6); assert (josephus(5, 5) == 2); assert (josephus(5, 17) == 4); assert (josephus(13, 2) == 11); System.out.println("JosephusSingly OK"); } } //exercice class JosephusArray { // attention : on utilise ici les indices 0,1,...,n-1 // pour désigner les joueurs 1,2,...,n static int josephus(int n, int p) { int[] next = new int[n]; for (int i = 0; i < n; i++) next[i] = (i + 1) % n; int pred = n - 1, c = 0; while (c != pred) { // tant qu'il reste au moins deux joueurs for (int i = 1; i < p; i++) { pred = c; c = next[c]; } System.out.println((c+1) + " est éliminé"); next[pred] = next[c]; c = next[c]; } System.out.println("le gagnant est " + (c+1)); return c+1; // on renvoie le joueur, pas l'indice } public static void main(String args[]) { assert (josephus(7, 5) == 6); assert (josephus(5, 5) == 2); assert (josephus(5, 17) == 4); assert (josephus(13, 2) == 11); System.out.println("JosephusSingly OK"); } }