Université Ibn Tofail
Ecole Supérieure de Technologie
Kénitra
Algorithmique Avancé et Structures de Données Abstraites
DUT / Génie Informatique (S2)
TP N° 1 : Les Types composés
Partie I : Exercices préliminaires
Exercice 1 : Recherche de sous-séquences
Écrire un programme C qui, à partir d’un tableau d’entiers T d’au moins un entier, fournit le
nombre de sous-séquences croissantes de ce tableau, ainsi que les indices de début et de fin
de la plus grande sous-séquence.
- Par exemple, soit T un tableau de 15 éléments :
1, 2, 5, 3, 12, 25, 13, 8, 4, 7, 24, 28, 32, 11, 14
- Les séquences strictement croissantes sont :
<1, 2, 5>;<3, 12, 25>;<13>;<8>;<4, 7, 24, 28, 32>;<11, 14>
- Le nombre de sous-séquence est : 6 et la plus grande sous-séquence est :
< 4, 7, 24, 28, 32 >
Exercice 2 : Fusionner deux tableaux triés
Ecrire un programme C qui permet de fusionner deux tableaux triés dans un troisième
tableau. Mettre bout à bout deux tableaux triés de façon que le tableau résultant soit trié, et
ce, sans exécuter de tris (coûteux).
Indication : Parcourir les 2 tableaux (avec 2 indices), et recopier dans le 3ème tableau la
plus petite des 2 valeurs du 1er et du 2nd tableau ; puis avancer dans le tableau d’où on a
recopié la valeur. A la fin de ce traitement, l’un des tableaux est copié, il suffit de copier les
éléments restant de l’autre.
Exercice 3 : Produit matriciel
Écrire un programme qui réalise le produit C(N,P) de deux matrices A(N,M) et B(M,P).
Avec N, M et P sont les dimensions des matrices.
Le calcul de la composante 𝐂𝐢,𝐣 est comme suit :
𝐌
𝐂𝐢,𝐢 = ∑ 𝐀 𝐢,𝐤 × 𝐁𝐤,𝐣
𝐤=𝟏
Exercice 4 : Structure Point
On considère deux tableaux de réels Tx et Ty de taille N représentant les positions de N points
différents dans le plan. Tx contient les abscisses x et Ty les ordonnées y des N points.
Pr. Moulay Youssef Hadi 1/3 DUT / GI S4)
Université Ibn Tofail
Ecole Supérieure de Technologie
Kénitra
Tx et Ty sont des variables globales et N est une constante globale. x et y sont des réels.
Ainsi, le plan est divisé en deux demi plan : demi plan sup (y≥0) et demi plan inf (y<0).
Exemple de 10 points :
Le 1er point (i=0) de coordonnée x=-0.7 et y=1.2 se trouve dans le demi plan supérieur.
Le 2ème point de coordonnée x=-0,1 et y=-1 se trouve dans le demi plan inférieur.
1. Définir une structure Point représentant un point dans un plan avec ses coordonnées
x et y.
2. Ecrire un programme C qui déclare les deux tableaux Tx et Ty et qui les copies dans
un tableau de structure Tp de type Point de taille N.
Exemple : Tp[2].x = Tx[2] et Tp[2].y = Ty[2]
3. Tester si un point d’indice i et j se trouve dans le plan sup ou dans le plan inf.
4. Calculer la distance dij entre les points d’indices i et j.
5. Calculer la distance dmax entre les 2 points les plus éloignés l’un de l’autre.
6. Calculer la distance di entre le point i et l’origine (0,0).
7. Calculer le rayon du cercle rmax, autour de l’origine, formé par le point du plan le plus loin
de l’origine.
8. Calculer le rayon du cercle rmin, autour de l’origine, formé par le point du plan le plus
proche de l’origine.
Partie II : Problème (Gestion de la facturation)
L’objectif de ce TP est de créer un programme qui permet de gérer la facturation d’un magasin
qui vent des produits achetés par des clients. Chaque produit a un code, un libellé et un prix de
vente. Un produit est représenté par la structure suivante :
typedef struct Produit{
int code;
char libelle[20];
float prix;
}Produit;
Le client qui achète les produits à un nom et une adresse (on se limite à la ville). Le client est
représenté par la structure suivante :
typedef struct Client{
char nom[20];
char adresse[40];
}Client;
Le client peut commander un produit avec une quantité définie. Cette commande est désignée
sous le nom ligne de commande et peut être représenté par la structure suivante :
typedef struct LigneCommande{
Produit prod;
int qte;
}LigneCommande;
Pr. Moulay Youssef Hadi 2/3 DUT / GI S4)
Université Ibn Tofail
Ecole Supérieure de Technologie
Kénitra
1. En utilisant les structures définies, écrire un programme main qui permet de :
a. Créer 3 produits et les saisir avec les données suivantes :
Code Libellé Prix
Produit p1 11 Table 3000
Produit p2 22 Chaise 250
Produit p3 33 PC 9000
b. Créer 3 lignes de commande et les saisir avec les données suivantes :
Produit Quantité
LigneCommande c1 p1 5
LigneCommande c2 p2 8
LigneCommande c3 p3 2
c. Créer 1 client et le saisir avec les données suivantes :
Nom Adresse
Client e Hamid Kenitra
d. Afficher l’ensemble des données des variables crées.
On désir maintenant créé la facture du client contenant l’ensemble des produits commandés par
le client (un tableau de ligne de commande de taille fixé par une constante N). La facture à un
numéro (num) et concerne un client (cli) qui commande un nombre quelconque (nbLC) de
produits dans une date donnée (dateFacture). La facture peut être représentée par la structure
suivante :
#define N 100
typedef struct Facture{
long num;
Client cli;
char dateFacture[10];
LigneCommande ligneC[N];
int nbLC;
float tva;
}Facture;
2. Ajouter au programme précédant la déclaration d’une facture f.
3. Saisir la facture f avec les données des variables crées et l’afficher comme suit :
Facture num : 1234 Date : 04/03/2021
Client : Hamid
Adresse : Kenitra
TVA : 20.00
-------------------------------------------------------------------
Designation Prix HT Quantite Prix TTC
-------------------------------------------------------------------
11 Table 3000.00 5 18000.00
22 Chaise 250.00 8 2400.00
33 PC 9000.00 2 21600.00
-------------------------------------------------------------------
Total : 42000.00
-------------------------------------------------------------------
-- FIN TP --
Pr. Moulay Youssef Hadi 3/3 DUT / GI S4)
