Cours 3

Décomposition et paramétrage des algorithmes

Algorithme trop long, trop complexe décomposition en plusieurs algorithmes, chacun résolvant une partie du problème posé.

(Ces algorithmes « s’appellent » entre eux)

1 - Introduction

Jusqu’ici, nous avons vu 2 types d’instructions :• celles qui traitent directement l’information :

l’affectation ( = ) la lecture/écriture vers écran/clavier (lire, écrire)

• celles qui commandent le déroulement du programme : structures de contrôle (si…alors…fsi) boucles(tant que, répéter, pour …)

Nous verrons dans ce chapitre un troisième type d’instruction : l’appel depuis un algorithme (l’appelant) d’un autre algorithme (l’appelé)

1 – Appel simpleExemple : un algorithme Appelant réalise deux séries de calculs, et fait toujours précéder et suivre ces calculs par deux lignes de 60 étoiles.Pour cela, il fait appel à un algorithme étoile qui affiche ces deux lignes d ’étoiles.

2 - Décomposition

Algorithme étoile()// affiche 2 lignes de 60 étoilesaux i,j: entier;début pour i de 1 à 2 faire pour j de 1 à 60 faire écrire(’*’); fait; écrire("\n");faitfin étoile

Algorithme Appelant()//…

débutétoile();//calculsétoile();//calculs étoile();

fin Appelant

Remarque : peu importe comment a été conçu et écrit l’algorithme étoile:Pour l’utiliser, il suffit de connaître ses spécifications (son en-tête).

On modifie donc étoile en conséquence:

On ajoute à étoile un paramètre : un identificateur + son type

2 – Passage de paramètre(s)Rappel: un paramètre est une variable reçue en entrée par un algorithme.

Même exemple que précédemment mais:on souhaite préciser à étoile la largeur de la ligne à afficher.

Dans Appelant, lors de l’appel de étoile, on précise dorénavant la valeur que l’on souhaite attribuer au paramètre nb.

Sinon étoile ne peut pas fonctionner.

Lors de l'exécution de l'appel, cette valeur est copiée dans nb.

distinguer paramètre formel et paramètre effectif

Un paramètre formel est une variable formelle - sans valeur - déclarée dans l'en-tête d'un algorithme.

Un paramètre effectif est une variable ou une valeur qui est copiée dans le paramètre formel correspondant au moment de l'appel.

On souhaite maintenant pouvoir préciser dans étoile (qui devient lignes):• le symbole à utiliser• le nombre de lignes• le nombre de symboles par ligne

Remarques : 1. un appel contient autant de paramètres effectifs qu’il y a de paramètres formels dans l'algorithme appelé; 2. la correspondance paramètre formel/paramètre effectif est établie en fonction de leur ordre dans l’appel et dans l’en-tête ; 3. chaque paramètre effectif doit être du même type que le paramètre formel lui correspondant. 4. les paramètres formels et effectifs associés n'ont pas forcément le même nom.

3 – Pourquoi décomposer des algorithmes?

A - Algorithme plus lisible, résolution facilitée

Algorithme tri_sélection(tab: tab100Entiers)// Trie 100 entiers et affiche le résultataux i, j, posmin, temp: entier;début

pour i de 1 à 99 faireposmin = i;pour j de i+1 à 100 faire

si tab[j] < tab[posmin] alorsposmin = j;

fsifaittemp = tab[i];tab[i] = tab[posmin];tab[posmin] = i;

faitpour i de 1 à 100 faire

écrire(tab[i]);fait

fin tri_sélection

Algorithme tri_sélection(tab: tab100Entiers)// Trie 100 entiers et affiche le résultataux i, posmin : entier;début

pour i de 1 à 99 faireposmin = cherchePosMin(tab, i, 100);échange(tab, i, posmin);

faitaffiche(tab);

fin tri_sélectionFonction cherchePosMin(tab:tab100Entiers, deb, fin: entier) retourne entier{deb<=fin, deb>=1, fin<=100}//Cherche le minima d'une portion du tableauaux i, posmin: entier;début

posmin = deb;pour i de deb+1 à fin faire

si tab[i] < tab[posmin] alorsposmin = i;

fsi;faitretourne posmin;

fin chercheMin

Algorithme échange(R tab:tab100Entiers, i,j :entier)//Echange deux cases d'un tableauaux t: entier;début

t = tab[i];tab[i] = tab[j];tab[j] = t;

fin échange

Algorithme affiche(tab:tab100Entiers)//Affiche le tableauaux i: entier;début

pour i de 1 à 100 faireécrire(tab[i]);

faitfin affiche

3 – Pourquoi décomposer des algorithmes?

A - Algorithme plus lisible, résolution facilitée

B - Réutilisation

• dans un même programme (ex: étoile)

• entre différents programmes (ex: tri)

C - Modification d'une sous-partie: seul le respect de l'interface importe

(Principe objet. Ex: recherche de position du minima du tri, voiture)

A PARTIR DE MAINTENANT,

ON MODIFIE LA SYNTAXE D'ÉCRITURE DES ALGORITHMES

!

Chaque paramètre d'un algorithme sera maintenant décrit par son nom de variable, son type et son mode de transmission (R ou V).

Algorithme truc(R a: entier)

3 – Les différents modes de transmissiondes paramètres

Ce mode de transmission indique si le paramètre effectif est :

1. une Valeur fournie par l’algorithme appelant à l'algorithme appelé

2. une Référence accessible et donc modifiable par les deux algorithmes concernés: l'appelé et l'appelant

1 – Le passage par valeur (noté V)

• Comportement utilisé depuis le début de l'année

• Seules les valeurs des paramètres effectifs sont transmises, le paramètre formel (appelé) est une copie du paramètre effectif (appelant)

• Avantage: garantie que les paramètres effectifs sont intacts après l'appel (ex: moyenne)

• Inconvénient: impossible de récupérer un résultat! (ex: moyenne)

LES PARAMÈTRES PASSÉS PAR VALEUR SONT DES ENTRÉES.

2 – Le passage par référence (noté R)

Dans ce mode, le paramètre effectif et le paramètre formel(dont les noms peuvent différer)

désignent une seule et même variable

modifiable par les deux algorithmes : l'appelé et l'appelant.

Exemple: moyenne d'entiers avec V ou R

Autre exemple: permutation d'entiers

On veut créer un algorithme qui permute deux valeurs.

LES PARAMÈTRES PASSÉS PAR RÉFÉRENCE SONT :

• SOIT DES SORTIES (Ex: moyenne)

•SOIT DES ENTRÉES/SORTIES (Ex: permutation).

On appelle fonction tout algorithme n'ayant qu'une seule sortie.

Fonction

Pour ces algorithmes, au lieu d'écrire l'en-tête suivant :

algorithme moyenne (V a, b : flottant, R m: flottant)

on pourra écrire:

fonction moyenne (V a, b : flottant) retourne flottant

Tous les autres algorithmes sont appelés "procédures" :

procédure étoile(V nblignes, nbsymb: entier,

V symbole: caractère)

4 – Procédures et fonctions

Du point de vue des SORTIES, quels sont les différents types d'algorithmes que nous pouvons rencontrer?

• des algorithmes sans sortie

• des algorithmes à une seule sortie

• des algorithmes à plusieurs sorties

Des fonctions, pour quoi faire?

• syntaxe rapprochée des fonctions mathématiques

• intégration des appels dans des expressions

Ex: moyenne : fonction ou procédure?

REMARQUE 1

Pourquoi ne pas utiliser que des fonctions?

Ex: algo « moyenne et somme »: multi-affectation? utilisation des structures?

REMARQUE 2

Le choix des E/S dans un algorithme a des conséquences importantes sur l'utilisation de cet algorithme.

Ex: moyenne de deux entiers et affichage

affichage ou saisie interdisent un usage interne de la fonction

REMARQUE 3

L'introduction du mot-clé retourne implique éventuellement l'existence de plusieurs points de sortie dans une fonction

ou une procédure.

Ex: …

REMARQUE 4

Il ne faut pas oublier qu'un appel de fonction ou procédure peut masquer un algorithme complexe et coûteux.

Ex: factorielle au carré

1 – Quelle représentation utiliser?

Nous choisissons de créer un type Polynôme : c'est une structure contenant un tableau des coefficients et un degré.

(Le degré du polynôme représenté est donc limité par la taille du tableau.)

Ex: Quelle représentation pour f(x) = 9.5 - 8.1 x + 3.2 x2 + 4.1 x4 ?

5 – Application: gestion de polynômes

2 – Opérations à implanterLes opérations que nous voulons effectuer sur ces polynômes sont :

• la saisie d’un polynôme

• l’affichage d’un polynôme

• le calcul de la valeur d’un polynôme f en x : f (x)

• le calcul de la dérivée d’un polynôme

• le calcul du produit de deux polynômes f et g