Algorithmes - Guide Complet

Algorithmique

#

Un algorithme sert à décrire de manière intelligible les étapes nécessaires à la réalisation d’un travail. Il permet d’expliquer clairement les idées de solution à un problème, indépendamment de tout langage de programmation. Grâce à l’algorithme, le développeur peut suivre les étapes définies dans un ordre précis afin d’atteindre le résultat attendu.

Il doit être :

• Compréhensible par une personne humaine
• Suffisamment précise pour être traduit dans un langage de programmation

Principes de base

#

Un algorithme est un compromis entre « langage naturel » et « langage informatique », présentant les étapes nécessaires à la résolution dʼun problème clairement exposé.

Structure générale

#

Entête

#

L’entête décrit les informations générales de l’algorithme et contient des informations telles que :

• Nom de l’algorithme : titre de lʼalgorithme (par exemple: « Calculer la moyenne »)
• Objectif : Description claire du but de lʼalgorithme (par exemple: « Calculer la moyenne des notes dʼun examen »)
• Données : les données connues de lʼalgorithme
• Résultat : ce que lʼalgorithme doit produire en résultat
• Principe : Principe(s) utilisé(s) dans lʼalgorithme

Corps de lʼalgorithme

#

Un corps, lʼalgorithme lui-même, est lʼensemble dʼopérations fini nécessaire à lʼobtention du résultat énoncé. Le corps est délimité par les mots réservés : Début … Fin

Exemple

#

Algorithme : AdditionEntiers
Rôle : Additionner deux entiers et conserver le résultat
Données : deux entiers connus
Résultat : Stockage de la somme des deux valeurs entières
Début
VAR resultat : ENTIER
resultat ← 5 + 3
Fin

Dans cet exemple, on utilise deux valeurs définies (5 et 3) pour réaliser lʼopération.

Variables et constantes

#

Definition dʼune variable

#

Une variable est une « étiquette» destinée à identifier un espace dans la mémoire de la machine. Dans cet espace, on pourra y stocker une information “variable” dans le temps.

On la définit avec :

• Le mot réservé : VAR
• Un nom (identifiant de la variable)
• Un type : lʼensemble des valeurs acceptées par la variable définie (Entier, Réel, Chaine, Caractère, Booléen, …)
• Et, optionnellement, une valeur : une valeur qui sera stockée dans la mémoire du dispositif exécutant le code final

On définit une variable lorsque notre algorithme impose de conserver ET modifier une information tout au long des diverses opérations.

Lʼespace mémoire qui est alloué à cette variable est donc accessible aussi bien :

• En lecture
• En écriture

VAR ma_variable: ENTIER // Définition de l’espace en mémoire
ma_variable <- 5 // Affectation de la valeur 5 à la variable
…
ma_variable <- ma_variable * 2 // Opération sur la variable

A lʼissue de lʼalgorithme, lʼespace mémoire défini par “ma_variable” vaudra donc 10 (5 x 2)

Definition dʼune constante

#

Une constante est aussi un espace en mémoire, mais à la différence dʼune variable, la valeur dʼune constante est définie au moment de sa déclaration et ne peut être modifiée en cours de programme.

Elle nʼest donc accessible quʼen :

• Lecture

CONST MA_CONSTANTE: ENTIER <- 3.14116 // PI

Il existe “nativement” des constantes en algorithmique :

• PI qui représente la fameuse valeur utilisée en géométrie. On peut utiliser la constante PI native dans un algorithme.

On définit donc une constante lorsque nous voulons nous assurer que la valeur de cette constante ne puisse pas être “mutée” durant lʼexécution de notre algorithme et ainsi renforcer la cohérence durant lʼexécution.

Récapitulatif

#

On peur utiliser des psueo-constantes comme PI ou E (valeurs fixes utilisées comme références).

Typage

#

Lorsquʼon définit une variable ou une constante, on doit impérativement lui associer un type. Le type est la “famille” des valeurs que peut accepter cette variable. Par exemple, si vous définissez la variable suivante :

VAR ma_variable: ENTIER

L’opération suivante est donc impossible :

ma_variable <- "Hello World"

En revanche, si vous définissez la variable suivante :

VAR ma_variable: CHAINE

L’opération suivante est possible :

ma_variable <- "Hello World"

Les types alphanumériques

#

Les types alphanumériques sont les types les plus simples à définir. Ils sont définis par leur famille de valeurs et leur taille.

Certaines fonctions “internes” et opérations sont applicables à ces types algorithmique : -LEN(chaine) : retournera la longeur de la chaîne de caractère -SUCC(char) : renverra le caractère suivant le caractère passé en paramètre -PRED(char): renverra le caractère précédent le caractère passé en paramètre

Les types numériques

#

Les types numériques sont des types qui permettent de stocker des valeurs numériques. Ils sont définis par leur famille de valeurs et leur taille.

Certaines “opérations” sont applicables aux types numériques :

• Addition (+), soustraction (-), produit (*), division (/),
• Division entière : DIV pour récupérer la partie entière d’une division,
• Modulo : MOD récupérant le “reste” d’une division entière
• Les opérateurs de comparaison : =, >, <, >=, <=, <> ou !=

Les types logiques

#

Les types logiques sont des types qui permettent de stocker des valeurs logiques. Ils sont définis par leur famille de valeurs et leur taille.

Certaines “opérations” sont applicables aux types logiques :

• Et (ET), ou (OU), non (NON), exclusive ou (XOR) Mais peuvent utiliser les opérateurs logiques de comparaison : =, >, <, >=, <=, <> ou != ainsi que les opérateurs logiques de logique : ET, OU, NON, XOR.

Les types complexes

#

On arrive très vite à saturation lorsquʼon utilise des types simples (chaine, caractère, booléen, nombre). En effet, si on souhaite par exemple calculer une moyenne, il faudrait déclarer n variables de type réel, puis réaliser une addition de toutes ces variables et finir par diviser par le nombre de notes pour obtenir cette fameuse moyenne. Le travail serait long et fastidieux, et générateur dʼerreurs. Les types complexes vont apporter une réponse efficace à cette problématique.

Le type tableau

#

Un tableau est un ensemble de données de même type (y compris Tableau aussi). Un tableau peut être un ensemble “fini” dont on a donc défini les limites dès la déclaration ou non fini, dans ce cas, il devient un ensemble dynamique.

VAR tableau: TABLEAU[] DE CHAINE
VAR num_tableau: TABLEAU[0..4] DE ENTIER
VAR tablo2tablo: TABLEAU[] DE TABLEAU[] DE REEL

La première déclaration défini un tableau non fini qui ne pourra contenir que des chaînes de caractères. La seconde déclaration définit un tableau de 5 éléments. Lʼindice de départ étant à 0, on va dénombrer 0, 1, 2, 3, 4 indices, donc 5 éléments. La dernière déclaration définit donc un tableau, qui contiendra un tableau à chaque indice.

Ajouter des données dans un tableau

#

Pour écrire des données dans un tableau, il suffit de faire suivre la variable (ou la constante) tableau de crochets vides.

VAR tableau: TABLEAU[] DE CHAINE
// Ecrire les données dans le tableau
tableau[] <- “Jean-Luc”
tableau[] <- “Elsa”
tableau[] <- “Max”

Après exécution, le tableau aura donc la forme suivante dans la mémoire de votre machine :

Lire des données dans un tableau

#

Après avoir alimenté de manière contigüe les données, vous pouvez lire une information en passant entre crochets la valeur de lʼindice souhaité dans le tableau.

...
VAR seconde: CHAINE <- tableau[1]

Replacer des données dans un tableau

#

Pour remplacer une donnée, il suffit juste de redéfinir la valeur à lʼindice concerné :

...
tableau[1] <- “Achraf”

On peut utiliser une pseudo-fonction LEN(tableau) pour récupérer le nombre d’éléments de ce tableau.

Operations et syntaxe

#

Lʼalgorithmique met en oeuvre un certain nombre dʼopérations (calcul) pour arriver à un résultat. Les opérandes (variables ou constantes) font lʼobjet dʼopérations (comparaison, addition, soustraction, produit ou division) ainsi que dʼopérations plus spécifiques (DIVision entière, MODulo reste de division), ou encore dʼopérations logiques (NON, OU, ET, XOU…).

Affectation

#

L’affectation définit la valeur d’une variable.

Le signe = est interdit pour l’affectation.

On utilise le signe <- pour l’affectation.

x <- 5

Operations

#

Un opérateur est un symbole dʼopération permettant dʼagir sur une variable (+, -, /, *, ET, OU, DIV, MOD, =, <, >, ≤, ≥, <>, …). Une opérande est une « entité » (variable, constante ou expression) utilisée par un opérateur. Une expression est une combinaison des deux éléments précédents, évaluée durant lʼexécution de lʼalgorithme et possède une valeur ainsi quʼun type.

La comparaison permet de comparer deux valeurs.

Les comparaisons renvoient toujours un booléen. (TRUE ou FALSE)

Operateurs de comparaison de base

#

On utilise les signes suivants pour la comparaison :

Exemple d’utilisation :

SI note >= 10 ALORS
    afficher("Admis")
SINON
    afficher("Échec")
FINSI

Autre exemple :

SI age < 18 ALORS
    afficher("Mineur")
SINON
    afficher("Majeur")
FINSI

Operations logiques

#

Les opérations logiques permettent de combiner des conditions logiques.

Exemple d’utilisation :

SI (age >= 18) ET (nationalite = "FR") ALORS
    afficher("Inscription possible")
SINON
    afficher("Refusée")
FINSI

SI NON(estValide) ALORS
    afficher("Erreur de saisie")
FINSI

SI (note >= 10) XOR (bonus = VRAI) ALORS
    afficher("Rattrapage accepté")
FINSI

Mise en garde

#

Un opérateur ne peut sʼappliquer sur des types différents :

VAR test : Booleen ← VRAI
VAR resultat ← « Bonjour » + test

Cependant, dans certains cas, cette règle peut être dérogée :

VAR prenom : Chaine ← « Marie »
VAR resultat ← « Bonjour » + chaine

Dans ce cas, lʼopérateur « + » joue le rôle dʼun opérateur de concaténation. Cʼest le cas aussi si vous concaténez une chaîne et un nombre :

VAR resultat: CHAINE <- prenom + “ “ + 3.25

resultat vaudra : “Marie 3.25”

Entrées / Sorties

#

En général, un algorithme tient compte de données « entrantes » (saisies utilisateurs, lecture de données, etc.) et permet « dʼécrire » vers le périphérique de sortie :

prenom : Chaine
prenom ← lire()
ecrire(« Bonjour » + prenom)

Instructions conditionnelles

#

On doit souvent opter pour une série de traitements, en fonction de lʼévaluation dʼune expression :

Lʼalgorithmique permet de traiter des conditions :

VAR data: Reel ← lire()
Si data < 0 Alors
    data ← data * -1
FinSi
ecrire(data)

L’instruction SINON est optionnelle.

Traitement de cas

#

Il est parfois nécessaire de comparer une valeur à plusieurs autres. Lors du paiement dʼun « panier » de commande, on propose à lʼutilisateur plusieurs modes de paiement => carte, virement, chèque, mandat, …

Ce problème peut sʼexprimer facilement par lʼinstruction CAS :

CAS modePaiement VALANT
    'carte' : 
        ECRIRE("Paiement par carte accepté.")
    'virement' : 
        ECRIRE("Paiement par virement accepté.")
    'cheque' : 
        ECRIRE("Paiement par chèque accepté.")
    'mandat' : 
        ECRIRE("Paiement par mandat accepté.")
AUTRE :
        ECRIRE("Mode de paiement non reconnu.")
FINCAS

Boucles

#

Il arrive souvent quʼil soit nécessaire de traiter une série dʼinstructions plusieurs fois dʼaffilée, sur un ensemble fini.

Pour lʼensemble des 10 verres sur la table, il faut les remplir.

Sur un ensemble dont on ne connaît pas la limite : tant quʼil y a du soleil, je profite de la plage.

Dans le premier cas, on parlera de répétitions inconditionnelles, et de répétitions conditionnelles dans lʼautre.

Répétitions inconditionnelles

#

La boucle POUR permet de répéter une série dʼinstructions un nombre « connu » de fois :

POUR var: Entier ALLANT DE valeurDepart à valeurFin Pas de inc
….
….
FIN POUR

tablo : Tableau ← [125, 201, 302, 5, 15, 12]
POUR indice : Entier de 0 à 5 inc 1
    afficher(tablo[indice] * 2)
FIN POUR

Cette boucle va parcourir un à un chacun des éléments du tableau et afficher la valeur multipliée par deux à chaque occurrence : 250 402, 604, 10, 30, 24.

tablo : Tableau ← [125, 201, 302, 5, 15, 12]
indice : Entier ← 0
REPETE
    afficher(tablo[indice] * 2)
    indice ← indice + 1
JUSQUʼA indice = 6

Une nouvelle fois, le résultat sera identique, pourtant :

• La boucle sera exécutée systématiquement au moins une fois

• La condition de sortie est évaluée en fin de boucle, ce qui explique la valeur 6 au lieu de 5 en fin dʼalgorithme

POUR peut être utiliser aussi comme ceci :

POUR CHAQUE entier DANS entiers

Répétitions conditionnelles

#

Une répétition conditionnelle exécutera les instructions tant quʼune condition est satisfaite, ou jusquʼà ce quʼune condition soit satisfaite. Dans le premier cas « tant que », les instructions peuvent ne pas être exécutée, si la condition en amont nʼest pas satisfaite. Dans le second cas, les instructions seront exécutées au moins une fois.

La boucle TANT QUE permet dʼexécuter une instruction tant quʼune condition est satisfaite. Si vous devez rendre la monnaie sur un montant donné et une somme fournie :

montant : Entier ← 15
somme : Entier ← lire()
aRendre : Entier ← somme - montant
Tant que aRendre > 0
    aRendre ← aRendre – 1
FinTantQue

tablo : Tableau ← [125, 201, 302, 5, 15, 12]
indice : Entier ← 0
TANT QUE indice < 5
    afficher(tablo[indice] * 2)
    indice ← indice + 1
FIN TANT QUE

Le résultat de cet algorithme est le même que précédemment.

A noter cependant quand dans ce cas :

• Si on oublie dʼinitialiser lʼindice à une valeur inférieure au nombre dʼéléments du tableau, la boucle peut ne pas être exécutée

• Qu’on doit incrémenter nous même la valeur de lʼindice

A lʼexécution :

indice : 0 => affichage 250, indice : 1 indice : 1 => affichage 402, indice : 2 indice : 2 => affichage 604, indice : 3 indice : 3 => affichage 10, indice : 4 indice : 4 => affichage 30, indice : 5 indice : 5 => affichage 24, indice : 6

=> Sortie de boucle

Avertissement

#

Des boucles mal formées peuvent conduire à des « dead loops », cʼest à dire des boucles qui ne sʼarrêtent jamais, conduisant à un plantage des applications.

POUR i : Entier VALANT 0 A 10 INC 1
    afficher(ʻindice : ʻ + indice)
    indice ← indice – 1
FIN POUR

indice : Entier ← 0
TANT QUE indice < 5
    saisie : Chaine ← lire()
FIN TANT QUE

Tableaux

#

Les tableaux peuvent se concevoir comme des collections, ensembles dʼinformations.

Dans un tableau, les informations sont « indicées », en dʼautres termes, chaque valeur de la collection est associée à une « étiquette » numérique qui donne sa position dans le tableau.

Un tableau se déclare en algorithmique de la manière suivante :

tablo : Tableau ← [15, 23, 201]

Lʼaccès aux éléments dʼun tableau se fait par référence aux indices, lʼindice de la valeur concernée est passé entre crochets :

uneValeur : Entier ← tablo[1]

Un tableau est considéré comme faisant partie de la famille des « itérables » . Un « itérable » est une variable sur laquelle il est possible de boucler :

unTablo : Tableau ← [15, 3, 20, 18, 1, 6]
POUR indice : Entier VALANT 0 A 5 INC 1
    afficher(unTablo[indice])
FIN POUR

Des fonctions « algorithmiques » aident à traiter les boucles : longueur(unTablo) retourne le nombre dʼéléments de la variable « unTablo ».

A lʼaide de la fonction LEN(tableau) il est possible de reprendre lʼexemple précédent sous une autre forme :

unTablo : Tableau ← [15, 3, 20, 18, 1, 6]
POUR indice : Entier VALANT 0 A longueur(unTablo) - 1 INC 1
    afficher(unTablo[indice])
FIN POUR

Notez dans la boucle lʼutilisation de : LEN(unTablo) – 1. En effet, il y a 6 éléments dans le tableau mais lʼindice varie de 0 à 5.

Tableaux multidimensionnels

#

Un tableau peut avoir plusieurs « dimensions », en dʼautres termes, chaque élément dʼun tableau peut lui-même être un tableau.

Pour pouvoir afficher le contenu de lʼensemble dʼun tableau à n dimensions, il est donc nécessaire dʼimbriquer nboucles :

unTablo : Tableau ← [[1,2],[3,4],[5,6], [7,8],[9,10], [11,12]]
POUR indice : Entier VALANT 0 A longueur(unTablo) - 1 INC 1
    POUR subIndice : Entier VALANT 0 A longueur(unTablo[indice]) – 1 INC 1
        afficher(unTablo[indice][subIndice])
    FIN POUR
FIN POUR

Lʼaccès à un élément dʼun tableau à plusieurs dimensions se fait de la manière suivante : unTablo[1][0] permettra dʼaccéder à la valeur « 4 » (premier indice du tableau présent à lʼindice 1).

Structures

#

Definition dʼune structure

#

Une structure est un type de donnée complexe qui regroupe plusieurs champs (ou attributs) de types différents sous un même nom. Elle permet de rendre un algorithme plus lisible, organisé et proche de la programmation orientée objet (POO).

On peut voir une structure comme l’équivalent d’un “objet” simplifié, sans les notions d’héritage ou d’encapsulation.

L’intérêt de la structure est de :

• Rendre le code plus lisible et intelligible

• Éviter les tableaux à plusieurs dimensions difficiles à comprendre

• Pouvoir regrouper logiquement des informations qui appartiennent ensemble

• Possibilité d’ajouter des fonctions internes (méthodes), qui opèrent sur les données de la structure

Exemple d’une structure

#

Une structure est définie par la syntaxe suivante :

STRUCTURE Apprenant
	DEBUT 
		VAR nom : CHAINE
		VAR prenom : CHAINE
	FIN
FIN STRUCTURE 

Cette structure permet de stocker les informations d’un apprenant (nom et prénom).

Utilisation :

CONST jl : Apprenant
jl.nom <- "Aubert"
jl.prenom <- "Jean-Luc"

Structures contenant un tableau d’une autre structure

#

Une structure peut contenir un tableau d’un autre type de structure. Exemple : un apprenant possède plusieurs notes.

STRUCTURE Note
	DEBUT 
		VAR matiere : CHAINE
		VAR note : ENTIER
	FIN
FIN STRUCTURE

Puis on enrichit la structure Apprenant :

STRUCTURE Apprenant
	DEBUT	
		VAR nom : CHAINE
		VAR prenom : CHAINE
		VAR notes : Tableau(Note)
	FIN
FIN STRUCTURE 

Ajouter des fonctions internes

#

Une structure peut aussi contenir une fonction qui agit sur ses propres données (comme une méthode d’objet).

STRUCTURE Apprenant
	DEBUT	
		VAR nom : CHAINE
		VAR prenom : CHAINE
		VAR notes : Tableau(Note)
		
		FONCTION general_avg() : REEL
			DEBUT
				VAR cumul_notes : ENTIER <- 0
				POUR CHAQUE la_note DANS CE.notes FAIRE
					cumul_notes <- cumul_notes + la_note.note
				FIN POUR
				RETOURNE cumul_notes / LEN(CE.notes)
			FIN
		FIN FONCTION	 
	FIN
FIN STRUCTURE 

Remarque :

• CE désigne l’instance actuelle (comme this ou self dans d’autres langages).
• On retourne la moyenne des notes de l’apprenant.

Exemple complet d’utilisation

#

VAR une_note : Note
une_note.matiere <- "Algo"
une_note.note <- 15

CONST jl : Apprenant
jl.nom <- "Aubert"
jl.prenom <- "Jean-Luc"
jl.notes[] <- une_note    // Ajout de la première note

une_note.matiere <- "Algo"
une_note.note <- 9
jl.notes[] <- une_note    // Ajout de la seconde note

ECRIRE(jl.general_avg())  // Affiche la moyenne générale de JL

Le tableau jl.notes contient :

{"Algo", 15}, {"Algo", 9}

et jl.general_avg() retournera 12.

Une fois qu’on a une liste d’apprenants, on peut calculer la moyenne globale :

CONST classe : Tableau(Apprenant)
VAR cumul_notes : ENTIER <- 0
VAR nb_notes : ENTIER <- 0

POUR CHAQUE apprenant DANS classe FAIRE
	POUR CHAQUE la_note DANS apprenant.notes FAIRE
		cumul_notes <- cumul_notes + la_note.note
		nb_notes <- nb_notes + 1
	FIN POUR
FIN POUR

CONST moyenne_generale : REEL <- cumul_notes / nb_notes
ECRIRE("Moyenne générale de la classe : ", moyenne_generale)

Fonctions

#

En algorithmique, on peut utiliser des fonctions « virtuelles » :

• lire() est une fonction capable de récupérer des informations venant du « monde extérieur » (saisie clavier, résultat dʼune requête SQL, informations provenant dʼune autre partie de code…).

• ecrire(message : Chaine) est une fonction capable de produire une « sortie » vers le « monde extérieur » (écran, imprimante, …) dʼune information.

• LEN(tableau : Tableau) retourne le nombre dʼéléments dʼun tableau.

Nous nʼavons pas à savoir comment ces instructions fonctionnent mais juste à savoir ce quʼelles font. On parle souvent de « boîtes noires ». Ces fonctions nʼont aucune existence réelle. Elles sont juste là pour permettre de faciliter lʼécriture des algorithmes.

Une fonction peut être considérée comme un « programme » autonome, dont le but est de traiter une série dʼinstructions et de retourner un résultat.

Imaginons que l’on doit réaliser un algorithme qui permet dʼadditionner les valeurs présentes dans deux tableaux distincts (de même dimension), et de ranger le résultat de lʼaddition dans un troisième tableau.

Une des solutions possibles serait la suivante :

firstValues : Tableau ← [5, 10, 15, 20]
secondValues : Tableau ← [3, 5, 7, 9]
results : Tableau
POUR indice : Entier VALANT 0 A longueur(firstValues) – 1 INC 1
    results[] ← firstValues[indice] + secondValues[indice]
FIN POUR

Après réflexion, il sʼavère que l’on doit non plus additionner mais multiplier, on doit revoir notre boucle pour changer lʼopérateur avec le risque de devoir à nouveau changer pour revenir à lʼétat précédent.

Pour éviter les risques, on peut donc écrire deux fonctions :

• Lʼune qui se chargera dʼadditionner deux valeurs et de retourner le résultat

• Lʼautre qui se chargera de multiplier ces deux valeurs et de retourner le résultat

FONCTION additionner(value1: Entier, value2: Entier) : Entier
    RETOURNE value1 + value2
FIN FONCTION

FONCTION muliplier(value1: Entier, value2: Entier) : Entier
    RETOURNE value1 * value2
FIN FONCTION

Ces deux fonctions « acceptent » en entrée deux « paramètres » (value1 et value2) qui seront à lʼappel de la fonction, alimentés par les valeurs fournies.

Au final, il est donc possible de « refactorer » lʼalgorithme de la manière suivante :

firstValues : Tableau ← [5, 10, 15, 20]
secondValues : Tableau ← [3, 5, 7, 9]
results : Tableau
POUR indice : Entier VALANT 0 A longueur(firstValues) – 1 INC 1
    results[] ← additionner(firstValues[indice],
    secondValues[indice])
FIN POUR


firstValues : Tableau ← [5, 10, 15, 20]
secondValues : Tableau ← [3, 5, 7, 9]
results : Tableau
POUR indice : Entier VALANT 0 A longueur(firstValues) – 1 INC 1
    results[] ← multiplier(firstValues[indice], secondValues[indice])
FIN POUR

Une fonction peut appeler une autre fonction.

FONCTION choixOperation(value1 : Entier, value2 : Entier, isAddition : Booleen) : Entier
    SI isAddition = VRAI ALORS
        RETOURNE additionner(value1, value2)
    SINON
        RETOURNE multiplier(value1, value2)
    FIN SI
FIN FONCTION

FONCTION additionner(value1, value2) : Entier
    RETOURNE value1 + value2
FIN FONCTION

FONCTION muliplier(value1, value2) : Entier
    RETOURNE value1 * value2
FIN FONCTION

Le code peut donc à nouveau être refactoré :

firstValues : Tableau ← [5, 10, 15, 20]
secondValues : Tableau ← [3, 5, 7, 9]
results : Tableau
POUR indice : Entier VALANT 0 A longueur(firstValues) – 1 INC 1
    results[] ← choixOperation(firstValues[indice],
secondValues[indice], VRAI)
FIN POUR

Une fonction peut aussi sʼappeler elle-même. Une telle fonction est dite « récursive ». Les fonctions « récursives » peuvent être risquées si les conditions de sortie sont mal évaluées, mais excessivement pratiques. En reprenant le tableau multidimensionnel, on peut très bien « afficher » tout le contenu en une seule boucle.

FONCTION dump(array : Tableau)
    POUR indice : Entier VALANT 1 A longueur(array) – 1 INC 1
        SI array[indice] IS Tableau ALORS
            dump(array[indice])
        SINON
            afficher(array[indice])
        FIN SI
    FIN POUR
FIN FONCTION

IS est utilisé ici pour déterminer le « type » de la donnée array[indice].

unTablo : Tableau ← [[1,2],[3,4],[5,6], [7,8],[9,10], [11,12]]
dump(unTablo)

Le résultat de lʼappel à la fonction « dump(unTablo) » donnera : 1 2 3 4 … 11

Commentaires

#

Les commentaires sont des instructions qui ne sont pas exécutées.

Pour inserer un commentaire, il suffit d’ajouter de rajouter REM devant le texte à commenter.

// est également un raccourci pour REM.

Exemple :

REM Ceci est un commentaire
// Ceci est un aussi commentaire

Gestion des erreurs

#

Il n’existe pas de try/catch dans l’algorithmique. En case de besoin, on peut simplement mentionner en commentaire le traitement envisageable de l’erreur.

Exemple :

REM Si la saisie est invalide, recommencer la lecture

Pseudo methodes

#

Les pseudo-méthodes sont des instructions qui permettent de simuler des méthodes (actions) pour décrire un comportement.

ajouter(element)
retirer(element)

Ces pseudo-méthodes sont symboliques et servent à rendre le code plus lisible.

Exercices

#

Exercice 1

#

Algorithme : Rendu Monnaie Rôle : Ventilation d’un rendu de monnaie en espèce par type de billet et / ou pièce ésultat : Obtenir le nombre de billets de 100, de 50, de 20, de 10, de 5 et le nombre de pièces de 2 euros

DEBUT
    CONST PRIX_PRODUIT: ENTIER <- 75
    CONST SOMME_VERSEE: ENTIER <- 100
    CONST A_RENDRE: ENTIER  <- SOMME_VERSEE - PRIX_PRODUIT

    VAR billet100, reste100, billet50, reste50, billet20, reste20, billet10, reste10, billet5, reste5, piece2, reste2: ENTIER <- 0

    // Traitement pour les billets de 100
    billet100 <-  A_RENDRE DIV 100 // Dans ce cas 0
    reste100 <- A_RENDRE MOD 100 // Dans ce cas 25 / 100 => 0.25 donc 25

    // Traitement pour les billets de 50
    billet50 <- reste100 DIV 50 // Dans ce cas 0
    reste50 <- reste100 MOD 50 // Dans ce cas 25 / 50 => 25

    // Traitement pour les billets de 20
    billet20 <- reste50 DIV 20 // Dans ce cas 25 / 20 => 1
    reste20 <- reste50 MOD 20 // Dans ce cas 5 / 20 => 5

    // Traitement pour les billets de 10
    billet10 <- reste20 DIV 10 // Dans ce cas 5 / 10 => 0
    reste10 <- reste20 MOD 10 // Dans ce cas 5

    // Traitement pour les billets de 5
    billet5 <- reste10 DIV 5 // Dans ce cas 1
    reste5 <- reste10 MOD 5 // Dans ce cas 0

    // Traite les pièces de 2
    piece2 <- reste5 DIV 2 // Dans ce cas 0
    reste2 <- reste5 MOD 2 // Dans ce cas 0
FIN

Exercice 2

#

CONST entiers <- [5, 8, 3, 12, 13, 25, 2] 

1. Combien il y a-t-il de valeurs paires dans le tableau ?

2. Copier dans un nouveau tableau les valeurs impaires.

3. Déterminer la plus grande valeur du tableau original.

4. Calculer la moyenne des valeurs du tableau.

5. Déterminer la factorielle du tableau.

VAR compteur : Entier
POUR VAR i : Entier ALLANT DE 0 A LEN(entiers) - 1 INC 1
	SI entiers[i] MOD 2 = 0 ALORS
		compteur <- compteur + 1
	FIN SI
FIN POUR

VAR tableau: Tableau[Entier] <- []
POUR VAR i : Entier ALLANT DE 0 A LEN(entiers) - 1
	SI entiers[i] MOD 2 = 1 ALORS
		tableau[] <- entiers[i]
	FIN SI
FIN POUR

VAR valeur_maximal : Entier <- entiers[0]
POUR VAR i : Entier ALLANT DE 1 A LEN(entiers) - 1 INC 1
	SI entiers[i] > max ALORS
		valeur_maximal <- entiers[i]
	FIN SI
FIN POUR

VAR moyenne : Reel 
VAR total_valeurs : Entier
POUR VAR i : Entier ALLANT DE 0 A LEN(entiers) - 1 INC 1
	total_valeurs <- total_valeurs + entiers[i]
FIN POUR
moyenne <- total_valeurs / LEN(entiers)

VAR factorielle: Entier <- 1
POUR CHAQUE entier DANS entiers
    factorielle <- factorielle * entier
FIN POUR

Exercice 3

#

Une classe est composée de “n” apprenants. Durant la formation, des notes par matières sont données à chaque étudiant : algorithmique, conception, sql. Chaque matière fait l’objet de 2 à 3 évaluations notées de 0 à 10.

Le responsable pédagogique souhaite disposer des informations suivantes :

• Moyenne générale de la classe toute matière confondue
• Moyennes réparties par matières pour l’ensemble de la promotion
• Moyennes par matière pour chaque étudiant
• Moyenne générale pour chaque étudiant

Vous allez devoir définir :

• La ou les structures de stockage des informations
• Elaborer les algorithmes nécessaires à la résolution des attendus
• Valider les algorithmes avec un jeu d’essai simple

// =====================
// Données initiales
// =====================
CONST Etudiants : Tableau(Tableau) <- [
    [1, "Denis", "Alibert"],
    [2, "Alice", "Villers"],
    [3, "Cedric", "Da Silva"]
]

CONST Matieres : Tableau(Tableau) <- [
    [1, "SQL"],
    [2, "Algorithmique"],
    [3, "Conception"]
]

CONST Notes : Tableau(Tableau) <- [
    [1, 2, 5],
    [1, 2, 7],
    [1, 3, 4],
    [2, 1, 10],
    [2, 3, 10],
    [2, 3, 8],
    [2, 2, 10],
    [3, 3, 10],
    [3, 2, 7],
    [3, 3, 5]
]

// =====================
// Variables de sortie
// =====================
VAR MoyenneParMatiereEtudiant : Tableau(Tableau) <- [] // [idEtudiant, idMatiere, moyenne]
VAR MoyenneGeneraleEtudiant : Tableau(Tableau) <- []   // [idEtudiant, moyenne]
VAR MoyenneParMatierePromo : Tableau(Tableau) <- []    // [idMatiere, moyenne]
VAR MoyenneGeneraleClasse : Réel <- 0

// =====================
// Calcul des moyennes par matière et par étudiant
// =====================
POUR VAR e : Entier DE 0 A LEN(Etudiants) - 1 INC 1 FAIRE
    POUR VAR m : Entier DE 0 A LEN(Matieres) - 1 INC 1 FAIRE
        VAR sommeNotes : Réel <- 0
        VAR compteur : Entier <- 0
        
        POUR VAR n : Entier DE 0 A LEN(Notes) - 1 INC 1 FAIRE
            SI Notes[n][0] = Etudiants[e][0] ET Notes[n][1] = Matieres[m][0] ALORS
                sommeNotes <- sommeNotes + Notes[n][2]
                compteur <- compteur + 1
            FIN SI
        FIN POUR
        
        SI compteur > 0 ALORS
            VAR moyMatiere : Réel <- sommeNotes / compteur
            AJOUTER [Etudiants[e][0], Matieres[m][0], moyMatiere] DANS MoyenneParMatiereEtudiant
        FIN SI
    FIN POUR
FIN POUR

// =====================
// Moyenne générale par étudiant
// =====================
POUR VAR e : Entier DE 0 A LEN(Etudiants) - 1 INC 1 FAIRE
    VAR sommeMoyennes : Réel <- 0
    VAR compteur : Entier <- 0
    
    POUR VAR n : Entier DE 0 A LEN(MoyenneParMatiereEtudiant) - 1 INC 1 FAIRE
        SI MoyenneParMatiereEtudiant[n][0] = Etudiants[e][0] ALORS
            sommeMoyennes <- sommeMoyennes + MoyenneParMatiereEtudiant[n][2]
            compteur <- compteur + 1
        FIN SI
    FIN POUR
    
    SI compteur > 0 ALORS
        VAR moyGenerale : Réel <- sommeMoyennes / compteur
        AJOUTER [Etudiants[e][0], moyGenerale] DANS MoyenneGeneraleEtudiant
    FIN SI
FIN POUR

// =====================
// Moyennes par matière pour l'ensemble de la promotion
// =====================
POUR VAR m : Entier DE 0 A LEN(Matieres) - 1 INC 1 FAIRE
    VAR sommeMoyennes : Réel <- 0
    VAR compteur : Entier <- 0
    
    POUR VAR n : Entier DE 0 A LEN(MoyenneParMatiereEtudiant) - 1 INC 1 FAIRE
        SI MoyenneParMatiereEtudiant[n][1] = Matieres[m][0] ALORS
            sommeMoyennes <- sommeMoyennes + MoyenneParMatiereEtudiant[n][2]
            compteur <- compteur + 1
        FIN SI
    FIN POUR
    
    SI compteur > 0 ALORS
        VAR moyPromo : Réel <- sommeMoyennes / compteur
        AJOUTER [Matieres[m][0], moyPromo] DANS MoyenneParMatierePromo
    FIN SI
FIN POUR

// =====================
// Moyenne générale de la classe
// =====================
VAR sommeGenerale : Réel <- 0
VAR nbEtudiants : Entier <- 0

POUR VAR i : Entier DE 0 A LEN(MoyenneGeneraleEtudiant) - 1 INC 1 FAIRE
    sommeGenerale <- sommeGenerale + MoyenneGeneraleEtudiant[i][1]
    nbEtudiants <- nbEtudiants + 1
FIN POUR

SI nbEtudiants > 0 ALORS
    MoyenneGeneraleClasse <- sommeGenerale / nbEtudiants
FIN SI

Ressources

#

• Exercice Algorithmique