Algorithmique et Programmation

Support de Cours MIC2

Année 2016-2017 esquirol@insa-toulouse.fr

2G.AURIOL, C. MERCE, P. ESQUIROL

Ce que vous savez faire (1/2)

� Sur le plan algorithmique� Utiliser à bon escient les structures de contrôle

� Séquence

� Répétitions (boucles) � Structure « for … loop … end loop»

� Structure « while … loop … end loop»

� Structures de choix� Alternative : « if … then … else …end if »

� Choix multiple : « case … when … end case »

� Ecrire des algorithmes « classiques »� Parcourir un tableau

� Chercher la valeur min[max] du tableau (indiquer la 1ere place qui le contient)

� Trier un tableau

� Ecrire des sous-programmes déjà spécifiés� La fonctionnalité du sous-programme est définie

� Les paramètres du sous-programme sont fixés

Ce que vous savez faire (2/2 )

� Sur le plan des structures de données� Utiliser des types simples� Utiliser des types composés

� Tableaux (array)

� Articles (record)

� Naviguer dans des structures composées� Tableaux d’articles, Articles contenant des tableaux,

� Matrices

� Tableaux de records, records de tableaux …

� …

� Sur le plan de la mise au point de programmes (en T P)� Utiliser l’environnement de programmation (Linux, Emacs, Gnat)� Mettre en œuvre une méthodologie de développement progressive

� écriture d’un sous-programme + sous-programmes de test

Objectifs du module (1/2)

� Sur le plan algorithmique, vous serez capable de :

� Concevoir et formaliser des algorithmes complexes selon la méthode de l’analyse descendante

� Maîtriser la spécification et le développement de sous-programmes� Ecrire des algorithmes « classiques »

� Recherche du min (ou du max) dans un tableau ou une liste

� Recherche d’une valeur dans un tableau ou une liste

� Tri croissant ou décroissant d’un tableau (différents algorithmes)

� Mettre en œuvre une analyse récursive et concevoir des sous-programmes récursifs

� Travailler sur des structures de données dynamiques (listes basées sur des pointeurs)

� Insérer[Supprimer] un élément en tête[fin] de liste

Objectifs du module (2/2)

� Sur le plan des structures de données, vous serez ca pable de :

� Maîtriser la déclaration et l’utilisation de tableaux notamment leur dimensionnement

� Définir des structures de données dynamiques en utilisant des pointeurs

� Choisir et concevoir les structures de données les mieux adaptées à un problème donné (suite au module du semestre 2)

� Sur le plan du développement de programmes en TP, v ous serez capable de :

� Mettre au point progressivement un programme répondant à un cahier des charges (analyse, conception, codage et tests)

� Réaliser les tests unitaires et fonctionnels

� Intégrer des données dans un programme à partir de saisies ou de fichiers textes.

� Travailler en autonomie et développer le programme complet

Organisation et plan du cours

� Organisation� Cours : 5 séances de 1h15� TD : 10 séances de 1h15� TP : 5 séances de 2h45 (en binôme ou monôme)

� Contrôles : 1 évaluation individuelle� 1 Contrôle sur machine (sans documents)

� Plan du cours (prévisionnel)� Cours 1 Analyse descendante et rappels sur les sous-programmes� Cours 2 Tableaux et problèmes de dimensionnement� Cours 3 Récursivité� Cours 4 Pointeurs � Cours 5 Pointeurs et Conclusion

G.AURIOL, C. MERCE, P. ESQUIROL

Bibliographie et logiciels

� Bibliographie� « Programmation Séquentielle avec Ada95 »

P. Breguet – L. Zaffalon

Presses Polytechniques et Universitaires Romandes

� « Programmer avec Ada95 »J. Barnes, Adison Wesley

� Pour faire de l’ADA � Compilateur gratuit et IDE

� Windows : Gnat et Adagide/Emacs

� Linux : Gnat et Emacs

� Mac : http://www.macada.org/

� Manuel officiel� Ada95 Reference Manual

� http://www.adahome.com/rm95/

� Sites internet : www.adapower.com/ www.ada-france.org/

Forme générale d’un programme avec S/P

-- Entête du programmeWITH ... ; USE ……. ;PROCEDURE Nom_Programme IS

-- Déclarations des constantes, types et sous-types…….

-- Spécifications et corps des S.-P.…….…….

-- Déclarations des variables du programme principal…….

BEGIN-- Instructions (dont appels aux S.-P.)…….

END Nom_Programme ;G.AURIOL, C. MERCE, P. ESQUIROL

Chapitre 1

Rappels sur les sous-programmes

Chap 1 – SP - Pourquoi faire des S/P?

� Améliorer � La lisibilité des programmes réalisés

� Programmes moins longs et plus clairs (1 page chacun au plus)

� La fiabilité et la maintenance des programmes� 1 fois le S.-P. écrit et testé, plus besoin d’y revenir

� Développer plus rapidement

� Réutiliser les S.-P. existants� Trouvés sur Internet, déjà développés au sein de l’entreprise,…

� Partager le développement entre équipes� Chaque équipe a en charge un ou plusieurs S.-P.

� Attention à la conception

� Comment décomposer en sous-programmes ?

� Quels paramètres ?

Chap. 1 : SP - Concepts de base

� Deux catégories de sous-programmes� Fonction

� Retourne 1 résultat unique

� Appel de fonction ≈ Expression

� Procédure� Effectue une action qui peut générer 0, 1 ou plusieurs résultats

� Appel de procédure (« invocation ») -> 1 Instruction

� Concepts de base

� Déclaration d’un S.-P. / Appel d’un S.-P.

� Echanges d’informations entre S.-P. et programme appelant� Paramètres formels / Arguments d’appel

� Portée des variables� Variables locales / variables globales

� Imbrication de sous-programmes

Chap. 1 : SP - Déclaration et appel d’une fonction

� Déclaration d’une fonction

� Appels de fonction, exemples :

function Nom_de_Fonction ( Parametres_Formels ) return Type_Resultat is

-- Déclaration de constantes, types, ss-types et variables locales

begin-- instructions….

return Expression ; -- de type Type_Resultatend Nom_de_Fonction;

Variable := Nom_de_Fonction ( Parametres_D_Appel ) ;

Put ( Nom_De_Fonction ( Parametres_D_Appel ) ) ;

if Nom_de_Fonction ( Parametres_D_Appel ) then

Ne pas oublier

Ou rien !

Chap. 1 : SP - Exemple d’une fonction Calculer_Somm e

Corps du sous-programme-- calcule la somme des valeurs rangées dans un tableau

function Calculer_Somme (T : in Tab_Entier) return Integer is

S : Integer; -- variable locale résultat

S := 0;

for I in T’range loop

S := S + T(I) ;

end loop ;

return S;

end Calculer_Somme;

---------------------------------------------------------------------

Appel du sous-programme

….Resu := Calculer_Somme ( Mon_Tableau );

Chap. 1 : SP - Exemple de déclaration d’une procédur e

� Spécification d’un sous-programme de facturation � Ecrire un sous-programme qui à partir

� Du prix unitaire d’un article

� Du nombre d’articles achetés

� Du taux de TVA appliqué

� Retourne� Le prix HT et le prix TTC

procedure Facture (PU : in float; N : in natural; TVA : in Float ;

PHT : out Float ; PTTC : out Float ) isbegin

PHT := PU * Float (N) ;

PPT := PHT + PHT * TVA ;

end Facture ;

Chap. 1 : SP - Exemples d’appel de la procédure

PROCEDURE Main IS

-- Declaration du sous-programme

procedure Facture(Pu : in float; N : in natural; TVA : in Float ; Pht , Pttc : out Float) is

…begin

…end Facture ;

-------------------------------------------------------------------------- Declarations des variables du programme principal (juste avant le begin)P1 : Float := 23.45 ;Montant_HT, Montant_TTC, X, Y : Float ;

begin…. --Pu N TVA Pht PttcFacture (P1 , 100 , 0.20, Montant_HT , Montant_TTC ) ;Facture ( 99.9 , 50 , 0.5, X, Y );….

end Main;

Chap. 1 : SP – Décl. et appel d’une procédure : form e générale

� Déclaration d’une procédure

� Appel de la procédure ( ≈ instruction)

procedure Nom_de_procedure ( Parametres_Formels ) is

-- Partie déclarative

-- instructions….

end Nom_de_procedure;

Nom_de_procedure ( Parametres_D_Appel ) ;

Chap. 1 : SP - Paramètres formels et paramètres d’ap pel

� Paramètres formels

� Matérialisent les échanges d’information entre S.-P. et programme d’appel

� Permettent de décrire le traitement effectué par le S.-P.

� Paramètres d’appel (valeurs ou variables figurant d ans l’appel)

� Valeurs ou variables échangées au moment de l’appel

� Sens des échanges (modes de passage) (page 29)

� in : valeur reçue par le S.-P. Le paramètre se comporte comme une constante dans le S.-P. (il ne peut pas modifier sa valeur)

� out : valeur uniquement fixée par le S.-P. Le paramètre se comporte comme une variable affectée par le S.-P. La valeur précédant l’appel du S.-P. est inutilisée et de toutes façons écrasée par la valeur fixée par le S.-P.

� in out : valeur modifiée par le S.-P. Le paramètre se comporte comme une variable dont la valeur est transmise au S.-P. puis modifiée par lui.

Chap. 1 : SP – Exemples de spécification de SP

� Si le mode de passage n’est pas spécifié � c’est le mode IN par défaut

� Si le S.-P. est une fonction, TOUS les paramètres formels sont

� Obligatoirement en mode IN

� Exemples : donner la spécifications d’un sous-progr amme qui

� affiche à l’écran le contenu d’une variable de type Tab

� fait le tri d’un tableau de type Tab

� permute les valeurs contenues dans 2 variables entières

� lit des valeurs fournies au clavier et les range dans un tableau

� Calcule le produit scalaire de 2 vecteurs

Chap. 1 : SP - Portée d’un objet ( variable ou sous- programme)

� Définition� Portée d’un objet dans un programme = zone du programme dans laquelle

l’objet est vu (et donc utilisable)� La portée d’un objet

� Commence à la déclaration de cet objet� Se termine au « end » du bloc dans lequel l’objet est déclaré

� Exemple

procedure Mon_Prog is

A , X : Integer ;

procedure Toto is

I, X : Float ;begin

end Toto;

end Mon_Prog ;

Portée de I et X (2)

Portée de A et X (1)

Chap. 1 : SP - Effet de bord (exemple) 1/2

procedure Exemple isA, B : Integer ;

------------------------------------------------procedure Permuter(X, Y : in out Integer ) is

Aux : Integer;begin

Aux := X; X := Y; Y := Aux;

end Permuter ; ----------------------------------------------------begin

A:=10 ; B :=20 ;Permuter (A, B) ; put (« A = ") ; put (A) ; put (« B = ") ; put (B) ;

end Exemple ;

procedure Exemple isA, B : Integer ;

------------------------------------------------procedure Permuter is

Aux : Integer;begin

Aux := A; A := B ; B := Aux ;

end Permuter ; ------------------------------------------------begin

A:=10 ; B :=20 ;Permuter ; put (« A = ") ; put (A) ; put (« B = ") ; put (B) ;

end Exemple ;

Effets de bord

Chap. 1 : SP - Effet de bord (exemple) 2/2

procedure Exemple is

procedure Permuter(X, Y : in out Integer ) isAux : Integer;

beginAux := X; X := Y; Y := Aux;

end Permuter ; ---------------------------------

A, B : Integer ;

beginA:=10 ; B :=20 ;Permuter (A, B) ;

put (A) ; put (B) ; end Exemple ;

procedure Permuter isAux : Integer;

beginAux := A; A := B; B := Aux;

end Permuter ; ------------------------

A, B : Integer ;

beginA:=10 ; B :=20 ;Permuter ; put (A) ; put (B) ;

end Exemple ;

INCORRECT

Chap. 1 : SP - Emboîtement de S/P

Variables et S.-P. visibles

procedure PRINCIPALE isToto : Integer ; procedure SP1(Params1 ….) is

Toto1 : Integer ;begin --SP1

-- Instructionsend SP1 ;procedure SP2(Params2 ….) is

Toto2 : integer;procedure SP2_1(Params21) is

Toto21 : Integer ;begin -- SP2_1

-- Instructionsend SP2_1;

begin --SP2-- Instructions

end SP2 ;begin -- PRINCIPALE

-- Instructionsend PRINCIPALE ;

Toto, Params1, Toto1SP1

Toto, Params2, Toto2Params21, Toto21,SP1, SP2_1

Toto, Params2, Toto2 SP1, SP2

Toto,SP1, SP2

Chapitre 2

Analyse descendante et méthodologie de développement d’un programme

Chap. 2 : Méthodologie de développement d’un progra mme

� Analyse et Conception � Analyse et compréhension du cahier des charges

� identifier les données d’entrée du programme, les fonctionnalités à développer et les résultats attendus

� Choix des structures de données adaptées aux besoins� Elaboration de l’algorithme principal

� Décomposition en fonctionnalités

� Implémentation de certaines fonctionnalités par app el à des sous-programmes (abstraction).

� Spécification de ces sous-programmes (? Nom, Paramètres formels ?)

� Identification des jeux de tests afin de valider le bon fonctionnement du programme final lorsqu’il sera terminé

� Elaboration de l’algorithme de chaque sous-programme

� Codage et mise au point� Codage de chaque sous-programme et tests unitaires

� Décomposition en s.-p. (etc)

� Codage de l’algorithme principal et tests fonctionnels

Chap. 2 : Analyse descendante - mise en œuvre sur un exemple

� Cahier

des charges

Mon_Programme

Saisir une nouvelle suitede10 éléments

Calculer la somme des éléments de la suite

Calculer la moyenne des éléments de la suite

Afficher la suite

� Pour une suite donnée, l’utilisateur du programme pourra choisir l’action qu’il souhaite exécuter à partir d’un menu qui s’affichera à l’écran

� Plusieurs suites pourront être traitées séquentiellement

� Phase d’analyse et de conception � Analyse du cahier des charges

� Pour cet exemple simple :� Données d’entrée du programme

� 10 valeurs fournies par l’utilisateur (saisies au clavier)

� Résultats attendus (� affichés à l’écran)� La somme des valeurs

� La moyenne des valeurs

� Fonctionnalités � Acquisition et stockage des 10 valeurs fournies dans un tableau

� Calcul de la somme d’un tableau

� Calcul de la moyenne d’un tableau

� Analyse et Conception � Analyse du cahier des charges

� Choix des structures de données adaptées aux besoins� Elaboration de l’algorithme principal

� Décomposition en fonctionnalités

� Implémentation de ces fonctionnalités par des sous-programmes.

� Spécification de ces sous-programmes

Structures de données et variables

Mon_Tableau : tableau de 10 composantes entières

Arret_Demande : booléen

Algorithme

Arret_Demandé false Saisie_Faite false

Tant que Arret_Demandé = false répéter

afficher le menu des actions possibles

lire (saisir) l’action souhaitée par l’utilisateur

en fonction de l’action souhaitée

lire (saisir) une suite des 10 valeurs fournies par l’utilisateur

Saisie_Faite true

afficher la suite à l’écran (si Saisie_Faite)

afficher la somme des valeurs (si Saisie_Faite)

afficher la moyenne des valeurs (si Saisie_Faite)

arrêter le programme :

Fin tant que

Arret_Demandé true

Structures de données et variables

Mon_Tableau : tableau de 10 composantes

Arret_Demande : booleen

Arret_demandé false

Tant que Arret_Demandé = false répéter

afficher le menu

lire (saisir) l’action souhaitée par l’utilisateur

en fonction de l’action souhaitée

saisir et enregistrer la suite de valeurs

Saisie_Faite true

afficher la suite à l’écran

afficher (la somme des valeurs)

afficher (la moyenne des valeurs)

Arret_Demandé true

Fin tant que

� Appel à un sous-programme Afficher_menu

� Appel à un s-p Afficher_Suite

� Appel à un s-p Calculer_Somme

� Appel à un s-p Calculer_Moyenne

� Appel à un s-p Saisir_Suite

Chap. 2 : Spécification des sous-programmes

� Spécifier un sous-programme c’est définir

� Le Nom et l’objectif du sous-programme

� Les informations qu’il va utiliser (paramètres en entrée)

� Les informations qu’il va générer (paramètres en sortie)

� Les informations qu’il va modifier (paramètres en entrée-sortie)

� Bonnes pratiques

� Un seul traitement par sous-programme

� Ne pas mélanger entrées/sorties (interface utilisateur) et traitement

� Choisir des noms de sous-programmes représentatifs

� Écrire le corps du sous-programme revient à écrire l’algorithme correspondant au traitement que doit faire le sous- programme

� Si l’algorithme est complexe, on applique à nouveau une analyse descendante

Chap. 2 : Spécification des sous-programmes de l’ex emple

� Afficher_Menu� Objectif : afficher les différentes actions offertes à l’utilisateur� Données d’entrée : aucune� Résultats générés : aucun

� Saisir_Suite� Objectif : saisir un tableau de valeurs � Données d’entrée : aucune (les donnée sont fournies par l’utilisateur via le

clavier) � Résultats générés : le tableau de valeurs

� Calculer_Somme� Objectif : calculer la somme des éléments d’‘un tableau� Données d’entrée : le tableau de valeurs� Résultats générés : la somme

� Remarque : � Algorithmes associés très simples � pas de décomposition supplémentaire

� Phase d’analyse

� Globalement indépendante du langage support

� Codage et tests

� Développer PROGRESSIVEMENT chaque sous-programme

� Ecrire pour chaque sous-programme développé un sous-programme de test qui

� Définit et initialise les variables qui servent au test

� Affiche le résultat attendu pour ces valeurs

� Appelle le sous-programme

� Affiche les valeurs obtenues

Chapitre 3

Types Tableaux Non Contraints Algorithme de recherche dans un tableau

Chap. 3 - Type tableau contraint ou non contraint

� Un tableau permet de regrouper des éléments de même nature

� Pour déclarer un type tableau, on précise� Le type de l’indice qui permet de le parcourir (plusieurs dim. possibles)� Le type des éléments contenus dans le tableau (les composantes)

� 2 possibilités pour déclarer un type tableau� Déclaration d’un type contraint

� �on fixe définitivement la taille de ce type de tableaux

� Déclaration d’un type non contraint � �on ne fixe pas une taille unique à la déclaration du type. Des tableaux

distincts pourront avec des tailles différentes

type Nom_Du_Type is array (type_de_l’indice ) of type_des_composantes ;

Chap. 3 - Type tableau contraint

� Déclaration : Le nombre de composantes est fixé à l a déclaration du type

� Déclaration des variables

� Bien adapté lorsque toutes les variables de type tableau ont toujours le même dimensionnement et la dimension est connue avant l’ exécution du programme

� Lourdeur si ce n’est pas le cas

type Un_Tab_contraint is array (Integer range 1..20) of Float ;

type Un_Autre_Tab_Contraint is array (Character range ‘A’..’Z’) of Float ;

A, B : Un_Tab_contraint ; -- A et B de même taille : 20 float chacun

X,Y : Un_Autre_Tab_Contraint ; -- X et Y de même taille : 26 character chacun

Chap. 3 - Type tableau non contraint (NC)

� Déclaration du type

� Exemples

� Caractéristiques importantes

� Les paramètres formels d’un ss-programme peuvent être non contraints� Comment écrire ce sous-programme ?

� Une variable d’un type tableau doit être dimensionnée lors de sa déclaration

� pb du dimensionnement

type identificateur_du_type is array (type_indice range <>) of type_composantes ;

type Un_Vecteur is array (Integer range <>) of Integer ;type Un_Tab is array (Character range <>) of Float ;

Vec1 : Un_Vecteur(0..9); Vec2 : Un_Vecteur(1..1000);

Tab1 : Un_Tab(‘a’ ..’z’); Tab2 : Un_Tab(‘A’..’E’);

Chap. 3 – Sous-programmes et types tab non contraint (1/2)

type Un_Vecteur is array (Integer range <>) of Integer ;

function Indice_Du_Min (De : in Un_Vecteur ) return Integer is-- retourne l’indice du min du vecteur De

begin…

end Indice_Du_Min ;

X : Un_Vecteur ( 1..10) ;Y : Un_Vecteur ( 0..100) ;

begin --Exemple-- Saisie de X et de Y

…-- afficher l’indice du min de X ?

Put(Indice_Du_Min(X)) ;

-- afficher l’indice du min de Y ?Put(Indice_Du_Min(Y)) ;

-- afficher l’indice du min dans la portion (tranche) 20..50 de YPut(Indice_Du_Min(Y(20..50))) ;

end Exemple ;

Exemple : SP qui retourne l’indice de la valeur minimum d’un tableau de type non contraint

1- spécification du SP et exemples d’appel

Chap. 3 – Sous-programmes et types tab non contraint (2/2)

procedure Exemple istype Un_Vecteur is array (Integer range <>) of Integer ;function Indice_Du_Min(De : in Un_ Vecteur ) return Integer is

Imin : integer; -- retourne l’indice du minimumbegin

Imin := De’first;for I in De’firtst+1..De’last loop

if De(I) < De(Imin) thenImin := I;

end if;end loop;

…return Imin;

end Indice_Du_Min ;X : Un_Vecteur (1..10) ;Y : Un_Vecteur (0..100) ;

begin…

end Exemple ;

Exemple : SP qui retourne l’indice de la valeur minimum d’un tableau de type non contraint

1- spécification du SP et exemples d’appel

2- écriture du SP

Chap3 - Problème du dimensionnement d’une variable t ableau (1/5)

� Différentes situations� On connait la dimension du tableau lorsqu’on écrit le programme

� pas de problème

� On ne connait pas la dimension du tableau lorsqu’on écrit le programme� on ne peut déclarer la variable de type tableau

il faut d’abord déterminer la dimension de ce tableau

procedure Exemple istype Un_Vecteur is array (Integer range <>) of Integer ;…

X : Un_Vecteur (1..10) ;Y : Un_Vecteur (0..100) ;

begin…

end Exemple ;

procedure Exemple istype Un_Vecteur is array (Integer range <>) of Integer ;

procedure Saisir (T : out Un_Vecteur) is

…end Saisir ;function Indice_Du_Min (De : in Un_Vecteur ) return Integer is

…end Indice_Du_Min ;Dim : Integer ;Mon_Tab : Un_Vecteur (1..Dim ) ;

beginput (« entrez la dimension »);Get (Dim ) ;

…Saisir(Mon_Tab) ;

…put(Indice_Du_Min(Mon_Tab));

…end Exemple ;

valeur ???

1ère tentative :

La dimension du tableau est fournie par l’utilisateur en début d’exécution

=> échec

C’est trop tard ! Mon_Tab a été créé avec une taille indéterminée …

…end Saisir ;function Indice_Du_Min (De : in Un_Vecteur ) return Integer is

…end Indice_Du_Min ;Dim : Integer;

beginput (« entrez la dimension »);Get (Dim);declare

Mon_Tab : Un_Vecteur(1..Dim ); begin

Saisir(Mon_Tab) ;…

put(Indice_Du_Min(Mon_Tab));…

end ;end Exemple ;

2ème tentative :

La dimension est fixée avant la déclaration

� Utiliser un bloc declare

…� begin

…� end;

Mon_Tab est déclaré APRES

On fixe d’abord Dim

end Saisir ;function Indice_Du_Min (De : in Un_Vecteur ) return Integer isend Indice_Du_Min ;

function Donne_La_Dimension return Integer isD: integer;

beginput (« entrez la dimension »);Get(D);

return D;end Donne_La_Dimension ;

Mon_Tab : Un_Vecteur (1.. Donne_La_Dimension ) ;

beginSaisir(Mon_Tab) ;

…put(Indice_Du_Min(Mon_Tab));

…end Exemple ;

3ème tentative :

La dimension est fixée par une fonction

� Avantage : ne nécessite pas le bloc

declare…begin…end;

procedure Exemple istype Un_Vecteur is array (integer range <>) of Integer ;

positivefunction Donne_La_Dimension return Integer is

…end Donne_La_Dimension ;

function Saisir return Un_Vecteur is-- retourne un vecteur dont la dimension et -- les valeurs sont saisies au clavier

V : Un_Vecteur (1..Donne_La_Dimension );begin

put("Saisir " & integer’image(V’last) & " entiers : " );for I in V’range loop

get(V(I));end loop;

return V;end Saisir;MonTab : Un_vecteur := Saisir ;

begin… put(Indice_Du_Min(Mon_Tab));…

end Exemple;

4ème tentative :

La dimension ET le tableau sont fixés par des fonctions

Mon_Tab est dimensionnélors de l’affectation parla fonction Saisir.

Attention, MonTab’first =positive ’first = 1maissi l’indice de Un_Vecteurétait integer , MonTab’first =integer ’first = -2147483648

Chap. 3 : À retenir (1/2)

� Souplesse des types « tableau non contraint »� Algorithmes généraux basés sur les attributs ‘first, ‘last, ‘range, ‘length� Possibilité de manipuler des « tranches de tableaux »

� Intérêt à utiliser des paramètres formels de S/P d’ un type tableau non contraint � Intérêt : sous-programme réutilisable pour des tableaux de toute dimension� Pousse à la généralisation (utilisation des attributs et non de valeurs particulières)

� Les variables (en particulier les paramètres d’appe l du S/P) sont obligatoirement contraintes lors de leur déclaratio n.

X : Un_Vecteur (1..10) ;Y : Un_Vecteur (0..100) ;

beginY( 50..55 ) := X( 3..8) ; -- 6 éléments copiésif X (1..4) < Y (5..8) then … -- 4 éléments comparés…

end Exemple ;

Chap. 3 - À retenir (2/2)

� Toute variable doit être contrainte lors de sa décl aration

� Plusieurs solutions pour « contraindre » une variable de type tableau n on contraint

� Technique 1 : Utiliser un bloc DECLARE dans le programme principal pour déclarer la variable après avoir déterminé sa dimension.

� Technique 2 : Utiliser une fonction de dimensionnement au moment de la déclaration, ex : Var : Un_Vecteur(1 .. Donner_Dimension);

� Technique 3 : Utiliser une déclaration+affectation à l’aide d’une fonctiond’initialisation, du type Var : Un_Vecteur := Saisir; La fonction d’initialisation peut elle-même utilsier une fonction de dimensionnement

� Un Type prédéfini non contraint important : le type STRING

Chap. 3 - Type prédéfini String ( chaîne de caractèr es)

� Déclarations� Le type String est un type non contraint prédéfini (connu du langage)

� Littéraux (valeurs de) chaînes de caractères �

� Déclarations de variables (il faut TOUJOURS que la dimension soit connue !)

"c'est une chaine" -- C'est une valeur de type string"s" -- C'est aussi une valeur de type string

type String is array ( Positive range <> ) of Character ;

Ch : String (1 .. 4) ;

Mess : String (1 .. 7) := "bonjour ";Texte1 : String := " ça va ?" ;Texte2 : String := Mess & Texte1;Faux : String ; -- erreur !!

Chap. 3 - Type prédéfini String ( chaîne de caractèr es)

� Opérations sur les String

(identiques à celles disponibles sur des tableaux à 1 dimension)� Attributs

� first , last , length , range

� Image , value

� AffectationRemarque : même longueur de part et d'autre de l'affectation

Integer'Image(123) = " 123"Integer'Value(" -123") = -123

type Couleur is (rouge, jaune, vert, bleu);Couleur'Image(rouge) = " ROUGE"

Ch : String (1 .. 5) ;Mess : String (1 .. 7) := "bonjour";

beginCh := "salut" ;Mess := "salut--" ;Ch := Mess(1.. 4) ; --erreur !!

Chap. 3 - Type prédéfini String (chaîne de caractère s)

� Opérations sur les String � Égalité

� Il faut des chaînes de même longueur de part et d’autre de l’égalité

� Ordre lexicographique� Chaînes quelconques

� Concaténation

"ABC" > "AB" ;"ABC" < "CD" ;

Mess : String (1 .. 7) := ("bonjour") ;Texte : String := (" ca va?") ;

beginPut_Line (Mess & Texte);Put_Line (Mess & '!');Put_line('A '& 'B');

end Exemple;

Chap. 3 – Le paquetage Ada.Text_IO

procedure Put(Item : in Character); -- affichage d’un caractèreprocedure Put(Item : in String); -- affichage d’un stringprocedure Put_Line(Item : in String) ; -- affichage puis retour-ligne

procedure New_Line(spacing : in positive_count := 1) ;-- spacing retours-ligne (par défaut : 1)

procedure Get(Item : out Character) ; -- lecture d’un caractèreprocedure Get(Item : out String) ; -- lecture d’un string -- il faut fournir autant de caractères que la longueur de Itemprocedure Get_Line(Item : out String ; Last : out Natural) ;-- lit les caractères fournis jusqu'à ce qu’une fin de ligne soit rencontrée-- ou que la longueur de Item soit atteinte.-- Last donne l'indice dans la chaîne du dernier caractère lu

procedure Skip_Line; -- « saute » tous les caractères jusqu’au retour-ligneG.AURIOL, C. MERCE, P. ESQUIROL

Chap. 3 - Algorithmique : recherche d’une valeur dan s un tableau

� Problème : � On souhaite écrire un sous-programme qui détermine si une valeur donnée

figure dans un tableau. � Si oui, on veut connaitre l’indice de la première occurrence de cette valeur

dans le tableau.� Spécification du sous-programme

� Données en entrée� La valeur cherchée

� Le tableau de valeurs

� Résultats en sortie� Un booléen qui indique si la valeur a été trouvée

� L’indice de la 1ère occurrence de la valeur cherchée

Chap. 3 - Recherche d’une valeur dans un tableau - 1 ere version

procedure Chercher ( Val : in Integer ; Dans : in Un_Vecteur;Trouve : out Boolean ; Pos : out Integer ) is

-- cherche Val dans le tableau Dans ; -- Trouve contient True si Val appartient à Dans ; Pos est l’indice de Val dans Dans

beginTrouve := FALSE;for I in Dans’range loop

if Dans(I) = Val thenTrouve := TRUE;Pos := I ;

end if;end loop ;

end Chercher ;

Commentaires: � cet algo fournit en réalité l’indice de la dernière occurrence car ilcontinue à parcourir le vecteur même lorsqu’on a tr ouvé la valeur

Algorithme incorrect !!

Chap. 3 - Recherche d’une valeur dans un tableau - 2 ème version

beginI := Dans’first ;while Dans (I) /= Val loop

I := I+1 ;end loop;...

end Chercher ;

Que se passe t-il si Val ne se trouve pas dans le vecteur Dans ??

Algorithme incorrect !!

beginI := Dans’first ;while I <= Dans’last and then Dans (I) /= Val loop

I := I+1 ;end loop ;if I > Dans’last then

Trouve := False ; else

Trouve := True; Pos := I ;end if ;

end Chercher ;

Algorithme correct et élégant … maisspécifique à ADA !!

beginI := Dans’first ; Trouve := false ;while I <= Dans’last and not trouve loop

if Dans(I) = Val thenTrouve := true;Pos := I ;

elseI := I+1;

end if ;end loop ;

end Chercher ;

Algorithme de recherche classiqueA RETENIR !

Chapitre 4

Récursivité

Chap. 4 : Récursivité - Introduction

� Définition récursive� "Un sous-programme récursif est un sous-programme récursif"

� Définition plus sérieuse� Un sous-programme est dit récursif lorsqu'il fait appel à lui-même

� Vous connaissez déjà!

Exemple en math : calcul de factorielle n� Définition de n! : n! = n × (n-1)!

0! = 1� Exemple 4! = 4 × 3!

3! = 3 × 2!

2! = 2 × 1!

1! = 1 × 0!

0! = 1

Cas trivial

La dimension change

Chap. 4 : Récursivité - 1 er exemple

� Écriture récursive de factorielle

procedure Test_Facto is

function Facto (N: in Natural) return Positive is…end Facto ;

Nb : natural; -- nombre lu

beginput ("entrer un nombre positif ou nul");get ( Nb ); put ( Nb ); put( " ! = " ); put (Facto(Nb) );

end Test_Facto;

Chap. 4 : Récursivité - 1 er exemple

� Écriture récursive de factorielle

function Facto (N: in Natural) return Positive isResu : Positive ;

return Resu;end Facto;

-- 0! = 1

-- n! = n×(n-1)!

if N=0 thenResu := 1;

elseResu := N*Facto(N-1):

end if;

Chap. 4 : Récursivité - Principe d’un fonctionnemen t récursif

� Un sous-programme récursif a le même fonctionnement qu’un sous-programme non récursif.

� Principe de fonctionnement� Exécution du sous-programme récursif(version 1)

� Appel récursif � interruption de la version en cours

� Le système sauvegarde dans une pile l'environnement du ss-prgme� Adresse de retour

� Valeur des paramètres de mode in de la version en cours

� Valeur des variables locales de la version en cours

� Une nouvelle version du sous-prgme (version 2) s’exécute avec une nouvelle version des paramètres formels in (leur valeur est celle spécifiée dans l’appel) ;

� Fin d'exécution de cette nouvelle version (version 2) ; retour des valeurs des paramètres de mode out et in out . ou du résultat de la fonction

� Reprise de la version appelante (version 1) là où elle s'était interrompue au moment de l’appel avec son environnement restauré tel qu’elle l’avait laissé

Chap. 4 : Récursivité - Fonctionnement de la Pile

� Qu’est ce que la pile ?� Zone mémoire particulière réservée à chaque programme

� Rôle� Stocker les valeurs des variables locales et des paramètres d'un s-p et

l’adresse de retour avant tout appel à un autre sous-programme� Gestion transparente pour l'utilisateur

� S/P récursif : à chaque appel récursif, toutes les variables locales sont stockées dans la pile (empilées) autant de fois qu' il y a d'appels récursifs

� En fin d’exécution d’une version, les variables son t « dépilées » pour que l’on retrouve l’environnement de la version précéde nte

� Attention au "débordement de pile" : Exception « Sto rage_Error »

C’est la manifestation d’une récursion infinie :

- l’arrêt de la récursion est mal défini

- l’appel récursif est erroné

Chap. 4 : Récursivité - Arbre d’appel de Facto pour N=3

function Facto (N: in Natural) return Positive isResu : Positive;

beginif N=0 then

Resu := 1;else

Resu := N * Facto (N-1);end if;return Resu;

end Facto;

put (Facto (3) ) ;

end Test_facto;

Programme Principal

put( ? )

Facto(N1) N1=3 Resu1=

Facto(N4) N4=0 Resu4= 1

put(6)

Chap. 4 : Récursivité - version itérative / version récursive

� Pour des problèmes simples, il existe une version i térative simple

� Comparer version itérative et version récursive

function Facto ( N : in Natural) return Positive isResu : Positive := 1;

beginfor J in 1..N loop

Resu := J * Resu ;end loop;return Resu;

end Facto;

Chap. 4 : Récursivité – Exemples

� Qu’affiche la procédure?

procedure Test_Toto2 is

procedure Toto (N: in Integer) isbegin

if N > 0 thenToto ( N-1);

end if ;put ( N , 5);

end Toto ;

beginToto ( 4 ) ;

end Test_Toto2;

procedure Test_Toto3 is

procedure Toto (N: in out Natural) isbegin

if N > 0 thenN := N-1;Toto (N);

end if ;put (N, 5);

end Toto ;

X: Integer :=4;

beginToto (X) ; put ( X ) ;

end Test_Toto3;

Chap. 4 : Récursivité - Analyse récursive d'un probl ème

� Quand envisager une conception récursive?� Lorsque l’algo itératif n’est pas évident� Lorsqu'il est facile de décomposer le problème en un ou plusieurs sous-

problèmes de même nature mais de taille plus petite � Une conception récursive comprend souvent 3 étapes non forcément

séquentielles� Décomposition du problème (la taille doit diminuer!)� Paramétrage (la taille est un paramètre)� Identification du (des) cas trivial(aux)

� Forme générale d'un algorithme récursif

� Il faut qu'un algorithme récursif se termine. Il fa ut montrer que

� la décomposition simplifie le problème et converge vers le cas trivial !

if cas trivial thenCalcul direct

else Appels récursifs

end if ;

Chap. 4 : Récursivité - Exemple : Inversion d’un vec teur (1/6)

� Quel est le problème?

� On a

� On veut

� Une analyse récursive comprend souvent 3 étapes non forcément séquentielles� Paramétrage du S/P

� Le vecteur à inverser� Rmq. : la taille d’un vecteur est intrinsèque à celui-ci � ce n’est pas

un paramètre (si on connaît X, on connaît aussi X’length)

� Identification du (des) cas trivial(aux)� Vecteur de taille nulle ou de taille 1

(dans ces cas l’inversion ne fait rien)

� Décomposition en ss-pbs de plus petite taille

10 30 20 15 40

40 15 20 30 10

� Structure de données

� Obligatoirement un tableau non contraint car le S/P va manipuler des vecteurs de tailles dégressives

� Paramétrage du sous-programme� Lié au besoin : veut-on conserver le vecteur initial ?

� si procédure

� si fonction

type Vecteur is array (Integer range <>) of Integer ;

procedure Inversion ( V : in out Vecteur ) ;

function Inversion ( V : in Vecteur ) return Vecteur ;

type Vecteur is array ( Integer range <> ) of Integer;

function Inversion ( V : in Vecteur ) return Vecteur isW : Vecteur(V’range);

beginif V’length <=1 then -- cas trivial

W := V; else -- appels récursifs

W(W’first) := V(V’last);W(W’last) := V(V’first);W(W’first+1..W’last-1) :=

Inversion(V(V’first+1..V’last-1));end if;

return W;end Inversion;

Fonction récursive

procedure Test_Inversion isX,Y : Vecteur (1..5);begin

X := (10, 30, 20, 15, 40) ;put ( " attendu apres inversion : 40 15 20 30 10 " ); Y := Inversion ( X ) ;-- affichage du vecteur inverséput ( " obtenu apres inversion : " ) ; for I in Y'range loop

put ( Y(I) ) ;end loop;

end Test_Inversion;

Test de la fonction récursive

procedure Inversion ( V : in out Vecteur ) is

Temp : Integer ;

if V'length = 0 then

null ;

Temp := V (V'last) ;

V (V'last) := V (V'first) ;

V (V'First) := Temp ;

Inversion ( V ( V'first+ 1 .. V'last- 1) ) ;

end if ;

end Inversion;

Procédure récursive

procedure Test_Inversion isX : Vecteur (1..5);

beginX := (10, 30, 20, 15, 40) ;put ( " attendu apres inversion : 40 15 20 30 10 " ); Inversion(X) ;-- affichage du vecteur inverséput ( " obtenu apres inversion : " ) ; for I in X'range loop

put(X(I)) ;end loop;

end Test_Inversion;

Test de la procedurerécursive

Chap. 4 : Récursivité - Exemple : Les tours de Hanoi

� La fin du monde!� Une légende asiatique raconte que dans un temple se trouvent trois

poteaux sur lesquels s'empilent 64 disques d'or. Les prêtresdéplacent continuellement les disques selon les règles édictées ci-après. D'après cette même légende, le dernier déplacement dedisque marquera la fin du monde

Chap. 4 : Récursivité - Exemple : Les tours de Hano i

� Règles de déplacement

� On ne déplace qu'un seul disque à la fois

� On ne peut déplacer que le disque situé au sommet d'un poteau

� On ne peut poser un disque que sur un poteau vide ou sur un poteau contenant des disques plus grands

� On souhaite écrire un programme qui écrit la suite des déplacements à effectuer

Chap. 4 : Récursivité - Les tours de Hanoi avec 1 di sque

� Exemple : déplacer 1 disque du socle ‘A’ vers le so cle ‘B’

� Liste des déplacements :

A � B

Socle A Socle B Socle C Socle A Socle B Socle C

Chap. 4 : Récursivité - Les tours de Hanoi avec 2 di sques

� Exemple : déplacer 2 disques du socle ‘A’ vers le s ocle ‘B’ (en utilisant ‘C’ comme socle intermédiaire)

� Déplacements:

A � C

A � B

C � B

Chap. 4 : Récursivité - Les tours de Hanoi avec 3 d isques !

� Exemple avec 3 disques

� DéplacementsA � BA � CB � CA � B

Chap. 4 : Récursivité - Les tours de Hanoi avec 3 disques !

C � AC � BA � B

� DéplacementsA � BA � CB � CA � B

Chap. 4 : Récursivité - Les tours de Hanoi : analys e récursive

� Une analyse récursive comprend souvent 3 étapes non forcément séquentielles

� Identification du (des) cas trivial(aux)

� Tour n’ayant aucun disque ! (il n’y a rien à faire)

� Paramétrage du S/P

� Le nombre de disques à déplacer � N

� Le nom des socles

� Socle de départ � Dep

� Socle d’arrivée � Arr

� Socle intermédiaire � Int

� Décomposition du problème initial en sous-problèmes de même nature mais de plus petite taille

Chap. 4 : Récursivité - Les tours de Hanoi : décompo sition récursive

Pour déplacer N disques d’un socle de départ Dep vers un socle d’arrivée Arren utilisant un socle intermédiaire Int , il faut

- Déplacer N-1 disques de Dep vers Int en utilisant Arr comme socle intermédiaire

- Déplacer un disque de Dep vers Arr

- Déplacer N-1 disques de Int vers Arr en utilisant Dep comme socle intermédiaire

Dep Arr Int

Chap. 4 : Récursivité - Les tours de Hanoi

procedure Test_Hanoi is

procedure Hanoi (N : in Natural; Dep, Arr, Int : in Character) isbegin

if N /= 0 thenHanoi( N-1, Dep, Int, Arr);put (" déplacer un disque de "); put (Dep);put(" vers "); put (Arr); new_line;Hanoi( N-1, Int, Arr, Dep);

end if;end Hanoi;

Nb: natural;

beginput (" Nombre de disques ? "); get (Nb) ; Hanoi (Nb, 'A', 'B', 'C');

end Test_Hanoi;

Dép Arr Int.

Dép Arr Int

Dép Arr Int.

Chap. 4 : Récursivité - Les tours de Hanoi : arbre d ’appel

3,A,B,C

2,A,C,B 2,C,B,A

1,B,C,A1,A,B,C

0,C,B,A0,A,C,B

Socle A

Socle B

Socle C

0,B,A,C

0,A,C,B

1 : A vers B 2 : A vers C 3 : B vers C 4 : A vers B 5 : C vers A

1,C,A,B

1,A,B,C

0,C,B,A

0,B,A,C 0,A,C,B 0,C,B,A

6 : C vers B 7 : A vers B

Chap. 4 : Récursivité - Les tours de Hanoi et la fin du monde !

� Calcul du nombre de déplacements à effectuer pour n disquesND(n) = 2 × ND (n-1) +1ND(0) = 0

Ce qui donne en « dérécursivisant »ND(1) = 1ND(2) = 2 × ND (1) + 1 = 2 + 1ND(3) = 2 × ND (2) + 1 = 22 + 2 + 1

ND(n) = 2n-1 + … + 2 + 1 = ∑ 2� =2� − 1��

� Calcul du temps mis pour déplacer 64 disques� On suppose 1 déplacement = 1 sec� Temps total ≈ 264 sec ≈ 0,2 × 1020 sec

� 1 année = 31 536 000 sec ≈ 0.3 × 108 sec

� 1 siècle ≈ 0.3 × 1010 sec

� Il faudra ≈ 1010 siècles pour déplacer les tours

Chapitre 5

Les pointeurs

Chap. 5 : Les pointeurs - Introduction

� Les variables manipulées jusqu’à présent sont dites statiques

� Statiques car explicitement déclarées� Déclarées en précisant

� Leur nom

� Leur type � Réservation figée d'un espace mémoire

� Exemple avec des tableaux

Type Un_Tab_Contraint is array (Integer range 1..5) of Float ;

Type Un_Tab_NON_Contraint is array (Integer range <>) of Float ;

X : Un_Tab_Contraint ;

Y : Un_Tab_Non_Contraint (1..10) ;

� Attention : une fois déclarées, X et Y ne peuvent pas changer de taille � LIMITATION

Chap. 5 : Les pointeurs – Exemple de liste

� Gérer la liste des personnes s'inscrivant pour une course à pieds et maintenir l’ordre alphabétique de la liste� On ne sait pas a priori combien de personnes vont participer à cette

course� Des nouveaux participants peuvent arriver à tout moment

� Des participants peuvent annuler à tout moment

� Difficile dans ces conditions de dimensionner une variable de type tableau

� � Besoin : on veut pouvoir créer des variables au fur et à mesure des besoins en cours d’exécution du programme � variables dynamiques

� � La notion de pointeur répond à ce besoin

Chap. 5 : Les pointeurs - Allocation dynamique

� Allocation dynamique� Mécanisme permettant de réserver « dynamiquement » de la mémoire

c’est à dire de créer « dynamiquement » une variable� Dynamiquement � en cours d’exécution du programme (au fur et à mesure

des besoins)� La réservation se fait dans une zone mémoire particulière de la machine

(appelée tas)� Les variables créées dynamiquement peuvent changer de place en mémoire

� Les variables de cette zone mémoire ne sont accessib les que par l’intermédiaire de leur adresse (par des pointeurs)

� Définition� Pointeur : variable contenant l’adresse d’une autre variable (ou d’un sous

programme- hors contexte de ce module) ;� On dit qu’elle « pointe » sur une autre variable

� Exemple : liste des coureurs

Chap. 5 : Les pointeurs – Utilisation de variables d ynamiques

� Rappels : utilisation de variables statiques (ex. t ableau)� Déclaration d’un type

� Déclaration d’une variable de ce type

� Accès à la variable par son nom

� Pointeurs et variables dynamiques� Déclaration d’un type « pointeur »� Déclaration d’une variable de type « pointeur »� Création et affectation d’une variable dynamique (allocation mémoire)� Accès au contenu� Libération espace mémoire (désallocation)

type Un_Vect is array (Integer range 1..10) of Integer ;

Mon_Vecteur : Un_Vect ;

Mon_Vecteur ( 1 ) := 8 ;

� Déclaration d’un type pointeur

� Forme générale

� Exemples

� Déclaration d’une variable d'un type pointeur

� Par défaut, en ADA, la valeur d’une variable de typ e pointeur est « null » lors de la déclaration

� Le pointeur pointe sur « rien »

� Il n’y a pas eu de réservation mémoire

Chap. 5 : Les pointeurs : déclarations

type Ptr_Int is access Integer ;type P_String is access String;

type Tab is array(1..6) of Boolean ;type Ptr_Tab is access Tab ;

type NomType is access TypePointé ;

P : Ptr_Int ;

M : Ptr_Tab ;

P : Ptr_Int := null ;

M : Ptr_Tab := null ;

Chap. 5 : Les pointeurs : Allocation mémoire (1/3)

� Création d’une variable dynamique � réservation mémoire

� Forme générale

La variable dynamique de NomPointeur est une adresse mémoire.

Le contenu est dénotée par l’expression NomPointeur .all

type NomType is access TypePointé ;

NomPointeur : NomType ;

NomPointeur := new TypePointé ;

-- accès à la variable

NomPointeur.all := xxxx ;

new = « Allocateur »- Cherche une zone disponible en mémoire, de taille adaptée au type pointé.- Réserve cette zone- Retourne l’adresse de la zone

� Exemple de création d’une variable dynamique non in itialisée

(ou Allocation d’un pointeur)

type Un_Ptr_Int is access Integer ;

type Tab is array (1..6) of Boolean ;

type Un_Ptr_Tab is access Tab ;

P : Un_Ptr_Int ; M : Un_Ptr_Tab ;

beginP := new Integer ;M := new Tab ;

� Création d’une variable dynamique initialisée

beginP := new Integer'(23) ;M := new Tab'(others => true) ;

true true true true true true

Chap. 5 : Les pointeurs : Accès à la variable dynam ique (1/4)

� Utilisation des pointeurs : accès aux variables dyn amiques� Forme générale

� Exemple

beginP.all := 23 -- variable pointée par P (dont l’adresse est dans P)M.all(2) := False : -- variable pointée par M (c’est un tableau)

NomPointeur.all « zone pointée » par NomPointeur

P.all (variable pointée par P ; contient 23)

Chap. 5 : Les pointeurs : Accès à la variable dynam ique(2/4)

� Réservation mémoire et initialisation de la zone mém oire réservée

type Ptr_Int is access Integer ;

P : Ptr_Int ; begin

P := new Integer'(23) ;

P : Ptr_Int ; begin

P := new Integer ;P.all := 23 ;

P 23 P ?23

Chap. 5 : Les pointeurs : Accès à la variable dynam ique (3/4)

� variables dynamiques d’un type composé (tableau ou structure)

type Tab is array (1..8) of Boolean ;

type Ptr_Tab is access Tab ;

beginM := new Tab'(others => True) ;for i in Tab'range loop

if M.all(i) then….

end if ;end loop;

type Tab is array (1..8) of Boolean ;type Ptr_Tab is access Tab ;

beginM := new Tab'(others => True) ;for i in Tab'range loop

if M(i) then….

end if ;end loop ; Omission de « .all »

M null ;

M true true true true true true

Chap. 5 : Les pointeurs : Accès aux variables dynam iques (4/4)

� Accès aux variables dynamiques d’un type composé (s uite)

beginM := new Tab'(others => True) ;for i in M.all' range loop

if M.all(i) then…

end if ;end loop;

beginM := new Tab'(others => True) ;

for i in M'range loopif M(i) then

…end if ;

end loop ;

Attribut classique de la variable M.all ( qui est de type Tab)

Chap. 5 : Les pointeurs : pointeur vs. variable dyn amique (1/3)

� Ne pas confondre pointeur et la variable pointée

� Que se passe-t-il à l’exécution ?

P : Ptr_Int ; begin

P := new Integer'(23) ;put ( P ) ;

P : Ptr_Int ; begin

P := new Integer'(23) ;put ( P.all ) ;

Chap. 5 : Les pointeurs : pointeur vs. variable dyn amique (2/3)

� Contenu de P1 et P2 après exécution ? Contenu de P1 .all et P2.all ?

� Dessiner les boîtes !

P1, P2 : Ptr_Int; begin

P1 := new Integer’(23) ; P2 := P1;put ( P1.all ) ;put ( P2.all ) ;

P1 := new Integer’(23) ; P2 := P1 ;P2.all := 21 ;put ( P1.all ) ;put ( P2.all ) ;

Chap. 5 : Les pointeurs : pointeur ou variable dyna mique (3/3)

� Contenu de P1 et P2 après exécution dans chaque cas ? Contenu de P1.all et P2.all ?

� Dessiner les boîtes !

P1, P2 : Ptr_Int;

beginP1 := new Integer’(23) ;P2 := new integer’(21);P2.all := P1.all ;put ( P1.all ) ;put ( P2.all ) ;

P1, P2 : Ptr_Int;

beginP1 := new Integer’(23) ;P2 := new integer’(21);P2 := P1 ;put ( P1.all ) ;put ( P2.all ) ;

Chap. 5 : Les pointeurs : Egalité entre ptrs ou entr e var. pointées

P1 := new Integer’(23) ;P2 := new integer;P2.all := P1.all;-- P1 = P2 ?? -- P1.all=P2.all ??

P1 := new Integer’(23) ; P2 := P1;-- P1 = P2 ?? -- P1.all=P2.all ??

L’expression P1 = P2 vaut TRUE si P1 et P2 contie nnent la même adresse (ie pointent sur la même variable dynamique ou pointent tous les deux sur null )

L’expression P1.all = P2.all prend la valeur TRUE si P1 et P2 pointent sur des variables contenant la même valeur

Chap. 5 : Les pointeurs : utilisation

� Structures de données dynamiques

� Listes � à travers des exemples

� Arbres, graphes –cf. module suivant

� Dimensionnement dynamique de tableaux (sans bloc d eclare)

� En fin de chapitre

Chap. 5 : Les pointeurs - Structure de liste

� Gérer la liste des personnes s'inscrivant pour une course à pieds� On ne sait pas a priori combien de personnes vont participer à cette

course� Des nouveaux participants peuvent arriver à tout moment

� Des participants peuvent annuler à tout moment

� Pour chaque coureur� Nom� Numéro de dossard

Chap. 5 : Les pointeurs : structure de liste

� Structure de données � Déclarations des types

subtype Chaine3 is String(1..3);

type Un_Coureur;type Un_Ptr_Coureur is access Un_Coureur;

type Un_Coureur is recordNom : Chaine3 := (others => ' ');Dossard : Natural;Suivant : Un_Ptr_Coureur;

end record;

Déclaration de la liste : une seule variable quel que soit le nombre d’éléments

Deb_Liste : Un_Ptr_Coureur;

� Gestion de la liste : algorithmes classiques� Parcours de la liste (par exemple pour afficher tous les éléments)� Rechercher si un élément appartient à la liste� Insérer / Supprimer un élément� …

Chap. 5 : Les pointeurs : Affichage de la liste

� version itérative

procedure Afficher_Coureurs (L : in Un_Ptr_Coureur) isAux : Un_Ptr_Coureur := L;

beginPut_Line(" la liste des coureurs est : ");while Aux /= null loop

Put (" ") ;Put ( Aux.all.Nom );Put( Aux.all.Dossard) ;New_Line;Aux := Aux.all.Suivant;

end loop;end Afficher_Coureurs;

Chap. 5 : Les pointeurs : Affichage de la liste

� version récursive

procedure Afficher_Coureurs (L : in Un_Ptr_Coureur) isbegin

if L /= null then-- affichage du 1er coureurPut (" ");Put (L.all.Nom);Put (L.all.Dossard,4);New_Line;-- affichage de la suiteAfficher_Coureurs (L.all.suiv);

end if;end Afficher_Coureurs;

Chap. 5 : Les pointeurs : affichage d’une liste

� Que fait ce sous-programme ?

procedure Afficher_Coureurs (L : in Un_Ptr_Coureur) isbegin

if L /= null then-- affichage de la suiteAfficher_Coureurs (L.all.suiv);-- affichage du 1er coureurPut (" ");Put (L.all.Nom);Put (L.all.Dossard,4);New_Line;

end if;end Afficher_Coureurs;

Chap. 5 : Les pointeurs - Recherche d’un élément dan s une liste

� Le coureur est identifié par son nom

function Chercher_Coureur ( Le_Nom : in chaine3 ; Dans : in Un_Ptr_Coureur ) return Boolean is

Aux : Un_Ptr_Coureur;Trouve : boolean :=false;

BeginAux := Dans;while Aux/=null and not Trouve loop

If Aux.all.nom = Le_Nom thenTrouve := True;

else -- on avance dans la listeAux := Aux.all.suiv;

end if;end loop;return Trouve;

end Ajouter_Coureur;

Remarque 1 : on pourrait retourner le pointeur sur l’élément recherché

Remarque 3 : version récursive ?

Remarque 2 : algo proche de celui de la recherche dans un tableau

Chap. 5 : Les pointeurs - Ajout d’un élément en débu t de liste

� Le nom et le num de dossard sont donnés

procedure Ajouter_Coureur ( L : ?? Un_Ptr_Coureur ; Le_Nom : in chaine3 ; Le_Num : in Natural) is

Aux : Un_Ptr_Coureur ;begin

-- réservation mémoireAux : = new Un_Coureur;-- actualisation des informations Aux.all.Nom := Le_Nom; Aux.all.Num := Le_Num;-- réalisation des chaînagesAux.all.suiv:= L;L:=Aux;

end Ajouter_Coureur; Mode de passage de L?

-- réservation mémoire-- actualisation des informations -- réalisation des chaînagesL := new Un_Coureur’(Le_Nom,Le_Num,L) ;

Chap. 5 : Les pointeurs - Structure de liste

� Ajout d’un élément en début d’une liste

� Démarche générale

� 1- Faire la réservation mémoire

� 2- Actualiser les informations

� 3- Trouver l’endroit d’insertion

� Algo de recherche

� Est ce possible si on pointe sur l’élément qui suivra celui que l’on veut insérer ?

� � On a besoin d’avoir un pointeur sur l’élément qui précède

� 4- Réaliser les chaînages

� Attention aux cas particuliers

Chap. 5 : Les pointeurs – Suppression du 1 er coureur de la liste

procedure Sup_1er_Coureur ( L : ?? Un_Ptr_Coureur) isbegin

if L= null then-- il n’y a aucun coureur dans la liste

Raise Suppression_Impossible;else

L : = L.all.suiv ;-- liberer l’espace inutilisé � cf module suivant

end Sup_1er_Coureur ;

Mode de passage de L ?

Chap. 5 : Les pointeurs – Structure de liste

� Suppression d’’un coureur dont le nom est fourni

� Démarche

� 1- chercher le coureur à supprimer

� Algo de recherche

� On a besoin d’avoir un pointeur sur l’élément qui précède

� 2- Modifier les chaînages

� Attention au cas particuliers

Chap. 5 : Les pointeurs - Utilisations de pointeurs

� Structures de données dynamiques � Listes � vues à travers un exemple� Arbres, graphes � cf. module suivant

� Dimensionnement dynamique de tableaux

� Déclarer un tableau dont la dimension est fournie par l’utilisateur en début de programme

� 2 solutions � Bloc declare (cf. chapitre types tableaux non contraints)

� Avec pointeur

Chap. 5 : Les pointeurs - Dimensionnement dynamique de tableaux

beginput ("nombre de composantes ? ");get (Nbre_Comp) ;declareMon_Tab : Un_Tab (1..Nbre_Comp);

beginfor I in Mon_Tab’range loop

Mon_Tab(I) :=0.0;end loop;

end ;end Exemple ;

type Un_Ptr_Sur_Tab is access Un_Tab ;P_Mon_Tab : Un_Ptr_Sur_Tab;begin

put ("nombre de composantes ? ");get (Nbre_Comp) ;

P_Mon_Tab:=new Un_Tab (1..Nbre_Comp);

for I in P_Mon_Tab.all’range loopP_Mon_Tab.all (I) :=0.0;

end loop;

end Exemple;

procedure Exemple istype Un_Tab is array (Integer range <>) of Float ;

Nbre_Comp : Natural ;

Chap. 5 : Les pointeurs - Dimensionnement dynamique de String

� Exemple

type Ref_String is access String ;

S : Ref_String ;

beginS := new String (1..8) ;S := new String’("bonjour!") ;S.all := "salut---" ;S := new string(1..20) ;

Algorithmique et Programmation - Cours en ligne de l'INSA ... · PDF fileSur le plan de...

Documents

LIFAP3 : Algorithmique et programmation avancée

Algorithmique et programmation : les bases (Python) Corrigécregut.perso.enseeiht.fr/ENS/2015-apad-algo1/algo1-apad...ALGORITHMIQUE ET PROGRAMMATION 1 Algorithmique et programmation

BTS IRIS 1ère annéeIntroduction à la programmation et algorithmique 1 Initiation à la programmation et algorithmique cours 4

Algorithmique avancée TD Programmation Dynamique

Cours IUFM Algorithmique et Programmation

Bases de Programmation I Algorithmique

MATHÉMATIQUES - cache.media.eduscol.education.fr · Algorithmique et programmation 3.

BTS IRIS 1ère annéeIntroduction à la programmation et algorithmique 1 Initiation à la programmation et algorithmique cours 2

Algorithmique, graphes et programmation dynamique

PHP - Algorithmique - Techniques Fondamentales de Programmation

Initiation à la programmation et algorithmique

Algorithmique et programmation - Sésamath

SECTION 31 ALGORITHMIQUE - PROGRAMMATION

Cours Algorithmique Et Programmation en C

Programmation Orientée Objet et Algorithmique

Algorithmique Programmation

LIFAP2 : ALGORITHMIQUE ET PROGRAMMATION RECURSIVE

Algorithmique et programmation - SIGAYRET

BTS IRIS 1ère annéeIntroduction à la programmation et algorithmique 1 Initiation à la programmation et algorithmique cours 3