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 à la page principale de Galg