Algorithme: Définition et Langage

• Objet : Rappel des définitions et de la syntaxe du langage algorithmique
• Niveau requis :

  débutant, avisé
• Commentaires : Contexte d'utilisation du sujet du tuto.
• Débutant, à savoir : Utiliser GNU/Linux en ligne de commande, tout commence là !.

Quelques éléments du langage algorithmique.

On utilise

• caractères A…Z ; a…z ;
• les chiffres 0 1 2 3 … ;
• des signes _ = < > ' " ( ) [ ] + - * / , : . <espace> ;
• les identificateurs : ce sont les noms donnés aux différents objets déclarés dans un algorithme.
  Ils peuvent être fait d'une suite de longueur quelconque de chiffres de lettre (min, maj) de soulignés.
• les commentaires : **//**explications sur les identificateurs, sur les étapes du programme d'algo

Il y a quatre sortes d'objets : les constantes, les variables, les fonctions et les procédures.

• Syntaxe de déclaration d'une constante :

nom_constante = valeur_de_la_constante  // On commente toujours le nom d'une constante.

• Exemple :

CONSTANTE
taille = '.' // caractère de terminateur

Une variable est un emplacement mémoire qui change de valeur au cours d'un programme ou d'un d'un algorithme.

• Syntaxe de déclaration d'une variable

nom_variable :type

• Exemple :

Nbjeunes :entier // Nombre de jeunes interrogés

• Affectation d'une variable

Elle n'est possible que s'il y a eu déclaration de la variable.

On note le signe d'affectation :=.

variable i : entier // déclaration
...
i := 3 // affectation de i par la valeur 3 
 
i := i + 1 // incrémentation de 1 
...
 
i := 4 * i // i est multiplié par 4 
 
...

Fonction et procédure réalisent un travail, par exemple un calcul, et ne font rien d'autre que ce travail.

Elles sont utilisée par des programmes qui les appelle, et qui font d'autre chose, par exemple afficher le résultat calculé par une procédure ou une fonction.

Comparons une fonction et une procédure qui toute deux calculent le cube d'un nombre ; puis comment un programme utilise l'une ou l'autre.

Voir la structure générale d'un algorithme

• Explication :

On imagine un tableau où on place 2, le nombre dont calcule la puissance de 3 ;
L'indice maximal de ce tableau est la puissance à laquelle on veut élever le nombre 2.

Pour i de 1 à 3 on fait :

   |   2   |   2   |    2   |
       |       |        |
    1 * 2      |        |
    = 2        |        |
             2 * 2      | 
             = 4        |
                      4 * 2
                      = 8

• Déclaration et mise en place de la fonction

Fonction fctcube (entrée x : entier):entier
  //cette fonction calcul la puissance trois d'un nombre
  // x est le nombre
  // la fonction retourne le cube du nombre

CONSTANTES

constante puissance = 3

VARIABLES

variable i : entier //comptage des puissances
variable y : entier // calcul intermédiaire


 début

   i := 1
   y := 1
  
      Tantque (i := puissance) FAIRE
    
        y := y * x
        i := i + 1
      FinTantque
    
   retourner (y)
 Fin
 fin

//Programme cube
// Programme qui calcule le cube d'un nombre et affiche le résultat

VARIABLES

nombre : entier // nombre à élever au cube

FONCTIONS

fonction fctcube (entrée x : entier):entier

  // cette procédure calcule le cube du nombre x et retourne le résultat

  Début
  
     lire(nombre)
     écrire ('le résultat est : ', fctcube(nombre))  // Appel de la fonction, elle rend la résultat qu'on affiche avec écrire
     
            // utilisation du résultat
  Fin

La différence avec un programme est l'en-tête.

procédure proccube (entrée x : entier, sortie y : entier)

  // Cette procédure calcule la puissance trois d'un nombre.
  
CONSTANTES

constante puissance = 3

VARIABLES

variable i :entier // comptage des puissances

   Début
   
        i := 1
        j := 1
           
           Tantque (i := puissance) FAIRE
           
              y := y * x
              i := i + 1
           FinTanque      
  
   Fin

// Programme qui calcule le cube d'un nombre

VARIABLES
 variable nombre :entier //nombre à élever au cube
 variable resultat :entier // cube du nombre

PROCEDURES

procédure proccube (entrée x : entier , sortie y : entier)
      //Cette procédure calcule le cube du nombre x et met le résultat dans y

  Début
   lire(nombre)
   
   proccube (nombre, resultat) // calcul du cube de nombre
   
   écrire('Le résultat est : ', résultat)
         // affichage du résultat du calcul
  
  Fin

Voir ci-dessous la structure en sous programme d'un algorithme complexe: algo-exo-constructions-d-algorithmes-de-procedure

Voir aussi : d'autres exemples simples d'algorithme de fonctions et de procédures : http://www.est-usmba.ac.ma/ALGORITHME/co/module_ALGORITHME_40.html

Il y a quatre types prédéfinis : entiers ; réels ; booléens ; caractères.
Les tableaux sont des types de variables créés.

• Les entiers ne sont pas limités par leur taille.
  

• Les constantes entières sont toujours en base 10.
  

Ils ont pour opérandes deux entiers et donnent un résultat booléen.

Ils ont pour opérandes deux entiers et donnent un résultat entier

238.45    420.0

Le résultat de la comparaison est un booléen.

Ce sont tous les caractères imprimables de la tables ASCII ; 'a' et 'A' sont deux caractères différents.

On distingue '2' en tant que caractère et en tant qu'entier.

On n'utilise que les opérateurs de comparaison ; ils sont ordonnés selon la tables ASCII.

Voir : http://fr.wikipedia.org/wiki/American_Standard_Code_for_Information_Interchange

• Deux valeurs possibles : VRAI FAUX
  

Le résultat d'une comparaison est soit VRAI soit FAUSSE : le résultat d'une comparaison est toujours un booléen.

...
i := entier 
bool : booléen // Déclaration d'une variable de type booléen
...
 
  SI (i > 5 ) ALORS
      bool := VRAI
   SINON
      bool := FAUX
  FINSI

bool := (i > 5)

Trois opérations nous intéresse : NON ET OU (du plus prioritaire au moins prioritaire).

Voir : algèbre de bool surtout la loi de Morgan.

• Déclaration et affectation

type // On annonce qu'on crée un nouveau type de variable.
blabla = tableau[n] d'un type_pré-défini

• Mettre (affecter) la valeur d'un indice (n° de case du tableau) dans une variable (cible) :

cible := nom_tableau[i]
  |          
 nom_variable <- valeur de tab[i]

• Mettre la valeur d'une variable (cible) dans une case de tableau (cible) :

nom_tableau[i] := cible
      | 
 case tableau   <- valeur de variable

• Vérifier une condition :

SI nom_tableau[i] = cible ALORS ...
      |               |
  valeur case        valeur de variable

SI nom_tableau[i] = nom_tableau[i + 1] ALORS ...
          |                      |
    valeur de case        valeur de case + 1

• Exemples 1:

Type
nombres : tableau[35] d'entiers

• Exemple 2 :

Type
tab : tableau[35] d'entiers 

lire(tab[2])
// enregistre en mémoire la valeur de la case 2 du tableau "tab".

écrire(tab[5])
// afficher à l'écran la valeur de la case 5 du tableau "tab".

...
variables  i: entier
           j: entier
           matcarré : matrice
 
  ...
matcarré [i][j] := 2 // matcarré est de type matrice
                     // matcarré[i] est de type tabent
                     // matcarré [i][j] est de type entier

Doc sur tableau :

• http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=6&ved=0CEAQFjAF&url=http%3A%2F%2F2igc.cours.free.fr%2Ftsttig%2F002I_Algo%2F02I_Algo02.doc&ei=1Lt6VLGUBIjdau32gbgG&usg=AFQjCNGBy4qN30W1FEHReM5fNcAHhdcQnQ&sig2=CYelZWE8ytMAn1tvjP7MRw&bvm=bv.80642063,d.d2s

Il s'agit des instructions et des outils d'entrée et de sortie.

• Syntaxe :

 SI <condition>  ALORS

    < instruction 1 >
          ...
    < instruction n >

 FinSI

Exemple :

variable i : entier //déclaration d'un variable nommée i
 
  SI i > 4 ALORS
 
      i := i - 1
 
  SINON
 
      i := i + 1
 
  FinSI    
 

• Syntaxe :

 CHOIX sur < variable > FAIRE

    < valeur 1 > :    <instruction1 1>
                      <instruction1 2>
                       ...
                      <instruction1 n(1)>

     < valeur M > :   <instructionM 1>
                      <instructionM 2>
                       ...                
                      <instructionM n(M)>
    
     AutreCas     :   <instruction (M+1) 1>
                       ...
                      <instruction (M+1) n(M+1)>

 FinCHOIX

AutreCas est obligatoire, même dans le cas où il n'y en a pas.

• Exemple :

variable i :entier
...
CHOIX sur i faire 
 
     1 : écrire(c'est bien)
     2 : écrire(c'est très bien)
     3 : écrire(c'est très nul)
 
     AutreCas : écrire('Les moyens') //cas tous regroupables
 
FinCHOIX 

age : entier //"age" c'est le nom de la variable
lire(age)    // 

écrire(blabla)    // 

age : entier
age := 25
écrire('La valeur de la variable age est :', age 'encore du texte si on veut.')    // 

Instruction exécutée par la boucle tant que la condition est remplie ; il faut une condition d'arrêt.

La boucle est toujours exécutée au moins une fois.

• Syntaxe :

  TantQue < condition > FAIRE   // condition de continuation
  
          < instruction1 >
          < instruction2 >
          ...
  FinTQ

• Exemple :

variable i : entier
i := 1
  TantQue ( i < 3 ) FAIRE   // La boucle s'arrêtera quand i sera >= à 3.
                            // On met dans le commentaire la condition contraire 
                            // c'est-à-dire la condition de terminaison.
 
     i := i + 1   // incrémentation
     écrire ('coucou')    // Tant que i < 3 il s'affiche "coucou" à l'écran.
 
  FinTQ
 
  écrire('la variable i est égale à ', i) // 

coucou
coucou
la variable i est égale à 3

Elle permet d'exécuter une instruction jusqu'à ce qu'une condition soit remplie.

Attention si la condition n'est jamais remplie, l'instruction n'est jamais exécutée, car la conditiion est placée après l'instruction !

• Syntaxe :

  Répéter 
        < instruction 1>
        < instruction n>
  Jusqu'à < condition >     // C'est une condition d'arrêt. 

• Exemple :

variable i : entier
i := 1
  Répéter 
        i := i + 1
        écrire('coucou')
  Jusqu'à ( i >= 3 )    // être égal à 3 est une condition d'arrêt.
écrire('la variable i est égale à ', i)

coucou
coucou
la variable i est égale à 3

ATTENTION la boucle s'effectue toujours une fois

répéter
 Afficher "Saisir un nombre strictement positif "
 Saisir i
 Si i (<= 0) alors 
  écrire("J'ai dit STRICTEMENT POSITIF !")
 Sinon 
  écrire("Bravo") 
 Finsi
jusqu'à i > 0

Un algorithme écrit d'un seul tenant devient difficile à comprendre et à gérer dès qu'il dépasse deux pages.

La solution consiste alors à découper l'algorithme en plusieurs parties plus petites. Ces parties sont appelées des sous-algorithmes.

Voici le schéma de l'algorithme d'un programme complexe, l'algorithme principal (P0) appelle les algorithmes de sous-programmes (P1, P2, P3), qui eux-mêmes en appellent d'autres … :

           __________| P0 |____________
          |            |               |
          |          _____             |
        | P1 |      | P2 |          | P3 |
          |                            |
 ____________________       ______________________
 |P11|        | P12 |       | P21|            P22 |

  

Le sous-algorithme est écrit séparément du corps de l'algorithme principal et sera appelé par celui-ci quand ceci sera nécessaire.

Les différentes parties d'un algorithme (sous-algorithmes) sont appelées des blocs.

Il existe deux sortes de sous-algorithmes : les procédures et les fonctions.

Quelque soit le niveau où l'on se trouve dans l'arborescence, tous les blocs, y compris l'algorithme du programme principal, se déclare comme ceci :

Interface de bloc // nom du programme, de la procédure ou de la fonction.
// Commentaire sur le rôle du bloc

CONSTANTE // On définit les constantes.

TYPES     // Définitions des types du bloc

VARIABLES // Définitions des variables

PROCEDURES ... // Définitions des sous-procédures appelées par le bloc, ce bloc
               // est alors un algorithme plus globale 

FONCTIONS ... // Définitions des fonctions appelées par le bloc


// Définition des actions du bloc

  Début
  
      actions // actions effectuées lors de l'activation du bloc
  
  Fin

Une procédure est une boîte (un petit algorithme) qu'on insère dans un programme ( gros algorithme) et à laquelle on donne les paramètres du programme. Ses paramètres sont appelés paramètres formels. Leurs valeurs ne sont pas connus lors de la création de la procédure.

Dans un programme principal qui utilise une procédure, on n'aura pas à expliquer comment fonctionne la procédure utilisée, mais seulement ce à quoi elle sert dans ce programme, et ce qu'on lui donne en paramètre dans ce programme. Dans le programme les paramètres passés à la procédure sont réels ; ils sont appelés paramètres effectifs.

• Syntaxe :

 Procédure nom_proc(entrée nom_parmètre1_formel : typeDuParamètre
                           nom_paramètre2_formel : typeDuParamètre
                    entrée sortie nom_paramètre1 : typeDuParamètre
                    sortie nom_paramètre1_formel : typeDuParamètre)

Cela est copier de l'étape n°4 de la présentation (algo-la-presentation-d-une-procedure

Une procédure est une série d'instructions regroupées sous un nom, qui permet d'effectuer des actions par un simple appel de la procédure dans un algorithme ou dans un autre sous-algorithme.

• On y trouve

1. la déclaration ;
2. ces composants (constantes, type_créé , variables) ;
3. le programme qui permet à cette procédure de fonctionné

Pour déclencher l'exécution d'une procédure dans un programme, il suffit de l'appeler. L'appel de procédure s'écrit en mettant le nom de la procédure, puis la liste des paramètres, séparés par des virgules. A l'appel d'une procédure, le programme interrompt son déroulement normal, exécute les instructions de la procédure, puis retourne au programme appelant et exécute l'instruction suivante.

...
Nom_procédure(liste de paramètres)
...

Donnez l'algorithme qui affiche un carré d'étoile à l'écran.

// Algorithme carréEtoile                              |
// Algorithme qui affiche un carré de 15 lignes         
// et de 15 colonnes                                    
                                                       
                                                        
Variables j : entier // nombre d'étoile sur une ligne   
Procédure Etoile ( ) // pas de paramètre                
                     //Procédure qui affiche une              
                     // ligne de 15 étoiles.                       
 DébutAlgo                                                      
       Pour j DE 1 à 15 FAIRE                                 
            // appel de la procédure   --------------->| Etoile(entrée i : entier , sortie i :entier)   
           Etoile( )                                   |  // Procédure qui affiche une ligne d'étoile
                                                       |  // Et qui va à la ligneFinProc
       FinPour                                         | 
 FinAlgo                                               | 
                                                       | Variables i :entier
                                                       |   DébutProc
                                                       |       Pour i DE 1 à 15
                                                       |          ecrire("*")
                                                       |       FinPour
                                                       |       ecrire("\n")
                                                       |   FinProc

                + 
 entrée     |       | sortie 
variables   |       | c = 3
a = 1 
b = 2

               entrée sortie   
          |                       |  
          | modifier une variable | 
          |  qui est donnée       |
          | en entrée et qui sort |
          | avec une autre valeur |