Discussion :

[Happpy]

Bonjour tout le monde, je suis en train de faire un exercice mais même après plusieurs tentatives, je ne trouve pas le résultat et je ne comprends pas pourquoi...

ÉNONCÉ :

Au premier siècle éclata une révolte des Juifs contre Rome. Un groupe de 40 Juifs fut capturé, parmi eux Flavius Josèphe le futur auteur de l'Histoire des Juifs. Afin d'éviter d'être réduits en esclavage, ils décidèrent un suicide collectif selon les modalités suivantes : s'étant placés en cercle, un vivant sur sept serait tué, et le dernier survivant se suiciderait. Ce dernier fut justement Flavius Josèphe qui se garda bien de s'exécuter.

Ecrire une fonction Flavius telle que l'appel (Flavius n k) rende un tableau qui contient l'ordre d'exécution de n individus lorsqu'on utilise l'algorithme précédent en tuant un individu sur k.

Exemple : Flavius 40 7 doit rendre le tableau :

[|7; 14; 21; 28; 35; 2; 10; 18; 26; 34; 3; 12; 22; 31; 40; 11; 23; 33; 5; 17; 30; 4; 19; 36; 9; 27; 6; 25; 8; 32; 16; 1; 38; 37; 39; 15; 29; 13; 20; 24|]


Je vous remercie d'avance pour des explications car je ne comprends pas du tout comment obtenir la séquence proposé, cela ne peut que signifier que j'ai mal compris l'algorithme à implémenter...
S'il vous plaît, si personne ne sait, dites-le moi car c'est encore plus dur de rester dans l'espérance alors que rien ne va venir...

[prgasp77]

Bonjour Happy.

La résolution de ton problème se fait en deux étapes bien distinctes. La première est de définir un algorithme* approprié au problème ; la seconde est d'implémenter cet algorithme.

Où en es-tu ? Peut-on voir ton algo en pseudo code ?

(*) Comme tu codes en caml, mieux vaut si possible trouver un algorithme récursif .

[Happpy]

Re bonjour, je ne vais malheureusement pas m'aventurer à utiliser la récursivité car nous ne l'avons pas encore assez travaillé.


Mon algorithme renvoie la séquence suivante :

[|32; 6; 11; 22; 19; 27; 1; 29; 25; 7; 16; 12; 38; 2; 36; 31; 20; 8; 23; 39; 3; 13; 17; 40; 28; 9; 26; 4; 37; 21; 14; 30; 18; 10; 5; 24; 34; 33; 35; 15|]

et il faut trouver : [|7; 14; 21; 28; 35; 2; 10; 18; 26; 34; 3; 12; 22; 31; 40; 11; 23; 33; 5; 17; 30; 4; 19; 36; 9; 27; 6; 25; 8; 32; 16; 1; 38; 37; 39; 15; 29; 13; 20; 24|]


On remarque que dans ma séquence on voit que la 7ème case est premiere, or en dessous, la première case du tableau a pour valeur 7, ainsi, je pense avoir à faire un changement mineur dans mon code pour corriger ce problème et "échanger" l'ordre et les valeurs.

[prgasp77]

Ton problème est que ton implémentation est tellement brouillon que tu ne repères pas la source de l'erreur. Il te faut diviser ton problème en sous-problèmes ; tu fais de la programmation fonctionnelle .

Alternativement, je te propose une solution peu efficace (d'un point de vue optimisation) mais assez simple à écrire ; on pourra aller plus loin ensuite si tu le souhaites.

Code :

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

1
2
3
4
Prends la liste [1;2;...;n] ;
Fais passer les k-1 premiers éléments en queue ([k;k+1;...;n;1;2;...;k-1]) ;
Enlève le premier élément de ta liste de travail et ajoute le dans le tableau solution ;
répète (jusqu’à atteindre une certaine condition d'arrêt).

Prends bien soin de créer des fonctions pour chacun des sous problèmes (créer une liste contenant les n premiers naturels ; appliquer une rotation de x éléments à une liste ; etc.).

[Happpy]

Re bonjour, je vais regarder la méthode que tu me propose. Mais je ne vois pas comment faire "passer" les k-1 éléments en queue, ça doit demander pas mal de manipulations non ?

Voila un autre code sur lequel je travaille :

*Code inutile*

[prgasp77]

Tu vas avoir du mal à trouver ton erreur, ton code est trop noyé. On peut faire un peu de ménage pour commencer.

Tout d'abord, ne vérifie pas la validité des arguments, on l'ajoutera plus tard. Ensuite pour les personnes, je te propose un type plus adéquat qui nous évitera des erreurs d’inattention :

Code :

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

type personne = Alive | Dead of int

Ainsi Alive est une constante du type personne et Dead 5 est aussi une personne (ce qui signifie que cette personne est morte la cinquième).

Continuons. Dans l'exercice, il te faut parcourir en boucle la ronde formée par les futur suicidés. Tu n'as aucune raison d'imbriquer deux boucles, ta première version était bonne.

Encore un « truc » : la fonction incr. Elle prend une int ref et l'incrémente. Elle est définie à peu près ainsi :

Code :

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

1
2
let incr intref =
   intref := !intref + 1

La fonction decr existe aussi et fait ce qu'on attend d'elle.


Conseil algorithmique. Ne perds pas ton temps à remplir le tableau résultat pendant le calcul, tu mélanges deux choses distinctes (calcul et présentation du résultat) et rends ton code plus difficile à suivre. Dans un premier temps (une fonction à part ?) aide ces braves juifs à se suicider et ensuite seulement récupère l'ordre dans lequel ils ont trépassé. Astuce : pour savoir dans quelle position se trouve la personne #i (où ronde est le tableau de personnes) :

Code :

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

1
2
3
4
let get_dead_order ronde i =
   match ronde.(i) with
   | Dead n -> n
   | Alive -> failwith("Ceci ne devrais pas arriver.\n")

[Happpy]

Re bonjour,
après avoir modifié un peu mon code, j'ai finalement terminée, le tout en une seule fonction.
Je n'ai pas crée de fonction auxiliaire pour "remettre le tableau" dans l'ordre car cela aurait nécessité de relire l'intégralité du tableau, ce qui n'aurait pas été négligeable si une gigantesque armée de soldats voulait se suicider...
J'ai résolu le problème directement dans ma boucle.

Je vous remercie pour les conseils.
Bonne continuation !

[prgasp77]

L'optimisation a priori est la racine de tous les maux* ! Apprends à produire un code lisible et simple. Il faut qu'un lecteur extérieur à ton projet comprenne du premier coup d'œil ce que fait chacun des morceaux de ton code.

Si tu es satisfait de ton travail tant mieux, mais lorsque « ça marche » tu n'es qu'à la moitié du chemin. Et pour être franc, si j'étais ton prof et que tu me fournissais un bout de code tel que donné avant, tu aurais le droit à un beau 10/20 parce que « ça marche ».

* "premature optimisation is the root of all evil", Knuth, Donald (December 1974). "Structured Programming with go to Statements". ACM Journal Computing Surveys 6.