Package algo Vincent Lozano Version 1.4 — Février 2008 http://lozzone.free.fr Résumé Ce document décrit l’utilisation et la configuration du merveilleux package algo permettant d’écriredesalgorithmesdansundocumentLATEX.Lestyleestceluid’unlangagetypéserapprochant du Pascal ou du C. On peut d’ailleurs utiliser l’une ou l’autre des syntaxes pour les déclarations de variables et de types. Ce package est entièrement paramétrable et devrait s’adapter à la plupart des besoinspourcequiestdel’écrituredesalgorithmes.Ilaétécréépourproduiredessupportsdecours d’informatique dispensé aux élèves de l’École nationale d’ingénieurs de Saint-Étienne. Cette version, programmée avec les pieds, est la première diffusion, seuls cinq utilisateurs ont vaillement passé les tests... Si vous voyez ce que je veux dire Alors Tournez la page Sinon Répéter Relisez le résumé Jusque ce que vous ayez compris Sommaire 1 Introduction 1 2 Utilisation 2 3 Personnalisations 12 4 Algorithmes flottants 19 5 Retour 20 1 Introduction Ce package permet d’écrire des programmes en langage algorithmique. Sa syntaxe est vaguement inspirée du package algorithmic de Peter Williams. Pour l’utiliser, il suffit d’insérer la commande : \usepackage{algo} dans le préambule du document. Les options qu’il est possible de passer au package sont : – noendkeyword qui supprime les mots de fin de clause (cf. 3.2); – numbered pour numéroter les algorithmes (cf. 3.1); – english pour écrire les mots clé en anglais; – cstyledecls pour utiliser le style du langage C pour les déclarations et les arguments de fonction (cf. § 3.10 page 18). Aprèschargementdupackage,ondisposed’unenvironnementalgodanslequeldescommandesspécifiques les programmes en langage algorithmique : \begin{algo} ... \end{algo} 1 2 Utilisation Tout d’abord, le fameux algorithme « hello world » : \begin{algo} Algorithme bonjour monde \ALGO{bonjour monde} Variable \VAR \DECLVAR{c}{chaine} c:chaine \DECLVAR[compteur]{i}{entier} i:entier { compteur } \ENDVAR Début \BEGIN c ← "bonjour monde" \STATE{c \recoit{} "bonjour monde"} { on affiche 3 fois le message } \COMMENT{on affiche 3 fois le message} \FOR{i}{1}{3} Pour i variantDe 1 à 3 Faire \STATE{Afficher(c)} Afficher(c) \ENDFOR FinPour \END Fin \end{algo} On constatera que tout est produit dans la fonte « machine à écrire » sauf les chaînes de caractères (délimitée par le caractère ") en roman, les commentaires en roman penché et les types en italique (cf. § 3.8 page 15 pour voir comment changer cela). On pourra dores et déjà noter que l’environnement algo ne tient pas compte des espaces et sauts de ligne, par conséquent le même algorithme aurait été produit par le code : \begin{algo} \ALGO{bonjour monde} \VAR \DECLVAR{c}{chaine} \DECLVAR{i}{entier}\ENDVAR \BEGIN \STATE{c \recoit{} "bonjour monde"} \FOR{i}{1}{3}\STATE{Afficher(c)} \ENDFOR \END \end{algo} 2.1 Constantes, types et Variables On pourra déclarer les constantes en utilisant des blocs : \CONST \ENDCONST Constante \TYPE \ENDTYPE Type Variable \VAR \ENDVAR 2.1.1 Constantes À l’intérieur de chacun de ces blocs, on pourra déclarer des constantes en utilisant trois syntaxes : – \DECLCONST{(cid:104)nom(cid:105)}{(cid:104)val(cid:105)} : Constante (cid:104)nom(cid:105) = (cid:104)val(cid:105) – \DECLCONST[(cid:104)description(cid:105)]{(cid:104)nom(cid:105)}{(cid:104)val(cid:105)} : Constante (cid:104)nom(cid:105) = (cid:104)val(cid:105) { (cid:104)description(cid:105) } – \DECLCONST[(cid:104)description(cid:105)][(cid:104)type(cid:105)]{(cid:104)nom(cid:105)}{(cid:104)val(cid:105)} : 2 Constante (cid:104)nom(cid:105):(cid:104)type(cid:105)=(cid:104)val(cid:105) { (cid:104)description(cid:105) } L’argument optionnel (cid:104)description(cid:105) permet d’ajouter une description sous la forme d’un commentaire à côté de la déclaration, et le deuxième argument optionnel permet de préciser le type de la constante si nécessaire : \CONST Constante \DECLCONST[][booléen]{OUVERT}{Vrai} OUVERT:booléen=Vrai \DECLCONST[$\pi$][flottant]{PI}{3.14} PI:flottant=3.14 { π } \DECLCONST[40 trucs au +]{MAX\_BIDULE}{40} MAX_BIDULE = 40 { 40 trucs au + } \ENDCONST 2.1.2 Variables Les variables peuvent être définies avec la syntaxe : Variable \DECLVAR{(cid:104)nom(cid:105)}{(cid:104)type(cid:105)} qui donnera : (cid:104)nom(cid:105):(cid:104)type(cid:105) ou, si l’on veut ajouter un commentaire à la déclaration de la variable : Variable \DECLVAR[(cid:104)desc(cid:105)]{(cid:104)nom(cid:105)}{(cid:104)type(cid:105)} qui donnera : (cid:104)nom(cid:105):(cid:104)type(cid:105) { (cid:104)desc(cid:105) } Quelques exemples : \VAR Variable \DECLVAR[compteurs]{i,j}{entier} i,j:entier { compteurs } \DECLVAR[le machin]{res}{flottant} res:flottant { le machin } \ENDVAR 2.1.3 Types On peut définir un nouveau type en écrivant : \TYPE Type \DECLTYPE{Tbidule}{entier} Tbidule = entier \ENDTYPE L’environnement algo permet également d’écrire la définition des types structurés tableau et enregistre- ment. La définition de type tableau peut être produite de la manière suivante : \TYPE Type \DECLTYPE{Ttab}{\ARRAY{entier}} Ttab = Tableau entier [] \ENDTYPE On pourra utiliser des tableaux à deux dimensions comme suit : \TYPE \DECLTYPE{Tmatrice}{% Type \ARRAY[2]{flottant}} Tmatrice = Tableau flottant [][] \ENDTYPE 3 Pour utiliser des tableaux dont on fixe la taille, on pourra avoir recours à la fonction \DIMARRAY prenant jusqu’à trois arguments optionnels : \TYPE \DECLTYPE{Tmatrice}{% Type \DIMARRAY[5][7]{flottant}} Tmatrice = Tableau flottant [5][7] \ENDTYPE Variable \VAR montab:Tableau entier [4] \DECLVAR{montab}{\DIMARRAY[4]{entier}} \ENDVAR Pour ce qui concerne les enregistrements, on utilisera la syntaxe suivante : \TYPE Type \RECORD{Tsequence} Tsequence = Enregistrement \DECLFIELD{nbre}{entier} \DECLFIELD{donnees}{% nbre:entier \DIMARRAY[20]{flottant}} donnees:Tableau flottant [20] \ENDRECORD FinEnregistrement \ENDTYPE 2.2 Algorithmes et instructions On écrit un algorithme dans un bloc : \BEGIN Début Fin \END et les instructions à l’aide de la clause : \STATE{...} Par exemple : \VAR Variable \DECLVAR{i,j}{entier} i,j:entier \DECLVAR{bidule}{flottant} bidule:flottant \ENDVAR Début \BEGIN j ← 20 \STATE{j \recoit{} 20} \STATE{i \recoit{} 2*j} i ← 2*j \END Fin 2.3 Structures de contrôle Le package propose plusieurs structures de contrôle dont voici quelques exemples pour en expliciter les constructions. 2.3.1 Si .. Alors ... Sinon La fameuse structure de contrôle sans la clause sinon : 4 \VAR Variable \DECLVAR{i}{entier} i:entier \ENDVAR Début \BEGIN Si i=0 Alors \IF{i=0} Afficher("i est nul") \STATE{Afficher("i est nul")} \ENDIF FinSi \END Fin La même avec la clause sinon : Variable \VAR \DECLVAR{b}{booléen} b:booléen \ENDVAR Début \BEGIN Si b=VRAI Alors \IF{b=VRAI} Afficher("Oui") \STATE{Afficher("Oui"} Sinon \ELSE \STATE{Afficher("Non")} Afficher("Non") \ENDIF FinSi \END Fin On peut également construire une clause du type alternative multiple de la manière suivante : Variable \VAR i:entier \DECLVAR{i}{entier} Début \ENDVAR \BEGIN Si i=0 Alors \IF{i=0} afficher("Nul") \STATE{afficher("Nul")} SinonSi i=1 Alors \ELSEIF{i=1} afficher("Un") \STATE{afficher("Un")} SinonSi i=2 Alors \ELSEIF{i=2} \STATE{afficher("Deux")} afficher("Deux") \ELSE Sinon \STATE{afficher("Ni 0, ni 1, ni 2")} afficher("Ni 0, ni 1, ni 2") \ENDIF FinSi \END Fin 5 2.3.2 SelonQue ... Variable \VAR rep:entier \DECLVAR{rep}{entier} Début \ENDVAR Afficher("Votre choix?") \BEGIN Lire(rep) \STATE{Afficher("Votre choix ?")} \STATE{Lire(rep)} SelonQue rep vaut \SWITCH{rep} Cas 1 : \CASE{1} bidule(rep) \STATE{bidule(rep)} FinCas \ENDCASE Cas 2 : \CASE{2} \STATE{truc(rep-1)} truc(rep-1) \ENDCASE FinCas \CASE{3} Cas 3 : \STATE{chouette(2*rep)} chouette(2*rep) \ENDCASE FinCas \ENDSWITCH \END FinSelonQue Fin On peut également écrire un Selon Que avec un cas par défaut : SelonQue rep vaut \SWITCH{rep} Cas 1 : \CASE{1} bidule(rep) \STATE{bidule(rep)} FinCas \ENDCASE Cas 2 : \CASE{2} \STATE{truc(rep-1)} truc(rep-1) \ENDCASE FinCas \DEFAULT Sinon \STATE{par\_defaut(2*rep)} par_defaut(2*rep) \ENDCASE FinCas \ENDSWITCH FinSelonQue Enfin on peut utliser une version condensée de la clause Cas : SelonQue rep vaut \SWITCH{rep} Cas 1 : bidule(rep) \SHORTCASE{1}{bidule(rep)} Cas 2 : truc(rep-1) \SHORTCASE{2}{truc(rep-1)} \DEFAULT Sinon \STATE{par\_defaut(2*rep)} par_defaut(2*rep) \ENDCASE FinCas \ENDSWITCH FinSelonQue 6 2.3.3 Répéter ... Jusqu’à Variable \VAR \DECLVAR{i}{entier} i:entier \ENDVAR Début \BEGIN i←0 \STATE{i\recoit{}0} Répéter \REPEAT Afficher("2 x ",i," = ",2*i) \STATE{Afficher("2 x ",i," = ",2*i)} \STATE{i\recoit{}i+1} i←i+1 \ENDREPEAT{i>10} Jusque i>10 \END Fin 2.3.4 Répéter ... TantQue \VAR Variable \DECLVAR{rep}{caractère} rep:caractère \ENDVAR Début \BEGIN \REPEAT Répéter \STATE{Afficher("Alors ? (o/n)")} Afficher("Alors? (o/n)") \STATE{Lire(rep)} Lire(rep) \ENDREPEAT[while]{rep$\not =$’o’ TantQue rep(cid:54)=’o’ ET rep(cid:54)=’n’ ET rep$\not=$’n’} Fin \END Notez l’utilisation de l’argument optionnel while à la commande \ENDREPEAT. 2.3.5 TantQue .. Faire \VAR Variable \DECLVAR{rep}{caractère} rep:caractère \ENDVAR Début \BEGIN \STATE{rep\recoit{}’?’} rep←’?’ \WHILE{rep$\not=$’o’ ET TantQue rep(cid:54)=’o’ ET rep(cid:54)=’n’ Faire rep$\not=$’n’} Afficher("Alors? (o/n)") \STATE{Afficher("Alors ? (o/n)")} Lire(rep) \STATE{Lire(rep)} FinTantQue \ENDWHILE Fin \END 2.3.6 Boucle Pour ... \VAR Variable \DECLVAR{c}{entier} c:entier \ENDVAR Début \BEGIN Afficher("La table de 3 : ") \STATE{Afficher("La table de 3 : ")} Pour c variantDe 1 à 10 Faire \FOR{c}{1}{10} Afficher("3 x ",c," = ",3*c) \STATE{Afficher("3 x ",c," = ",3*c)} \ENDFOR FinPour \END Fin 7 On peut également utiliser la notion de pas d’incrémentation avec la commande \FORSTEP : \VAR Variable \DECLVAR{c}{entier} c:entier \ENDVAR Début \BEGIN Pour c variantDe 1 10 parPasDe 2 Faire \FORSTEP{c}{1}{10}{2} Afficher(c) \STATE{Afficher(c)} \ENDFOR FinPour \END Fin Pour avoir une version générale de la boucle Pour, on utilisera la commande \FORGEN Début \BEGIN Pour chaque expression e Faire \FORGEN{chaque expression $e$} \STATE{décoder $e$} décoder e \STATE{exécuter $e$} exécuter e \ENDFOR FinPour \END Fin Enfin il existe une version boucle PourChaque : Début \BEGIN \FOREACH[clef]{val}{montab} PourChaque clef(cid:66)val De montab Faire \STATE{Faire\_truc\_avec(clef,val)} Faire_truc_avec(clef,val) \ENDFOREACH FinPourChaque \END Fin ou plus simplement : Début \BEGIN \FOREACH{val}{montab} PourChaque val De montab Faire \STATE{Faire\_truc\_avec(val)} Faire_truc_avec(val) \ENDFOREACH FinPourChaque \END Fin 2.3.7 Contrôle de l’exécution Onpourraindiquerqu’onveutexplicitementarrêterledéroulementdel’algorithmeaveclacommande \EXIT produisant par défaut le mot clé Stop : Début \BEGIN Si Plus de mémoire Alors \IF{Plus de mémoire} \STATE{Afficher("Bon bé...")} Afficher("Bon bé...") \EXIT[Arrêt du programme] Stop { Arrêt du programme } \ENDIF FinSi \END Fin 8 Enfin, on pourra indiquer qu’on veut explicitement quitter le déroulement de la structure de contrôle itérative courante avec la commande \BREAK produisant par défaut le mot clé Quitter : Début \BEGIN Pour chaque bouteille B Faire \FORGEN{chaque bouteille B} Déboucher(B) \STATE{Déboucher(B)} \IF{Si B est bouchonné} Si Si B est bouchonné Alors \STATE{Contacter(révendeur)} Contacter(revendeur) \BREAK[sortie de la boucle Pour] Quitter { sortie de la boucle Pour } \ENDIF FinSi \ENDFOR FinPour \END Fin 2.4 Routines, procédures et autre fonctions Le package algo permet de construire une routine de la manière suivante : \FUNCTION{(cid:104)identificateur(cid:105)}{(cid:104)arguments(cid:105)}{ (cid:104)type renvoyé(cid:105)} S’il est nécessaire de faire explicitement la distinction entre procédure et fonction comme dans le langage Pascal, on pourra utiliser la syntaxe suivante : \PROC{(cid:104)identificateur(cid:105)}{(cid:104)arguments(cid:105)} pour une procédure, et pour une fonction : \FUNC{(cid:104)identificateur(cid:105)}{(cid:104)arguments(cid:105)}{(cid:104)type renvoyé(cid:105)} Où (cid:104)arguments(cid:105) pourra être un ou plusieurs appels aux commandes suivante : – \pfarg{(cid:104)id(cid:105)}{(cid:104)identificateur(cid:105)} pour un argument; – \pfargin{(cid:104)id(cid:105)}{(cid:104)identificateur(cid:105)} pour un argument de nature « donnée »; – \pfargout{(cid:104)id(cid:105)}{(cid:104)identificateur(cid:105)} pour un argument de nature « résultat »; – \pfarginout{(cid:104)id(cid:105)}{(cid:104)identificateur(cid:105)} pour un argument de nature « transformée ». ces commandes produiront le noms des arguments formels et leur type en respectant la cohérence de l’ensemble des algorithmes. Voici maintenant quelques exemples. \FUNCTION{message}{\pfarg{c}{chaine}}{} Routine message(c:chaine) \VAR Variable \DECLVAR{i}{entier} i:entier \ENDVAR Début \BEGIN Pour i variantDe 1 à 10 Faire \FOR{i}{1}{10} \STATE{Afficher("Message : ",c)} Afficher("Message : ",c) \ENDFOR FinPour \END Fin \FUNCTION{somme}{% Routine somme(x,y:entier):entier \pfarg{x,y}{entier}}{entier} Début \BEGIN Retourner x+y \RETURN{x+y} \END Fin 9 \PROC{pond}{ \pfargin{x,y}{entier} ; Procédure pond((cid:13)D x,y:entier;(cid:13)R s:flottant) \pfargout{s}{flottant}} Début \BEGIN s ← .3*x+.7*y \STATE{s \recoit{} .3*x+.7*y} Fin \END \FUNC{somme}{% Fonction somme(x,y:entier):entier \pfarg{x,y}{entier}}{entier} Début \BEGIN Retourner x+y \RETURN{x+y} \END Fin 2.5 Commentaires On peut insérer un commentaire dans le code grâce à la commande \COMMENT : \BEGIN Début \COMMENT{Début de l’algo} { Début de l’algo } \END Fin Certaines structures de contrôle prennent en paramètre optionnel un commentaire qui sera inséré sur la même ligne. Ces structures sont : \DECLVAR \DECLTYPE \DECLCONST \DECLFIELD \STATE \IF \ELSE \ELSEIF \FOR \WHILE \REPEAT \SWITCH \CASE \DEFAULT \FUNCTION \FUNC \PROC \RETURN \BREAK \EXIT Voici un exemple : \begin{algo} \VAR \DECLVAR[compteur]{i}{entier} \ENDVAR \BEGIN \COMMENT{une super boucle} \FOR[on compte jusqu’à 10]{i}{1}{10} \IF[test de parité]{i mod 2 = 0} \STATE[affichage à l’écran]{Afficher(i," pair")} \ELSE[là c’est impair] \STATE{Afficher(i," impair")} \ENDIF \ENDFOR \END \end{algo} qui donne : 10