| Prochaine révision | Révision précédente |
| root:feuille1 [2016/09/12 14:57] – créée blanc | root:feuille1 [2016/09/12 15:19] (Version actuelle) – [Exercice 3. Recherchez un élément dans un tableau] blanc |
|---|
| //Nous supposerons que les tableaux ont déjà été vus et utilisés dans un cadre de programmation.// Pré-requis : le [[http://dept-info.labri.fr/ENSEIGNEMENT/algoprog/|cours d'algorithmique et programmation]] suivi en L1 | //Nous supposerons que les tableaux ont déjà été vus et utilisés dans un cadre de programmation.// Pré-requis : le [[http://dept-info.labri.fr/ENSEIGNEMENT/algoprog/|cours d'algorithmique et programmation]] suivi en L1 |
| |
| Un //tableau// est un //type concret// (par opposition à //type abstrait//), puisqu'on précise comment les éléments sont //physiquement// stockés. Dans la plupart des langages, les éléments d'un tableau sont indexés à partir de 0. Ainsi, le premier élément d'un tableau $T$ est $T[0]$, le second est $T[1]$, etc. Avec cette convention de numérotation (le premier élément a l'indice 0), l'indice le plus grand dans le tableau est donc ''len''($T$) - 1 où ''len'' désigne la longueur d'un tableau $T$. | Un //tableau// est un //type concret// (par opposition à //type abstrait//), puisqu'on précise comment les éléments sont //physiquement// stockés. Dans la plupart des langages, les éléments d'un tableau sont indexés à partir de 0. Ainsi, le premier élément d'un tableau T est T[0], le second est T[1], etc. Avec cette convention de numérotation (le premier élément a l'indice 0), l'indice le plus grand dans le tableau est donc ''len''(T) - 1 où ''len'' désigne la longueur d'un tableau T. |
| |
| L'accès aux éléments s'effectue directement par l'indice, pour accéder à l’élément d’indice $i$ on écrit $T[i]$. | L'accès aux éléments s'effectue directement par l'indice, pour accéder à l’élément d’indice i on écrit T[i]. |
| Le temps de calcul pour accéder à un élément du tableau est constant. | Le temps de calcul pour accéder à un élément du tableau est constant. |
| |
| ==== Exercice 1. Décalez les entrées d'un tableau d'entiers ==== | ==== Exercice 1. Décalez les entrées d'un tableau d'entiers ==== |
| |
| Soit $T$ un tableau d'entiers de taille $N$. | Soit T un tableau d'entiers de taille N. |
| |
| - Proposez un algorithme qui décale d'une case vers la droite les entrées du tableau $T$ à partir de la position $k$. Par exemple si $T =[b,o,n,j,o,u,r]$, $N=7$ et $k=3$ le décalage donnera $T=[b,o,n,j,j,o,u]$. | - Proposez un algorithme qui décale d'une case vers la droite les entrées du tableau T à partir de la position k. Par exemple si T =[b,o,n,j,o,u,r], N=7 et k=3 le décalage donnera T=[b,o,n,j,j,o,u]. |
| * Remarques : On ne se soucie pas ici du fait que la valeur $T[k]$ sera égale à la valeur $T[k+1]$.On ne se soucie pas non plus d'avoir en quelque sorte perdu l'entrée $T[N-1]$ initiale. | * Remarques : On ne se soucie pas ici du fait que la valeur T[k] sera égale à la valeur T[k+1].On ne se soucie pas non plus d'avoir en quelque sorte perdu l'entrée T[N-1] initiale. |
| - Dans quel cas l'algorithme de décalage peut-il être utilisé ? | - Dans quel cas l'algorithme de décalage peut-il être utilisé ? |
| |
| ==== Exercice 2. Fusionnez deux tableaux d'entiers triés par ordre croissant ==== | ==== Exercice 2. Fusionnez deux tableaux d'entiers triés par ordre croissant ==== |
| |
| Soient deux tableaux d'entiers $T, T'$ de taille $N, N'$ respectivement, qu'on supposera triés par ordre croissant. On souhaite obtenir un nouveau tableau $T''$ de taille $N + N'$ contenant les entrées des tableaux $T$ et $T'$, triées dans l'ordre croissant aussi. | Soient deux tableaux d'entiers T, T' de taille N, N' respectivement, qu'on supposera triés par ordre croissant. On souhaite obtenir un nouveau tableau T" de taille N + N' contenant les entrées des tableaux T et T', triées dans l'ordre croissant aussi. |
| |
| * Considérons un algorithme (pas très rusé) qui débute par recopier le tableau $T$ au début de $T''$, puis insère une à une les entrées de $T'$ | * Considérons un algorithme (pas très rusé) qui débute par recopier le tableau T au début de T", puis insère une à une les entrées de T' |
| * A chaque fois, on recherchera à partir du début de $T''$ l'endroit où l'entrée $T'[i]$ doit être insérée dans $T''$, puis on décale les entrées au besoin. | * A chaque fois, on recherchera à partir du début de T" l'endroit où l'entrée T'[i] doit être insérée dans T", puis on décale les entrées au besoin. |
| |
| * Considérons maintenant un algorithme plus malin, qui ajoute dans $T''$ //à la position courante//, soit une entrée de $T$, soit une entrée de $T'$ | * Considérons maintenant un algorithme plus malin, qui ajoute dans T" //à la position courante//, soit une entrée de T, soit une entrée de T' |
| * On tiendra à jour des indices $i$ et $i'$ indiquant le prochain élément de $T$ et $T'$ à ajouter à $T''$ | * On tiendra à jour des indices i et i' indiquant le prochain élément de T et T' à ajouter à T" |
| * On détermine qui de $T[i]$ ou $T'[i']$ doit être inséré dans $T''$ | * On détermine qui de T[i] ou T'[i'] doit être inséré dans T" |
| * On l'insère et on incrémente la position $i''$ où doit être inséré le prochain élément dans $T''$ | * On l'insère et on incrémente la position i'' où doit être inséré le prochain élément dans T" |
| * On met à jour $i$ ou $i'$ | * On met à jour i ou i' |
| |
| ===== TD machine ===== | ===== TD machine ===== |
| ==== Exercice 3. Recherchez un élément dans un tableau ==== | ==== Exercice 3. Recherchez un élément dans un tableau ==== |
| |
| * Ecrivez la fonction //rechercheElem// qui recherche si un élément donné $elem$ est présent dans un tableau $tab$. | * Ecrivez la fonction //rechercheElem// qui recherche si un élément donné //elem// est présent dans un tableau //tab//. |
| |
| ==== Exercice 4. Décalez les entrées d'un tableau d'entiers ==== | ==== Exercice 4. Décalez les entrées d'un tableau d'entiers ==== |
