CorrectionTD2 .pdf



Nom original: CorrectionTD2.pdf

Ce document au format PDF 1.2 a été généré par TeX output 2008.10.07:1756 / dvipdfm 0.13.2d, Copyright © 1998, by Mark A. Wicks, et a été envoyé sur fichier-pdf.fr le 28/04/2015 à 18:52, depuis l'adresse IP 105.100.x.x. La présente page de téléchargement du fichier a été vue 480 fois.
Taille du document: 63 Ko (4 pages).
Confidentialité: fichier public


Aperçu du document


Institut Galil´ee
Algorithmique et structures de donn´ees
Ing´enieurs 1`ere ann´ee (MACS/T´el´ecom/Mesures/Energie) 2008/2009

Correction du T.D. 2

Les tableaux
1

Exercice 1

Ecrire les algorithmes permettant :
1. Le calcul du nombre d’occurences d’un ´el´ement donn´e dans un tableau.
Nb_occurences (T: Tableau d’entier, N: entier) : entier
VAR i,nb_occ : entiers
Debut
nb_occ <- 0
Pour i <- 1 a N Faire
Si T[i] = X
Alors nb_occ <- nb_occ + 1
Fsi
Fpour
retourner nb_occ
Fin
2. Le calcul de la moyenne et du minimum des ´el´ements d’un tableau.
Moyenne (T: Tableau d’entier, N: entier) : r´
eel
VAR somme, i: entiers
moyenne : r´
eel

ebut
somme <- 0
Pour i <- 1 a N Faire
somme <- somme + T[i]
Fpour
moyenne <- somme / N
retourner moyenne
Minimum (T: Tableau d’entier, N: entier): entier
VAR min, i: entiers

ebut
min <- T[1]
Pour i <- 2 a N Faire
Si T[i]<min
Alors min=T[i]
Fsi
Fpour
retourner min
3. De tester si un tableau est tri´e.
1

Est_trie (T: Tableau d’entiers, N: entier): bool´
een
VAR i: entiers
est_trie: Bool´
een
Debut
i <- 1
Tant que i < N ET T[i] <= T[i+1] Faire
i <- i + 1
Ftque
est_trie <- (i = N)
retourner est_trie
Fin
4. Le calcul du
produit scalaire de deux vecteurs r´eels u et v de dimension
Pi=n
n : u.v = i=1 ui ∗ vi
Produit_scalaire (u: Tableau d’entiers, v: Tableau d’entiers, n:
entier): entier
VAR i, prod_scalaire: entiers
Debut
prod_scalaire <- 0
Pour i <- 1 a n Faire
prod_scalaire <- prod_scalaire + u[i] * v[i]
Fpour
retourner prod_scalaire;
Fin

2

Exercice 2

Ecrire l’algorithme effectuant le d´ecalage des ´el´ements d’un tableau.
Exemple :
• Tableau initial D

E

C

A

L

A

G

E

• Tableau modifi´e (d´ecalage `a gauche) E

C

A

L

A

G

E

D

Proc´
edure Decalage_gauche (T: Tableau de caract`
eres, N: entier)
VAR tmp: caract`
ere
i: entier
Debut
tmp <- T[1]
Pour i <- 1 a N-1 Faire
T[i] <- T[i+1]
Ftque
T[N] <- tmp
Fin

3

Exercice 3

Ecrire l’algorithme qui calcule le produitP
de deux matrices car´ees r´eelles A =
k=n
(aij ) et B = (bij ) de dimension n : cij = k=1 aik ∗ bkj .
2

Produit_matriciel (a: Matrice carr´
ee , b: Matrice carr´
ee, n:
entier): Matrice carr´
ee
VAR c: Matrice carr´
ee n*n
i: entier
Debut
Pour i <- 1 a n Faire
Pour j de 1 a n Faire
c[i][j] <- 0
Pour k de 1 a n Faire
c[i][j] <- c[i][j] + a[i][k] * b[k][j]
Fpour
Fpour
Fpour
retourner c
Fin

4

Exercice 4

Soit un tableau T avec T (i) ∈ {0, 1}. Ecrire un algorithme qui retourne la
position i dans le tableau telle que T [i] est le d´ebut de la plus longue suite
cons´ecutive de z´eros.
pos_suite_0 (t: Tableau d’entiers, n: entier): entier
VAR pos, lmax, lg, i: entiers
suite: Bool´
een
Debut
pos = -1
lmax = 0
suite = Faux
pour i
Pour i <- 1 a n Faire
Si t[i]= 0
Alors
Si NON suite
Alors
lg <- 0
suite = 1
Fsi
lg = lg+1
Sinon //t[i] dif´
erent de z´
ero
Si suite = Vrai
Alors
suite <- Faux
Si lg > lmax
Alors
lmax = lg
pos = i - lg
Fsi
3

Fsi
Fsi
Fpour
Si suite=Vrai ET lg > lmax
Alors
pos = i - lg + 1
Fsi
return pos
Fin

5

Exercice 5

Ecrire un algorithme qui calcule le plus grand ´ecart dans un tableau (l’´ecart est
la valeur absolue de la diff´erence de deux ´el´ements).
plus_grand_ecart (t: Tableau d’entiers, n: entier): entier
VAR: min, max, i: entiers
Debut
min = t[1]
max = t[1]
Pour i <- 2 a n Faire
Si t[i] > max
Alors
max = t[i]
Fsi
Si t[i] < min
Alors
min = t[i]
Fsi
Fpour
return max - min
Fin

4


CorrectionTD2.pdf - page 1/4
CorrectionTD2.pdf - page 2/4
CorrectionTD2.pdf - page 3/4
CorrectionTD2.pdf - page 4/4

Télécharger le fichier (PDF)










Documents similaires


correctiontd2
finale
solution examen s4 science economique
exo version koffi
exercices algorithmiques 1 corriges
serie2 120824031151 phpapp01 1