Class notes
Informatique - Les tableaux
- Course
- Institution
Bases de l'informatique: Programmation et algorithme. Langage C.
[Show more]
Seller
Follow
Streamerine
Content preview
Chapitre 7 : Les tableauxI. Tableau à n dimension
On nomme le tableau ci dessous T :
Numéro 0 1 2 3 4
case
Valeur -6 0 12 7 24
En générale on les écrit
T=[-6, 0, 12, 7, 24]
Attention : En C, les cases sont numérotées à partir de 0
Formellement, un tableau représente un produit cartésien
A*A...*A= A^k de taille fixée( ici k ) et homogène ( que des A, pas A*B*C)
Par contre A peut-être ce qu'on veut
→ tableau de réels
→ tableau d'entiers
→ tableau de booléens
→ tableau de rationnels
Type abstrait :
ex : les tableaux de réels
Types importés : entier_tan (pour le numéro de cases)
réel (pour le contenu des cases)
Opérateurs
nouveau_tableau : entier_nat (taille du tableau) → tableau
ecrire_tableau : entier_nat*réel*tableau → tableau
lire_tableau : entier_nat*tableau → réel
Attention : nouveau tableau crée un tableau « vide »
→ dans un algo, si on lit le contenu d'une case « vide », on a une erreur
→ en C si on lit le contenu d'une case non initialisée, on récupère n'importe
quoi ( ce qu'il y avait avant dans cette case mémoire de l'ordinateur)
Notations
lire_tableau (i, T) s'écrit T[i]
T:= ecrire_tableau (i, x, T) s'écrit T[i]:=x
t:=nouveau_tableau(n) s'écrit T:= nouveau tableau de n réels
Application :
Écrire un algo itératif qui étant donné un tableau T de n entiers, et un entier a
et renvoie
→ le plus petit numéro de case i tel que T[i] = a s'il existe
,→ -1 si aucune case ne contient la valeur a
Recherche dans un tableau
→ si le tableau est déjà trié
Une méthode efficace : la dichotomie
On a un tableau T à m cases et on cherche la valeur x, on va à la case m/2
• Si T[m/2] >x [2,3,8,12,15,22]
On va chercher x dans la première moitié du tableau
• Si T[m/2] =x on a trouvé
→ Pour chercher dans une moitié de tableau, on ré applique la méthode
→ Si on a coupé le tableau assez de fois, on arrive à un tableau vide et on
conclut que la valeur n'y est pas.
Exemple : T=[2 3 8 12 15 22]
n=6
On regarde T[n/2]=T[3]=12, on a 12<15. Donc on cherche x
On cherche x=15
dans [15 22] ou 22 est une valeur supérieur a x. Donc on
cherche dans [15]
valeur=x=trouvé
T=[2 3 8 12 15 22]
n=6
On cherche x=5
Valeur de la case n/2=12 ( donc 3ème case)
On a 12>x donc on cherche dans
[ 2 3 8]
Valeur de la case milieu =3<x
Donc on cherche x dans [8]
Valeur de la case milieu=8>x
Donc on cherche x dans []
→ x n'est pas dans le tableau
Algorithme itératif de la recherche dans le tableau.
Fonction_recherche(m : entier_nat, T : Tableau, x:entier) : entier
Var :i,j : entier_nat /*i et j délimitent le sous-tableau dans lequel on cherche x
*/
m : entier_nat /* numéro de la case « milieu »*/
|Début|
i:=0
j:=n-1
Tant que i <=j faire
m:=(j+i)/2 /* fait la division entière*/
Si T[m]<x alors
i:=m+1
Sinon
Si T[m]>x alors
, j:=m-1
Sinon
retourner m /* cas ou T[m]=x */
Finsi
Finsi
Fintantque
retourner -1
|Fin|
Quand un algorithme est correct , il fait ce qu'on lui a demandé dans la
spécification, on s’intéresse alors à son efficacité. On parle alors de notion de
complexité (en temps)
= nb d'opérations élémentaires effectuées par l'algorithme en fonction de la
table des donnés.
Pour les algo sur les tableaux, la taille de la donnée est n=nb de cases.
Notations : O(f(x)) environ plus petit que k*f(n) quand on est grand( k=cte).
Par exemple : O(n)=ne grandit pas plus vite que k*n
Pour un tableau non trié, combien fait-on de comparaison en fonction de n
→ meilleur cas : O(1)
→ pire cas : O(n)
→ en moyenne : O(n) (pire cas/2)
Avec la dichotomie
→ meilleur cas O(1)
→ pire cas O(log2(n))
Spécification :
Étant donné un tableau T à n cases contenant deux entiers, je veux modifier T
pour trier les valeurs des cases par ordre croissant.
Fonction max_tab(T : Tableau, n:entier) : entier
var : i:entier_nat
max : entier_nat
|Début|
max:=T[0]
Pour i allant de 1 à n-1 faire
Si T[i]>max
alors T[i]=max
Finsi
Finpour
retourner max
|Fin|
Exemple : T= [ 2 26 3 24 3 6 5]
doit retourner T= [2 3 3 5 6 24 26]
fonction_selection(T : Tableau, n: entier_nat) : Tableau
The benefits of buying summaries with Stuvia:
Guaranteed quality through customer reviews
Stuvia customers have reviewed more than 700,000 summaries. This how you know that you are buying the best documents.
Quick and easy check-out
You can quickly pay through credit card or Stuvia-credit for the summaries. There is no membership needed.
Focus on what matters
Your fellow students write the study notes themselves, which is why the documents are always reliable and up-to-date. This ensures you quickly get to the core!
Frequently asked questions
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
Satisfaction guarantee: how does it work?
Our satisfaction guarantee ensures that you always find a study document that suits you well. You fill out a form, and our customer service team takes care of the rest.
Who am I buying these notes from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller Streamerine. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy these notes for $3.74. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
52355 documents were sold in the last 30 days
Founded in 2010, the go-to place to buy study notes for 14 years now