Partage

[Exercices] Venez vous entraîner !

Ce mois: Parseur de fonctions mathématiques

31 mars 2009 à 21:45:27

Solution du mois de janvier 2009



Re-Bonjour tout le monde ! Il est temps que je dévoile avec encore plus de retard, une solution pour l'exercice du mois de janvier. Vous avez été 8 à m'envoyer une solution. Ce n'est pas beaucoup, surtout que l'exercice était relativement simple et court.

Voici ma solution.

Partie "Papier-Crayon"



Il n'y avait pas grand chose à faire ici. L'algorithme étant entièrement décrit dans la donnée. L'exercice consistait surtout à utiliser correctement les fonctions du C++ pour la lecture de fichiers.

Choix des structures de données



Là non plus, pas de grande difficulté. Le choix naturel d'utiliser les fstream est certainement la meilleure option. Reste à voir comment les utiliser pour faire ce que l'on veut.

Documentation



En farfouillant un peu dans la documentation de la classe ifstream, on tombe rapidement sur la fonction read() qui permet de lire les données directement depuis le flux dans un tableau de caractères.

De même, la documentation de ofstream, nous mène directement vers la fonction write() permettant d'écrire le contenu d'un tableau de caractères dans un fichier.

Programmation



Les deux fonctions citées ci-dessus attendent en argument un tableau de caractères. Nous ne voulons "jouer" qu'avec un seul caractère à la fois, nous aurons donc simplement un tableau de taille 1.

La fonction de cryptage/décryptage est alors:


//Crypte un fichier et écrit le résultat dans un nouveau fichier
void crypte(const string& cle,const string& fichier,const string& nouveauFichier)
{
    //On verifie que le fichier d'entrée est différent du fichier de sortie
    if(fichier == nouveauFichier)
        throw string("Le fichier d'entrée est le même que le fichier de sortie");

    //On ouvre les deux fichiers
    ifstream entree(fichier.c_str());
    ofstream sortie(nouveauFichier.c_str());

    //Un "iterateur" sur la cle pour avoir la position courante dans la cle
    int i=0;

    //Un caractère temporaire (= tableau de taille 1)
    char temp;

    //Tant qu'on a pas atteind la fin du fichier, on lit un caractère
    while (entree.read(&temp,1))
    {
        //On utilise le XOR sur le caractère avec le caractère courant de la clé
        temp ^= cle[i];

        //On écrit le résultat dans le fichier de sortie
        sortie.write(&temp,1);

        //On passe au caractère suivant de la clé
        ++i;
        i%=cle.size();
    }
}


Il ne reste plus alors qu'à ajouter un main() qui lit les paramètres et les envoit à la fonction. Le code complet est donc:

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

//Crypte un fichier et écrit le résultat dans un nouveau fichier
void crypte(const string& cle,const string& fichier,const string& nouveauFichier)
{
    //On verifie que le fichier d'entrée est différent du fichier de sortie
    if(fichier == nouveauFichier)
        throw string("Le fichier d'entrée est le même que le fichier de sortie");

    //On ouvre les deux fichiers
    ifstream entree(fichier.c_str());
    ofstream sortie(nouveauFichier.c_str());

    //Un "iterateur" sur la cle pour avoir la position courante dans la cle
    int i=0;

    //Un caractère temporaire (= tableau de taille 1)
    char temp;

    //Tant qu'on a pas atteind la fin du fichier, on lit un caractère
    while (entree.read(&temp,1))
    {
        //On utilise le XOR sur le caractère avec le caractère courant de la clé
        temp ^= cle[i];

        //On écrit le résultat dans le fichier de sortie
        sortie.write(&temp,1);

        //On passe au caractère suivant de la clé
        ++i;
        i%=cle.size();
    }
}

int main(int argc, char** argv)
{

    //On verifie que le nombre d'arguments est correct
    if(argc < 3 || argc > 4)
    {
        cerr << "ERREUR: Nombre de paramètres incorrects. \n 2 ou 3 paramètres attendus.";
        return 1;
    }

    //On lit les parametres
    const string cle(argv[1]);
    const string fichier(argv[2]);
    string fichierSortie;

    //Pour le fichier de sortie, si il n'est pas donne on le cree a partir du fichier d'entree
    if(argc == 4)
        fichierSortie = argv[3];
    else
        fichierSortie = fichier + ".crypt";

    //Et finalement, on crypte
    try{
        crypte(cle,fichier,fichierSortie);
    }
    catch(const string& e)
    {
        cerr << "ERREUR: " << e << endl;
        return 1;
    }

    return 0;
}


On peut alors utiliser le programme comme suit:

crypt 23fsaddai aCrypter.txt result.crypt


Voilà voilà. La suite de la crypto après l'exercice sur les polynômes.
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
31 mars 2009 à 23:28:18

Le while de lecture n'est pas bon.
Le test doit être réalisé juste après le read. Sinon il y a aura exploitation d'un caractère invalide ou du dernier 2 fois.
C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
1 avril 2009 à 13:40:09

En effet. Corrigé.

Merci.
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
1 avril 2009 à 14:53:24

Les polynomes ça se voit en première scientifique dans R non ?.. Allez, je tente :)
1 avril 2009 à 16:02:24

Citation : Nanoc

Mmmh je crois qu'on a compris.

Je pense pas que ce soit le lieu pour un comparatif entre établissements scolaires ni pour un débat sur l'éducation...

Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
1 avril 2009 à 16:57:21

Pour ceux qui veulent un peu documentation sur les polynômes voici le pdf actif du cours de mon école (UTC)
cours polynômes
1 avril 2009 à 17:23:05

Ton lien n'est pas accessible (et c'est normal c'est un document interne).
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
1 avril 2009 à 21:28:57

Pas accessible ?? bizarre j'ai vérifié avant de mettre le lien, je ne me suis pas loggué pour y accédé !
Perso pour moi il marche le lien ! et je suis quasi sûr de ne pas être loggué (il l'affiche normalement) bas tant pis alors!

EDIT : en fais il est possible que la 1er fois que vous suivez le lien vous tombez sur la page d'accueil, mais en suivant le lien une 2eme fois vous tombez bien sur le pdf.
2 avril 2009 à 11:39:05

Dites, je n'ai pas l'impression que ma réponse ait été prise en compte (pour le cryptage XOR), j'ai envoyé un mp à Reponse_Exercice mais le message est toujours en non lu, est-ce normal ?
2 avril 2009 à 12:20:31

Citation : Nanoc

Citation : Cyprien_

Il y a juste un truc qui m'intrigue pour les polynômes, il s'agit de la comparaison de deux polynômes.

Pour comparer deux flottants, je crois qu'il est impossible d'utiliser == et !=, il faut se donner une erreur.
Mais comment généraliser ça à un type template ?



Théoriquement, la classe Polynome ne fera qu'utiliser l'opérateur == surchargé de la classe utilisée comme type. Le problème est donc reporter vers la classe utilisée comme type.
Pour les types POD (double, float, ...), on peut toujours spécialiser la fonction.



Ayant déjà fini l'exercice je souhaiterais approfondir ce point !
Quel sont exactement les spécificités apportés au type POD pour les comparaisons ??
Comment faire un comparaisons de 2 float en utilisant une marge d'erreur ??
(me suis jamais possé la question j'aurais bêtement fais un == )

D'avance merci pour vos éclaircissement !
2 avril 2009 à 13:24:40

s/POD/flottants/
int est POD, FILE est POD, T* est POD, etc.

Et réponse dans la FAQ de développez: http://cpp.developpez.com/faq/cpp/?pag [...] ons_flottants
C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
2 avril 2009 à 13:39:14

Citation : pepetiti

Dites, je n'ai pas l'impression que ma réponse ait été prise en compte (pour le cryptage XOR), j'ai envoyé un mp à Reponse_Exercice mais le message est toujours en non lu, est-ce normal ?



Si si t'en fais pas. J'utilise lu/non-lu pour trier. Ton code faisait une lecture sur eof() -> pas OK.

EDIT: Plus de 1000 réponses !
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
2 avril 2009 à 15:33:25

Sans ajouter beaucoup de difficulté, on peut ajouter une fonction qui renvoi la dérivé du polynôme !
Polynome polynome::derive()

EDIT :
Voir pourquoi pas une fonction qui calcule une primitive (qui s'annule en zéro ou avec une constante)
Polynome polynome::primitive()
Polynome polynome::primitive( T constante)
2 avril 2009 à 16:36:18

This is gonna be a piece of cake !!
A quel ensemble est-ce que notre polynome appartient ?? |R ??
smoking heals
2 avril 2009 à 16:43:36

Le polynome appartient a l'ensemble des polynomes a une indeterminé dans R (je pense) pour les 2° premiers niveau, et pour ne 3° niveau il s'agit justement d'étendre a n'importe quel ensemble tant que c'est mathématique cohérent.
FaQ : Fr | En 1 2 | C++11 | Template || Blog : Deloget | C++|Boost--Dev | C++Next | GotW || Installer Boost
2 avril 2009 à 16:45:31

Citation : guigui'

Sans ajouter beaucoup de difficulté, on peut ajouter une fonction qui renvoi la dérivé du polynôme !
Polynome polynome::derive()

EDIT :
Voir pourquoi pas une fonction qui calcule une primitive (qui s'annule en zéro ou avec une constante)
Polynome polynome::primitive()
Polynome polynome::primitive( T constante)



Pourquoi pas. Aller plus loin n'est pas interdit !!
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
2 avril 2009 à 21:29:06

Je suis confronté à un petit dilemme :
Pour stocker mes coefficients j'utilise une map mais la fonction :
T map<KEY,T>::operator[](const KEY key)
qui permet d'accéder au élément contenu n'est pas une fonction const (normale puisqu'elle offre là possibilité de modifié cette élément).
Du coup, si je souhaite rendre une fonction (ou un paramètre) const je suis obligée de crée une copie de ma map au lieu de me servir direct de celle-ci.

La question est la suivante :
Qu'est t-il préférable : ne pas rendre la fonction et les paramètre constant (alors qu'ils le sont) ou crée à chaque fois une copie (quitte à alourdir le programme) ??
2 avril 2009 à 21:32:58

Je poserais la question différemment:

Pourquoi utiliser une map ?

http://cpp.developpez.com/faq/cpp/inde [...] oix_conteneur
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
2 avril 2009 à 21:54:03

La map peut avoir du sens pour X^42 + X^2. Mais cela va-t-il souvent se produire ?
Sinon, pour les accesseurs non modifiants qui vont taper dans des membres de type map, il faut appeler la fonction std::map::find. Il n'y a pas vraiment le choix.
C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
3 avril 2009 à 0:03:56

Je t'accorde Nanoc que la map n'est peut être pas le plus adapter mais il me paraissais très bien pour les situations telle que celle proposé par Lmghs X^42 + X^2, même si au finale c'est assez rare.
Bref j'ai utilisé une map et je trouver finalement ça assez agréable. (je voyais pas trop comment faire avec un vector ou autre sans trop me faire chier et là c'est cool)

Lmghs merci de ton aide, c'était effectivement la bonne solution (je l'avais aperçut mais avais un doute), et en jouant bien j'ai obtenu quelque chose de propre et claire (et aprioris rapide).


EDIT:
Bon, maintenant que j'ai ajouté la dérivée et les primitives j'ai plus trop d'idée d'ajout pour la classe ...
Donc a moins que quelqu'un est une idée d'ajout je vais pouvoir rendre ma copie ! ^^
3 avril 2009 à 0:40:01

Il y a toutes sortes de choses à s'assurer:
- const-correctness
- symétries
- exception-safety
- justesse des calculs

Il y a des outils adaptés à ce type de développement pour le dernier point tout particulièrement -> les test-unitaires

Et après c'est tout comme les matrices: il y a de quoi amuser débutants et experts.
- quid d'avoir des politiques pour exploiter en interne des vecteurs (cas courant), ou des map (cas de polynômes "creux" X^42+X^2)
- recherche des racines (ça c'est des maths)
- optimisation (pour wanabe-gurus) dans le cas vecteur pour éviter d'avoir à construire trop de temporaires (chercher expression-template ; c'est ce qui est fait dans Blitz++, newmat, boost.ublas)

Bref, si tu t'embêtes, il y a de quoi s'occuper et apprendre sur ce genre de projets. :)
C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
3 avril 2009 à 0:56:02

Mon implémentation utilise un std::vector et j'ai tenté il y a pas longtemps une version avec une map.

Je vais peut-être me pencher un de ces jours sur une implémentation avec une liste. Le random access n'ayant que peu d'intérêt, cela peu-être un choix. A voir...
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
Anonyme
3 avril 2009 à 9:36:18

Bonjour,
Veuillez noter qu'il y a une petite erreur puisque le polynôme nul est, en fait, de degré (-infini) (ceci est une convention).

3 avril 2009 à 10:55:14

Merci Lmghs pour tes idées !

Par-contre si tu pouvais m'expliquer ce que tu entend par symétrie ?!
Là j'avoue ne pas savoir/voir de quoi tu parle.
3 avril 2009 à 11:39:33

Il parle de symétrie des opérateurs si je ne m'abuse.
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
3 avril 2009 à 12:25:01

Dsl ça m'aide pas !! (des lacunes sûrement !!)
3 avril 2009 à 13:54:45

Oui.
C'est pour faire en sorte que "1+P", "P+1", "P+P" fonctionnent tous. C'est d'autant plus visible quand il y a des conversions implicites au milieu.

Si vous définissez les opérateurs comme ils sont décrits dans le tuto du sdz, il y aura des déséquilibres à cause des conversions implicites qui ne pourront pas s'opérer sur le membre gauche.
C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
3 avril 2009 à 14:52:15

OK, donc en suivant ce que tu dit Lmghs (merci pour le lien Nanoc)
là où moi j'ai fais :
template<class T> Polynome<T> operator+(const T a,const Polynome<T>& poly);
// Pour a + P
Polynome< T > Polynome< T >::operator+(const Polynome< T > &poly) const;
// Pour P + P
Polynome< T > Polynome< T >::operator+(const T a) const;
// Pour P + a


Toi tu ferais juste :
template<class T> Polynome<T> operator+(const T a,const Polynome<T>& poly);
// Pour a + P   ET  pour P + a
template<class T> Polynome<T> operator+(const Polynome< T > &poly,const Polynome< T > &poly2);
// Pour P + P


C'est bien ça ??

Donc je vient d'apprendre que operator+( T , A) marche pour T+A et pour A+T.

Et bien merci pour ce "cours".
Et je vais de ce pas aléger ma classe !