Buts:
- [Récursivité, Recherche, Tri et Introduction à VS.NET2003].
Récursivité
Recherche
- Q5: Ayant un tableau contenant n chaînes de caractères,
écrire une fonction qui retourne la première chaîne dont la taille est supérieure à 15 caractères.
- Q6: Écrire une fonction qui prend un tableau de n entiers
et return le nombre d'entiers qui sont une puissance de 2. Essayer de le coder si un nombre est une
puissance de 2 sur une seule ligne de code.
Tri
- Q7: En utilisant le tri à bulles, Tracer les différentes
opérations permettant de trier le tableau suivant: 4, 7, 2, 5, 6
- Q8: Utiliser le tri par sélection pour trier le tableau
suivant: 4, 3, 8, 22, 1, 5. Quel sera le résultat après la première itération de tri?
- Q9: Programmer un des tris les plus populaires,
implanté dans la plupart des langages: le quick sort. Cet algorithme de tri efficace se
décompose en deux étapes:
- le partitionnement: qui consiste à organiser le tableau à
trier selon une valeur pivot (le premier élément du tableau à
trier). Le pivot doit à la suite de cette opération se trouver à sa
place finale avec à sa gauche des éléments (pas nécessairement triés)
inférieurs et à sa droite des éléments (pas nécessairement triés)
supérieurs.
- la récursivité: l'étape précédente fait apparaître deux
tableaux: celui à droite de la valeur pivot et celui à gauche. Lancer
le partitionnement de ces deux tableaux.
On voit clairement la récursivité inhérente à cette définition:
programmez là ! Vous définirez pour cela une méthode à trois
arguments: une référence sur le tableau à trier, l'indice de l'élément
où doit commencer le tri, et l'indice du dernier élément à trier.
Note: pour placer le premier élément du tableau T à sa
place finale, appliquez l'algorithme suivant où d et f
désignent respectivement l'indice de début et de fin de tableau et
T[i] le i-ème élément de T:
- tant que T[f] est supérieur à T[d], décrémenter f
de 1.
- permuter (s'il y a lieu) T[f] avec T[d]
- incrémenter d de 1.
- tant que T[d] est inférieur à T[f], incrémenter d.
- permuter (s'il y a lieu) T[d] avec T[f]
- décrémenter f
- aller en 1
Inspirez-vous de l'exemple suivant où le nombre en gras représente
le pivot et celui en italique la valeur à permuter.
37 | 2 | 6 | 4 | 89 | 8 | 10 | 12 | 68 | 45 |
12 | 2 | 6 | 4 | 89 | 8 | 10 | 37 | 68 | 45 |
12 | 2 | 6 | 4 | 37 | 8 | 10 | 89 | 68 | 45 |
12 | 2 | 6 | 4 | 10 | 8 | 37 | 89 | 68 | 45 |
.NET
|
|