Remerciez-le!

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

´ Ecole Centrale de Nantes EI1 – 2013 / 2014 Algorithmique et Programmation Dev

´ Ecole Centrale de Nantes EI1 – 2013 / 2014 Algorithmique et Programmation Devoir Surveill´ e, Algorithmique et Programmation 18 novembre 2013, de 8h ` a 10h (+30 min pour les ´ etudiants ´ etrangers – amphi A) Aucun Document Autoris´ e la ﬁche de traduction est disponible en derni` ere page du sujet Nom : Pr´ enom : Groupe : Note : 1. R´ epondez sur l’´ enonc´ e : les r´ eponses fournies hors de la zone r´ eserv´ ee pourront ˆ etre ignor´ ees par le correcteur ; 2. Les questions sont de diﬃcult´ es vari´ es, lisez le sujet en entier avant de commencer ; 3. Les algorithmes sont ` a r´ ediger en fran¸ cais ou en anglais, et non pas en langage de programmation. 4. Sauf mention explicite du contraire, on suppose que la num´ erotation des indices des tableaux commence ` a 0 ; 1 / 10 ´ Ecole Centrale de Nantes EI1 – 2013 / 2014 1 Algorithmes 1.1 Analyse d’algorithme (3 points) Question 1 : Que repr´ esente le type de donn´ ees ? Que fait cet algorithme principal, ainsi que la fonction qu’il utilise ? types t myType : Enregistrement entier a, t myType b, t myType c, Fin enregistrement monAlgoPrincipal variables entier : a t myType : t d´ ebut t ←lire("input data.txt") a ←myFunction(t) ´ ecrire("la valeur est " + a) fin fonction myFunction : r ←myFunction(u) entr´ ees t myType : u sorties entier : r d´ ebut r ←u.a si (u.b ̸= RIEN) alors r ←max(r, myFunction(u.b)) finsi ´ ecrire(u.a + " :") si (u.c ̸= RIEN) alors r ←max(r, myFunction(u.c)) finsi retourner r fin 2 / 10 ´ Ecole Centrale de Nantes EI1 – 2013 / 2014 1.2 ´ Ecriture d’algorithmes (4 points) Question 2 : ´ Ecrivez un algorithme qui permet de traiter une ﬁle de caract` eres alphanum´ eriques sur le mod` ele (caract` ere, chiﬀre, caract` ere, chiﬀre, ... caract` ere, chiﬀre) termin´ ee par un point. Le premier traitement transforme la ﬁle en ´ ecrivant un nombre de caract` ere ´ egal au chiﬀre qui suit, et supprime le chiﬀre. Le deuxi` eme traitement demande un motif ` a l’utilisateur, et fait une recherche du nombre de motif pr´ esent dans la ﬁle. Vous ne pouvez pas stocker toute la ﬁle d’entr´ ee en m´ emoire (dans un tableau ou dans un ﬁchier), mais vous pouvez stocker le motif et le r´ esultat du premier traitement. exemple : file d’entr´ ee : a 1 b 2 c 0 a 1 b 1 d 0 b 1 a 1 b 2 e 0 a 1 . r´ esultat du premier traitement : a b b a b b a b b a . motif entr´ e par l’utilisateur : a b b a r´ esultat du deuxi` eme traitement : 3 3 / 10 ´ Ecole Centrale de Nantes EI1 – 2013 / 2014 4 / 10 ´ Ecole Centrale de Nantes EI1 – 2013 / 2014 2 Programmation 2.1 Analyse de code C++ (4 points) Question 3 : D´ eboguez le code suivant (rayez les erreurs et corrigez directement dans le code) : /* author : V. Tourre file name : question3debug.cpp */ #include <cstdlib> #include <fstream> int division(int a, int b, int& c, int* d){ c = a/b; *d = a%b; } void main(void){ int a, b q; cout << "Entrer le nombre ` a diviser" << endl cin >> a; while(a < 0) { cout << "Le nombre doit ^ etre positif ou nul" << endl; cin >> a; } cout << "Entrer le diviseur" >> endl; cin >> b; while(b < 1) cout << "Le nombre doit ^ etre positif" << endl; cin >> b; } division(a, b, &q, r); cout << "le r´ esultat de la division est " << q << endl << "le reste de la division est << r << endl; return (EXIT_SUCCESS); } 5 / 10 ´ Ecole Centrale de Nantes EI1 – 2013 / 2014 2.2 ´ Ecriture de code C++ (6 points) Question 4 : ´ Ecrivez en C++ : – la d´ eﬁnition d’une liste d’entier simplement chain´ ee t liste dans un ﬁchier typedef.h, – une fonction d’aﬃchage d’une liste et une fonction de somme des ´ el´ ements d’une liste dans un ﬁchier fonctions.cpp ainsi que la d´ eclaration de ces fonctions dans un ﬁchier fonctions.h associ´ e, – un programme principal dans un ﬁchier main.cpp qui cr´ e´ e une liste ` a partir d’un ﬁchier, aﬃche cette liste et calcule la somme de ces ´ el´ ements. La d´ eclaration de la fonction creerListe pour cr´ eer une liste ` a partir d’un ﬁchier est fournie dans un ﬁchier utils.h. Vous ne devez pas ´ ecrire la fonction creerListe, vous devez l’utilisez dans votre fonction principale. /* utils.h */ t_liste creerListe(string nomFichier); 6 / 10 ´ Ecole Centrale de Nantes EI1 – 2013 / 2014 7 / 10 ´ Ecole Centrale de Nantes EI1 – 2013 / 2014 8 / 10 ´ Ecole Centrale de Nantes EI1 – 2013 / 2014 3 Analyse descendante (3 points) Proposez un programme pour trier une liste de mots par ordre alphab´ etique. Le programme permettra de charger un ensemble de mots depuis un ﬁchier, de trier les mots avec l’algorithme de votre choix et de stocker le r´ esultat dans un ﬁchier texte. Question 5 : Faire l’analyse descendante de ce probl` eme : les structures de donn´ ees, l’algorithme principal (forme libre autoris´ ee), les sp´ eciﬁcations des fonctions secondaires pertinentes, et l’algorithme de la fonction de tri. 9 / 10 ´ Ecole Centrale de Nantes EI1 – 2013 / 2014 10 / 10 Correspondance Algorithme & C++ STRUCTURES DE DONNÉES Types de données (simples) booléen bool entier int réel float ou double caractère char Données simples variables entiers nb1, nb2, somme int nb1, nb2, somme; réel moyenne float moyenne; constantes réel PI const float PI=3.15; entier MAX const int MAX=10; caractère OUI const char OUI=’o’; Opérateurs < ≰= = ≥> < <= != == >= > et ou non && || ! Types de données (composés) types Tableaux t_VectEnt : vecteur d’entiers typedef int t_VectEnt[MAX]; t_MatReels : matrice de réels typedef float t_MatReels[MAX][MAX]; Enregistrements t_Article : enregistrement entier : référence Chaine_de_caractère : libellé réel : prix ﬁn enregistrement # include<string> using namespace std; struct t_Article { int reference; string libelle; float prix; }; Données composées t_VectEnt vect t_VectEnt vect; t_MatReels matReels t_MatReels matReels; t_Article artCour t_Article artCour; STRUCTURES ALGORITHMIQUES Instructions Affectation Sx←sin(A+3∗x) Sx=sin(A+3*x); matReels(nb1, nb2) ←1 matReels[nb1][nb2]=1; artCour.reference←123 artCour.reference=123; Lecture/Ecriture #include <iostream> using namespace std; nb1 ←lire ( ) cin>>nb1; artCour ←lire ( ) cin>>artCour.reference >>artCour.libelle >>artCour.prix; écrire (nb1, nb2) cout<<“nb1 :”<<nb1 <<“nb2 :”<<nb2; écrire (vect) for(i=0; i<MAX; i++){ cout<<vect[i]<<endl; } Commentaires /* commentaire C / commentaire / sur plusieurs lignes*/ // commentaire C++ Structure générale problème . .. /* Explications sur le programme */ spéciﬁcation . .. /* inclusions */ #include <...> types ... typedef ... constantes ... const ... algorithme int main() { début //début du programme corps de l’algorithme //corps du programme ﬁn } //fin du programme Structures de choix Choix alternatif si nb1<nb2 alors if (nb1<nb2) { écrire (nb2) cout<<nb2<<endl; sinon } else { écrire (nb1) cout<<nb1<<endl; ﬁn si } Choix sélectif choix selon : var = 1 : écrire (“positif”) var = -1 : écrire (“négatif”) autre : écrire (“nul”) ﬁn choix selon switch (var) { case 1 : cout<<“positif”; break; case -1 : cout<<“négatif”; break; default : cout<<“nul”; } Structures répétitives Tant que . . .Faire nb1 ←lire ( ) tant que nb1>0 faire somme ←somme+nb1 nb1 ←lire ( ) ﬁn tant que cin>>nb1; while (nb1>0) { somme=somme+nb1; cin>>nb1; } Pour . . .Faire pour i ←0 à MAX faire somme ←somme+vect(i) ﬁn pour for (i=0;i<=MAX;i=i+1){ somme=somme+vect[i]; } 1 11 uploads/Management/ algpr-2013-ds2-novembre-pdf.pdf