Cours+series - TAB 1dim - 14-15

IPEI El Manar
Anne universitaire 2014/2015
Les tableaux une dimension

I. Dfinitions
Un tableau est une structure de donnes permettant de ranger un nombre fini dlments de
mme type , qui sont appeles les composantes du tableau. Le nombre de composantes N est
alors la dimension du tableau.
Un tableau est caractris par :
Son nom (identificateur)
Sa taille (nombre dlments quil contient)
Le type des lments quil contient.
II. Dclaration
1 re mthode
<Nom_tableau> : tableau [<borne_inf> ..
<borne_sup>] de type des lments
Exemples
Les dclarations suivantes en langage algorithmique,
var
T1 : tableau [1..25] dentier
T2 : tableau [1..99] de rel
T3 : tableau [1..10] de boolen
T4 : tableau [1..24] de chane
III.
2eme mthode
Type <nom_type>= Tableau[bi..bs] de
<type_des_elements>
Dclaration dune variable tableau :
<Nom_var > :<nom_type>
Exemples
Les dclarations suivantes en langage algorithmique,
Type tab =tableau [1..100] dentier
Var T:tab
Accs aux composantes
En dclarant un tableau par:

T : tableau [1..7] dentier
On peut accder directement aux lments dun tableau en lecture ou en criture, en utilisant
les indices (rangs) de chaque lment. Pour accder au ime lment : T[i] tel que 1 i taille
du tableau T [1], T [2], ..., T [5]
Remarque :
Considrons un tableau T de dimension N:
- l'accs au premier lment du tableau se fait par T [1]
- l'accs au dernier lment du tableau se fait par T [N]
La structure pour se prte particulirement bien au travail avec les tableaux (Saisie,
Affichage, )
Saisie dun tableau
Pour i de 1 N faire
Ecrire( donner llment n : ,i)
Lire(T[i])
Fin pour
Classe : 1re Anne MP, PC, PT
Affichage dun tableau

Pour i de 1 N faire
Ecrire (T[i])
Fin pour
IPEI El Manar
Srie dexercices : Les tableaux une dimension

NB : on suppose avoir les dclarations suivantes :
CONSTANTE
NMAX=100
TYPE
TAB=TABLEAU[1..NMAX] DENTIERS
Exercice N1 :
La distance de Hamming entre deux tableaux de mme taille est le nombre de positions ou les
deux tableaux diffrent. Par exemple, la distance de Hamming entre [0 1 0 0] et [1 1 0 1 ]
gale 2. Ecrire une fonction qui calcule la distance de Hamming entre deux tableaux donns
(vous pouvez supposer que les deux tableaux sont de mme taille).
Exercice N2 :
crire une procdure algorithme nomme suit_trie qui partir dun tableau dentiers t de
taille N, affiche le nombre de sous-squences croissantes de ce tableau, ainsi que les indices
de dbut et de fin de la plus grande sous-squence.
Exemple : soit t un tableau de 15 lments : [1, 2, 5, 3, 12, 25, 13, 8, 4, 7, 24, 28, 32, 11, 14 ]
Les squences strictement croissantes sont :
[ 1, 2, 5] [ 3, 12, 25 ] [13 ] [8] [4, 7, 24, 28, 32 ] [ 11, 14 ]
Le nombre de sous-squence est : 6 et la plus grande sous-squence est : [ 4, 7, 24, 28, 32 ]
Exercice N3 :
Soit n un entier non nul et T un tableau une ligne de taille N. On dit que T est un
drangement, si T est form en utilisant exactement une fois chaque entier de 1 n de tel sorte
que lentier i ne soit pas en position i.
1. Ecrire une fonction derangement qui teste si un tableau est un drangement, si cest le cas
elle retourne VRAI.
2. Soit T un drangement, on veut construire un tableau P (de mme taille que T) de la faon
suivante : si lentier j apparait la position i dans le tableau T alors on met la valeur i la
position j du tableau P.
Exemple : si T = [5 3 1 2 4] alors P = [3 4 2 5 1]
Ecrire alors la procdure Indice qui construit ce tableau P partir de la donne du tableau T.
Exercice N4:
Soient les suites U et V dfinies par :
U 1 1
V1 3
U 2 5
V2 4
U V U
V (V V ) U
; n 3
; n 3
n 1
n
n 1
n
n 1
n2
n2
On se propose de calculer et afficher n termes des deux suites U et V tel que n est une donne
compris entre 1 et 1000.
Lide consiste utiliser deux tableaux T1 et T2 une dimension stockant respectivement les
n termes de ces deux suites.
Ecrire une procdure nomm SUITE permettant de calculer et afficher les n termes de
deux suites U et V.
IPEI El Manar
Exercice N5 :
Considrons un tableau T de bits (entiers valant 0 ou 1) de type TAB, cest une alternance de
groupes de 1 conscutifs et de groupes de 0 conscutifs.
On cherche dterminer la longueur maximale dun groupe constitu uniquement dlments
nuls.
Ecrire une fonction algorithmique nomme grpe_nul_maxi qui prend en entre le tableau T et
son dimension n et qui retourne la longueur du plus long groupe dlments nuls de T.
Exemple :
Si
T= 1 1 1 1 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 1 1
Alors la fonction doit retourner la valeur 6.
Exercice N6 :
On suppose avoir effectu les dclarations suivantes :
CONSTANTE NMAX=100
TYPE
TAB=TABLEAU [1..NMAX] DE REEL
Etant donn un nuage de N points, dfinis par leur coordonnes X et Y stockes dans deux
tableaux une dimension, on veut dterminer les coefficients a et b de la droite dite droite
des moindres carres exprims comme suit :
i 1
N
i 1
N
i 1
N
i 1
i 1
N . X [i ].Y [i ] X [i ]. Y [i ]
N . X [i ]. X [i ] X [i ]. X [i ]
i 1
Y [i] a. X [i]
i 1
i 1
Ecrire un procdure nomm NUAGE permettant de calculer les coefficients a et b de la

droite.
Exercice N7 :
On suppose avoir effectu les dclarations suivantes :
CONSTANTE NMAX=100
TYPE
TAB=TABLEAU [-1..NMAX] DES ENTIERS
On se propose de dfinir partir dun tableau T un polynme P de degr n, fonction de x,
dvelopp selon les puissances croissantes de x en utilisant la dfinition suivante :
n
T 1 degr de P et P x T i xi
i 0
Exemple :
T:
4
-1
5
0
9
1
2
2
-1
3
3
4
Le polynme P de degr 4, dfini partir de T est le suivant : P( x) 3x 4 x 3 2 x 2 9 x 5

1. Ecrire une procdure nomm SAISIE permettant de saisir un tableau T une
dimension reprsentant un polynmes P de degr n
2. Ecrire une procdure nomm POLYNOMES permettant de calculer dans un
tableau rsultat la somme de deux polynmes P1 de degr n1 et P2 de degr n2.
Exercice N8 :
Soit le type suivant :
TYPE TAB=tableau [0..100] dentier
1) Ecrire une fonction algorithmique SOMME qui retourne la valeur de la somme
n 1
suivante :
T .T
i 0
n 1i
IPEI El Manar
Ti tant llment dindice i dans un tableau T de n cases.

2) On dfinit les nombres de Catalan comme suit :
n 1
n Ck .Cn1k Si n
k 0
C 1
Si n 0
0
Ecrire une procdure algorithmique CATALAN calculant la valeur du nime nombre de

Catalan Cn . Pour ce faire vous utiliserez un tableau de type TAB permettant de stocker
petit petit les valeurs Ck pour k 0, n .
Exercice N9 :
Dans un pays, N parties politiques ont prsent leur liste de candidats aux lections (listes
lectorales numrotes de 1 N). Ces lections ont vu la participation de M votants, chacun
inscrit un numro de liste dans un bulletin de vote saisi dans un tableau de votes V de taille M.
V[i] = j signifie que le vote i (1 i < M) est partie pour la liste j (1 j N).
Un vote blanc ou annul nest pas considr vote valide et V[i]=0.
Exemple de 25 votants sur 6 listes :
i
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
Les rsultats des listes sont stockes dans un tableau P de taille N+1 o P[i]=j signifie que le
nombre de votes valides obtenus par la liste i est j.
P[0] contient le total des votes blancs ou annuls.
Exemple : Les rsultats de lexemple prcdent :
0
1
2
3
4
5
6
I
1
4
5
1
6
3
P
5
Le problme consiste aider la commission dorganisation des lections appliquer les rgles
lectorales pour dcompter les rsultats, nommer le gagnant majoritaire ou prvoir la coalition
de listes idale.
Une liste obtenant plus de 50% des voix valides est considre majoritaire et dsigne
vainqueur des lections. De lexemple prcdent, la liste qui obtient au moins 11 voix valides
gagnera les lections.
1. Dfinir le type du tableau rsultat P.
2. Ecrire la procdure scores qui remplit le tableau P des rsultats des listes et les votes
blancs.
3. Ecrire la fonction nbVoix qui retourne le nombre de voix valides des lections.
4. Ecrire la fonction gagnant qui retourne le gagnant majoritaire sil existe sinon -1.
Aprs dcompte des voix, on limine de V les voix non valides en prservant lordre des
votes.
Exemple : V prcdent devient :
i
10
11
12
13
14
15
16
17
18
19
20
5. Ecrire la procdure purger qui ralise llimination des voix non valides de V.
6. Si V est tri (ex. tri dcroissant), crire la fonction gagnant2 qui retourne le gagnant
majoritaire.

Cours+series - TAB 1dim - 14-15

Transféré par

Droits d'auteur :

Formats disponibles

Cours+series - TAB 1dim - 14-15

Transféré par

Informations du document

Description originale:

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Cours+series - TAB 1dim - 14-15

Transféré par

Droits d'auteur :

Formats disponibles

IPEI El Manar

Anne universitaire 2014/2015

Les tableaux une dimension

Accs aux composantes

En dclarant un tableau par:

Classe : 1re Anne MP, PC, PT

Affichage dun tableau

Anne universitaire 2014/2015

Srie dexercices : Les tableaux une dimension

Classe : 1re Anne MP, PC, PT

Anne universitaire 2014/2015

Ecrire un procdure nomm NUAGE permettant de calculer les coefficients a et b de la

Le polynme P de degr 4, dfini partir de T est le suivant : P( x) 3x 4 x 3 2 x 2 9 x 5

Classe : 1re Anne MP, PC, PT

Anne universitaire 2014/2015

Ti tant llment dindice i dans un tableau T de n cases.

Ecrire une procdure algorithmique CATALAN calculant la valeur du nime nombre de

Classe : 1re Anne MP, PC, PT

Vous aimerez peut-être aussi