IUT R&T - 1ère année - Informatique
Programmation et algorithmique 2

TD n°1 - Tableaux (suite)

EXERCICE 1

1.1. Ecrire en C une procédure  void Remplir(int Tableau[],int n)  qui remplit un tableau avec n entiers donnés par l'utilisateur.
N.B. Cette procédure modifiera le tableau par effet de bord.

1.2. Ecrire en C une procédure  void Afficher(int Tableau[],int n)  qui affiche les n valeurs d'un tableau d'entiers.

1.3. Ecrire en C la fonction correspondant à l'algorithme* ci-dessous. Cette fonction retournera la nouvelle taille du tableau après avoir modifié le tableau par effet de bord.
Problème Supprimer
Donnée : un tableau T de n entiers, une valeur entière x.
Résultat : toutes les occurrences** de x sont supprimées dans le tableau, la taille du tableau est mise à jour.
decalage←0;
Pour i de 0 à n−1 faire
T[i-decalage]←T[i];
Si T[i]=x alors decalage←decalage+1;
n←n−decalage;
*Si cet algorithme est erroné, rectifiez-le :-)
**occurrences : toutes les fois où x est présent dans T.

Exemple : Supprimer x=1 dans T=[5; −4; 1; 0; 1; 6; −1; 7; 1; −8], avec n=10, donne T=[5; −4; 0; 6; −1; 7; −8; *; *; *], avec trois suppressions et une nouvelle taille effective de 7 sur un total disponible de 10. Ainsi, par exemple la valeur 0 qui était dans T[3] a été transférée dans T[2] à cause de la suppression de la valeur x=1 de T[2].
N.B. Plus généralement, chaque valeur T[i]≠x sera déplacé vers T[i−k], où k est le nombre d'occurrence de x entre T[0]et T[i−1].

1.4. A faire hors TD : Pour tester les fonction et procédures ci-dessus, créer un programme qui :
– définit un tableau T de taille=10 entiers, la taille étant donnée par une macro-instruction.
– fait remplir ce tableau par l'utilisateur,
– affiche T,
– demande à l'utilisateur une valeur x,
– supprime toutes les occurrences de x dans T et affiche le nombre d'occurrences supprimées,
– affiche T après cette modification (en prenant en compte sa nouvelle taille).

EXERCICE 2

Ecrire en C une fonction Longueur qui donne, sans utiliser la fonction strlen, la longueur d'une chaine de caractères S de type char*.
Indications :
En C, une chaine de n caractères S de type char* est un tableau de longueur n+1 avec S[n]='\0' (caractère de code 0).
Au contraire, avec char S[n], on définit un tableau de n caractères.
Dans les deux cas, le k-ième caractère est S[k−1], puisqu'en C l'indiçage commence à 0.

EXERCICE 3

3.1. Ecrire un algorithme pour le problème suivant :
Problème EstPalindrome
Donnée : une chaine de caractère S de longueur n.
Résultat : S est-elle un palindrome ?
Exemples de palindromes : "ici", "radar", "elle", "esoperesteicietserepose".
Indications : utiliser deux indices i (antérograde) et j (rétrograde).

3.2. Traduire cet algorithme en C et écrire un programme qui l'utilise.
N.B. On peut utiliser ici la fonction prédéfinie strlen de string.h qui donne la longueur d'une chaine de type char* non vide.

Exercice 4 : à faire hors TD

Que modifier dans les questions 1.1. et 1.2. de l'exercice 1 pour travailler sur un tableau d'entiers à deux dimensions T[n;p] ?