Algorithmique

Langages informatiques

• Un langage informatique est un outil permettant de donner des ordres (instructions) à la machine.
• À chaque instruction correspond une action du processeur.
• Intérêt : écrire des programmes (suite consécutive d'instructions) destinés à effectuer une tâche donnée.
• Exemple : un programme de gestion de comptes bancaires.

Du langage machine aux langages évolués

• Problème : le langage machine est difficile à comprendre par l'humain.
• Idée : trouver un langage compréhensible par l'homme qui sera ensuite converti en langage machine.
• Assembleur (1er langage) : exprimer les instructions élémentaires de façon symbolique.

ADD A, 4
LOAD B
ADD A, B
…

• Inconvénients de l'assembleur :
  • Dépend du type de la machine (n'est pas portable).
  • Pas assez efficace pour développer des applications complexes.
  • ➜ Apparition des langages évolués.

Langage haut niveau

Intérêts multiples du haut niveau :

• Proche du langage humain (compréhensible).
• Permet une plus grande portabilité (indépendant du matériel).
• Manipulation de données et d'expressions complexes (réels, objets, a*b/c, …).
• Nécessite un traducteur (compilateur / interpréteur).

Algorithme

• Le terme algorithme vient du nom du mathématicien arabe Al-Khawarizmi (820 après J.-C.).
• Un algorithme est un ensemble d'actions (ou d'instructions) séquentielles et logiquement ordonnées, permettant de transformer des données d'entrée (Inputs) en données de sortie (Outputs), afin de résoudre un problème.
• Une fois l'algorithme écrit, il sera transformé — après le choix d'un langage de programmation — en un programme code source, qui sera compilé (traduit) et exécuté par l'ordinateur.

Compilation

Étapes de réalisation d'un programme

Données : Entrées / Sorties

Vue globale d'un algorithme

Structure d'un algorithme

Un algorithme (Données + Instructions) se compose de trois parties :

Modèle d'écriture d'un algorithme :

Algorithme <ident_Algo>
    <Déclarations>
Début
    <instructions>
Fin

Exemple :

Algorithme Max_Deux_Nbre
Variables A, B : entier
Début
    Lire(A)
    Lire(B)
    Si (B < A)
        Ecrire("A est plus grand que B")
    Sinon
        Ecrire("B est plus grand que A")
    Fin Si
Fin

Données : variables et constantes

Une donnée représente une information liée à un élément du problème traité par l'algorithme.

Données : Identificateur

Chaque donnée (variable ou constante) manipulée par un algorithme est désignée par un nom unique appelé IDENTIFICATEUR.

Règles générales (variant selon le langage) :

• Un nom doit commencer par une lettre alphabétique. Valide : A1 — Invalide : 1A
• Doit être constitué uniquement de lettres, chiffres et du soulignement _ (éviter ponctuation et espaces). Valides : E2019, E_2019 — Invalides : E 2019, E;2019
• Doit être différent des mots réservés du langage (ex. en Java/C : int, float, else, switch, case, for, main, return…).
• La longueur du nom doit être inférieure à la taille maximale spécifiée par le langage.

Types des variables

Le type d'une variable détermine l'ensemble des valeurs qu'elle peut prendre. Les types offerts par la plupart des langages :

• Type numérique (entier ou réel)
  • Byte (codé sur 1 octet) : de 0 à 255
  • Entier court (codé sur 2 octets) : −32 768 à 32 767
  • Entier long (codé sur 4 ou 8 octets)
  • Réel simple précision (codé sur 4 octets)
  • Réel double précision (codé sur 8 octets)
• Type logique ou booléen : deux valeurs VRAI ou FAUX.
• Type caractère : lettres majuscules, minuscules, chiffres, symboles… — ex. 'A', 'a', '1', '?'
• Type chaîne de caractères : toute suite de caractères — ex. "Nom, Prénom", "code postale: 1000"

Déclaration des variables

• Toute variable utilisée dans un programme doit avoir fait l'objet d'une déclaration préalable.
• Forme en pseudo-code :

Variables  liste d'identificateurs : type

Exemple :

Variables  i, j, k : entier
           x, y : réel
           OK : booléen
           ch1, ch2 : chaîne de caractères

Types d'instructions

• Pour les entrées → l'instruction de lecture.
• Pour les sorties → l'instruction d'écriture.
• Pour les traitements, plusieurs instructions :
  • L'instruction d'affectation
  • L'instruction de tests (conditionnelles)
  • Les instructions de boucles (de répétition)
  • Les instructions de sauts (ou de branchements)

Instructions d'entrées-sorties : lecture et écriture

Les instructions de lecture et d'écriture permettent à la machine de communiquer avec l'utilisateur.

Lecture — permet d'entrer des données à partir du clavier :

lire (var)

Écriture — permet d'afficher des résultats (valeur fixe, valeur d'une variable ou valeur calculée) à l'écran (ou de les écrire dans un fichier) :

écrire (var | val_fixe | expr)

Exemple 1 — double d'un nombre :

Algorithme Calcul_double
variables A, B : entier
Début
    écrire("entrer le nombre ")
    lire(A)
    B ← 2*A
    écrire("le double de ", A, " est :", B)
Fin

Exemple 2 — nom complet :

Algorithme AffichageNomComplet
variables Nom, Prenom, Nom_Complet : chaîne de caractères
Début
    écrire("entrez votre nom")
    lire(Nom)
    écrire("entrez votre prénom")
    lire(Prenom)
    Nom_Complet ← Nom & " " & Prenom
    écrire("Votre nom complet est : ", Nom_Complet)
Fin

Instruction d'affectation

• L'affectation consiste à attribuer une valeur à une variable (remplir ou modifier le contenu d'une zone mémoire).
• En pseudo-code, elle se note avec le signe ← :

Var ← X   // attribue la valeur de X à la variable Var

• X peut être une valeur, une autre variable ou une expression.
• Var et X doivent être de même type ou de types compatibles.
• L'affectation ne modifie que ce qui est à gauche de la flèche.

Exemples valides :

i ← 1        j ← i          k ← i+j
x ← 10.3     OK ← FAUX      ch1 ← "SMI"
ch2 ← ch1    x ← 4          x ← j

Exemples non valides :

i ← 10.3     OK ← "2AP"     j ← x

Exemple 1 — suivi des valeurs : donnez les valeurs de A, B et C après exécution.

Variables A, B, C : Entier
Début
    A ← 3
    B ← 7
    A ← B
    B ← A+5
    C ← A + B
    C ← B – A
Fin

Exemple 2 — échange ? donnez les valeurs de A et B après exécution. Ces deux dernières instructions permettent-elles d'échanger les valeurs ?

Variables A, B : Entier
Début
    A ← 1
    B ← 2
    A ← B
    B ← A
Fin

Exemple 3 : écrire un algorithme permettant d'échanger les valeurs de deux variables A et B.

Une expression peut être une valeur, une variable ou une opération constituée de variables reliées par des opérateurs. Exemples : 1, b, a*2, a + 3*b - c, …

L'évaluation de l'expression fournit une valeur unique qui est le résultat de l'opération. Les opérateurs dépendent du type de l'opération :

• Arithmétiques : +, -, *, /, % (modulo), ^ (puissance)
• Logiques : NON, OU, ET
• Relationnels : =, ≠, <, >, <=, >=
• Sur les chaînes : & (concaténation)

Une expression est évaluée de gauche à droite mais en tenant compte des priorités.

Priorités des opérateurs

Pour les opérateurs arithmétiques, du plus au moins prioritaire :

1. ^ (élévation à la puissance)
2. *, / (multiplication, division)
3. % (modulo)
4. +, - (addition, soustraction)

Exemple : 2 + 3 * 7 vaut 23. En cas de doute, utiliser les parenthèses : (2 + 3) * 7 vaut 35.

Tests

Les instructions conditionnelles servent à exécuter une instruction ou une séquence d'instructions seulement si une condition est vérifiée.

Forme complète :

Si condition alors
    instruction ou suite d'instructions1
Sinon
    instruction ou suite d'instructions2
Finsi

• La condition ne peut être que vraie ou fausse.
• Si la condition est vraie → instructions1 sont exécutées.
• Si la condition est fausse → instructions2 sont exécutées.
• La condition peut être simple ou composée de plusieurs conditions.

Forme simplifiée (la partie Sinon n'est pas obligatoire ; si la condition est fausse, aucun traitement n'est réalisé) :

Si condition alors
    instruction ou suite d'instructions1
Finsi

Exemple 1 — valeur absolue (avec Sinon) :

Algorithme AffichageValeurAbsolue
Variable x : réel
Début
    Ecrire("Entrez un réel : ")
    Lire(x)
    Si (x < 0) alors
        Ecrire("la valeur absolue de ", x, " est :", -x)
    Sinon
        Ecrire("la valeur absolue de ", x, " est :", x)
    Finsi
Fin

Exemple 2 — valeur absolue (variable intermédiaire) :

Algorithme AffichageValeurAbsolue
Variable x, y : réel
Début
    Ecrire("Entrez un réel : ")
    Lire(x)
    y ← x
    Si (x < 0) alors
        y ← -x
    Finsi
    Ecrire("la valeur absolue de ", x, " est :", y)
Fin

Exemple 3 — divisible par 3 :

Algorithme Divisible_par3
Variable n : entier
Début
    Ecrire("Entrez un entier : ")
    Lire(n)
    Si (n%3 = 0) alors
        Ecrire(n, " est divisible par 3")
    Sinon
        Ecrire(n, " n'est pas divisible par 3")
    Finsi
Fin

Conditions composées

Une condition composée est formée de plusieurs conditions simples reliées par des opérateurs logiques : NON, ET, OU, XOR (OU exclusif).

Exemples :

• X compris entre 2 et 6 : (X > 2) ET (X < 6)
• N divisible par 3 ou par 2 : (N%3 = 0) OU (N%2 = 0)
• Une des deux valeurs (A ou B) qui vaut C : (A = C) XOR (B = C)

Tables de vérité :

Tests imbriqués

Les tests peuvent avoir plusieurs niveaux d'imbrication :

Si condition 1 alors
    Si condition 2 alors
        instructions A
    Sinon
        instructions B
    Finsi
Sinon
    Si condition 3 alors
        instructions C
    Finsi
Finsi

Exemple 1 — négatif / positif / nul (version 1, imbriquée) :

Algorithme Test_Nombre
Variable n : entier
Début
    Ecrire("entrez un nombre : ")
    Lire(n)
    Si (n < 0) alors
        Ecrire("Ce nombre est négatif")
    Sinon
        Si (n = 0) alors
            Ecrire("Ce nombre est nul")
        Sinon
            Ecrire("Ce nombre est positif")
        Finsi
    Finsi
Fin

Exemple 1 — version 2 (tests indépendants) :

Algorithme Test_Nombre
Variable n : entier
Début
    Ecrire("entrez un nombre : ")
    Lire(n)
    Si (n < 0) alors
        Ecrire("Ce nombre est négatif")
    Finsi
    Si (n = 0) alors
        Ecrire("Ce nombre est nul")
    Finsi
    Si (n > 0) alors
        Ecrire("Ce nombre est positif")
    Finsi
Fin

Dans certaines situations, on est amené à répéter l'exécution d'une ou plusieurs instructions.

Algorithme Exemple1
Début
    Ecrire(1)
    Ecrire(2)
    Ecrire(3)
    Ecrire(4)
    Ecrire(5)
Fin

Comment écrire un algorithme qui affiche les nombres de 1 à 10000 ? ➜ Les boucles. Elles servent à répéter l'exécution d'un groupe d'instructions un certain nombre de fois. On distingue trois sortes de boucles :

• Tant que : on répète des instructions tant qu'une certaine condition est réalisée.
• Répéter … jusqu'à : on répète des instructions jusqu'à ce qu'une certaine condition soit réalisée.
• Pour (avec compteur) : on répète des instructions en faisant évoluer un compteur entre une valeur initiale et une valeur finale.

Les boucles Pour

L'instruction Pour répète l'exécution d'un bloc d'instructions. Elle utilise un compteur d'itération, une valeur initiale et une valeur finale ; le compteur est incrémenté automatiquement.

Pour compteur allant de initiale à finale Faire
    instructions
FinPour

Fonctionnement :

1. La valeur initiale est affectée au compteur.
2. On compare le compteur et la valeur finale :
   • a) Si compteur > finale (pas positif) — ou compteur < finale (pas négatif) — on sort de la boucle et on continue après FinPour.
   • b) Sinon les instructions sont exécutées :
     • i. Le compteur est incrémenté du pas (ou décrémenté si pas négatif).
     • ii. On recommence l'étape 2.

Exemple — x à la puissance n :

Variables x, puissance : réel
          n, i : entier
Début
    Ecrire("Entrez la valeur de x ")
    Lire(x)
    Ecrire("Entrez la valeur de n ")
    Lire(n)
    puissance ← 1
    Pour i allant de 1 à n Faire
        puissance ← puissance*x
    FinPour
    Ecrire(x, " à la puissance ", n, " est égal à ", puissance)
Fin

Exemple — version 2 (pas négatif) :

Variables x, puissance : réel
          n, i : entier
Début
    Ecrire("Entrez respectivement les valeurs de x et n")
    Lire(x, n)
    puissance ← 1
    Pour i allant de n à 1 Faire
        puissance ← puissance*x
    FinPour
    Ecrire(x, " à la puissance ", n, " est égal à ", puissance)
Fin

Pour i allant de 1 à 5 Faire
    i ← i -1
    écrire(" i = ", i)
FinPour

Boucles Pour imbriquées :

Pour i allant de 1 à 5 Faire
    Pour j allant de 1 à i
        écrire("O")
    FinPour
    écrire("X")
FinPour

Exécution :

OX
OOX
OOOX
OOOOX
OOOOOX

Les boucles Tant que

TantQue (condition)
    instructions
FinTantQue

• La condition (condition de contrôle) est évaluée avant chaque itération.
• Si vraie → on exécute les instructions, puis on retourne tester la condition, etc.
• Si fausse → on sort de la boucle et on exécute l'instruction qui suit FinTantQue.

i ← 4
TantQue (i > 0) Faire
    i ← i+1   // Erreur : + au lieu de - → boucle infinie
FinTantQue

Exemple (version 1) — premier N tel que la somme 1..N dépasse strictement 100 :

Algorithme Somme_Entier_100
Variables som, i : entier
Début
    i ← 0
    som ← 0
    TantQue (som <= 100) Faire
        i ← i+1
        som ← som+i
    FinTantQue
    Ecrire("La valeur cherchée est N= ", i)
Fin

Cas d'utilisation de TantQue :

• Dans tous les cas où la boucle Pour s'applique, on peut utiliser TantQue.
• Quand la boucle dépend d'une condition compliquée (expression booléenne avec opérateurs logiques, ex. a <> 0 et b <= n).
• Il faut s'assurer de l'initialisation de la condition et qu'une instruction rend la condition fausse après un certain nombre d'itérations.

Relation entre Pour et TantQue : la boucle Pour est un cas particulier de TantQue (nombre d'itérations connu et fixé). Tout ce qui s'écrit avec Pour peut être remplacé par TantQue (la réciproque est fausse).

Pour compteur allant de initiale à finale par pas valeur du pas
    instructions;
FinPour

équivaut à :

compteur ← initiale
TantQue compteur <= finale
    instructions
    compteur ← compteur + pas
FinTantQue

Exemple — x à la puissance n (version TantQue) :

Variables x, puiss : réel
          n, i : entier
Début
    Ecrire("Entrez la valeur de x ")
    Lire(x)
    Ecrire("Entrez la valeur de n ")
    Lire(n)
    puiss ← 1
    i ← 1
    TantQue (i <= n)
        puiss ← puiss*x
        i ← i+1
    FinTantQue
    Ecrire(x, " à la puissance ", n, " est égal à ", puiss)
Fin

Les boucles Répéter … Jusqu'à

Répéter
    instructions
Jusqu'à condition

À chaque itération, une expression booléenne (condition) est réévaluée :

• Si l'expression est vraie → on arrête la boucle et on exécute l'instruction qui vient après.
• Si l'expression est fausse → on continue la boucle (itération suivante).

Exemple — premier N tel que la somme 1..N dépasse strictement 100 (version Répéter) :

Variables som, i : entier
Début
    som ← 0
    i ← 0
    Répéter
        i ← i+1
        som ← som+i
    Jusqu'à (som > 100)
    Ecrire("La valeur cherchée est N= ", i)
Fin

Utilisation de Répéter :

• Dans tous les cas où la boucle Pour s'applique, on peut utiliser Répéter.
• Quand la boucle dépend d'une condition compliquée (ex. a <> 0 et b <= n).
• En général, si la première itération est réalisée sans condition, on peut utiliser Répéter au lieu de TantQue.

Choix d'un type de boucle

• Si le nombre d'itérations est connu avant l'exécution → boucle Pour.
• Si le nombre d'itérations n'est pas connu → TantQue ou Répéter … Jusqu'à.
• Entre TantQue et Répéter :
  • Tester la condition avant de commencer les instructions → TantQue.
  • La condition dépend d'une première exécution des instructions → Répéter … Jusqu'à.

Structure conditionnelle à choix multiples

Le Si … alors … sinon … Fsi permet deux choix. Pour plusieurs choix, on utilise des si-alors-sinon imbriqués ; certains langages offrent une solution plus simple :

Variable Note : entier
Lire(Note)
Cas Note vaut
    Note > 16 : Ecrire « très bien »
    Note > 14 : Ecrire « bien »
    Note > 12 : Ecrire « Assez bien »
    Note > 10 : Ecrire « passable »
    Sinon     : Ecrire « ajourné »
Fin cas

Exemple — afficher la saison à partir du numéro du mois :

Algorithme Saison;
Var M : entier;
Début
    Ecrire('Donner un numéro de mois 1--12');
    Répéter
        Lire(M);
    Jusqu'à (M > 0 et M < 13);
    Cas M Vaut
        3,4,5    : Ecrire('La saison est : PRINTEMPS');
        6,7,8    : Ecrire('La saison est : ETE');
        9,10,11  : Ecrire('La saison est : AUTOMNE');
        12,1,2   : Ecrire('La saison est : HIVER');
    FinCas;
Fin.

Exemple introductif

Pour conserver les notes d'une classe de 200 étudiants et extraire des informations (ex. nombre d'étudiants ayant une note > 10), le seul moyen sans tableau serait de déclarer 200 variables (N1, …, N200), avec 200 instructions lire puis 200 instructions Si :

nbre ← 0
Si (N1 > 10) alors nbre ← nbre+1 FinSi
…
Si (N200 > 10) alors nbre ← nbre+1 FinSi

➜ C'est lourd à écrire ! Les langages offrent une structure de donnée unique appelée Tableau.

Définition

• Un tableau permet d'allouer (réserver) un espace mémoire (dans la RAM) pour stocker N valeurs de même type.
• Un tableau est un ensemble de variables ; chaque variable représente un élément du tableau.
• Ces éléments (cases) sont accessibles par un (ou plusieurs) indice(s).
• Un indice indique la position d'un élément et permet de déterminer sa valeur.

Tableaux à une dimension — Syntaxe et sémantique

La déclaration précise le type des éléments et la dimension (nombre d'éléments) :

variables tableau identificateur[dimension] : type

Exemple :

variables tableau notes[200] : réel

On peut définir des tableaux de tous types : entiers, réels, caractères, booléens, chaînes de caractères.

Exemple — nombre d'étudiants ayant une note > 10 :

Programme Note_superieure_a_10
Variables i, nbre : entier
          tableau notes[200] : réel
Début
    nbre ← 0
    Pour i allant de 1 à 200
        Si (notes[i] > 10) alors
            nbre ← nbre+1
        FinSi
    FinPour
    écrire("le nombre des notes supérieures à 10 est : ", nbre)
Fin

Tableaux à une dimension — Lecture et Écriture

Lecture :

Lire(n)
Pour i allant de 1 à n faire
    Lire(T[i])
FinPour

Écriture :

Pour i allant de 1 à n faire
    Ecrire(T[i])
FinPour

Exemple :

Algorithme Tableau_lecture_ecriture
Variables Tableau T[50] : réel
          n, i : entier
Début
    Lire(n)
    Pour i allant de 1 à n faire
        Lire(T[i])
    FinPour
    Pour i allant de 1 à n faire
        Ecrire(T[i])
    FinPour

Avec la fonction longueur : certains langages offrent une fonction longueur qui donne la dimension du tableau.

Algorithme Tableau_lecture_ecriture
Variables Tableau T[50] : réel
          i : entier
Début
    Pour i allant de 1 à longueur(T) faire
        Lire(T[i])
    FinPour
    Pour i allant de 1 à longueur(T) faire
        Ecrire(T[i])
    FinPour

Tableaux à une dimension — Problèmes classiques

• La recherche d'un élément dans un tableau.
• La somme et produit cartésien de deux vecteurs.
• Somme et moyenne des éléments d'un tableau.
• Inverser les éléments d'un tableau (résultat dans un autre tableau ou dans le même).
• Recherche de l'élément minimum (et/ou maximum) et de sa position (indice).
• Trier les éléments d'un tableau (ordre croissant ou décroissant).
• Ajouter une même valeur à tous les éléments d'un vecteur.

Tableaux à deux dimensions — Syntaxe et sémantique

Les valeurs sont repérées par deux indices (utile pour les matrices) :

variables tableau identificateur[dimension1][dimension2] : type

Exemple : matrice A de 3 lignes et 4 colonnes, éléments réels :

variables tableau A[3][4] : réel

A[i][j] accède à l'élément situé à l'intersection de la ligne i et de la colonne j.

Lecture d'une matrice :

lire(n)
Lire(m)
Pour i allant de 1 à n faire
    Pour j allant de 1 à m faire
        lire(A[i][j])
    FinPour
FinPour

Écriture d'une matrice :

Pour i allant de 1 à n faire
    Pour j allant de 1 à m faire
        écrire("A[", i, "][", j, "]=", A[i][j])
    FinPour
FinPour

Exemple — somme de deux matrices :

Algorithme Somme2Matrice
Variables tableau A[10][10] : réel
          tableau B[10][10] : réel
          tableau C[10][10] : réel
          i, j, n, m : entier
Début
    lire(n, m)
    Pour i allant de 1 à n faire
        Pour j allant de 1 à m faire
            C[i][j] ← A[i][j] + B[i][j]
        FinPour
    FinPour
Fin

Tableaux à deux dimensions — Problèmes classiques

• Recherche d'une valeur dans une matrice.
• Somme et moyenne des éléments d'une matrice.
• Somme et moyenne de chaque ligne et/ou de chaque colonne.
• Somme et moyenne de la ligne N° i (ou de la colonne N° j).
• Recherche de l'élément minimum (et/ou maximum) et de ses positions (indices de ligne et de colonne).
• Tri d'une matrice (ordre croissant ou décroissant).
• Somme et produit de deux matrices réelles.
• Ajouter une même valeur à tous les éléments d'une matrice.

Algorithme de recherche

Recherche séquentielle : consulter les éléments de la liste et les comparer un à un avec l'élément recherché, du début jusqu'à trouver l'élément ou atteindre la fin de la liste (réalisée à l'aide d'une structure itérative). Exemples : recherche d'un nom dans une liste de noms ; recherche d'un nombre dans une liste de nombres.

Recherche de la valeur x dans un tableau T de N éléments :

Variables x, i : entier, Trouvé : booléen
Début
    i ← 1
    Trouvé ← Faux
    TantQue ((i <= N) ET (Trouvé = Faux))
        Si (T[i] = x) alors
            Trouvé ← Vrai
        FinSi
        i ← i+1
    FinTantQue
    Si (Trouvé = vrai) alors
        écrire("x appartient au tableau")
    Sinon
        écrire("x n'appartient pas au tableau")
    FinSi
Fin

Version fonction (retourne un booléen indiquant si x appartient au tableau T de dimension N ; x, N et T sont des paramètres) :

Fonction Recherche(x : réel, N : entier, tableau T : réel) : booléen
Variable i : entier
    Pour i allant de 0 à N-1
        Si (T[i] = x) alors
            retourne (Vrai)
        FinSi
    FinPour
    retourne (Faux)
FinFonction

Exemple introductif

Calcul du coefficient binomial : Cⁿₖ = n! / (k! * (n-k)!)

Algorithme Calcule_Combinaison
Variables n, k, c : entier
          nf, kf, nkf : entier
Début
    // Entrées
    Lire(n, k)
    // Traitement
    {trt 1}  → Calculer n!
    {trt 2}  → Calculer k!
    {trt 3}  → Calculer (n-k)!
    c ← nf/(kf*nkf)
    // Sorties
    Ecrire(c)
Fin

Détail des trois traitements (presque identiques) :

{Calculer n!}
nf ← 1
Pour i allant de 2 à n faire
    nf ← nf*i
Fin Pour

{Calculer k!}
kf ← 1
Pour i allant de 2 à k faire
    kf ← kf*i
Fin Pour

{Calculer (n-k)!}
nkf ← 1
Pour i allant de 2 à (n-k) faire
    nkf ← nkf*i
Fin Pour

Sous-Programme

Un sous-programme est une séquence d'instructions qui possède un nom unique (identificateur). Intérêts :

• Permet de factoriser les programmes (mettre en commun les parties répétées).
• Permet une structuration et une meilleure lisibilité.
• Facilite la maintenance (une seule modification suffit).
• Peut éventuellement être réutilisé dans d'autres programmes.

Structure du programme principal :

Structure d'un sous-programme :

Appel à un sous-programme

Fonctions — Déclaration

Le rôle d'une fonction en programmation est similaire à celui d'une fonction mathématique : elle retourne un résultat à partir des valeurs des paramètres. Une fonction s'écrit en dehors du programme principal :

Fonction nom_fonction (paramètres et leurs types) : type_fonction
    Instructions constituant le corps de la fonction
    retourne …
FinFonction

• Le choix d'un nom de fonction respecte les mêmes règles que les noms de variables.
• type_fonction est le type du résultat retourné.
• L'instruction retourne sert à retourner la valeur du résultat.

Appel à une fonction

L'appel se fait dans le programme principal ou dans une autre fonction, par une instruction indiquant le nom de la fonction.

Déclaration — paramètres formels :

Fonction exemple_fct (p1:type, p2:type, …, pn:type) : typeFonction
    …
FinFonction

Appel — paramètres effectifs :

Algorithme exempleAppelFonction
Début
    exemple_fct (vp1, vp2, …, vpn)
    …
Fin

Fonctions — Remarques

• Éviter d'utiliser les données globales (variables/constantes) dans une fonction ➜ la fonction doit être autonome.
• Utiliser uniquement les paramètres pour communiquer avec une fonction.
• Éviter de faire les lectures (et éventuellement les écritures) à l'intérieur d'une fonction.

Fonctions — Exemples

Somme des carrés de deux réels :

Fonction SommeCarre (x : réel, y : réel) : réel
Variable z : réel
    z ← x^2 + y^2
    retourne (z)
FinFonction

Tester si un nombre est pair :

Fonction Pair (n : entier) : booléen
    retourne (n%2 = 0)
FinFonction

Utilisation : le nom de la fonction s'écrit dans le programme principal ; le résultat (une valeur) doit être affecté ou utilisé dans une expression, une écriture, etc.

Algorithme AppelFonction
variables z : réel, b : booléen
Début
    b ← Pair(3)
    z ← 5*SommeCarre(7,2) + 1
    écrire("SommeCarre(3,5)= ", SommeCarre(3,5))
Fin