Eléments de base de l’algorithme

Facebook Tweet Pin Email

ATTENTION : en C++ on trouve les notions de paramètres d’entrées et de paramètres d’entrée/sorties mais pas les paramètres de sorties (un paramètre de sortie peut donc être vu comme un paramètre d’entrée/sortie dont on n’utilise pas la valeur d’entrée.)
3 Appel Actions – passages de paramètres
Exemple :
Division Entière (X, Y, A, B)
Un appel d’action est une action élémentaire (instruction)
Remarque :
¾ Le nombre d’arguments doit correspondre au nombre de paramètres.
¾ Lien argument paramètre : se fait selon l’ordre de la liste.

Que ce passe-t-il lors du passage de paramètres :
• En ASD :
1. Au moment de l’appel, les valeurs des arguments d’entrée ou d’entrée/sortie sont recopiées dans les paramètres.
2. L’action appelée s’exécute.
3. A la fin de cette exécution, les valeurs des paramètres S ou ES sont
recopiées dans les arguments.
• En C++ :
1. Pour les paramètres d’entrée : idem ASD (passage par valeur)
2. Pour les paramètres d’entrée/sortie : passage par référence :
Chaque paramètre d’entrée/sortie possède une zone mémoire permettant de stocker une adresse mémoire.
a) Au moment de l’appel :
¾ Recopie les valeurs des arguments d’entrée
¾ Recopie l’adresse des arguments d’entrée/sortie dans la zone des
paramètres
b) La fonction appelée s’exécute mais en travaillant directement
sur la zone mémoire contenant la valeur des arguments ES.
c) A la fin de l’exécution de l’appelée : rien ! (les arguments possèdent déjà les valeurs.)

Remarque :
¾ Les arguments d’entrée peuvent être des variables ou des expressions (car la valeur est transmise).
¾ Les arguments S ou ES doivent être des variables.
¾ Une action ne doit jamais modifier ses paramètres d’entrée. Pourquoi ? Car suivant le langage de programmation, ils seront ou non modifiés.

La notion de fonction :

Certaines actions n’ont que des paramètres d’entrée et un seul paramètre de sortie. Dans ce cas, l’utilisation est plus souple sous forme de fonction.
5.1 Exemple de fonction avec récursivité : la fonction factorielle :
n!=1*2*…*n
0!=1
n!=n*(n-1)! : cette dernière écriture est une définition récursive : on utilise (n-1)! Pour définir
n!
Elle permet une traduction immédiate :
Fonction FACT (n :entier) : entier
Début
Si n=0 alors retourner (1)
Sinon retourner (n*FACT(n-1))
Fin
Si l’on fait le graphe des appels on se rend donc bien compte que la fonction FACT appelle la
fonction FACT : donc elle est récursive.
Mais faisons tourner cet algorithme sur un exemple : n=3
Calcul de FACT(3) : met en suspens FACT(3) et va chercher FACT(2)
Calcul de FACT(2) : met en suspens FACT(2) et va chercher FACT(1)
Calcul de FACT(1) : met en suspens FACT(1) et va chercher FACT (0)
FACT(0) connu (=1) : il remonte a FACT(1)
FACT(1) connu (=1) : il remonte a FACT(2)
FACT(2) connu (=2) il remonte a FACT(3)
FACT(3) connu (=6)
Fin du programme
Remarque : toute fonction récursive doit donc nécessairement contenir un cas ou il n’y a pas d’appel récursif et ce cas doit toujours être atteint.
Autre remarque importante : la fonction FACT est plus performante dans sa fonction itérative (avec une structure Pour) car même si le nombre d’opérations est identique, choisir d’utiliser la fonction récursive demande une mémoire et temps plus important pour les traitements.

Autre mauvais exemple
Prenons un autre exemple pour montrer que l’option récursivité n’est pas a utiliser n’importe comment car parfois plus facile elle rend les calculs très longs.
Faisons un programme qui calcule le nombre de Fibonacci : 0 1 1 2 3 5 8 13 21
C’est en réalité la suite définie par :

INTRODUCTION GENERALE
ELEMENTS DE BASE DE L’ALGORITHME
LES ACTIONS
TYPES ET STRUCTURES DE DONNEES
COMPLEXITE DES ALGORITHMES
LES TYPES ABSTRAITS DE DONNEES