Discussion :

[bilboboy]

Donc voilà, j'ai découvert ce problème il y a peu sur un site et je me demandais s'il était possible de le coder en pascal sous forme de tableau, de liste circulaire simplement et doublement chaînées, et l'intitulé sur un certain site d'un devoir pour des personnes en IUT info est :

On considère un ensemble de n éléments placées sur un cercle. Les éléments sont placés dans l’ordre de 1 à n. Toutes les k ièmes éléments sont retirés du cercle et la suivant devient le nouveau numéro 1. On veut ainsi connaître le rang du i ième élément retiré et en particulier le rang du dernier qui est le survivant.

Et je vois pas trop par où commencer et comment faire surtout, pouvez vous m'aider ? :/

[Roland Chastain]

Donc voilà, j'ai découvert ce problème il y a peu sur un site et je me demandais s'il était possible de le coder en pascal sous forme de tableau, de liste circulaire simplement et doublement chaînées, et l'intitulé sur un certain site d'un devoir pour des personnes en IUT info est :

Bonjour !

Si tu veux recevoir de l'aide, il faut que tu proposes ton essai.

Si j'étais toi, je commencerais par essayer de résoudre un cas simple, en fixant les valeurs de n et de k.

En faisant une recherche rapide, je suis tombé sur un document très bien présenté, avec des exemples de code en Pascal :

Le problème de Flavius Josèphe

[Roland Chastain]

A l'époque j'avais fait une petite animation pour montrer comment le problème pouvait être résolu au moyen d'un tableau. Malheureusement, je n'arrive plus à remettre la main sur la source ; mais j'ai retrouvé l'exécutable (voir pièce jointe).

Le début du code, c'était quelque chose comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
const
  n = 10;
  k = 2;
 
var
  i: integer; // ordre d'élimination de 1 à n
  j: integer; // rang de 1 à n
  c: integer; // compteur de 1 à k
  a: array[1..n]of boolean; // pour savoir qui a été éliminé

Ensuite il n'y a plus qu'à compter. Tant que les n personnes n'ont pas été éliminées...

Le cas où n est égal à 10 et k égal à 2 correspond à l'exemple de la page 32 dans le document que j'ai mentionné plus haut.

[bilboboy]

Merci je vais lire tout celà ensuite je vous donnerez mon code et vous me direz si tout va bien ? Après j'essaierais en faisant une liste simplement puis doublement chainée

[Roland Chastain]

Merci je vais lire tout cela ensuite je vous donnerai mon code

Non, tu n'as pas besoin de tout lire ! J'ai mis la référence du document pour tout le monde, parce qu'il m'a paru bien fait.

Pour faire l'exercice, il suffit de lire les deux premières pages (31 et 32). Le problème est bien présenté, et le résultat est donné pour deux exemples, celui de l'histoire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
const
  n = 40+1; // Les quarante assiégés plus Flavius Josèphe
  k = 3;

et un autre encore plus simple (celui que j'ai représenté dans mon animation).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
const
  n = 10;
  k = 2;

Tu pourrais résoudre d'abord ce dernier exemple, avec un crayon et du papier, pour vérifier que tu as bien saisi la procédure. Tu peux comparer ton résultat avec celui du document.

[Roland Chastain]

J'ai amélioré mon programme (pièce jointe plus haut). Maintenant l'utilisateur choisit les valeurs de n et de k.

L'animation met en évidence l'inconvénient de la résolution par tableau.