Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

MOOC Init Prog C++ Corrigés semaine 8 Les corrigés proposés correspondent à l'o

MOOC Init Prog C++ Corrigés semaine 8 Les corrigés proposés correspondent à l'ordre des apprentissages : chaque corrigé correspond à la solution à laquelle vous pourriez aboutir au moyen des connaissances acquises jusqu'à la semaine correspondante. Exercice 23 : tranche maximale Pour commencer, on avait à faire : 1. Définissez le type Position comme un entier non-signé Solution : typedef unsigned int Position; 2. Définissez le type Sequence comme un tableau d'entiers. Solution : typedef vector<int> Sequence; 3. Définisez la structure SousSequence contenant 2 champs, debut et fin, de type Position, et un champs somme de type entier. Solution : struct SousSequence { Position debut; Position fin; int somme; }; 4. Dans le main(), déclarez la variable seq de type Sequence et initialisez la une valeur choisie, par exemple : 11, 13, -4, 3, -26, 7, -13, 25, -2, 17, 5, -8, 1 Solution C++11 : int main() { Sequence seq = { 11, 13, -4, 3, -26, 7, -13, 25, -2, 17, 5, -8, 1 return 0; } En C++98, il faudrait ajouter toutes ces valeurs une à une avec des push_back(). 5. Ensuite, il nous fallait définir tranche_max_1. Commençons par son prototype : SousSequence tranche_max_1(Sequence a); L'implémentation de l'algorithme donné ne doit poser aucun problème. Il faut juste, informatiquement, faire attention au cas où la séquence est vide, et éviter les «Segmentation Fault» : SousSequence tranche_max_1(Sequence a) { SousSequence rep = { 0, 0, 0 }; if (a.size() != 0) { rep.somme = a[0]; for (Position debut(0); debut < a.size(); ++debut) { for (Position fin(debut); fin < a.size(); ++fin) { int somme(0); for (Position p(debut); p <= fin; ++p) { somme += a[p]; } if (somme > rep.somme) { rep.debut = debut; rep.fin = fin; rep.somme = somme; } } } } return rep; } Voici donc le programme complet : #include <iostream> #include <vector> using namespace std; typedef size_t Position; typedef vector<int> Sequence; struct SousSequence { Position debut; Position fin; int somme; }; // PROTOTYPES SousSequence tranche_max_1(Sequence a); SousSequence tranche_max_2(Sequence a); SousSequence tranche_max_3(Sequence a); void affiche(SousSequence s, Sequence a); // ---------------------------------------------------------------------- int main() { /* ATTENTION, Les initialisations ci-dessous ne sont valables qu'en C++ * Si vous compilez en C++98, utilisez des push_back(); */ Sequence seq = { 11, 13, -4, 3, -26, 7, -13, 25, -2, 17, 5, -8, 1 } // Sequence seq = { -3, -4, -1, -2, -3 }; // Sequence seq = { -1, -4, -3, -2, -3 }; // Sequence seq = { 3, 4, 1, 2, -3 }; // Sequence seq = { 3, 4, 1, 2, 3 }; // Sequence seq = { 3, -1, -1, -1, 5 }; // Sequence seq = { -5, -4, 1, 1, 1 }; affiche(tranche_max_1(seq), seq); affiche(tranche_max_2(seq), seq); affiche(tranche_max_3(seq), seq); return 0; } /* ====================================================================== * Recherche la sous-sequence de somme maximale dans une sequence. * L'algorithme utilisé ici est l'algorithe naïf de complexité cubique. * Entree : la sequence où chercher * Sortie : la sous-séquence de somme maximale * ====================================================================== SousSequence tranche_max_1(Sequence a) { SousSequence rep = { 0, 0, 0 }; if (a.size() != 0) { rep.somme = a[0]; for (Position debut(0); debut < a.size(); ++debut) { for (Position fin(debut); fin < a.size(); ++fin) { int somme(0); for (Position p(debut); p <= fin; ++p) { somme += a[p]; } if (somme > rep.somme) { rep.debut = debut; rep.fin = fin; rep.somme = somme; } } } } return rep; } /* ====================================================================== * Recherche la sous-sequence de somme maximale dans une sequence. * L'algorithme utilisé ici est l'algorithe naïf de complexité quadrati * Entree : la sequence où chercher * Sortie : la sous-séquence de somme maximale * ====================================================================== SousSequence tranche_max_2(Sequence a) { SousSequence rep = { 0, 0, 0 }; if (a.size() != 0) { rep.somme = a[0]; for (Position debut(0); debut < a.size(); ++debut) { int somme(0); for (Position fin(debut); fin < a.size(); ++fin) { somme += a[fin]; if (somme > rep.somme) { rep.debut = debut; rep.fin = fin; rep.somme = somme; } } } } return rep; } /* ====================================================================== * Recherche la sous-sequence de somme maximale dans une sequence. * L'algorithme utilisé ici est l'algorithe linéaire * Entree : la sequence où chercher * Sortie : la sous-séquence de somme maximale * ====================================================================== SousSequence tranche_max_3(Sequence a) { SousSequence rep = { 0, 0, 0 }; if (a.size() != 0) { rep.somme = a[0]; int somme(0); Position debut(0); for (Position fin(0); fin < a.size(); ++fin) { somme += a[fin]; if (somme > rep.somme) { rep.debut = debut; rep.fin = fin; rep.somme = somme; } if (somme <= 0) { debut = fin + 1; somme = 0; } } } return rep; } // ---------------------------------------------------------------------- void affiche(SousSequence s, Sequence seq) { cout << "La tranche maximale est "; for (Position i(s.debut); i <= s.fin; ++i) cout << seq[i] << ", "; cout << endl << "de somme " << s.somme << endl; } Exercice 24 : tri de Shell Cet exercice correspond à l'exercice n°44 (pages 98 et 288) de l'ouvrage C++ par la pratique (3e édition, PPUR). La principale difficulté de cet exercice réside dans la manipulation des indices. Le but premier de cet exercice est en effet de vous faire réfléchir au passage de la notation mathématique (qui utilise des indices de 1 à N) à la notation C++ (qui utilise des indices de 0 à N-1). Très souvent, il suffit de changer la boucle 1->N en une boucle 0->N-1 et le tour est joué. Mais en fait la vraie bonne traduction est plus subtile que cela. Quand en math on note ui, i.e. le i-ème élément de u (i ≥ 1), cela correspond en C++ à un u[i-1]. Donc, en fait, c'est l'accesseur aux éléments du tableau qui translate les indices de 1, et lui seul ! La seule et unique bonne façon de passer de la notation mathématique à la notation C++ à tous les coups sans se tromper consiste donc à translater (de 1) tous les accesseurs. Ni plus, ni moins. Ensuite, et seulement ensuite, si une écriture plus simple existe, alors on peut réécrire le tout (avec un changement d'indice). C'est exactement ce qui se passe pour le cas des boucles les plus simples que l'on peut donc écrire de 0 à N-1. Mais ceci n'est qu'un cas particulier, très simple, qui ne fonctionne pas à tous les coups... ...en particulier pas pour le tri Shell qui a des boucles plus compliquées (voir le corrigé). Pour finir, un autre piège ici serait de coder j en unsigned : il peut être négatif (comme indiqué dans la donnée). #include <iostream> #include <vector> #include <utility> // pour swap using namespace std; typedef int type_el; typedef vector<type_el> Tableau; void affiche(const Tableau& tab) { for (auto el : tab) cout << el << " "; } void tri_Shell(Tableau& tab) { for (size_t k(tab.size()/2); k >= 1; k /= 2) for (size_t i(k+1); i <= tab.size(); ++i) { int j(i-k); while (j > 0) { if (tab[j-1] > tab[j+k-1]) { swap(tab[j-1], tab[j+k-1]); affiche(tab); cout << endl; j -= k; } else { j = 0; } } } } int main() { Tableau tab = { 3, 5, 12, -1, 215, -2, 17, 8, 3, 5, 13, 18, 23, 5, 4, 3, 2, 1 }; tab = { 5, 4, 1, 2, 3 }; cout << "A trier : "; affiche(tab); cout << endl; tri_Shell(tab); cout << "Résultat : "; affiche(tab); cout << endl; return 0; } Exercice 25 : culture de masse Cet exercice correspond à l'exercice n°43 (pages 97 et 282) de l'ouvrage C++ par la pratique (3e édition, PPUR). On peut imaginer de très nombreuses manières pour résoudre cet exercice et ce n'est que l'une d'entre elles qui est présentée ici. Partie 1 : le calcul des points Il faut commencer par définir les structures de données qui nous permettrons de stocker les résultats de chaque équipe : struct Equipe { string nom; int points; int marques; int encaisses; }; struct Match { int prems; int deuz; }; En utilisant ces structures, définissons (dans la fonction main) le tableau déterminant la liste des matchs, ainsi que celui permettant de stocker les résultats de chaque équipe : array<Match, 6> matchs = { {3, 1}, // Suisse - Croatie {2, 0}, // France - Angleterre {3, 0}, // Suisse - Angleterre {2, 1}, // France - Croatie {0, 1}, // Angleterre - Croatie {3, 2} // Suisse - France }; array<Equipe, 4> groupe2 = { { "Angleterre" , 0, 0, 0 }, // equipe 0 { "Croatie" , 0, 0, 0 }, // equipe 1 { "France" , 0, 0, 0 }, // equipe 2 { "Suisse" , 0, 0, 0 }, // equipe 3 }; Il faut maintenant initialiser les données du tableau des équipes. Pour cela, on itère sur les matchs ayant été joués, et pour chacun d’eux on demande à l’utilisateur le résultat. On peut dans le même temps cumuler les nombres de buts marqués et encaissés pour les équipes protagonistes, et uploads/Science et Technologie/ corrigeexosem-8.pdf