Correction 9
Structures

Exercice 1 : nombres complexes

#include <iostream>
using namespace std;
 
struct Complexe {
  double x;
  double y;
};
 
// Solution simple
void affiche(Complexe z) 
{
  cout << "(" << z.x << "," << z.y << ")";
 
  // autre solution :  cout << z.x << "+" << z.y << "i";
}
 
// Solution plus complexe mais plus élégante
void affiche2(Complexe z)
{
  if ((z.x == 0.0) and (z.y == 0.0)) {
    cout << "0";
    return;
  }
 
  if (z.x != 0.0) {
    cout << z.x;
    if (z.y > 0.0)
      cout << "+";
  }
  if (z.y != 0.0) {
    if ((z.x == 0.0) and (z.y == -1.0))
      cout << "-";
    else if (z.y != 1.0)
      cout << z.y;
    cout << "i";
  }
}
 
Complexe addition(Complexe z1, Complexe z2)
{
  return { z1.x + z2.x, z1.y + z2.y };
}
 
Complexe soustraction(Complexe z1, Complexe z2)
{
  return { z1.x - z2.x, z1.y - z2.y };
}
 
Complexe multiplication(Complexe z1, Complexe z2)
{
  return { z1.x * z2.x - z1.y * z2.y ,
           z1.x * z2.y + z1.y * z2.x };
}
 
Complexe division(Complexe z1, Complexe z2)
{
  const double r(z2.x*z2.x + z2.y*z2.y);
  return { (z1.x * z2.x + z1.y * z2.y) / r ,
	   (z1.y * z2.x - z1.x * z2.y) / r };
}
 
int main()
{
  Complexe un = { 1.0, 0.0 };
  Complexe i  = { 0.0, 1.0 };
 
  affiche(un); cout << " + "; affiche(i); cout << " = ";
  Complexe j(addition(un, i));
  affiche(j); cout << endl;
 
  affiche(i); cout << " * "; affiche(i); cout << " = ";
  affiche(multiplication(i,i)); cout << endl;
 
  affiche(j); cout << " * "; affiche(j); cout << " = ";
  Complexe z(multiplication(j,j));
  affiche(z); cout << endl;
 
  affiche(z); cout << " / "; affiche(i); cout << " = ";
  affiche(division(z,i)); cout << endl;
 
  z= { 2.0, -3.0 };
  affiche(z); cout << " / "; affiche(j); cout << " = ";
  affiche(division(z,j)); cout << endl;
 
  return 0;
}

Exercice 2 : Relevés de températures (structures, algorithmes de base, niveau 2)

#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");

/* ======================================================================
 * Trouve la mesure avec la température maximale
 * dans un ensemble de mesures
 */
Mesure find_max_record(const Records& records)
{
	Mesure mesure ({ -1, MIN_TEMP, UNKNOWN_DATE });
	if (records.empty()) return mesure;

	Mesure max_mesure(records[0]);

	for (size_t i(1); i < records.size(); ++i){
		if (records[i].temperature > max_mesure.temperature){
			max_mesure = records[i];
		}
	}
	return max_mesure;
}

/* ======================================================================
 * Trouve la moyenne des températures relevées
 * dans un ensemble de mesures
 */

double average_temperature(const Records& records)
{
	double average(0.);
	if (records.empty()) return average;
	for (const auto& mesure : records){
		average += mesure.temperature;
	}

	return average/records.size();
}

/* ======================================================================
 * Trouve les deux dates où les mesures ont les températures les 
 * plus proches et retourne l'écart de température entre ces deux
 * mesures
 */
double find_closer_dates(const Records& records,
						 Date& date1,
						 Date& date2)
{
	date1 = UNKNOWN_DATE;
	date2 = UNKNOWN_DATE;
	double min_diff (abs(MAX_TEMP-MIN_TEMP));
	double diff(min_diff);
	/* une façon simple de faire consiste à
	 * considérer toutes les paires de mesures possibles
	 * en imbriquant deux boucles for :
	 */
	for (const auto& mesure1 : records){
		for (const auto& mesure2 : records){
			diff  = abs(mesure1.temperature - mesure2.temperature);
			// il faut cependant faire attention à ne pas comparer
			// une mesure avec elle-même !!
			if ( (mesure1.id != mesure2.id) and diff < min_diff ) {
				date1 = mesure1.date;
				date2 = mesure2.date;
				min_diff = diff;
			}
		}
	}
	return min_diff;
}


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;
}

Exercice 3 : QCM

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
struct QCM {
  string question;
  vector<string> reponses;
  unsigned int solution;
};
 
typedef vector<QCM> Examen;
 
void affiche(const QCM& question);
unsigned int demander_nombre(unsigned int min, unsigned int max);
unsigned int poser_question(const QCM& question);
Examen creer_examen();
 
// ======================================================================
int main()
{
  unsigned int note(0);
  Examen exam(creer_examen());
 
  for (auto question : exam) {
    if (poser_question(question) == question.solution) {
      ++note;
    }
  }
 
  cout << "Vous avez trouvé " << note << " bonne";
  if (note > 1) cout << 's';
  cout << " réponse";
  if (note > 1) cout << 's';
  cout << " sur " << exam.size() << "." << endl;
 
  return 0;
}
 
 
// ======================================================================
void affiche(const QCM& q)
{
  cout << q.question << " ?" << endl;
  unsigned int i(0);
  for (auto reponse : q.reponses) {
    cout << "    " << ++i << "- " << reponse << endl;
  }
}
 
// ======================================================================
unsigned int demander_nombre(unsigned int a, unsigned int b)
{
  unsigned int res;
 
  if (a > b) { res=b; b=a; a=res; }
 
  do {
    cout << "Entrez un nombre entier compris entre "
	 << a << " et " << b <<" : ";
    cin >> res;
  } while ((res < a) or (res > b));
 
  return res;
}
 
// ======================================================================
unsigned int poser_question(const QCM& q)
{
  affiche(q);
  return demander_nombre(1, q.reponses.size());
}
 
// ======================================================================
Examen creer_examen()
{
  return {
    // 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
    }
  };
}

Exercice 4 : LIEN PARTIE THÉORIQUE : problème du sac à dos (structures, tableaux, fonctions, niveau 2)

#include <iostream>
#include <vector>
#include <algorithm> // pour sort()
using namespace std;
 
struct Object {
  double weight;
  double value;
};
 
/* ======================================================================
 * This is the first algorithm:
 * solve it naively, in the given order.
 */
void solve_naive(vector<Object> const& objects, double remaining_weight)
{
  double value(0.0);
  for (auto const& object : objects) {
    cout << "considering : w=" << object.weight << ", v=" << object.value;
    if (object.weight <= remaining_weight) {
      value += object.value;
      remaining_weight -= object.weight;
      cout << " --> taking";
    }
    cout << endl;
  }
  cout << "value = " << value << ", remaining weight = " << remaining_weight << endl;
}
 
// ======================================================================
bool higher_value(Object const& o1, Object const& o2)
{ return o1.value > o2.value; }
 
/* ======================================================================
 * This is the second algorithm: greedy.
 */
void solve_greedy(vector<Object> const& objects, double maximum_weight)
{
  vector<Object> sorted_objects(objects); // need a copy to sort
  sort(sorted_objects.begin(), sorted_objects.end(), higher_value);
  solve_naive(sorted_objects, maximum_weight);
}
 
/* ======================================================================
 * This is the third algorithm: try all.
 */
double solve_exact_recursive(vector<Object> const& objects, size_t start, double& remaining_weight)
{
  double best_value(0.0);
 
  if ((not objects.empty()) and (start < objects.size())) {
    // 1) consider NOT taking first object
    double best_remaining_weight(remaining_weight);
    best_value = solve_exact_recursive(objects, start+1, best_remaining_weight);
 
    // 2) consider taking the first object, if possible
    if (objects[start].weight <= remaining_weight) {
      double weight(remaining_weight - objects[start].weight);
      const double value(objects[start].value + solve_exact_recursive(objects, start+1, weight));
 
 
      // 3) keep the best of the two
      if (value > best_value) {
        best_remaining_weight = weight;
        best_value = value;
      }
    }
    remaining_weight = best_remaining_weight;
  }
  return best_value;
}
 
void solve_exact(vector<Object> const& objects, double remaining_weight)
{
  double value(solve_exact_recursive(objects, 0, remaining_weight));
  cout << "value = " << value << ", remaining weight = " << remaining_weight << endl;
}
 
// ======================================================================
int main()
{
  const vector<Object> objects({
      { 4.0,  8.0 },
      { 2.0,  3.0 },
      { 5.0,  7.0 },
      { 6.0, 10.0 },
  });
  constexpr double MAX(9.0);
 
  solve_naive (objects, MAX);
  solve_greedy(objects, MAX);
  solve_exact (objects, MAX);
 
  return 0;
}