UdMHaut
UdMBAS

IFT1166
Programmation Orientée Objet avec C++

Département d'informatique et de recherche opérationnelle

Direction de l'enseignement de service en informatique
 

Image C++
 
Été 2008

Accueil

Professeurs et
Démonstrateurs

Horaires et locaux

Notes de cours

Cours
après Cours

Démonstrations
et devoirs

Examens

Liens utiles

Au sujet du
livre de cours

Consultez vos notes

Foire aux questions
(FAQ)

Sessions antérieures

  Démonstration #11  
 
Dernière mise à jour : sam 03 mai 2008 14:18:57 EDT
 

Buts:

  • [Récursivité, Recherche, Tri et Introduction à VS.NET2003].

Récursivité

  • Q1: Écrire la fonction récursive inverse. Cette fonction prend deux arguments une chaîne de caractères et la taille de cette chaîne; et modifie la chaîne en question en disposant ses caractères dans un ordre inverse.

  • Q2: On vous donne un segment donné de la mémoire contenant une série de chaînes de caractères, divisée en deux sections a et b. Ces deux sections sont disposées en mémoire dans cet ordre: d'abord a puis b. On vous donne aussi la taille de a et celle de b. Écrire la fonction itérative inverse_mem qui utilise la fonction récursive de la question -1- pour inter changer les sections a et b. Les sections seront disposées ainsi, d'abord la section b, elle sera suivie par la section a.

  • Q3: Écrire la fonction récursive compte_espaces(char* s) qui compte le nombre d'espaces blancs se trouvant dans une chaîne de caractères. Vous pouvez utiliser la fonction isspace() définie dans cctype pour déterminer si un caractère est un caractère d'espacement.

  • Q4: Écrire deux versions (itérative et récursive) d'une fonction permettant de tester si une chaîne donnée est un palindrome. Pour mémoire, une chaîne est un palindrome si elle peut être lue indifféremment dans les deux sens en gardant la même signification. Par exemple le mot "ressasser" en est un, "radar", "laval" de même que les phrases:

    "Elu par cette crapule"

    "Engage le jeu que je le gagne"


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:

    1. tant que T[f] est supérieur à T[d], décrémenter f de 1.
    2. permuter (s'il y a lieu) T[f] avec T[d]
    3. incrémenter d de 1.
    4. tant que T[d] est inférieur à T[f], incrémenter d.
    5. permuter (s'il y a lieu) T[d] avec T[f]
    6. décrémenter f
    7. 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.

    3726489810126845
    1226489810376845
    1226437810896845
    1226410837896845

.NET




pift1166@iro.umontreal.ca
[top]