Partage

[Exercices] Venez vous entraîner !

Ce mois: Parseur de fonctions mathématiques

<< 1 ... 11 12 13 ... 47 >>

freecircus

3 juin 2008 à 13:31:02

@zero ptt >
Il y en a qui jouent un peu trop

L'énoncé à été mis à jour :

Citation : Nanoc

Et on est face à un nouveau problème, comment gérer les cas ou le flag apparait quand même dans le texte à compresser. Dans ce cas particulier, on choisit la syntaxe spéciale "flag flag"

Genius

3 juin 2008 à 13:41:08

Bon ben j'ai fait le programme sans flag

Je peux quand même l'envoyer à Reponse_exercices ?

Sachant qu'il compresse plus que le programme demandé

1 caractère => 1 caractère
n caractères (n >= 2) => 2 caractères

Kurlze

3 juin 2008 à 13:43:38

Citation : Genius

Bon ben j'ai fait le programme sans flag

Je peux quand même l'envoyer à Reponse_exercices ?

Sachant qu'il compresse plus que le programme demandé

1 caractère => 1 caractère
n caractères (n >= 2) => 2 caractères

Comment tu peux arriver à compresser & décompresser correctement sans flag ?

Nanoc

3 juin 2008 à 14:01:01

Tu peux te l'envoyer si ça te fait plaisir, mais il ne servira pas de corrigé pour les zéros puisque il ne correspond pas à la donnée du problème.

Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.

zero ptt

3 juin 2008 à 15:14:05

projet terminée!
on peut mettre le flag choisi dans le debut du fichier pour sa decompression plus tard?

Anonyme

3 juin 2008 à 15:31:44

@zero ptt :Lis les messages précédents

Zopieux

3 juin 2008 à 18:10:29

Merci Nanoc pour l'interêt que tu portes à mon outil. Je viens de le modifier un tantinet afin de proposer davantage de caractères (94 en tout, les basiques, càd du code ASCII 33 à 127).

En passant, il est très laid niveau code, donc c'est pas un exploit :-°

...

Varmin

3 juin 2008 à 18:41:37

Déjà je vais vous proposer deux petit fichier a compresser pour le test.

msn-(printf(,:;!é&&é"'(-èè_çà)=)salut@test.fr
msn@0salut@test.fr : pseudo : "salut tt le monde ^^ £¤"
msn@salut@test.fr :: pseudo : #0doña ~ignes! Lol :) °+}-{
msn@salut@test.fr : pseudo : Guten tag, iß das! |||123456789|| j'adore le s tset! aller un petit coup de plus : ßßßßßßßß : hahahaha ¯-_-¯ lol!!!!!!! hilarant!!!!!!!!!!
msn@salut@test.fr : pseudo : a² + b² = c² : Théorème de Pythagore. 
19°F[{(Hahaha!)))}}}]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]@saaaaaaaaaaaaaaalut@test.fr
BooOooNjour !!!! ça va tout le monde? J'ai perdu mon œil et mes œufs. 





Joyeux noël tt le monde du C/C++!!!!!!!

Voila normalement cela devrait suffir comme code d'exemple aussi essayer de compiler votre code source.

Il doit gérer les majuscules, les \n, et les caractères spéciaux. Et faire une gestion d'erreur si vous n'avez pas prévu.

évidemment je poste dans un but instructif c'est plus pour que vous me critiquiez et que vous me corrigiez pour que j'apprenne aussi que dans le but de frimer ou autre.
J'expose mes idées pour que l'on sache ce qui ne va pas et donc que l'on me corrige.

Buldo

3 juin 2008 à 20:01:47

Si le flag apparait plus de deux fois d'affiler (par exemple 3 fois), on doit compresser en @@@@ ou bien en 3@@ ?

Nanoc

3 juin 2008 à 20:45:13

J'ai déjà répondu 2 fois. On "compresse" la séquence "flag flag flag" en "flag flag flag flag flag flag".

Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.

Buldo

3 juin 2008 à 20:54:50

ok merci et désolé

Nanoc

3 juin 2008 à 21:12:03

Solution du mois de mai

Bonjour tout le monde ! Il est temps que je dévoile une solution pour l'exercice du mois de mai. Vous avez été 7 à m'envoyer une solution. C'est moins que le mois passé. Apparement, la question était trop difficile, ou disons que vous avez pensé que c'était trop difficile.
Je vous fais donc part d'un mélange des solutions que j'ai reçu. Les prototypes de la classe et des fonctions membres sont de moi. Les corps des fonctions viennent pour la plus-part des réponses reçues. Beaucoup avait de bonne partie mais toutes avaient un problème quelque part. A noter que seul deux personnes ont utilisé les std::vector, ce qui simplifiait grandement le travail.

La correction est assez longue. Je vous conseille de lire le début, d'essaxer par vous-même et de ragarder le corrigé si ça ne va pas.

Analyse de la donnée

La principale difficulté de cet exercice consistait à considérer un grand nombre comme un tableau de chiffres entre 0 et 9. Une fois ce pas franchi, il fallait ensuite essayer de minimiser nos efforts en programmant le moins de chose inutile. Pour cela, il fallait comprendre comment jouer avec les opérateurs pour en réaliser le plus possible avec le moins de code.

Choix des structures de données

J'ai choisi de représenter les nombres "dans l'ordre inverse". C'est-à-dire que le chiffre des unités sera dans la case 0 du tableau, le chiffre des dizaines dans la case 1 et ainsi de suite. Pour me simplifier la taĉhe, j'ai utilisé un std::vector<short int> comme tableau. C'est un choix arbitraire, on aurait très bien pu représenter les nombres dans l'ordre normal. Pour le signe, j'ai choisi un booléen, avec la convention qu'il sera vrai si le nombre est >=0.

On a donc quelque chose comme:

class BigInt{
public: 
    //plein de trucs
private:
    std::vector<short int> m_chiffres;
    bool m_signe; //true si le nombre est >=0
};

Je ne vais pas tout vous détailler, mais je vais présenter les points clés.

Constructeurs

Prenons le cas du contructeur prenant en argument un entier n de type int. La première chose à faire est de sauvegarder le signe de n. Puis le cas échéant, d'en prendre la valeur absolue pour ne travailler qu'avec les chiffres bruts.

On peut alors découper le nombre en chiffres en utilisant l'opérateur modulo (%). Si vous ne savez pas ce que c'est, sachez qu'il correspond au reste d'une division entière.

BigInt::BigInt(int n)
        :m_chiffres(0),m_signe(true)
{
    //On sauvegarde le signe
    m_signe = n>=0;
    n=std::abs(n);

    //Si c'est zero
    if (!n)
    {
        zero();  //Fonction membre privée qui met le tableau à 0 et le signe à +
        return;
    }

    //Sinon, on stocke les chiffres dans le vector dans l'ordre inverse
    while (n)
    {
        m_chiffres.push_back(n%10);
        n/=10;
    }

    //Et on supprime les zeros en-tete du vector
    supprimer_zeros();  //Fonction membre privée de la classe 
}

Le code traite en plus le cas spécial où n==0. A la fin, il supprime les zéros pour éviter les cas où n==000123 en les remplaçant par n=123.

Le constructeur qui prend en argument une string est similaire.

Constructeur de copie et operator=

Comme notre classe ne possède aucun pointeur comme attribut et qu'elle n'alloue aucune mémoire, la version fournie par le compilateur de ces deux fonctions nous suffit. On a donc même pas besoin de les écrire.

Destructeur

Comme nous n'avons alloué aucune mémoire, il n'y a rien à faire dans le destructeur. On a donc même pas besoin de l'écrire.

Accès aux chiffres

Il peut être intéressant d'avoir un accès aux chiffres qui composent le nombre. (En tout cas pendant la période de développement.) Le moyen le plus naturel est d'utiliser pour ceci l'opérateur [].
Pour cet opérateur, on fournit toujours deux versions. Une permettant une modification du chiffre et l'autre non. Ce qui donne dans notre cas :

short int& BigInt::operator[](unsigned int i)//Variante qui autorise la modification
{
    //On renvoit la composante i du vector
    return m_chiffres[i];
}

const short int& BigInt::operator[](unsigned int i) const  //Pas de modification
{
    //idem
    return m_chiffres[i];
}

Affichage en console

La première fonction à coder est certainement celle permettant d'afficher un BigInt en console. Cela nous permettra de faire des essais pour les autres fonctions dans la suite.

Cette fonction doit toujours être déclarée en-dehors de la classe. Son prototype est toujours le même. Il s'agit de :

ostream& operator<<(ostream&,const MaClasse& );

Ce qui donne dans notre cas:

ostream& operator<<(ostream& flux,const BigInt& n)
{
    if (!n.getsigne())  //On recupere le signe via une fonction membre de la classe
        flux << "-";    //Si il est negatif, on met le "-"
    for (int i(n.longueur()-1);i>=0;--i) //On parcourt le BigInt à l'envers (si on veut afficher dans l'ordre usuel) 
        flux << n[i];  //Et on affiche les chiffres en utilisant l'operateur [] de la classe
    return flux;
}

A partir de là, on peut s'attaquer à la partie mathématique du problème.

Opérateurs d'égalité

Commençons par les opérateurs d'égalité == et !=. Deux BigInt sont égaux si ils ont le même signe, si ils ont la même longueur et si tous leurs chiffres sont identiques. On a donc la définition suivante :

bool operator==(const BigInt& a,const BigInt& b)
{
    if (a.getsigne() == b.getsigne())  //si a et b ont le meme signe
    {
        if (a.longueur() == b.longueur())  //qu'ils ont la meme longueur
        {
            for (unsigned int i(0);i<a.longueur();++i) //et qu'ils ont aucun chiffre different
                if (a[i] != b[i])
                    return false;  //Si il y a un différent on renvoit false
            return true;  //alors ils sont égaux
        }
    }
    return false;  //sinon ils sont differents
}

L'opérateur != se code alors très facilement, puisqu'il suffit d'écrire :

bool operator!=(const BigInt& a, const BigInt& b)
{
    return !operator==(a,b);  //ou bien : !(a==b)
}

Opérateurs de comparaison

Pour les opérateurs de comparaison, c'est la même chose. En en définissant un, on a les trois autres de manière. Prenons donc l'opérateur a<=b comme base. Un nombre A est plus petit ou égal à B si :

1) A est négatif et B positif
2) Sinon si A est moins long que B si ils ont le même signe
3) Sinon si le premier chiffre différent entre A et B est plus petit dans A que dans B.

On peut donc écrire quelquechose comme :

bool operator<=(const BigInt& a,const BigInt& b)
{
    if (!a.getsigne() && b.getsigne()) //a negatif et b positif
        return true;
    else if (a.getsigne() && !b.getsigne()) //a positif et b negatif
        return false;
    else                              //a et b de meme signe
    {
        if (a.longueur() < b.longueur())  //si la longueur de a et plus petite que b
            return a.getsigne();             //ce sera vrai si a est positif et faux sinon

        else if (a.longueur() > b.longueur()) //si a est plus long que b
            return !a.getsigne();                //ce sera vrai si a est négatif

        else                                //si ils ont la meme longueur
        {
            for (int i(a.longueur()-1);i>=0;--i)  //on cherche le premier chiffre de a plus grand que b
                if (a[i] > b[i])                  //si il y en a un
                    return !a.getsigne();            //le test est vrai si a est negatif et faux sinon
                else if (a[i] < b[i])
                    return a.getsigne();
        }

    }
    return true; //a est <= à b
}

A partir de là, on a les 3 autres opérateurs :

bool operator>=(const BigInt& a,const BigInt& b)
{
    return operator<=(b,a);
}

bool operator>(const BigInt& a,const BigInt& b)
{
    return !operator<=(a,b);
}

bool operator<(const BigInt& a,const BigInt& b)
{
    return !operator>=(a,b);
}

Les opérateurs << == != < > <= et >= ne sont pas des fonctions membres de la classe.

Opposé d'un BigInt

L'opposé d'un nombre est le même nombre auquel on a changé le signe. On utilise l'opérateur moins unaire pour cela. Ce qui donne :

BigInt BigInt::operator-() const
{
    //On cree une copie de l'objet avec le signe oppose et on la renvoit
    BigInt retour(*this);
    retour.m_signe = !m_signe;
    return retour;
}

Addition

Entrons dans le vif du sujet. Pour code l'addition, commençons par coder l'opérateur +=.

BigInt& BigInt::operator+=(const BigInt& autre)

Pour cela, on peut distinguer 3 cas pour l'addition a + b

1) Les deux nombres ont le même signe.
2) Les nombres sont de signe opposé et abs(a) >= abs(b)
3) Les nombres sont de signe opposé et abs(a) < abs(b)

Dans le premier cas, on doit additionner les parties chiffres des nombres comme on l'a appris au primaire.
Dans le deuxième cas, on doit effectuer une sonstraction comme on l'a appri au primaire.
Dans le troisième cas, on inverse a et b et on se retrouve dans le cas 2.

On aura donc quelque chose comme :

BigInt& BigInt::operator+=(const BigInt& autre)
{
    if (m_signe == autre.m_signe)
        addition(autre);   //Addition de type primaire

    else if (abs() >= autre.abs())
        soustraction(autre);//Soustraction de type primaire
    else
        operator=(autre+(*this));  //Inversion de a et b

    return *this;
}

Les codes des fonctions membres addition() et soustraction() sont dans le code source final.

Opérateurs qui dépendent de l'addition

A partir de là, on peut définir toute une flopée d'opérateurs.

Le moins binaire.

BigInt& BigInt::operator-=(const BigInt& autre)
{
    //Effectuer a-b revient a faire a+(-b)
    operator+=(-autre);
    return *this;
}

L'incrémentation et la décrémentation

BigInt& BigInt::operator++()
{
    return operator+=(1);
}

BigInt BigInt::operator++(int)
{
    BigInt ans = *this;
    operator+=(1);
    return ans;
}

BigInt& BigInt::operator--()
{
    return operator-=(1);
}

BigInt BigInt::operator--(int)
{
    BigInt ans = *this;
    operator-=(1);
    return ans;
}

ainsi que les opérateurs + et - externes.

BigInt operator+(const BigInt& a,const BigInt& b)
{
    BigInt retour(a);
    return retour+=b;
}

BigInt operator-(const BigInt& a,const BigInt& b)
{
    BigInt retour(a);
    return retour-=b;
}

Le reste des opérateurs

En vous inspirant de ce qui a été fait. Il est aisé de coder les opérateurs restants. Pour la division et le modulo, il peut être intéressant d'utiliser une fonction amie qui renvoie une structure de type:

struct Resultat
{
    BigInt quotient;
    BigInt reste;
};

Afin d'éviter une duplication inutile du code.

Le code complet

Le code étant assez long, je l'ai mis dans les balises secret.

BigInt.h

#include <vector>
#include <string>
#include <ostream>

struct Resultat;

class BigInt
{

public:

//CONSTRUCTEURS ----------------------------------------------------------------

    BigInt(int n=0);
    BigInt(std::string chaine);

// FONCTIONS MEMBRES SIMPLES ---------------------------------------------------

    unsigned int longueur() const;  //La longueur du nombre
    bool getsigne() const;          //Le signe sous forme de boolene
    BigInt abs() const;             //Renvoit la valeur absolue

//ACCES AUX CHIFFRES -----------------------------------------------------------

    short int& operator[](unsigned int i);
    const short int& operator[](unsigned int i) const;
    short int& at(unsigned int i);
    const short int& at(unsigned int i) const;

//OPPOSE -----------------------------------------------------------------------

    BigInt operator-() const;

//OPERATEURS ARITHMETIQUES -----------------------------------------------------

    BigInt& operator+=(const BigInt&);
    BigInt& operator-=(const BigInt&);
    BigInt& operator*=(const BigInt&);
    BigInt& operator/=(const BigInt&);
    BigInt& operator^=(int n);
    BigInt& operator%=(const BigInt&);

//OPERATEURS D'INCREMENTATION --------------------------------------------------

    BigInt& operator++();      //Incrémente de 1
    BigInt operator++(int);
    BigInt& operator--();
    BigInt operator--(int);

private:

// FONCTIONS ASSISTANTES -------------------------------------------------------

    void addition(const BigInt&);             //Additione deux nombres de meme signe
    void soustraction(const BigInt&autre);    //Effectue la soustraction *this - autre si |*this| > |autre|
    friend Resultat division(BigInt dividende, BigInt diviseur); //Effectue la division dividende/diviseur et renvoit
    //Une structure de type Resultat avec le quotient et le reste

    BigInt& multiplication_10n(int n);          //Multiplie le BigInt par 10^n
    BigInt(std::vector<short int> v);           //Constructeur a partir d'un vector<>. Cree un nombre positif
    std::vector<short int> getVecteur() const;  //Renvoit le tableau m_chiffres

    void supprimer_zeros();                     //Supprime les zeros en tete du nombre
    void zero();                                //Met le BigInt a 0

//ATTRIBUTS --------------------------------------------------------------------

    std::vector<short int> m_chiffres;      //Les differents chiffres du nombre
    bool m_signe;                           //true si le BigInt >=0

};

//PETITE STRUCTURE POUR LES DIVISIONS ------------------------------------------

struct Resultat
{
    BigInt quotient;
    BigInt reste;
};

// OPERATEURS D'ECRITURE DANS LES FLUX ----------------------------------------

std::ostream& operator<<(std::ostream& flux, const BigInt& n);

//OPERATEURS DE COMPARAISON-----------------------------------------------------

bool operator==(const BigInt& a,const BigInt& b);
bool operator!=(const BigInt& a,const BigInt& b);
bool operator<=(const BigInt& a,const BigInt& b);
bool operator>=(const BigInt& a,const BigInt& b);
bool operator<(const BigInt& a,const BigInt& b);
bool operator>(const BigInt& a,const BigInt& b);

//OPERATEURS ARITHMETIQUES EXTERNES --------------------------------------------

BigInt operator+(const BigInt& a,const BigInt& b);
BigInt operator-(const BigInt& a,const BigInt& b);
BigInt operator*(const BigInt& a,const BigInt& b);
BigInt operator/(const BigInt& a,const BigInt& b);
BigInt operator^(const BigInt& a,int n);
BigInt operator%(const BigInt& a,const BigInt& b);

//FONCTIONS MATHEMATIQUES USUELLES ---------------------------------------------

BigInt abs(const BigInt& n);      //Valeur absolue
BigInt signe(const BigInt n);     //Fonction signe

BigInt.cpp

#include "BigInt.h"
#include <cstdlib> //Pour abs()

#include <iostream>
using namespace std;

//CONSTRUCTEURS ----------------------------------------------------------------

BigInt::BigInt(int n)
        :m_chiffres(0),m_signe(true)
{
    //On sauvegarde le signe
    m_signe = n>=0;
    n=std::abs(n);

    //Si c'est zero
    if (n==0)
    {
        zero();
        return;
    }

    //Sinon, on stocke les chiffres dans le vector dans l'ordre inverse
    while (n>0)
    {
        m_chiffres.push_back(n%10);
        n/=10;
    }

    //Et on supprime les zeros en-tete du vector
    supprimer_zeros();
}

BigInt::BigInt(string chaine)
        :m_chiffres(0),m_signe(true)
{
    //Si il y a un moins devant, on met un signe -
    if (chaine[0]=='-')
    {
        m_signe=false;
        chaine.erase(0,1);
    }

    //On stocke ensuite les chiffres dans le vector
    for (int i(chaine.size()-1);i>=0;--i)
        m_chiffres.push_back(chaine[i]-'0');

    //Et on supprime les zeros en-tete du vector
    supprimer_zeros();
}

// FONCTIONS MEMBRES SIMPLES ---------------------------------------------------

unsigned int BigInt::longueur() const
{
    return m_chiffres.size();
}

bool BigInt::getsigne() const
{
    return m_signe;
}

BigInt BigInt::abs() const
{
    //On cree une copie de l'objet avec un signe positif et on la renvoit
    BigInt retour(*this);
    retour.m_signe = true;
    return retour;
}

//ACCES AUX CHIFFRES -----------------------------------------------------------

short int& BigInt::operator[](unsigned int i)
{
    //On renvoit la composante i du vector
    return m_chiffres[i];
}

const short int& BigInt::operator[](unsigned int i) const
{
    //idem
    return m_chiffres[i];
}

short int& BigInt::at(unsigned int i)
{
    //On renvoit la composante i du vector avec un test de validité
    return m_chiffres.at(i);
}

const short int& BigInt::at(unsigned int i) const
{
    //idem
    return m_chiffres.at(i);
}

//OPPOSE -----------------------------------------------------------------------

BigInt BigInt::operator-() const
{
    //On cree une copie de l'objet avec le signe oppose et on la renvoit
    BigInt retour(*this);
    retour.m_signe = !m_signe;
    return retour;
}

//OPERATEURS ARITHMETIQUES -----------------------------------------------------

BigInt& BigInt::operator+=(const BigInt& autre)
{
    if (m_signe == autre.m_signe)
        addition(autre);   //Addition de type primaire

    else if (abs() >= autre.abs())
        soustraction(autre);//Soustraction de type primaire
    else
        operator=(autre+(*this));  //Inversion de a et b

    return *this;
}

BigInt& BigInt::operator-=(const BigInt& autre)
{
    //Effectuer a-b revient a faire a+(-b)
    operator+=(-autre);
    return *this;
}

BigInt& BigInt::operator*=(const BigInt& autre)
{
    BigInt backup(*this);
    BigInt backup2(autre);
    zero();

    for (unsigned int i(0);i<backup2.longueur();++i)
    {
        BigInt temp(backup);

        int retenue(0);
        for (unsigned int j(0);j<temp.longueur();++j)
        {
            if (((temp[j] *= backup2[i])+=retenue) >= 10)
            {
                retenue = temp[j]/10;
                temp[j]%=10;
            }
            else
                retenue =0;
        }
        if (retenue)
            temp.m_chiffres.push_back(retenue);

        temp.multiplication_10n(i);
        operator+=(temp);
    }

    m_signe = backup.m_signe == backup2.m_signe;
    supprimer_zeros();

    return *this;
}

BigInt& BigInt::operator/=(const BigInt& autre)
{
    operator=(division(*this,autre).quotient);
    return *this;
}

BigInt& BigInt::operator%=(const BigInt& autre)
{
    operator=(division(*this,autre).reste);
    return *this;
}

BigInt& BigInt::operator^=(int n)
{
    if (n<0)
        zero();
    else
    {
        BigInt a(*this);
        operator=(1);
        for (int i(0); i<n;++i)
        {
            operator*=(a);
        }
    }
    return *this;
}

//OPERATEURS D'INCREMENTATION --------------------------------------------------

BigInt& BigInt::operator++()
{
    return operator+=(1);
}

BigInt BigInt::operator++(int)
{
    BigInt ans = *this;
    operator+=(1);
    return ans;
}

BigInt& BigInt::operator--()
{
    return operator-=(1);
}

BigInt BigInt::operator--(int)
{
    BigInt ans = *this;
    operator-=(1);
    return ans;
}

// FONCTIONS ASSISTANTES -------------------------------------------------------

void BigInt::addition(const BigInt& autre)
{
    unsigned int l(longueur() < autre.longueur() ? longueur() : autre.longueur());
    int retenue(0);

    for (unsigned int i(0);i<l;++i)
    {
        if ((m_chiffres[i] += autre[i] + retenue) >=10)
        {
            m_chiffres[i] %=10;
            retenue =1;
        }
        else
            retenue =0;
    }

    if (longueur() > autre.longueur())
        for (unsigned int i(l);i<longueur();++i)
        {
            if ((m_chiffres[i]+= retenue) >=10)
            {
                m_chiffres[i] %=10;
                retenue =1;
            }
            else
            {
                retenue =0;
            }
        }

    else if (autre.longueur() > longueur())
        for (unsigned int i(l);i<autre.longueur();++i)
        {
            if ((autre[i] + retenue) >=10)
            {
                m_chiffres.push_back((retenue+autre[i])%10);
                retenue =1;
            }
            else
            {
                m_chiffres.push_back(autre[i]+retenue);
                retenue =0;
            }
        }

    if (retenue!=0)
    {
        m_chiffres.push_back(1);
    }
}


void BigInt::soustraction(const BigInt& autre)
{
    int l(autre.longueur());

    int retenue(0);
    for (int i(0);i<l;++i)
    {
        if ((m_chiffres[i]-= (autre[i]+retenue)) <0)
        {
            m_chiffres[i] = (m_chiffres[i] +10)%10;
            retenue = 1;
        }
        else
            retenue =0;
    }

    while (retenue!=0)
    {
        if ((m_chiffres[l]-=1) <0)
        {
            m_chiffres[l] = (m_chiffres[l] +10)%10;
            retenue =1;
            ++l;
        }
        else
            retenue =0;
    }

    supprimer_zeros();

}


BigInt& BigInt::multiplication_10n(int n)
{
    m_chiffres.insert(m_chiffres.begin(),n,0);
    return *this;
}

BigInt::BigInt(std::vector<short int> v)
        :m_chiffres(v), m_signe(true)
{
    supprimer_zeros();
}

std::vector<short int> BigInt::getVecteur() const
{
    return m_chiffres;
}

void BigInt::supprimer_zeros()
{
    int i(longueur()-1);
    while (i>=1 && m_chiffres[i] ==0)
    {
        m_chiffres.pop_back();
        --i;
    }
    if (i==0 && m_chiffres[i]==0)
        zero();
}

void BigInt::zero()
{
    m_signe = true;
    m_chiffres.clear();
    m_chiffres.push_back(0);
}

// OPERATEURS DE LECTURE ET ECRITURE DANS LES FLUX -----------------------------

ostream& operator<<(ostream& flux,const BigInt& n)
{
    if (!n.getsigne())
        flux << "-";
    for (int i(n.longueur()-1);i>=0;--i)
        flux << n[i];
    return flux;
}


//OPERATEURS DE COMPARAISON-----------------------------------------------------

bool operator==(const BigInt& a,const BigInt& b)
{
    if (a.getsigne() == b.getsigne())  //si a et b ont le meme signe
    {
        if (a.longueur() == b.longueur())  //qu'ils ont la meme longueur
        {
            for (unsigned int i(0);i<a.longueur();++i) //et qu'ils ont aucun chiffre different
                if (a[i] != b[i])
                    return false;  //Si il y a un différent on renvoit false
            return true;  //alors ils sont égaux
        }
    }
    return false;  //sinon ils sont differents
}

bool operator!=(const BigInt& a, const BigInt& b)
{
    return !operator==(a,b);
}

bool operator<=(const BigInt& a,const BigInt& b)
{
    if (!a.getsigne() && b.getsigne()) //a negatif et b positif
        return true;
    else if (a.getsigne() && !b.getsigne()) //a positif et b negatif
        return false;
    else                              //a et b de meme signe
    {
        if (a.longueur() < b.longueur())  //si la longueur de a et plus petite que b
            return a.getsigne();             //ce sera vrai si a est positif et faux sinon

        else if (a.longueur() > b.longueur()) //si a est plus long que b
            return !a.getsigne();                //ce sera vrai si a est négatif

        else                                //si ils ont la meme longueur
        {
            for (int i(a.longueur()-1);i>=0;--i)  //on cherche le premier chiffre de a plus grand que b
                if (a[i] > b[i])                  //si il y en a un
                    return !a.getsigne();            //le test est vrai si a est negatif et faux sinon
                else if (a[i] < b[i])
                    return a.getsigne();
        }

    }
    return true;
}

bool operator>=(const BigInt& a,const BigInt& b)
{
    return operator<=(b,a);
}

bool operator>(const BigInt& a,const BigInt& b)
{
    return !operator<=(a,b);
}

bool operator<(const BigInt& a,const BigInt& b)
{
    return !operator>=(a,b);
}

//OPERATEURS ARITHMETIQUES EXTERNES --------------------------------------------

BigInt operator+(const BigInt& a,const BigInt& b)
{
    BigInt retour(a);
    return retour+=b;
}

BigInt operator-(const BigInt& a,const BigInt& b)
{
    BigInt retour(a);
    return retour-=b;
}

BigInt operator*(const BigInt& a,const BigInt& b)
{
    BigInt retour(a);
    return retour*=b;
}

BigInt operator/(const BigInt& a,const BigInt& b)
{
    return division(a,b).quotient;
}

BigInt operator%(const BigInt& a,const BigInt& b)
{
    return division(a,b).reste;
}

BigInt operator^(const BigInt& a,int n)
{
    BigInt retour(a);
    return retour^=n;
}

Resultat division(BigInt dividende, BigInt diviseur)
{
    Resultat r;

    //On traite le cas ou |diviseur| > |dividende|
    if (diviseur.abs() > dividende.abs())
    {
        r.quotient.zero();
        r.reste = dividende;
        r.reste.m_signe = dividende.m_signe;
        return r;
    }

    //On traite le cas de la division par zero
    if (diviseur.abs()==0)
        return r;

    //A partir d'ici, on est dans un cas normal

    //On cree une table de toutes les multiplications du diviseur
    vector<BigInt> tableau;
    for (int i(0);i<=10;++i)
        tableau.push_back(i*(diviseur.abs()));

    //On cree un tableau pour le quotient
    vector<short int> quotient;

    //On cree un tableau avec les premiers chiffres du dividende
    std::vector<short int> temp(diviseur.longueur());
    for (unsigned int i(1);i<=temp.size();++i)
        temp[temp.size()-i] = dividende[dividende.longueur()-i];

    //Le nombre de chiffres descendus
    unsigned int nbr_descendu(temp.size());

    do
    {
        //Si le tableau n'est pas assez grand, on ajoute le chiffre suivant
        if (BigInt(temp)< diviseur.abs())
        {
            temp.insert(temp.begin(),dividende[dividende.longueur()-nbr_descendu-1]);
            ++nbr_descendu;
        }

        //On cherche le multiple i du diviseur le plus grand que l'on peut mettre dans temp
        int i(0);
        while ((BigInt(temp) >= tableau[i]))
        {
            ++i;
        }
        if (i>0)
            --i;

        //On ajoute i au quotient
        quotient.insert(quotient.begin(),i);

        //Et on effectue la soustraction
        temp = (BigInt(temp)-= tableau[i]).getVecteur();

        //On recommence tant qu'on a pas descendu tous les chiffres
    }
    while (nbr_descendu < dividende.longueur());

    //On sauve le quotient et le reste
    r.quotient = quotient;
    r.reste = temp;

    //Et on gere les signes
    r.quotient.m_signe = dividende.m_signe == diviseur.m_signe;

    if (r.reste.abs() == 0)
        r.reste.zero();
    else
        r.reste.m_signe = dividende.m_signe;

    return r;
}


//FONCTIONS MATHEMATIQUES USUELLES ---------------------------------------------

BigInt abs(const BigInt& n)
{
    return n.abs();
}

BigInt signe(const BigInt n)
{
    return n.getsigne() ? 1: -1;
}

N'hésitez pas à posez des questions si des points restent obscures.

Remarques sur les codes reçus

Bravo à poulecaca et lanfeusst, qui malgrè le fait d'avoir utilisé des tableaux "à la C" ont presque entièrement réussi l'exercice.

Usez et abusez des std::vector en C++ !
Attention aux fonctions membres const. C'est important de les spécifier
Ne confondez pas le = et le ==.

Il ne sert à rien d'envoyer votre code si il ne fonctionne pas ou pire, si il ne compile pas.

Merci à tous ceux qui ont participé. Et bonne chance avec l'exercice suivant !

EDIT : Modification de la réponse. Ajout de at() et amélioration du style.

Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.

Anonyme

4 juin 2008 à 7:42:22

Merci beaucoup pour cette solution

.

Par contre, serait-il possible d'avoir également la solution qui optimise les calculs, c'est-à-dire en base 2^(sizeof(unsigned int)*8) ?

Celle-là m'intéresserait grandement, vu que je bloquais dès le départ

.

Bien sûr, si ça prend trop de temps de la coder ou si tu n'en as pas l'envie, pas de problème

lmghs

4 juin 2008 à 10:20:54

Pour la comparaison, il y avait même moyen d'utiliser operator==(vector, vector). Et pour deux vecteurs de longueurs égales, on pouvait utiliser <, >, etc je pense.

Pour la version optimisant l'occupation mémoire, je m'y serai bien amusé, mais je n'en ai pas trop le temps malheureusement.

Sinon, les algos sont identiques, c'est juste la formule pour détecter les dépassements qui change un chouilla -- j'avais donné un version bidouillée il y a quelques pages de cela.

MatteX

4 juin 2008 à 18:22:17

Voici une ligne que vous devriez essayer de compresser et de décompressé parfaitement. Si vous y arriver c'est que votre algorithme est fonctionnel

(Remplacez le @ par votre flag)
1@29955555@@@@6665999999999999999999992@@1@3@@@0

Compressé ça me donne
1@@2995@58@@@3@659@99@99924@@@1@@36@@@0

81% de la taille originale. Et ça décompresse aisément. Je souhaite beaucoup de plaisir à ceux qui n'ont pas de flags

Petit indice : @ devient @@, @@ devient 4@@@, @@@ devient 6@@@, @@@@ devient 8@@@, etc... donc on a une perte de compression de 1 @ mais à partir de 2 et plus c'est bon... Aucun doute possible.

Je tient à rappeler que ce genre de compresssion ne sert absolument pas à traiter des fichiers de texte ordinaires. Il est rares que dans le langage écrit par des humains qu'il y ai plusieurs caractères de suite. Exception fait des expressif qui aime trop la pontuaction. Mais dans des fichier binaires ils se peut qu'il y ai vraiment beaucoup d'octets nul (0x00) ou DEL (0xFF) ou autre les uns à la suite des autres. C'est dans ces cas là que la compression devient utile. C'est un exercice, cela ne vous servira probablement jamais dans un cas réel.

[EDIT]J'ai fait une modif et il n'y a plus de @@@@[/EDIT]

zero ptt

4 juin 2008 à 18:27:33

je crois que @@@ doit devenir @@ @@ @@ (sans espaces)

Genius

4 juin 2008 à 18:32:08

Citation : MatteX

81% de la taille originale. Et ça décompresse aisément. Je souhaite beaucoup de plaisir à ceux qui n'ont pas de flags

En effet, 58%, ça fait plaisir

MatteX

4 juin 2008 à 18:45:27

Et ça décompresse bien Genius?

Genius

4 juin 2008 à 18:49:08

Ben oui, sinon ça compterait pas

MatteX

4 juin 2008 à 21:18:22

Qu'est-ce que tu fais pour savoir que 321 ça donne 311 ou 2221 ?

Genius

4 juin 2008 à 21:21:58

Je t'envoie le code

Nico_n

4 juin 2008 à 21:59:00

moi je pense que le flag qui serai pas mal c'est le §
il est plus que rarement utilisé.

TiPouss

4 juin 2008 à 22:15:01

Citation

3@ -> 3@0 -> 000 En effet. C'est pour cela, qu'on utilise un flag qui n'apparait jamais dans le texte. Il n'y a pas de solution à ce problème si on utilise un flag. Il y aura toujours une séquence de caractère qui coince. Une solution est souvent de remplace la séquence "flag" par "flagflag", ce qui ne résoud pas entièrement le problème.
Ne pas utiliser de flags pose lui un autre problème, celui que j'ai soulevé dans la première partie. Comment savoir si "33" est 3 suivi de 3 ou 3 fois 3 ?

Si on utilise un flag de plus de 1 caractère, le problème reste le même et en plus, ça diminue gravement le taux de compression.

Bonjour à tous

J'ai réfléchi au problème du flag pour ma partie Analyse.
Je ne me suis pas encore posé sur la programmation en elle-même (il me faut lire le tutoriel en même temps pour m'apprendre).

Comme on a dit qu'il fallait choisir pour flag un caractère "rare",si on prend comme le proposait nanoc le caractère "@" et que comme le donne l'énoncé,on ne compresse pas une suite de moins de 3 éléments successifs,pourquoi ne pas coder "exceptionnellement" le flag qui se trouverai dans la séquence à compresser en :

xxx@@ pour une répétition de x "@" dans la séquence

Ainsi,la séquence @@@ se transformerai en 333@@ et non en @@@@@@
De plus,en voyant dans la compression un @@,on aura qu'à regarder ce qui précède et en voyant 333,on saura qu'il s'agit de @@@.
Si la compression donne 999@@,on comprendra @@@@@@@@@.
Biensur,cela rallonge la séquence contenant le flag dans le cas où la succession du flag est inférieure à 5,mais comme on choisit pour flag un caractère rare,ce soucis sera limité...

Par ailleurs,si la série de flag est dupliquée à plus de 10 exemplaire,on pourra toujours la divisé en 2 morceaux comme donné dans l'énoncé.

Ex: @@@@@@@@@@@@@@@ = 999@@666@@

Test sur l'exemple de MatteX :

1@29955555@@@@6665999999999999999999992@@1@3@@@0 (48 caractères)

deviendrai :

1111@@2995@5444@@3@659@99@92@9222@@1111@@3333@@0 (48 caractères)

=> Bon,là le flag est très présent dans la séquence à compresser,mais en prenant un autre flag,où même en prenant 9 comme flag,on serait déjà sur une compression favorable

flag "9" :

119@22229959549@39659999999999222992@@1@339@0 (45 caractères)

Je vais réfléchir à ce que je viens de dire et essayer de voir si je trouve une faille dans cette hypothèse

Si vous en voyez une,n'hésitez pas !

Isra17

5 juin 2008 à 4:06:47

Matex, ta méthode de (dé)compression n'est pas valide

Nanoc

5 juin 2008 à 8:50:20

A nouveau, je le répète, ce moyen de compression n'est qu'un exemple simple. Le but n'est pas la performance, mais plutôt la manière de coder, de présenter le code, d'utiliser les outils du C++.

Je pensais que donner un contexte au sujet du mois serait une bonne idée pour stimuler. Apparement, c'est plutôt le contraire, ça stimule la contestation et le débat. Ce n'est en soit pas un défaut, mais ça finit par embrouiller les gens qui cherchent juste à répondre à la donnée.

Envoyer un programme qui ne correspond pas à la donnée ne sert à rien, puisqu'il ne pourra servir de correction.

Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.

Anonyme

5 juin 2008 à 18:24:48

Pour la correction, pourqoi ne fait tu aucun controle d'acces?
il vaut mieux utiliser at() au lieu de []

Nanoc

5 juin 2008 à 18:35:06

Pour ce qui est du code dans les fonctions membres, je le fais pas parce que je sais que mon algorithme est correcte et que je ne dépasserai pas. C'est donc un test superflu et donc une perte de temps. Bien que l'optimisation ne soit pas le but ici.
Si on sait qu'on ne va pas dépasser, alors autant utiliser [] qui est plus rapide.

Pour ce qui est du code de l'opérateur [], j'ai décidé de ne pas faire de test pour fournir une fonction qui joue le même rôle que [] sur un vector.
J'aurais également pu fournir une fonction at() qui, elle, aurait fait le contrôle d'accès.

Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.

dadouf

8 juin 2008 à 15:14:34

Bonjour et merci Nanoc pour ces exercices.
Je suis tombé il y a quelques jours sur ce topic, et j'ai déjà fait les exercices des mois précédents (avec succès

).
J'ai une question pour l'exercice du mois de juin, par rapport aux exceptions. Quand tu dis :

Citation : Nanoc

utiliser les exceptions pour gérer le cas des fichiers qui sont mal formatés (qui contiennent des erreurs)

Veux-tu dire qu'ils faut les utiliser au moment de la décompression, pour détecter si le fichier a été compressé avant ? Doit-on générer une exception lorsqu'on essaye de décompresser un fichier "normal", c'est-à-dire qui n'a pas le format de compression ?

J'espère avoir été assez clair

Anonyme

8 juin 2008 à 16:27:38

Tu peux utiliser les exceptions quand tu rencontres une erreur que tu ne peux pas corriger. Je ne donne pas de réponse trop précise pour ne pas donner de réponse.

Nanoc

8 juin 2008 à 17:22:28

J'ai mis cette proposition de manière générale. On ne peut pas prévoir à priori les erreurs que pourrait contenir le fichier à compresser ou à décompresser.
L'idée est d'utiliser une exception pour gérer les cas "non-standards".

Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.

<< 1 ... 11 12 13 ... 47 >>

[Exercices] Venez vous entraîner !

Ce mois: Parseur de fonctions mathématiques

Solution du mois de mai

Analyse de la donnée

Choix des structures de données

Constructeurs

Constructeur de copie et operator=

Destructeur

Accès aux chiffres

Affichage en console

Opérateurs d'égalité

Opérateurs de comparaison

Opposé d'un BigInt

Addition

Opérateurs qui dépendent de l'addition

Le reste des opérateurs

Le code complet

Remarques sur les codes reçus

Supprimer

Modérer

Signaler le message aux modérateurs