IUT R&T - 1ère année - Informatique
Programmation et algorithmique 2
TP n°2.5
A la fin du TP, envoyer sur l'ENT le programme contenant une solution de l'exercice 1 ainsi que les algorithmes et tests associés (même principe que pour le TP1)
EXERCICE 1*
1.1. Créer une fonction nommée CreerTableau qui prend en paramètre un entier naturel n et qui crée dynamiquement un tableau de n entiers. La fonction retournera la taille du tableau créé, ou −1 en cas de problème.
1.2. Créer une fonction nommée DesallouerTableau qui désalloue un tel tableau.
1.3. Créer une fonction nommée RemplirTableau qui remplit aléatoirement un tableau T de n entiers.
La fonction retournera 0 s'il n'y a pas eu de problème.
N.B. Plutôt que d'utiliser le générateur aléatoire de C, vous pouvez utiliser un polynôme avec plusieurs zéros positifs. Par exemple la valeur placée dans chaque T[i] peut être la partie entière de : i4 −100 i3 +3000 i2 −600 i +80000, basée sur le polynôme P(x)=x4−100x3+3000x2−600x+80000.
1.4. Créer une fonction nommée AfficheTableau qui affiche un tableau de n entiers. La fonction retournera −1 en cas de problème ou 0 sinon.
1.5. Créer une fonction nommée TrierTableauqui trie un tableau de n entiers par ordre croissant.
1.6. Créer, dans le programme principal, un menu à la disposition de l'utilisateur sur le modèle suivant. Le programme saisira un caractère fournit par l'utilisateur avec getchar pour réaliser un des items du menu. Les caractères autres que ceux attendus ('0' à '1') seront ignorés.
N.B. Si l'utilisateur saisit : 1234, les quatre commandes '1' à '4' seront réalisées et le retour à la ligne (caractère '\n') de fin de saisie sera ignoré.
-1- Création aléatoire d'un tableau de taille n donnée
-2- Affichage du tableau
-3- Trier le tableau
-4- Effacer le tableau
-0- Quitter
---
N.B. Le programme devra être robuste et convivial. Il prendra notamment en compte le fait qu'une instruction puisse être incompatible avec une des précédentes. Les allocations mémoires seront libérées en terminant le programme.
EXERCICE 2
On veut réaliser la "linéarisation" d'un tableau T à deux dimensions en recopiant les valeurs de T dans un tableau U à une dimension.
2.1. Ecrire une fonction nommée CreerT2 qui prend en paramètres deux entiers naturels non nuls p et q, et qui retourne un tableau à deux dimensions p×q rempli aléatoirement.
2.2. Ecrire une fonction nommée Lineariser qui prend en paramètres un tableau T à deux dimensions et ses deux dimensions p et q, et retourne un tableau à une dimension pq alloué dynamiquement et rempli avec les valeurs de T.
2.3. Compléter le programme pour tester ces fonctions.
2.4. Ecrire un algorithme qui trie les valeurs d'un tableau à deux dimensions de manière que T[h,i]≤T[h,i+1] et T[h,i]<T[h+1,j] pour tous i, j, k.
N.B. On pourra utiliser une linéarisation implicite du tableau en gérant un indice unique calculé à partir des deux indices du tableau à deux dimensions.
EXERCICE 3 (A faire hors TD)
En quoi l'exercice 1 peut-il aider à créer un programme pour les questions suivantes ?
On veut réaliser une loterie en tirant au hasard des boules numérotées dans un sac.
1.1. Définir un tableau Sac de 50 booléens pour préciser si chaque boule Sac[i] de numéro i est dans le sac.
1.2. Créer une fonction nommée combien qui donne au hasard un entier, compris entre 1 et 50, qui correspond au nombre de boules que l'on veut retirer du sac.
1.3. Créer une fonction nommée tirage qui retire n boules d'un sac. La fonction retournera la liste des numéros des boules tirées. Cette liste sera créée par allocation dynamique.
1.4. Créer une fonction nommée liberer qui libère l'espace mémoire occupé par une liste de numéros de boules. La fonction retournera 0 en cas de succès, 1 si la liste n'avait pas été allouée auparavant, et −1 en cas d'autre problème.
1.5. Tester ce programme avec une interface conviviale.