Upload
nel-durieux
View
114
Download
3
Embed Size (px)
Citation preview
Algorithmes et structures de données avancées
5ème cours
Patrick Reuter
http://www.labri.fr/~preuter
Ingrédients d’algorithmes
• Affectation (ex. mois := 6, jours[1] := 31)• Condition/Comparaison (ex. mois <= 12)• Appel de fonction (ex. writeln(mois))
• Structure de contrôle– Branchements conditionnels (multiples) (si .. Alors .. Sinon)
– Boucles (tant que..faire, pour.. faire)
• Bloc d’instructions (begin .. end)
Aujourd'hui
TYPES:– tableau 1D– tableau 2D– types énumérés– enregistrements– ..
Déclaration de variables
Comme dans un livre de recettes
Ingrédients(pour 8-10 personnes) :
- 1 kg de couscous roulé - 1 kg de mouton - 1 poignée de pois chiches - 2 oignons secs - 3-4 tomates fraîches ou 1 cuillère.à soupe de concentré de tomate - 3-4 pommes de terre - 3-4 navets - 3-4 carottes - 3-4 courgettes - 1 tranche de courge - 4 cuillères à soupe d'huile - 1/2 cuillère à café de cannelle - 1 pincée de poivre noir - 1/2 cuillère à soupe de piment rouge doux ou de paprika - 1/2 cuillère à soupe de ras-el-hanout - 1 piment rouge sec - 100 g de beurre ou 3 cuillères à soupe d'huile - sel
Préparation :
La veille, mettez les pois chiches dans un bol d'eau.
Le jour même, roulez le couscous .Si vous utilisez du couscous roulé et séché, rincez-le à l'eau froide, égouttez-le et laissez-le gonfler pendant 30 mn.
Coupez la viande en morceaux.Pelez les oignons et coupez-en 1 en morceaux.
Lavez et passez les tomates à la moulinette.Mettez la viande dans une marmite et ajoutez les morceaux d'oignon, les tomates ou le concentré de tomate dilué dans 1 verre d'eau, l'huile, le poivre, le piment, la cannelle et du sel.
Faites revenir …..
Déclaration de variables
var compteur : integer;
var diviseur : single;
var c : char;
var precision : double;
var nom : string;
var masculin : boolean;
var jours : array[1..12] of byte;
diviseur := 1.1; { Affectation }compteur : = 1;Nom := ‘Gerhard’;
Nombre entier
Nombre à virgule flottante
Nombre à virgule flottante avec double précision
Chaîne de caractères
Tableau
Déclaration de variables
var compteur : integer;
var diviseur : single;
var c : byte;
var precision : double;
var nom : string;
var masculin : boolean;
var jours : array[1..12] of byte;
diviseur := 1.1; { Affectation }compteur : = 1;Nom := ‘Gerhard’;
Nombre entier
Nombre à virgule flottante
Nombre à virgule flottante avec double précision
Chaîne de caractères
Tableau
TYPE
Déclaration de variables
• Types prédéfinis– integer, boolean, single, …
• Types que l’on peut définir soi-même
type t_nombre_entier = integer;var i : t_nombre_entier;
{ pas vraiment d’intérêt ... }
au lieu de
var i : integer;
Déclaration de variables
• Types prédéfinis– Integer, boolean, single, …
• Types que l’on peut définir soi-même
type t_tableau = array[1..12] of byte;
var jours : t_tableau;
au lieu de
var jours : array[1..12] of byte;
Organisation de la mémoiretype t_tableau = array[1..12] of byte;var jours : t_tableau; {12 octets}
#0
jours[1] #2000
...
#536.870.910#536.870.911
...
jours[index] #(2000+index-1)
jours[3] #2002
jours[12] #2011
...
Occupe de la place successivedans la mémoire
jours[2] #2001312831
31
• Tableau 2D
Type tableau à 2 dimensions :
var a : array[1..lignes] of array[1..colonnes] of real;
Type tableau à 2 dimensions :
var a : array[1..lignes] of array[1..colonnes] of real;
Ou bien
var a : array[1..lignes, 1..colonnes] of real;
Type tableau à 2 dimensions :
var a : array[1..lignes] of array[1..colonnes] of real;
Ou bien
var a : array[1..lignes, 1..colonnes] of real;
Ou bien
type t_ligne = array[1..colonnes] of real;var a : array[1..lignes] of t_ligne;
Type tableau à 2 dimensions :
var a : array[1..lignes] of array[1..colonnes] of real;
Ou bien
var a : array[1..lignes, 1..colonnes] of real;
Ou bien
type t_ligne = array[1..colonnes] of real;var a : array[1..lignes] of t_ligne;
Ou bien
type t_ligne = array[1..colonnes] of real;type t_tableau2 = array[1..lignes] of t_ligne;var a : t_tableau2;
Ou bien
type t_tableau2 = array[1..lignes, 1..colonnes] of real;var a : t_tableau2;
Ou bien
type t_tableau2= array[1..lignes] of array[1..colonnes] of real;var a : t_tableau2;
• Dans certains langages simplement
int a[lignes][colonnes];
Type tableau à 2 dimensions
type t_ligne = array[1..colonnes] of real;type t_tableau2 = array[1..lignes] of t_ligne;var a : t_tableau2;
{ Affectation: }
a[1][1] := 0;a[1][2] := 0;..a[1][colonnes] := 0;a[2][1] := 0;a[2][2] := 0;....a[lignes][colonnes] := 0;
Déclaration de variables
POUR i de 1 à n FAIREPOUR j de 1 à n FAIRE
a[i][j] := 0;FIN POUR
FIN POUR
²
Déclaration de variables
Type tableau à 2 dimensions :
type t_ligne = array[1..n] of real;type t_tableau2 = array[1..n] of t_ligne;var a : t_tableau2;var i,j : integer;
POUR i de 1 à n FAIREPOUR j de 1 à n FAIRE
a[i][j] := 0;FIN POUR
FIN POUR
- Complexité ?- Remplir une matrice identité ?
Déclaration de variables
Type tableau à 2 dimensions : n = lignes = colonnes
type t_ligne = array[1..n] of real;type t_tableau2 = array[1..n] of t_ligne;var a : t_tableau2;var i,j : integer;
Déclaration de variables
Type tableau à 2 dimensions : n = lignes = colonnes
type t_ligne = array[1..n] of real;type t_tableau2 = array[1..n] of t_ligne;var a : t_tableau2;var i,j : integer;
POUR i de 1 à n FAIREPOUR j de 1 à n FAIRE
SI i=j ALORS a[i][j] := 1;
SINONa[i][j] := 0;
FIN POURFIN POUR
Déclaration de variables
Organisation de la mémoire
Organisation de la mémoiretype t_ligne = array[1..3] of byte;
type t_tableau2 = array[1..3] of t_ligne;
var a : t_tableau2;
#0
a[1][1] #2000
...
#536.870.910#536.870.911
...
...
Occupe de la place successivedans la mémoire
a[1][2] #2001a[1][3] #2002a[2][1] #2003a[2][2] #2004
...
a[3][3] #2008
a[i][j] #(2000+(3*(i-1))+ j - 1 )
Organisation de la mémoiretype t_ligne = array[1..colonnes] of byte;
type t_tableau2 = array[1..lignes] of t_ligne;
var a : t_tableau2;
a[i][j] #(2000+j+((colonnes)*(i-1)) -1)
Organisation de la mémoiretype t_ligne = array[0..colonnes-1] of byte;
type t_tableau2 = array[0..lignes-1] of t_ligne;
var a : t_tableau2;
a[i][j] #(2000+j+((colonnes)*i) )
Déclaration de variables
Des nombres entiers sont souvent utilisés quand un choix parmi un petit nombre d’alternatives est souhaité.
Nombre entiers
Type de base : byte, integer;
var jour : integer;jour := 1; { signifie par exemple lundi }…jour := 3; { signifie par exemple mercredi }
Déclaration de variables
Les types énumérés
type t_jourdesemaine =(lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche);
var jour : t_jourdesemaine;
jour := lundi;
…
jour := mercredi;
Déclaration de variablesLes types énumérés
Autres exemples
type t_jourdesemaine =(lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche);
type t_couleur =(rouge, vert, bleu, gris);
type t_sexe =(masculin, feminin);
Organisation de la mémoire
var jour : t_jourdesemaine;
#0#1#2#3#4#5
...
#536.870.910#536.870.911
#1.000
...
jour
Déclaration de variables
type t_carte =(7,8,9,10,vallee,dame,roi,as);
var ma_meilleure_carte : t_carte;
var cartes : array[1..8] of t_carte;
ma_meilleur_carte := roi;
cartes[1] := 10;
cartes[2] := dame;
cartes[3] := 7;
...
cartes[8] := 9;
Motivation
Structure de données:
- tableau à 2 dimensions…
type t_ligne = array[1..8] of byte;
Motivation
Structure de données:
- tableau à 2 dimensions…
type t_ligne = array[1..8] of byte;type t_damier = array[1..8] of t_ligne;
Motivation
Structure de données:
- tableau à 2 dimensions…
type t_ligne = array[1..8] of byte;type t_damier = array[1..8] of t_ligne;var damier : t_damier;
MotivationImaginons la convention suivante :
- 0 pour un champs vide- 1 pour un champs blanc- 2 pour un champs noir
type t_ligne = array[1..8] of byte;type t_damier = array[1..8] of t_ligne;var damier : t_damier;
Pour initialiser un damier vide :
MotivationImaginons la convention suivante :
- 0 pour un champs vide- 1 pour un champs blanc- 2 pour un champs noir
type t_ligne = array[1..8] of byte;type t_damier = array[1..8] of t_ligne;var damier : t_damier;var i,j : integer;
Pour initialiser un damier vide :
POUR i = 1 à 8 faire POUR j = 1 à 8 faire damier[i][j] := 0; FIN POURFIN POUR
Motivation
Structure de données:
- tableau à 2 dimensions…
type t_ligne = array[1..8] of byte;type t_damier = array[1..8] of t_ligne;var damier : t_damier;
Motivation
Structure de données:
- tableau à 2 dimensions…
type t_champ =(vide, blanc, noir); {pour le jeu de dames}
Motivation
Structure de données:
- tableau à 2 dimensions…
type t_champ =(vide, blanc, noir); type t_ligne = array[1..8] of t_champ;type t_damier = array[1..8] of t_ligne;var damier : t_damier;
Motivation
type t_champ =(vide, blanc, noir); type t_ligne = array[1..8] of t_champ;type t_damier = array[1..8] of t_ligne;var damier : t_damier;var i,j : integer;
Pour initialiser un damier vide :
POUR i = 1 à 8 faire POUR j = 1 à 8 faire damier[i][j] := vide; FIN POURFIN POUR