Série 10
Structures
But
Cette série a pour but de vous faire pratiquer la notion de structure.Création du projet sous QTCreator
Afin de vous inciter à vous familiariser avec QTCreator, une façon simplifiée de configurer cet outil vous est proposé dans cette série. Inspirez-vous de la vidéo de la semaine 4 en utilisant cette fois l'archive serie10.zip.
Exercice 0 : reprise de l'exemple du cours (structures, niveau 0)
(page 45 dans la 2e édition).
Le but de cet exercice est de reprendre l'exemple du cours illustrant la gestion des structures.
Cliquez ici si vous souhaitez faire cet exercice.
Exercice 1 : Nombres complexes (structures, niveau 1)
Le but de ce programme est d'effectuer les manipulations élémentaires sur les nombres complexes : addition, soustraction, multiplication et division.
Dans le fichier complexes.cc, définissez une structure Complexe représentant un nombre complexe comme deux double (forme cartésienne).
Ensuite, prototypez puis définissez une procédure affiche qui prend un nombre complexe en argument et l'affiche.
Dans le main(), déclarez et initialisez un nombre complexe. Affichez-le. Compilez et exécutez votre programme pour vérifier que tout fonctionne comme prévu jusqu'ici.
Prototypez puis définissez une fonction addition qui prend deux nombres complexes en argument et retourne leur somme.
Testez votre fonction dans le main().
Terminez l'exercice en écrivant puis testant les fonctions soustraction, multiplication et division.
Rappel : la multiplication de z=(x,y) par z'=(x',y')
est le nombre complexe z*z'=(x*x'-y*y', x*y'+y*x').
la division de z=(x,y) par z'=(x',y')
est le nombre complexe z/z'=((x*x'+y*y')/(x'*x'+y'*y'),
(y*x'-x*y')/(x'*x'+y'*y')).
Exemple d'exécution
(1,0) + (0,1) = (1,1) (0,1) * (0,1) = (-1,0) (1,1) * (1,1) = (0,2) (0,2) / (0,1) = (2,0) (2,-3) / (1,1) = (-0.5,-2.5)
Exercice 2 : Relevés de températures (typedef, structures, algorithmes de base, niveau 2)
Soit l'ébauche de programme suivante (que vous pouvez copiez chez vous en cliquant sur ce lien) :
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
using namespace std;
/*modélisation d'une température*/
typedef double Temperature;
/* modélisation d'une date */
typedef string Date;
/* modélisation d'une mesure de température */
struct Mesure
{
// numéro d'identification unique de la mesure
int id;
//température relevée
Temperature temperature;
// date de la mesure
Date date;
};
/*modélisation d'un ensemble de relevés de températures*/
typedef vector<Mesure> Records;
constexpr double MAX_TEMP(60.0);
constexpr double MIN_TEMP(-60.0);
const string UNKNOWN_DATE("date inconnue");
Mesure find_max_record(const Records& records)
{
// A COMPLETER
}
double average_temperature(const Records& records)
{
// A COMPLETER
}
double find_closer_dates(const Records& records,
Date& date1,
Date& date2)
{
// A COMPLETER
}
int main()
{
Records r1 (
{
{ 4, 13.0, "10.3.2019" },
{ 5, 28.5, "10.8.2019" },
{ 6, 35.0, "10.7.2019" },
{ 7, 25.0, "10.10.2019" },
{ 8, 15.2, "11.11.2019" },
{ 9, 30.2, "10.9.2019" },
{ 10, 25.5, "10.9.2019" },
{ 1, 31.0, "10.7.2018" },
{ 2, -3.0, "10.1.2019" },
{ 3, -1.5, "10.2.2019" }
});
Mesure mesure(find_max_record(r1));
cout << "Le jour le plus chaud est le "
<< mesure.date
<< " avec "
<< mesure.temperature
<< " degrés"
<< endl;
cout << "La moyenne des températures est de "
<< average_temperature(r1)
<< " degrés"
<< endl;
Date date1(UNKNOWN_DATE);
Date date2(UNKNOWN_DATE);
double delta(find_closer_dates(r1, date1, date2));
cout << "Les deux dates avec l'écart le plus faible sont le "
<< date1
<< " et le "
<< date2
<< " avec un écart de "
<< delta << " degrés"
<< endl;
return 0;
}
Complétez-y les fonctions manquantes :
- la fonction find_max_record trouve la mesure avec la température la plus élevée (et la mesure { -1, MIN_TEMP, UNKNOWN_DATE} si l'ensemble des relevés passé en paramètre est vide);
- la fonction average_temperature trouve la moyenne des températures de l'ensemble de relevés passé en paramètres;
- la fonction find_closer_dates trouve les dates des deux relevés ayant le plus faible écart de températures entre eux, ainsi que cet écart. Pour calculer l'écart, utiliser la valeur absolue, donnée en C++ par la fonction double abs(double) de cmath.
L'exécution du programme doit donner ceci :
La moyenne des températures est de 19.89 degrés
Les deux dates avec l'écart le plus faible sont le 10.10.2019 et le 10.9.2019 avec un écart de 0.5 degrés
Exercice 3 : Questionnaire QCM (structures + vectors, niveau 2)
On cherche ici à faire un programme d'examen sous forme de questionnaire à choix multiple (QCM) où une question est posée et la réponse est à choisir parmi un ensemble de réponses proposées (une seule bonne réponse possible par question).
Dans un programme qcm.cc, définissez une structure QCM comprenant 3 champs :
- un champ question, chaîne de caractères, qui contiendra la question à poser
- un champ reponses qui sera un tableau de
taille variable de chaînes de caractères contenant les réponses
proposées
(c'est un tableau de taille variable car les questions n'auront pas toutes le même nombre de réponses proposées) - un champ entier solution (entier positif) qui contient le numéro de la bonne réponse (dans le champ reponses).
Prototypez puis définissez une procédure affiche qui prend un QCM en argument et l'affiche. Par exemple :
Combien de dents possède un éléphant adulte ?
1- 32
2- de 6 à 10
3- beaucoup
4- 24
5- 2
Dans le main(), créez et initialisez le QCM ci-dessus, puis affichez le. Compilez et vérifiez que tout fonctionne correctement jusqu'ici.
Reprenez la fonction demander_nombre (avec 2 arguments, point 4 de l'exercice 2 de la série 5) définie dans ../corriges-prog/5/code/proto5.cc , et créez une fonction poser_question qui prend un QCM en argument, appelle successivement affiche et demander_nombre et retourne la réponse de l'utilisateur.
Avant de continuer, testez votre programme (affichage de la question et saisie de la réponse).
On cherche maintenant à faire un examen de plusieurs questions. Définissez le type Examen comme un tableau dynamique de QMC. Créez un Examen dans le main(), puis remplissez-le (dans une fonction creer_examen c'est mieux !) avec les questions suivantes (code partiel) :
| C++11 | C++98 |
|---|---|
// Question 1
{ "Combien de dents possède un éléphant adulte",
{ "32", "de 6 à 10", "beaucoup", "24", "2" },
2 // réponse
},
// Question 2
{ "Laquelle des instructions suivantes est un prototype de fonction",
{ "int f(0);" ,
"int f(int 0);" ,
"int f(int i);" ,
"int f(i);" },
3 // réponse
},
// Question 3
{ "Qui pose des questions stupides",
{ "le prof. de math",
"mon copain/ma copine",
"le prof. de physique",
"moi",
"le prof. d'info",
"personne, il n'y a pas de question stupide",
"les sondages" } ,
6 // réponse
}
|
q.question = "Combien de dents possède un éléphant adulte";
q.reponses.push_back("32");
q.reponses.push_back("de 6 à 10");
q.reponses.push_back("beaucoup");
q.reponses.push_back("24");
q.reponses.push_back("2");
q.solution=2;
q.question = "Laquelle des instructions suivantes est un prototype de fonction";
q.reponses.push_back("int f(0);");
q.reponses.push_back("int f(int 0);");
q.reponses.push_back("int f(int i);");
q.reponses.push_back("int f(i);");
q.solution=3;
q.question = "Qui pose des questions stupides";
q.reponses.push_back("le prof. de math");
q.reponses.push_back("mon copain/ma copine");
q.reponses.push_back("le prof. de physique");
q.reponses.push_back("moi");
q.reponses.push_back("le prof. d'info");
q.reponses.push_back("personne, il n'y a pas de question stupide");
q.reponses.push_back("les sondages");
q.solution=6;
|
Pour terminer :
- Posez les questions une à une ;
- Comptez le nombre de bonnes réponses
- Donnez le score à la fin
Exemple d'exécution
Combien de dents possède un éléphant adulte ?
1- 32
2- de 6 à 10
3- beaucoup
4- 24
5- 2
Entrez un nombre entier compris entre 1 et 5 : 2
Laquelle des instructions suivantes est un prototype de fonction ?
1- int f(0);
2- int f(int 0);
3- int f(int i);
4- int f(i);
Entrez un nombre entier compris entre 1 et 4 : 3
Qui pose des questions stupides ?
1- le prof. de math
2- mon copain/ma copine
3- le prof. de physique
4- moi
5- le prof. d'info
6- personne, il n'y a pas de question stupide
7- les sondages
Entrez un nombre entier compris entre 1 et 7 : 5
Vous avez trouvé 2 bonnes réponses sur 3.
Exercice 4 : LIEN COURS ICC : problème du sac à dos (structures, tableaux, fonctions, niveau 2)
Cadre général
Le problème dit « du sac à dos » consiste à trouver, parmi un ensemble initial d'objets ayant chacun un poids et une valeur, quels objets mettre dans le sac de sorte que celui-ci ai une valeur maximale, mais ne pèse pas plus qu'un poids fixé au départ.
Par exemple, on chercher à remplir au mieux (valeur maximale) le sac à dos à partir des objets suivants, mais sans dépasser un poids total de 9 kg :
- boîte de 4 kg de valeur 8 ;
- bouteille de 2 kg de valeur 3 ;
- paquet de 5 kg de valeur 7 ;
- tente de 6 kg de valeur 10.
A noter que c'est bien la contrainte du poids maximal à ne pas dépasser qui rend ce problème « intéressant ». Sans une telle contrainte, il suffirait de tout mettre dans le sac pour maximiser sa valeur !
Ce problème « du sac à dos » est un problème NP-complet, c.-à-d. qu'à ce jour on ne connaît pas de meilleur algorithme pour le résoudre que celui qui consiste à essayer toutes les solutions.
Face à ce genre de problème, on peut alors chercher à ne pas le résoudre de façon optimale, mais utiliser un algorithme plus efficace que la recherche exhaustive, mais qui ne donnera qu'une solution approximative (une bonne solution mais qui n'est pas garantie pour être la meilleure).
Par exemple, un algorithme simple non optimal consiste à simplement remplir le sac avec les objets dans l'ordre dans lequel ils sont donnés/posés sur la table, si c'est possible (c.-à-d. ajouter l'objet ne fait pas dépasser le poids maximal autorisé).
Un autre algorithme simple non optimal consiste remplir le sac en mettant l'objet qui vaut le plus en premier si c'est possible, puis ensuite le 2e objet qui vaut le plus si c'est possible, etc. C'est le même algorithme que le précédent mais où l'on a au préalable trié les objets par valeurs décroissantes. On appelle cet algorithme, un algorithme « glouton » car il « veut » consommer le plus en premier.
Si l'on applique le premier algorithme à l'exemple ci-dessus :
- on met la boîte de 4 kg de valeur 8 : poids total = 4 kg, valeur totale = 8 ;
- on met la bouteille de 2 kg de valeur 3 : poids total = 6 kg, valeur totale = 11 ;
- on ne peut pas mettre le paquet de 5 kg car le poids total serait trop grand (11 kg) ;
- on ne peut pas non plus mettre la tente de 6 kg.
Au final, on arrive avec un poids total = 6 kg et une valeur totale de 11.
Si l'on applique l'algorithme glouton :
- on met la tente de 6 kg de valeur 10 (plus grande valeur) : poids total = 6 kg, valeur totale = 10 ;
- on ne peut pas mettre la boîte de 4 kg de valeur 8 (2e plus grande valeur) car le poids total serait trop grand (10 kg) ;
- on ne peut pas mettre le paquet de 5 kg non plus ;
- on met la bouteille de 2 kg de valeur 3 : poids total = 8 kg, valeur totale = 13.
Au final, on arrive avec un poids total = 8 kg et une valeur totale de 13, ce qui est déjà mieux.
Mais la solution optimale consiste ici à prendre la boîte et le paquet. Le poids total est de 9 kg et la valeur totale de 15.
Mise en pratique
Le but est de programmer ces trois algorithmes. Commencez pour cela par représenter la liste des objets possibles, par exemple comme un ensemble de paires de valeurs.
Implémentez ensuite la recherche naïve (premier algorithme) dans une fonction qui prend en paramètres une liste d'objets et un poids maximal. Cette fonction affichera la valeur maximale trouvée et le poids restant libre dans le sac (avec notre exemple, elle afficherait : « valeur : 11, poids restant : 3 kg »).
Implémenez ensuite l'algorithme glouton en :
- triant l'ensemble d'objets par valeurs décroissantes ;
- appliquant la fonction précédente.
La partie la plus difficile est la recherche exacte. Celle-ci se fera de façon récursive en considérant le meilleur résultat des deux solutions consistant à prendre ou non le premier objet de la liste puis rechercher sur la suite de la liste des objet.
Plus précisément : écrire une fonction (récursive) qui prend une liste d'objet, un index de début et un poids passé par référence et qui
- si la liste est vide retourne 0 (valeur d'une liste d'objet vide) ;
- sinon, lance la recherche sur la liste privée du premier élément (c.-à-d. en passant simplement l'index de départ à un de plus que celui reçu) et mémorise la valeur obtenue (appelons-la « valeur 1 ») ;
-
puis, si le poids du 1er objet est inférieur au poids maximum possible :
- relance la recherche sur la liste privée du premier élément (en passant l'index de départ plus 1) avec un poids maximal réduit du poids de ce 1er objet ;
- si la somme de la valeur obtenue par cette nouvelle recherche et de la valeur du 1er objet est plus grande que celle obtenue précédemment (« valeur 1 »), alors retourner cette somme, sinon retourner la « valeur 1 ».
Cette fonction retournera ainsi la valeur optimale du sac. Le poids restant, une fois le sac rempli, sera consigné dans le paramètre par référence.
Notez que pour trier un vector dont les valeurs sont de type Type (appelons-le vect), vous pouvez utiliser la fonction sort de la bibliothèque algorithm selon la syntaxe suivante:
sort(vect.begin(), vect.end(), greater)où greater est une fonction de prototype:
bool greater(Type val1, Type val2)retournant true si val1 est supérieure à val2 et false sinon. Dans notre cas, on considérera qu'un objet est supérieur à un autre si sa valeur est plus grande que celle de l'autre.
Exercice 5 : Devoir du MOOC
Vous êtes encouragés à programmer le devoir de la semaine 6 pour vous entraîner à l'utilisation de structures de données.