CORRIGÉS DES PROBLÈMES ALGORITHME

Problème de Joseph

Étude • Phase de construction Avec n = 12 et k = 3 : • création de la liste circulaire ; • création d’une liste chaînée avec les 12 éléments en croissante arithmétique de raison un en partant de un ; puis repli de cette liste sur elle-même grâce au concat(&l, &l). Figure 3.4 Liste Joseph 116 Corrigés des problèmes • Phase de suppressions Suppressions jusqu’à épuisement de la liste : un nouvel ordre émerge, celui des éliminations.

Appelons donc cette nouvelle liste Joséphine. Figure 3.5 Liste Joséphine • Finalisation Pour la finalisation d’une liste circulaire doublement chaînée (reste deux, puis un élément, il convient d’être prudent) : Figure 3.6 Finalisation d’une LDCC (Liste doublement chaînée circulaire)  Dunod – La photocopie non autorisée est un délit 117 Chapitre 3 • Structures séquentielles complexes Architecture fonctionnelle Figure 3.7 Architecture fonctionnelle de PlayJoseph • Fonction principale Spécification de l’algorithme FONCTION playJoseph(n : entier, k : entier) VAR joseph : list, i : entier DEBUT AFFICHER(« Joseph pour n= », n,  » et k= », k) joseph ← newJosephCList(n) printListGraph(joseph, « 1 ») i ← 2 TANTQUE (joseph =6 NULL) FAIRE joseph ← removeKst(&joseph, k) AFFICHER(i) i ← i+1 printListGraph(joseph, «  ») FAIT FIN Implantation C // Exécution du procédé d’élimination de Joseph void playJoseph(int n, int k) { printf(« \nPlay Joseph for n=%d and k=%d\n », n, k); list joseph = newJosephCList(n); printListGraph(joseph, « 1 »); 118 Corrigés des problèmes int i = 2; while (joseph != NULL) { joseph = removeKst(&joseph, k); printf(« %d », i++); printListGraph(joseph, «  »); } } • Construction de la liste circulaire Spécification de l’algorithme FONCTION newJosephCList(longueur : entier) : list VAR joseph : list DEBUT SI (longueur < 1) ALORS RETOURNER NULL FINSI joseph ← newJosephList(longueur, 1) // appel de la fonction qui suit concat(&joseph, &joseph) RETOURNER joseph FIN FONCTION newJosephList(longueur : entier, premier : entier) : list VAR tête : list DEBUT SI (longueur < 1) ALORS RETOURNER NULL FINSI RESERVER(tête) tête→contenu ← premier tête→succ ← newJosephList(longueur – 1, premier + 1) RETOURNER tête FIN Implantation C // Création d’une liste circulaire de 1 à n (version récursive) list newJosephCList(int longueur) { if (longueur < 1) return NULL; list joseph = newJosephList(longueur, 1); concat(&joseph, &joseph); // voir exercice 2.2 return joseph;  } Dunod – La photocopie non autorisée est un délit 119 Chapitre 3 • Structures séquentielles complexes list newJosephList(int longueur, int first) { if (longueur < 1) return NULL; // cas de la liste vide // initialisation de la chaîne avec la création de la tête list head = malloc(sizeof(place)); // allocation mémoire head->contenu = first; // affectation du contenu head->succ = newJosephList(longueur – 1, first + 1); return head; // retour du pointeur sur la tête } • Retrait du kième élément Spécification de l’algorithme FONCTION removeKst(*pl : list, k :entier) : list VAR tête, courant, prev : list VAR circulaire : booléen ; périmètre : entier DEBUT tête ← *pl courant ← *pl SI (courant = NULL) ALORS RETOURNER NULL FINSI circulaire ← isCircular(courant) périmètre ← getCLength(courant) SI (circulaire = vrai) ET (périmètre = 1) ALORS *pl ← NULL RETOURNER *pl FINSI SI (circulaire = vrai) ALORS prev ← getKstElement(*pl, périmètre-1) SINON prev ← NULL FINSI TANTQUE (courant→succ =6 NULL) ET (k > 1) FAIRE k ← k-1 prev ← courant courant ← courant→succ FAIT SI (courant→succ = NULL) ET (k > 0) ALORS RETOURNER *pl FINSI SI (circulaire = vrai) ALORS prev→succ ← courant→succ.