retour vers la page d'accueil

STS IG 2 - année 2002/2003
TD n°5 : Tirage du loto
éléments de correction

T_Element est une structure
                info est un entier

                PrecedentTirage,
                SuivantTirage,

                SuivantNumero sont des pointeurs de T_Element
              fin structure

DONNEES
  BorneMin est un entier et est initialisée à 1
  BorneMax est un entier et est initialisée à 99

  Ptr_RacineTirage,
  Ptr_DernierTirage,
  Ptr_RacineNumero,
  Ptr_DernierNumero sont des pointeurs de T_Element

algorithme InitialiserTirage
// cet algorithme initialise le(s) chainage(s) dynamique(s).
début
  Ptr_RacineTirage  <-- PTR_NUL
  Ptr_DernierTirage <-- PTR_NUL
  Ptr_RacineNumero  <-- PTR_NUL
  Ptr_RacineNumer   <-- PTR_NUL
fin

algorithme ViderTirage
// cet algo efface tous les numéros sortis en libérant les structures dynamiques.
début
  tant que (Ptr_RacineTirage <> PTR_NUL) faire
    AnnulerTiragePrecedent
  fin tant que
fin

algorithme AnnulerTiragePrecedent
// cet algo retire le dernier numéro sorti, qui peut donc de nouveau être tiré.
début
  si (Ptr_RacineTirage <> PTR_NUL) alors             // On vérifie qu'il y a déjà des numéros de sortis...
    si (Ptr_DernierTirage = Ptr_RacineTirage) alors  // Cas où il n'y a qu'un numéro de sorti
      Ptr_Ancien <-- Ptr_RacineTirage
      Liberer (Ptr_Ancien)

      InitialiserTirage
    sinon                                            // Cas où il y a plus d'un numéro de sorti
      Ptr_Ancien <-- Ptr_DernierTirage

      // Mise à jour du chainage selon l'ordre du tirage
      Ptr_DernierTirage <-- Ptr_DernierTirage^.PrecedentTirage
      Ptr_DernierTirage^.SuivantTirage <-- PTR_NUL

      // Mise à jour du chainage selon l'ordre numérique
      Ptr_Courant <-- Ptr_RacineNumero

      si (ptr_RacineNumero = Ptr_Ancien) alors     // On vérifie si l'élément à retirer est le premier dans l'ordre numérique
        Ptr_RacineNumero <-- Ptr_Ancien^.SuivantNumero
      sinon
        tant que (Ptr_Courant^.SuivantNumero <> Ptr_Ancien) faire  // On recherche l'élément situé avant celui à retirer
          Ptr_Courant <-- Ptr_Courant^.SuivantNumero
        fin tant que
        si (Ptr_DernierNumero = Ptr_Ancien) alors  // On vérifie si l'élément à retirer est le dernier dans l'ordre numérique
          Ptr_DernierNumero <-- Ptr_Courant
          Ptr_Courant^.SuivantNumero <-- PTR_NUL
        sinon
          Ptr_Courant^.SuivantNumero <-- ptr_Ancien^.SuivantNumero
        fin si
      fin si

      // On détruit la structure dynamique
      libérer (Ptr_Ancien)
    fin si
  fin si
fin

fonction SortirNumero renvoie un entier
// cette fonction renvoie le numéro nouvellement tiré et l'ajoute dans les structures dynamiques.
début
  Allouer (Ptr_Nouveau)

  Ptr_Nouveau^.PrecedentTirage <-- PTR_NUL
  Ptr_Nouveau^.SuivantTirage   <-- PTR_NUL
  Ptr_Nouveau^.PrecedentNumero <-- PTR_NUL

  // Tirer le numéro
  répéter
    Ptr_Nouveau^.info <-- EntierAleatoire (BorneMax - BorneMin + 1) + BorneMin
  jusqu'à (ChercherNumero (Ptr_Nouveau^.info) = 0)

  // Cas où il s'agit du premier numéro sorti
  si (Ptr_RacineTirage = PTR_NUL) alors
    Ptr_RacineTirage  <-- Ptr_Nouveau
    Ptr_DernierTirage <-- Ptr_Nouveau
    Ptr_RacineNumero  <-- Ptr_Nouveau
    Ptr_DernierNumero <-- Ptr_Nouveau
  sinon
    // Mise à jour de la chaine des tirages
    Ptr_Nouveau^.PrecedentTirage <-- Ptr_DernierTirage
    Ptr_DernierTirage^.SuivantTirage <-- Ptr_Nouveau

    Ptr_DernierTirage <-- Ptr_Nouveau

    // Mise à jour de la chaine des numeros
    si (Ptr_Nouveau^.Info < Ptr_RacineNumero^.Info) alors    // Placer en début de chainage
      Ptr_Nouveau^.SuivantNumero <-- Ptr_RacineNumero
      Ptr_RacineNumero <-- Ptr_Nouveau
    sinon
      si (Ptr_Nouveau^.Info > Ptr_DernierNumero^.info) alors // Placer en fin de chainage
        Ptr_DernierNumero^.SuivantNumero <-- Ptr_Nouveau
        Ptr_DernierNumero <-- Ptr_Nouveau
      sinon                                                  // Placer en cours de chainage
        ptr_Courant <-- Ptr_RacineNumero  // Rechercher l'élement après lequel placer le nouveau numéro
        tant que (Ptr_Nouveau^.Info > Ptr_Courant^.SuivantNumero^.info) faire
          Ptr_Courant <-- Ptr_Courant^.SuivantNumero
        fin tant que

        // Mise en place de l'élément nouveau
        Ptr_Nouveau^.SuivantNumero <-- Ptr_Courant^.SuivantNumero
        Ptr_Courant^.SuivantNumero <-- Ptr_Nouveau
      fin si
    fin si
  fin si
fin

fonction ChercherNumero (E: Numero est un entier) renvoie un entier
// Cette fonction recherche si le numéro passé en paramètre est déjà sorti. Il renvoie le numéro du tirage correspondant.
// Par exemple : si le tirage des 4 premiers numéros donne 24, 15, 75, 49
// alors l'appel de ChercherNumero (75) donnera 3
// tandis que l'appel de ChercherNumero (62) donnera 0 (car le 62 n'est pas encore sorti)
début
  Ptr_Courant <-- Ptr_RacineTirage
  compteur <-- 1
  tant que (ptr_Courant <> Ptr_DernierTirage) ET (Ptr_Courant^.info <> Numero) faire
    Ptr_Courant <-- Ptr_Courant^.SuivantTirage
  fin tant que

  si (Ptr_Courant^.Info <> Numero) alors
    Compteur <-- 0
  fin si

  retourner (Compteur)
fin

algorithme AfficherTirage (entrée : OrdreNumerique est un booléen)
// Affiche tous les numéros déjà sortis ordonnés de la manière suivante (en reprenant l'exemple du tirage ci-dessus) :
//   si OrdreNumerique est à VRAI, alors les numéros      seront donnés dans l'ordre numérique (15, 24, 49 et 75)
//   si OrdreNumerique est à FAUX, alors les numéros      seront donnés dans l'ordre du tirage (24, 15, 75 et 49)
début
fin