[Exercices] Venez vous entraîner !

<code type="cpp">
#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

<code type="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);
zero();

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

int retenue(0);
for (unsigned int j(0);j<temp.longueur();++j)
{
if (((temp[j] *= autre[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 == autre.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;
}