First commit.

1 files changed, 101 insertions, 0 deletions

diff --git a/tests/exec/josephus.cpp b/tests/exec/josephus.cpp
new file mode 100644
index 0000000..f43dac6
--- /dev/null
+++ b/tests/exec/josephus.cpp
@@ -0,0 +1,101 @@
+#include <iostream>
+
+/*** listes circulaires doublement chaînées ***/
+
+class ListeC {
+  public:
+  int valeur;
+  ListeC *suivant;
+  ListeC *precedent;
+  ListeC(int v);
+  void insererApres(int v);
+  void supprimer();
+  void afficher();
+};
+
+/* constructeur = liste réduite à un élément */
+ListeC::ListeC(int v) {
+  valeur = v;
+  suivant = precedent = this;
+}
+
+/* insertion après un élément */
+void ListeC::insererApres(int v) {
+  ListeC *e = new ListeC(0);
+  e->valeur = v;
+  e->suivant = suivant;
+  suivant = e;
+  e->suivant->precedent = e;
+  e->precedent = this;
+}
+
+/* suppression d'un élément */
+void ListeC::supprimer() {
+  precedent->suivant = suivant;
+  suivant->precedent = precedent;
+}
+
+/* affichage */
+void ListeC::afficher() {
+  ListeC *c = this;
+  std::cout << c->valeur << " ";
+  c = c->suivant;
+  for (; c != this;) {
+    std::cout << c->valeur << " ";
+    c = c->suivant;
+  }
+  std::cout << "\n";
+}
+
+/*** problème de Josephus ***/
+
+/* construction de la liste circulaire 1,2,...,n;
+   l'élément retourné est celui contenant 1 */
+ListeC *cercle(int n) {
+  ListeC *l = new ListeC(1);
+  int i;
+  for (i = n; i >= 2; i--) {
+    l->insererApres(i);
+  }
+  return l;
+}
+
+/* jeu de Josephus */
+int josephus(int n, int p) {
+  /* c est le joueur courant, 1 au départ */
+  ListeC *c = cercle(n);
+
+  /* tant qu'il reste plus d'un joueur */
+  for (; c != c->suivant;) {
+    /* on élimine un joueur */
+    int i;
+    for (i = 1; i < p; i++)
+      c = c->suivant;
+    c->supprimer();
+    // std::cout << c->valeur << " est éliminé";
+    c = c->suivant;
+  }
+  // std::cout << "le gagnant est " << c->valeur;
+  return c->valeur;
+}
+
+/*** Tests ***/
+
+int main() {
+  ListeC l = ListeC(1);
+  l.afficher();
+  l.insererApres(3);
+  l.afficher();
+  l.insererApres(2);
+  l.afficher();
+  l.suivant->supprimer();
+  l.afficher();
+
+  ListeC *c = cercle(7);
+  c->afficher();
+
+  if (josephus(7, 5) == 6 &&
+      josephus(5, 5) == 2 &&
+      josephus(5, 17) == 4 && josephus(13, 2) == 11)
+    std::cout << "ok\n";
+}