Quelques exemples d'algorithmes valides en Galg

Tous les algorithmes commencent par un commentaire avec un nom d'auteur.
Un algorithme s'arrête là où vous voyez une fine barre horizontale.

     gilles.hunault@univ-angers.fr


########################################################
#                                                      #
#  auteur : (gH)                                       #
#  bonjour.alg : un algorithme de bonjour              #
#                (avec dialogue et appels systèmes)    #
#                                                      #
########################################################


   # la demande = une question + une réponse

   écrire   " Bonjour. Quel est ton nom ? "
   lire     id

   # ce qu'on fait répondre par la machine

   écrire   " Le ", date(), " à ", heure(), " au revoir " , maju(id)





########################################################
#                                                      #
#  auteur : (gH)                                       #
#  secondes.alg : nombre de secondes écoulées          #
#                 entre l'an 0 et l'an 2000            #
#                                                      #
########################################################


   affecter   an        <-- 2000  # en l'an 2000
   affecter   nbAnBi    <-- an/4  # nombre d'années bissextiles (2000/4)
   affecter   nbJours   <-- (an*365) + nbAnBi
   affecter   nbHeur    <-- nbJours * 24
   affecter   nbSec     <-- (nbHeur*60)* 60

   écrire "Entre l'an 0 et l'an " , an , " il s'est écoulé " , nbSec , " secondes."




########################################################
#                                                      #
#  auteur : (gH)                                       #
#  tabmult.alg : la table de multiplication            #
#                avec entrée controlée                 #
#                                                      #
########################################################



   # demande initiale

   écrire  " Donner un entier compris entre 1 et 100 "
   lire nbChoisi

   # relance éventuelle

   tant_que (non entier(nbChoisi))
       écrire " nombre incorrect. Redonner un nombre ENTIER "
       lire nbChoisi
   fin_tant_que # nombre invalide

   # boucle d'affichage

   écrire " Table de " , nbChoisi
   pour indb de1a 10
       affecter produit <-- nbChoisi*indb
       affecter find    <-- formatEntier(indb,2,0)
       affecter fpro    <-- formatEntier(produit,5,0)
       écrire find , " fois " , nbChoisi , " = " , fpro
   fin_pour # indb de1a 10




########################################################
#                                                      #
# cfe.alg  ;  conversion de francs vers euros          #
#          -- auteur : gh                              #
#                                                      #
########################################################

   # 1. Saisie ou conversion du paramètre

   si _nbParametres()=0
      alors écrire   " Quel est le montant en Francs ? "
            lire     mntF
      sinon affecter mntF <-- _valeur( _parametre( 1 ) )
   fin_si # nbParametres()=0

   # 2. Conversion et affichage

   affecter mntE <-- mntF / 6.55957
   écrire   mntF , " Francs font " , mntE , " euros."
   écrire   " et si on arrondit : " , _partieEntiere( 0.5+mntE ), " euros."




########################################################
#                                                      #
#  maxocc.alg : comptage des occurences du maximum     #
#               d'un tableau en une seule boucle       #
#                                                      #
#  -- auteur  : gh                                     #
#                                                      #
########################################################

   # initialisation du tableau avec 15 éléments
   # entiers entre 10 et 100


   affecter nbElt <-- 15
   appeler init_Tab( monT , nbElt , 10 , 20 )

   # détermination du max et comptage du nb d'occurences
   # du max en une seule boucle

   # initialisation de la valeur du maximum (valMax)
   # et de son nombre d'occurences (nbMax)

   affecter valMax  <-- monT[ nbElt ]
   affecter nbMax   <-- 1

   # on parcourt alors le tableau
   # sans utiliser le dernier élément déja comptabilisé

   pour indb de1a nbElt-1
        affecter eltCourant <-- monT[ indb ]
        si eltCourant > valMax
           alors # nouveau maximum local
                 affecter valMax  <-- eltCourant
                 affecter nbMax   <-- 1
           sinon
                 si eltCourant = valMax
                    alors # une fois de plus le maximum
                          affecter nbMax <-- nbMax + 1
                 fin_si # nouvelle occurence du maximum
        fin_si # nouveau maximum
   fin_pour # indb de1a 10

   # affichage de fin

   écrire " Le maximum dans le tableau est : " , valMax
   écrire " et il apparait " , nbMax , " fois."
   écrire " Pour vérification, voici les éléments du tableau : "

   appeler affiche_Tab( monT , 1 , nbElt , 4)




########################################################
#                                                      #
#   brutese.alg : brutesearch, auteur (gH)             #
#                                                      #
########################################################
#                                                      #
# source : Algorithms, second edition                  #
#          pages 279, 280                              #
#          R. Sedgewick, Addison-Wesley 1988           #
#                                                      #
########################################################
#                                                      #
#  recherche "brute" du tableau P dans le tableau A    #
#  (en anglais : P pour pattern, A pour array)         #
#  les variables sont renommées tabP et tabA           #
#  pour plus de lisibilité                             #
#                                                      #
########################################################

   affecter chP <--  "STING"
   affecter chA <--  "A STRING SEARCHING EXAMPLE CONSISTING OF..."

   # conversion des chaines en tableau

   affecter M <-- _longueur(chP)
   pour ind de1a M
     affecter tabP[ ind ] <--  _codeAscii( _sousChaine(chP,ind,1) )
   fin_pour # ind de1a _longueur(chP)

   affecter N <-- _longueur(chA)
   pour ind de1a N
     affecter tabA[ ind ] <--  _codeAscii(_sousChaine(chA,ind,1) )
   fin_pour # ind de1a _longueur(chA)

   # algorithme de recherche

   affecter i <-- 1
   affecter j <-- 1

   répéter

     si tabA[i] = tabP[j]
        alors
              affecter i <-- i + 1
              affecter j <-- j + 1
        sinon
              affecter i <-- i - j + 2
              affecter j <-- 1
     fin_si # tabA[i] = tabP[i]

   jusqu'à (j>M) ou (i>N)

   # affichage du résultat

   si j>M
      alors
            écrire chP , " vue dans " , chA , " à partir de la position " , i-M
      sinon
            écrire chP , " non vue dans ", chA
   fin_si # j>M

   # détail des tableaux (on suppose M < N)

   écrire " Elément   tableau P         tableau A "
   pour ind de1a N
       si (ind<=M)
          alors
                écrire format(ind,3) , " : " , format(tabP[ind],8) , format(tabA[ind],8)
          sinon
                écrire format(ind,3) , " : " , copies(" ",8)   ,   format(tabA[ind],8)
       fin_si # (ind<=M)
   fin_pour # ind de1a max( N,M)




########################################################
#                                                      #
# glouton.alg : affectation de taches selon            #
#               la méthode de mac Naughton             #
# -- auteur (gH)                                       #
#                                                      #
########################################################

   affecter nbMachines  <-- 3
   affecter nbTaches    <-- 6

   affecter dureeTache[ 1 ]  <--   5
   affecter dureeTache[ 2 ]  <--   3
   affecter dureeTache[ 3 ]  <--   4
   affecter dureeTache[ 4 ]  <--   5
   affecter dureeTache[ 5 ]  <--   2
   affecter dureeTache[ 6 ]  <--   5


   # 1. Calcul de la durée minimale

   affecter somDuree <-- 0
   pour indTache de1a nbTaches
        affecter dureeCour <-- dureeTache[ indTache ]
        affecter somDuree  <-- somDuree + dureeCour
        si indTache=1
           alors affecter dureeMax <-- dureeCour
           sinon
                 si dureeCour > dureeMax
                    alors affecter dureeMax <-- dureeCour
                 fin_si # dureeCour > dureeMAx
        fin_si # indTache=1
   fin_pour # indTache de1a nbTaches
   affecter dureeMin <-- max( somDuree / nbMachines , dureeMax)

   écrire " la durée minimale est " , dureeMin ," heures."

   # 2. Affectation des taches aux machines

   # 2.1 Initialisation du tableau de répartititon

   pour indTache de1a nbTaches
        affecter nbTache[ indTache ] <-- 0
        pour indMachine de1a nbMachines
              affecter machineTacheNumero[ indTache , indMachine ] <-- 0
              affecter machineTacheDuree[ indTache , indMachine ]  <-- (-1)
        fin_pour # indMachine de1a nbMachines
   fin_pour # indTache de1a nbTaches

   # 2.2 Boucle d'affectation

   affecter tempsPris   <-- 0
   affecter machineCour <-- 1
   pour indTache de1a nbTaches
       affecter dureeCour <-- dureeTache[ indTache ]

       si tempsPris+dureeCour <=  dureeMin

          alors # on peut affecter toute la tache a la machine courante

                affecter tacheCour                                      <--  nbTache[ machineCour ] + 1
                affecter nbTache[ machineCour ]                         <--  tacheCour
                affecter machineTacheNumero[ machineCour , tacheCour ]  <--  indTache
                affecter machineTacheDuree[  machineCour , tacheCour ]  <--  dureeCour
                affecter tempsPris                                      <--  tempsPris + dureeCour
                si tempsPris = dureeMin
                   alors affecter machineCour <-- machineCour + 1
                         affecter tempsPris   <-- 0
                fin_si # tempsPris = dureeMin

          sinon # on n'a le droit d'affecter qu'une partie a la machine courante

                affecter tacheCour                                     <--  nbTache[ machineCour ] + 1
                affecter nbTache[ machineCour ]                        <--  tacheCour
                affecter machineTacheNumero[ machineCour , tacheCour ] <--  indTache
                affecter resteTemps                                    <--  dureeMin - tempsPris
                affecter machineTacheDuree[  machineCour , tacheCour ] <--  resteTemps

                # et on affecte ce qui reste a la machine suivante

                affecter machineCour                                   <--  machineCour + 1
                affecter tacheCour                                     <--  nbTache[ machineCour ] + 1
                affecter nbTache[ machineCour ]                        <--  tacheCour
                affecter machineTacheNumero[ machineCour , tacheCour ] <--  indTache
                affecter machineTacheDuree[  machineCour , tacheCour ] <--  dureeCour - resteTemps
                affecter tempsPris                                     <--  dureeCour - resteTemps

       fin_si # tempsPris+dureeTache[ tacheCour ] <=  dureeMin

   fin_pour # indTache de1a nbTaches

   # 3. Affichage des répartitions

   pour indMachine de1a nbMachines
       écrire "  -- machine " , indMachine , " : "
       affecter nbTacheCour <-- nbTache[ indMachine ]
       si nbTacheCour > 0
          alors
                pour indTache de1à nbTacheCour
                     affecter dureeCour <-- machineTacheDuree[  indMachine , indTache ]
                     affecter tacheCour <-- machineTacheNumero[ indMachine , indTache ]
                     écrire   "          ===========> tache " , tacheCour , " durée " , dureeCour
                fin_pour # indTache de1à nbTacheCour
       fin_si # numMachine > 0
   fin_pour # indTache de1a nbTaches




########################################################
#                                                      #
# trifus.alg : tri-fusion de fichiers-textes déjà      #
#              triés par ordre alphabétique            #
# -- auteur (gH)                                       #
#                                                      #
########################################################

   # nommage des variables pour noms de fichier

   affecter nomFic1 <-- "triFus.f1"
   affecter nomFic2 <-- "triFus.f2"
   affecter nomFic3 <-- "triFus.f3"

   # initialisation des nombres de lignes lues et écrites

   affecter nbl1 <-- 0
   affecter nbl2 <-- 0
   affecter nbl3 <-- 0

   # ouverture des 3 fichiers

   ouvrir nomFic1 en_lecture  comme fic1
   ouvrir nomFic2 en_lecture  comme fic2
   ouvrir nomFic3 en_écriture comme fic3

   # lecture du premier enregistrement sur fic1

   si non fin_de_fichier(fic1)
      alors # lecture possible
            lire ligne1 sur fic1
            affecter nbl1 <-- nbl1 + 1
   fin_si # lecture du fic1

   # lecture du premier enregistrement sur fic2

   si non fin_de_fichier(fic2)
      alors # lecture possible
            lire ligne2 sur fic2
            affecter nbl2 <-- nbl2 + 1
   fin_si # lecture du fic1

   # boucle de tri-fusion

   tant_que (non fin_de_fichier(fic1)) et (non fin_de_fichier(fic2))
     si _mot(ligne1,2) <= _mot(ligne2,2)
        alors  # écriture de fic1 vers fic3
               écrire " (fic1) " , ligne1 sur fic3
               affecter nbl3 <-- nbl3 + 1
               si (non fin_de_fichier(fic1))
                  alors # lecture possible
                        lire ligne1 sur fic1
                        affecter nbl1 <-- nbl1 + 1
                  sinon affecter ligne1 <-- ""
               fin_si # lecture du fic1
        sinon  # écriture de fic2 vers fic3
               écrire " (fic2) " , ligne2 sur fic3
               affecter nbl3 <-- nbl3 + 1
               si (non fin_de_fichier(fic2))
                  alors  # lecture possible
                        lire ligne2 sur fic2
                        affecter nbl2 <-- nbl2 + 1
                  sinon affecter ligne2 <-- ""
               fin_si # lecture du fic2
     fin_si # comparaison ligne 1 et ligne 2
   fin_tant_que # lecture sur les deux fichiers

   si (_longueur(ligne1)>0) et (_longueur(ligne2)>0)
        alors
              si _mot(ligne1,2) <= _mot(ligne2,2)
                 alors  # écriture de fic1 vers fic3
                        écrire " (fic1) " , ligne1 sur fic3
                        affecter nbl3 <-- nbl3 + 1
                        écrire " (fic2) " , ligne2 sur fic3
                        affecter nbl3 <-- nbl3 + 1
                 sinon  # écriture de fic2 vers fic3
                        écrire " (fic2) " , ligne2 sur fic3
                        affecter nbl3 <-- nbl3 + 1
                        écrire " (fic1) " , ligne1 sur fic3
                        affecter nbl3 <-- nbl3 + 1
              fin_si # comparaison ligne 1 et ligne 2
   fin_si # on compare en fin de fichier

   # s'il reste des lignes dans f1, on recopie f1

   tant_que non fin_de_fichier(fic1)
        lire   ligne1 sur fic1
        affecter nbl1 <-- nbl1 + 1
        écrire " [fic1] " , ligne1 sur fic3
        affecter nbl3 <-- nbl3 + 1
   fin_tant_que # lecture sur f1

   # s'il reste des lignes dans f2, on recopie f2

   tant_que non fin_de_fichier(fic2)
        lire   ligne2 sur fic2
        affecter nbl2 <-- nbl2 + 1
        écrire " [fic2] " , ligne2 sur fic3
        affecter nbl3 <-- nbl3 + 1
   fin_tant_que # lecture sur f1

   # fermeture des fichiers

   fermer fic1
   fermer fic2
   fermer fic3

   # affichage du nombre de lignes lues et écrites :

   écrire "    "  , format(nbl1,4) , " lignes lues    sur " , nomFic1
   écrire "    "  , format(nbl2,4) , " lignes lues    sur " , nomFic2
   écrire "    "  , format(nbl3,4) , " lignes écrites sur " , nomFic3

   quitter 0



########################################################
#                                                      #
# creeidc.alg : création des dictionnaires             #
#               d'un fichier texte                     #
# -- auteur (gH)                                       #
#                                                      #
########################################################
#                                                      #
#   Création des dictionnaires alphabétique            #
#   et d'occurence de la variable fichier FICT         #
#                                                      #
########################################################

#        Version 2 : tableaux et boucles classiques
#        voir "Algorithmique raisonnée, G. Hunault (2000)"
#        pour plus de précisions sur le langage
#        utilisé et les raisons de l'utiliser

# 1. Parcours du fichier texte et comptage des
#    mots à la volée
#    NBMT   est le nombre de mots en tout
#    NBML   est le nombre de la ligne courante
#    NBDIFM contient le nombres de mots différents
#    TMOT   est le tableau dont les indices
#           sont numériques et les valeurs sont les mots
#    TOCC   est le tableau  qui contient en même
#           position le nombre d'occurence du mot

     AFFECTER NbMt   <-- 0
     AFFECTER NbDifM <-- 0

     TANT_QUE fin_de_fichier( ficT ) = 0

        LIRE ligneTexte SUR ficT # ligne courante
        AFFECTER NbMl <-- NbMots( ligneTexte )
        AFFECTER NbMt <-- NbMt + NbMl

        POUR indM DE1A NbMl
             # gestion du mot courant
             AFFECTER motC <-- MotNumero( indM , ligneTexte )
             AFFECTER pdM  <-- position( motC , TMOT )
             SI pdM = 0
                ALORS
                      AFFECTER NbDifM <-- NbDifM + 1
                      AFFECTER TMOT[ NbDifM ] <-- motC
                      AFFECTER TOCC[ NbDifM ] <-- 1
                SINON
                      AFFECTER TOCC[ pdM ]    <-- TOCC[ pdM ] + 1
             FIN_SI # pdM = 0
        FIN_POUR # indM DE1A NbMl

     FIN_TANT_QUE # fin_de_fichier( ficT ) = 0


   # 2. Tri du dictionnaire et recopie
   #    dans le fichier Dico.Alp
   #    (ordre alphabétique croissant)

     APPELER TrieTableaux( tMot, tOcc )

     OUVRIR "Dico.Alp" EN_ECRITURE COMME FdicAlpha

     POUR indM DE1A NbDifM
        AFFECTER motC <-- tMot[ indM ]
        AFFECTER nbOc <-- tOcc[ indM ]
        ECRIRE FormatCar( motC , 20 ) , Format( nbOc , 6) SUR  FdicAlpha
     FIN_POUR # indM DE1A NbDifM

     FERMER FdicAlpha

   # 3. Tri du fichier des mots et recopie
   #    dans le fichier Dico.Ocd
   #    (ordre d'occurences décroissant)

     OUVRIR "Dico.Ocd" EN_ECRITURE COMME FdicOccd

   # on trie sur le mot numéro  2 (nb d'occurences)

     APPELER TrieFichierSuivant(  FdicAlpha , FdicOccd , 2 )

     écrire "Vous pouvez utiliser Dico.Alp et Dico.cd."




    retour page principale de galg  Retour à la page principale de Galg