Posts Tagged ‘C++’

Mandelbrot

Saturday, February 18th, 2012

L’ensemble de Mandelbrot est une fractale bien connue pour son aspect si particulier en forme de cardioïde :

Cet ensemble est défini selon une formule relativement simple que nous verrons plus loin. Mais comme cette formule fait intervenir les nombres complexes, un petit rappel ne fera pas de mal.

Les nombres complexes

Si l’on se limite à l’ensemble des nombres réels (R), il est impossible de calculer la racine carrée d’un nombre négatif, comme par exemple .

L’ensemble des nombres complexes () permet de résoudre ce genre de problème. L’idée est de nommer le résultat de par la lettre i. Cette lettre représente la partie imaginaire du nombre. Ainsi :

$$\sqrt{-16}=\sqrt(-1\cdot 16)=\sqrt(-1)\cdot\sqrt(16)=i4$$

On dit que i4 est la partie imaginaire d’un nombre. Rien n’empêche qu’un nombre complexe possède également une partie réelle. On note donc un nombre complexe sous la forme (a + ib), où a est la partie réelle et b la partie imaginaire.

Comme les nombres réels sont constitués de deux composantes (la partie réelle et la partie imaginaire), il est facile de les représenter graphiquement sur un plan. Par convention, la partie réelle du nombre est dessinée en abscisse et la partie imaginaire en ordonnée. Voici par exemple la représentation du nombre complexe (3 + i4) :

Plutôt que d’utiliser la forme (a + ib), il est également possible de représenter un nombre complexe par son module (la longueur du segment) et son argument (l’angle). On parle de notation polaire.

Le module, noté |z|, se calcule facilement au moyen du théorème de Pythagore :

$$|z|=\sqrt{a^{2}+b^{2}}$$

Opérations utiles

L’addition et la multiplication de nombres complexes est associative, commutative et distributive, au même titre qu’avec les nombres réels.

L’addition de deux nombres complexes (a+ib) et (a’+ib’) est une opération très simple :

$$(a + ib) + (a{}’ + ib{}’) = a+a{}’ + i(b+b{}’)$$

La multiplication de deux nombres complexes est une opération également relativement simple :

$$(a + ib) \cdot (a{}’ + ib{}’) = aa{}’ + aib{}’ + iba{}’ + i^{2}bb{}’$$

Comme i2= -1, on peut donc écrire :

$$(a + ib) \cdot (a{}’ + ib{}’) = aa{}’ – bb{}’ + i(ab{}’+a{}’b)$$

Pour représenter graphiquement l’ensemble de Mandelbrot, nous n’aurons pas besoin d’autres opérations.

L’ensemble de Mandelbrot

Un nombre complexe C fait partie de l’ensemble de Mandelbrot si la suite < ne tend pas vers l'infini (en module). . Il a été démontré en 1990 que cet ensemble a une dimension de Hausdorff de 2. Cela signifie que dès que le module de cette suite dépasse 2, c’est que le nombre en question ne fait pas partie de l’ensemble de Mandelbrot.

À savoir également que l’ensemble de Mandelbrot est compris entre les nombres complexes (-2.1 – i1.2) et (0.6 + i1.2).

Représentation de l’ensemble de Mandelbrot

Pour afficher à l’écran l’ensemble de Mandelbrot, l’idée est d’associer à la surface de la fenêtre un intervalle de nombres complexes. Ainsi, chaque pixel de la fenêtre représente un nombre complexe pour lequel on pourra déterminer s’il appartient ou non à l’ensemble.

Il faut donc, pour chaque pixel de l’écran déterminer à quel nombre complexe il correspond, puis vérifier si ce nombre fait partie de l’ensemble de Mandelbrot. Si c’est le cas, le pixel sera affiché en noir. Sinon, il restera en blanc.

La plupart des langages de programmation ne permettent pas de manipuler en standard les nombres complexes. Toutefois, le calcul de la suite étant assez simple, il est facile de la calculer au moyen de nombres réels uniquement.

Posons et .

Calculons :

$$Z_{n+1}=Z_{n}\cdot Z_{n} + C=(Za_{n}+iZb_{n})\cdot (Za_{n}+iZb_{n}) + (Ca+ib)$$

$$Z_{n+1}=Za{_{n}}^{2}-Zb{_{n}}^{2}+i(2\cdot Za_{n} \cdot Zb_{n}) + Ca+iCb$$

Nous obtenons donc les calculs réels suivants :

$$Za_{n+1}=Z{_{na}}^{2}-Z{_{nb}}^{2}+Ca$$

$$Zb_{n+1}=2\cdot Za_{n} \cdot Zb_{n} + Cb$$

Reste à calculer cette suite pour déterminer si elle converge vers l’infini ou pas.

Nous avons vu plus haut que dès que le module de Z dépasse 2, il est certain que le nombre complexe en question ne fait pas partie de l’ensemble de Mandelbrot.

Il faut tester si le module est inférieur à 2 :

$$|z| < 2$$

Donc :

$$\sqrt{a^{2}+b^{2}} < 2$$

Nous pouvons simplifier le calcul en élevant les deux termes au carré :

$$a^{2}+b^{2} < 4$$

Par contre, si le nombre fait partie de l’ensemble, il faudrait calculer la suite à l’infini, ce qui n’est bien sûr pas réaliste. L’idée est donc de calculer les éléments de la suite jusqu’à un nombre d’itérations maximal, par exemple 200. Si après 200 itérations, le module de Z ne dépasse pas 2, on considère que la suite ne tend pas vers l’infini et que le nombre complexe fait partie de l’ensemble de Mandelbrot.

Il est donc impossible de dessiner cet ensemble de façon exacte. Sa représentation est une approximation dont l’exactitude dépend du nombre maximal d’itérations.

Algorithme

Voici l’algorithme permettant de vérifier si un nombre complexe C fait partie de l’ensemble de Mandelbrot :

procédure déterminant si C fait partie de l'ensemble de Mandelbrot
données : C : complexe
          Ca, Cb, Za, Zb, ZaTemp : réels
          Iteration, MaxIteration : entiers

début
   MaxIteration ← 200
   Ca ← partie réelle de C
   Cb ← partie imaginaire de C

   Za ← 0
   Zb ← 0

   Iteration ← 0

   tant que Za*Za + Zb*Zb < 4 et Iteration < MaxIteration faire
      ZaTemp ← Za*Za-Zb*Zb+Ca
      Zb ← 2*Za*Zb+Cb
      Za ← ZaTemp
      Iteration ← Iteration+1
   fin tant que

   si Iteration = MaxIteration alors
      le point fait partie de l'ensemble de Mandelbrot
   sinon
      le point ne fait pas partie de l'ensemble de Mandelbrot
   fin si
fin

Reste à utiliser cet algorithme pour dessiner quelque chose à l’écran. Il faut donc passer en revue chaque pixel de l’écran, déterminer à quels nombres complexes ils correspondent et les afficher s’ils appartiennent à l’ensemble de Mandelbrot.

Pour simplifier les choses, et comme l’ensemble de Mandelbrot est symétrique par l’abscisse, nous pouvons inverser l’orientation mathématique de l’axe imaginaire (l’ordonnée, axe vertical) afin qu’il soit dans la même direction que l’axe vertical d’affichage de l’écran.

procédure dessin de l'ensemble de Mandelbrot
données : LargeurEcran, HauteurEcran, Ligne, Colonne : entiers
          IntervalleComplexeGauche, IntervalleComplexeHaut,
          IntervalleComplexeDroite, IntervalleComplexeBas : réels
début
   IntervalleComplexeGauche ← -2.1
   IntervalleComplexeHaut ← 1.2
   IntervalleComplexeDroite ← 0.6
   IntervalleComplexeBas ← -1.2

   pour Ligne allant de 0 à HauteurEcran faire
      pour Colonne allant de 0 à LargeurEcran faire
         Ca ← Colonne * (IntervalleComplexeDroite - IntervalleComplexeGauche) / LargeurEcran + IntervalleComplexeGauche
         Cb ← Ligne * (IntervalleComplexeBas - IntervalleComplexeHaut) / HauteurEcran + IntervalleComplexeHaut

         si (Ca,Cb) fait partie de l'ensemble de Mandelbrot faire
            dessiner en Colonne, Ligne un point noir
         sinon
            dessiner en Colonne, Ligne un point blanc
         fin si
      fin pour
   fin pour
fin

 Implémentation en C++ avec Qt

Voici une implémentation simple en C++ et Qt des algorithmes présentés ci-dessus.

#include <QtGui/QApplication>

#include <QImage>
#include <QLabel>

const int IMAGE_WIDTH = 1024;
const int IMAGE_HEIGHT = 1024;

const int MAX_ITERATION = 200;

const unsigned int WHITE = 0x0FFFFFFFF;
const unsigned int BLACK = 0x0FF000000;

bool isInMandelbrotSet(double Ca, double Cb);

// Programme principal
int main(int ArgC, char *ArgV[]) {
    QApplication App(ArgC, ArgV);

    // Construit une image vide
    QImage Image(IMAGE_WIDTH, IMAGE_HEIGHT, QImage::Format_RGB32);
    Image.fill(WHITE);

    // Détermine l'intervalle à afficher
    QRectF ComplexArea(-2.2, -1.5, 3, 3);

    // Vérifie si les points font partie de l'ensemble de Mandelbrot
    for (int Line = 0; Line < IMAGE_HEIGHT; ++Line) {
        for (int Col = 0; Col < IMAGE_WIDTH; ++Col) {
            double Ca = Col * ComplexArea.width() / IMAGE_WIDTH + ComplexArea.left();
            double Cb = Line * ComplexArea.height() / IMAGE_HEIGHT + ComplexArea.top();

            if (isInMandelbrotSet(Ca, Cb))
                Image.setPixel(Col, Line, BLACK);
        }
    }

    // Affiche l'image dans une fenêtre
    QPixmap MandelbrotPixmap = QPixmap::fromImage(Image);
    QLabel Label;
    Label.setWindowTitle("Mandelbrot");
    Label.setPixmap(MandelbrotPixmap);
    Label.setMinimumSize(IMAGE_WIDTH, IMAGE_HEIGHT);
    Label.show();

    return App.exec();
}

// Détermine si le nombre complexe défini par Ca+iCb fait
// partie de l'ensemble de MandelBrot.
bool isInMandelbrotSet(double Ca, double Cb) {
    double Za = 0;
    double Zb = 0;

    int Iteration = 0;

    while (Za*Za + Zb*Zb < 4. && Iteration < MAX_ITERATION) {
        double ZaTemp = Za * Za - Zb * Zb + Ca;
        Zb = 2. * Za * Zb + Cb;
        Za = ZaTemp;
        ++Iteration;
    }

    return Iteration == MAX_ITERATION;
}

Et voilà le résultat :

Représentation colorée

Si vous avez déjà vu des représentations de l’ensemble de Mandelbrot, vous serez sans doute déçus par le résultat austère, noir et blanc, obtenu.

Toutefois, la représentation ci-dessus est conforme à la donnée mathématique : les points noirs sont ceux qui font partie de l’ensemble de Mandelbrot.

Par contre, ce qui est intéressant, ce sont les points qui ne font pas partie de l’ensemble. Au bout d’un certain nombre d’itérations, ces points sont exclus. L’idée est alors de leur donner un couleur, différente selon le nombre d’itérations qu’il a fallu pour les exclure.

Solution simple

Un ordinateur est capable de recréer des millions de couleurs en mélangeant (synthèse additive) les trois couleurs primaires rouge, vert et bleu.

Pour chaque couleur primaire, il est possible de donner une intensité comprise en zéro (noir) et 255 (couleur vive).

Nous pourrions donc fixer à 256 le nombre maximal d’itérations dans notre algorithme. Dès lors, il suffit d’utiliser directement le nombre d’itérations obtenu comme intensité d’une des couleurs de base, par exemple le rouge.

Si le nombre maximal (256) est atteint le point sera dessiné en noir.

Le programme doit être modifié de telle sorte que la méthode isInMandelbrotSet() retourne un paramètre supplémentaire contenant le nombre d’itérations.

#include <QtGui/QApplication>

#include <QImage>
#include <QLabel>

const int IMAGE_WIDTH = 1024;
const int IMAGE_HEIGHT = 1024;

const int MAX_ITERATION = 256;

const unsigned int WHITE = 0x0FFFFFFFF;
const unsigned int BLACK = 0x0FF000000;

bool isInMandelbrotSet(double Ca, double Cb, int* pIterationCount = 0);

// Programme principal
int main(int ArgC, char *ArgV[])
{
    QApplication App(ArgC, ArgV);

    // Construit une image vide
    QImage Image(IMAGE_WIDTH, IMAGE_HEIGHT, QImage::Format_RGB32);
    Image.fill(WHITE);

    // Détermine l'intervalle à afficher
    QRectF ComplexArea(-2.2, -1.5, 3, 3);

    // Vérifie si les points font partie de l'ensemble de Mandelbrot
    for (int Line = 0; Line < IMAGE_HEIGHT; ++Line) {
        for (int Col = 0; Col < IMAGE_WIDTH; ++Col) {
            double Ca = Col * ComplexArea.width() / IMAGE_WIDTH + ComplexArea.left();
            double Cb = Line * ComplexArea.height() / IMAGE_HEIGHT + ComplexArea.top();

            int Iteration = 0;
            if (isInMandelbrotSet(Ca, Cb, &Iteration))
                Image.setPixel(Col, Line, BLACK);
            else
               Image.setPixel(Col, Line, Iteration*256*256);
        }
    }

    // Affiche l'image dans une fenêtre
    QPixmap MandelbrotPixmap = QPixmap::fromImage(Image);
    QLabel Label;
    Label.setWindowTitle("Mandelbrot");
    Label.setPixmap(MandelbrotPixmap);
    Label.setMinimumSize(IMAGE_WIDTH, IMAGE_HEIGHT);
    Label.show();

    return App.exec();
}

// Détermine si le nombre complexe défini par Ca+iCb fait
// partie de l'ensemble de MandelBrot.
bool isInMandelbrotSet(double Ca, double Cb, int* pIterationCount) {
    double Za = 0;
    double Zb = 0;

    int Iteration = 0;

    while (Za*Za + Zb*Zb < 4. && Iteration < MAX_ITERATION) {
        double ZaTemp = Za * Za - Zb * Zb + Ca;
        Zb = 2. * Za * Zb + Cb;
        Za = ZaTemp;
        ++Iteration;
    }

    if (pIterationCount)
       *pIterationCount = Iteration;
    return Iteration == MAX_ITERATION;
}

Voilà le résultat obtenu :

Il y a sans doute moyen de faire mieux !

Le problème vient du fait que la surface éloignée de l’ensemble de Mandelbrot est très sombre, car il faut peu d’itérations pour déterminer que ces points ne font pas partie de l’ensemble.

Par contre, pour les points proches de la frontière de l’ensemble, les variations du nombre d’itérations sont plus marquées, mais le choix des couleurs ne rend pas compte de cette diversité.

Solution avancée

La meilleure solution est donc de mettre au point un dégradé de couleurs. Toute la difficulté sera de choisir judicieusement les couleurs constituant ce dégradé.

Voici un dégradé possible :

Les couleurs clés sont les suivantes :

Position Couleur R V B Hexadécimal
0 % rouge foncé 128 0 0 800000h
20 % jaune 255 255 0 FFFF00h
40 % orange 255 165 0 FFA500h
60 % pourpre 160 32 240 A020F0h
80 % bleu nuit 25 25 112 191970h
100 % rouge foncé 128 0 0 800000h

Et voilà le résultat correspondant :

Le rendu est bien plus satisfaisant !

La principale difficulté consiste donc à programmer le dégradé de couleur, en particulier en ce qui concerne les couleurs intermédiaires.

Pour ce faire, le plus simple est de coder une classe capable de gérer un dégradé entre certaines couleurs clé.

Le code étant trop long pour être affiché sur cette page, il peut être téléchargé : Projet Qt : MandelBrotGUI

À la découverte de la fractale

La partie amusante peut maintenant commencer : changer l’intervalle affiché afin d’admirer de magnifiques figures fractales.

C’est la ligne suivante qui détermine l’intervalle qui sera affiché :

    // Détermine l'intervalle à afficher
    QRectF ComplexArea(-2.2, -1.5, 3, 3);

Le premier nombre indique la limite gauche de l’intervalle (-2.2). Le deuxième nombre, sa limite haute (-1.5). Les deux derniers nombres indiquent la largeur et la hauteur de l’intervalle (3). Pour un affichage dans une fenêtre carrée, il faudrait que la largeur et la hauteur soient identiques.

Observons ce que l’on obtient avec les valeurs suivantes : -0.83, -0.21, 0.05, 0.05. La ligne de code devient QRectF ComplexArea(-0.83, -0.21, 0.05, 0.05);

Lissage des couleurs

Cette vue spectaculaire souffre toutefois encore d’un petit défaut : le dégradé de couleurs présente un effet d’escaliers. C’est la conséquence d’utiliser directement le nombre d’itérations pour obtenir une couleur, qui est un nombre entier. Le résultat est donc discret (à l’opposé de continu), ce qui provoque  dans certaines situations ces escaliers disgracieux.

Pour y remédier il existe différents algorithmes dont le normalized iteration count*. Il permet de calculer une variation décimale du nombre d’itérations pour obtenir un dégradé plus fin.

La formule est la suivante :

$$n+\frac{\log (\log b)-\log(\log \left | Z_{n} \right |)}{\log 2}$$

n est le nombre d’itérations et b le rayon de sortie (qui correspond à la dimension de Hausdorff et qui vaut donc 2 dans notre cas).

L’amélioration est nette :

Essayons d’autres valeurs : -0.749, -0.177488, 0.02, 0.02. La ligne de code devient QRectF ComplexArea(-0.749, -0.177488, 0.02, 0.02);

Nombre d’itérations

Nous avons vu plus haut que pour déterminer si un nombre fait partie de l’ensemble ou pas, il faudrait théoriquement calculer la suite à l’infini. Une approximation est donc réalisée en limitant le nombre d’itérations effectué lors du calcul de la suite.

Le problème d’une telle approximation, c’est que lorsqu’on veut afficher des détails, elle a un impact direct sur la précision obtenue.

Voici, pour les valeurs -0.726277, -0.257609, 0.000332257, 0.000332257 le résultat avec une limite de 256 itérations :

La cardioïde est passablement déformée. Voici une meilleure approximation avec une limite de 512 itérations :

Avec une limite de 1024 itérations :

Et enfin avec une limite de 2048 itérations :

Toute la difficulté revient à trouver une limite qui donne de bons résultats, en un temps acceptable !


Sources :

Wikipédia : Ensemble de Mandelbrot

Wikipedia : Mandelbrot set

Coloring dynamical systems in the complex plane, Garcia, Fernandez, Barrallo, Martin

Calculs cycliques et modulo

Friday, December 16th, 2011

Le modulo

L’opération arithmétique modulo est souvent utilisée en informatique, et plus particulièrement dans le développement.

Elle est souvent présentée comme le reste d’une division entière. Par exemple :

7 ÷ 2 = 3 reste 1. Ainsi, 7 modulo 2 = 1.

27 ÷ 24 = 1 reste 3. Ainsi, 27 modulo 24 = 3.

C’est une opération qui se révèle très utile dès que l’on a affaire à des calculs cycliques, le plus connu étant le problème de l’horloge.

En effet, une horloge (digitale dans notre exemple) indique l’heure de la journée de façon numérique, les heures allant de 0 (minuit) à 23. Une heure après 23 heures, il est minuit. L’horloge recommence un cycle à zéro.

Il existe bien sûr d’autres exemples, ayant des cycles différents. Par exemple, une montre analogique a un cycle de 12 : lorsque l’aiguille a fait un tour complet, elle reprend à 1.


Les angles (en degrés) ont un cycle de 360, etc.

Calculs cycliques

Lorsque des calculs cycliques doivent être effectués, il faut tenir compte de la durée du cycle.

Par exemple, s’il est 10 heures et que l’on souhaite calculer l’heure qu’il sera dans 5 heures, il suffit de faire une addition : 10 + 5 = 15 heures.
Par contre, si il est 22 heures (et que l’on souhaite encore calculer l’heure qu’il sera dans 5 heures), la simple addition abouti à un résultat erroné : 22 + 5 = 27 heures.

Le problème vient du fait que toutes les 24 heures, l’horloge recommence à zéro. Elle travaille donc dans une arithmétique modulaire (cyclique) dont le cycle, nous l’avons vu, est de 24 heures.

L’opération arithmétique modulo permet de tenir compte du cycle. Ainsi, pour garantir que le résultat soit toujours conforme au cycle de 24 heures de l’horloge, il suffit d’appliquer un modulo à l’addition :

heure ultérieure = (heure actuelle + décalage) modulo 24.

En reprenant notre exemple :

heure ultérieure = (22 + 5) modulo 24 = 3

Ce qui est correct : 5 heures après 22 heures, il sera 3 heures du matin.

Maintenant, essayons de faire la même chose mais pour calculer une heure précédente.

Par exemple, s’il est 11 heures et que l’on souhaite calculer l’heure qu’il était il y a 7 heures, il suffit de faire une soustraction : 11 – 7 = 4 heures.
Par contre, s’il est 6 heures (et que l’on souhaite encore calculer l’heure qu’il était il y a 7 heures), la simple soustraction aboutit à un résultat erroné : 6 -7 = -1 heures. Ce n’est pas une surprise.

Dès lors, il semble logique qu’il faille appliquer la technique du modulo :

heure précédente = (heure actuelle – décalage) modulo 24.

ou selon notre exemple : heure précédente = -1 modulo 24.

Mais quel est le reste de la division de -1 par 24 ?

-1 ÷ 24 = 0 reste -1

C’est là que les problèmes commencent : dans le cas d’une arithmétique cyclique, le résultat attendu n’est pas -1 mais 23.

Cet exemple met en lumière que le reste d’une division entière et le modulo ne sont pas interchangeables :

  • Tant que les calculs sont effectués sur des nombres positifs, le reste de la division entière et le modulo donnent des résultats identiques.
  • Dès qu’un des nombres de la division est négatif, les deux opérations ne fournissent plus les mêmes résultats.

En résumé

Nous venons de voir que le modulo n’est pas une opération identique au reste de la division entière. Elle diffère en particulier lorsque le dividende et/ou le diviseur sont négatifs.

Voici un tableau récapitulatif :

Dividende Diviseur Quotient Reste Modulo
27 24 1 3 3
24 24 1 0 0
15 24 0 15 15
0 24 0 0 0
-1 24 0 -1 23

Reprenons la façon de calculer le reste d’une division :

La partie intéressante est l’arrondi : quel arrondi utiliser pour convertir le résultat de la division (un nombre réel) en un nombre entier ? Car il y a bien sûr plusieurs façons d’arrondir un nombre.

La réponse la plus évidente est de ne garder que la partie entière du résultat (c’est une troncature). Par exemple, la partie entière de 3.4 est 3. La partie entière de 4.9 est 4.

Il en résulte que la partie entière est toujours inférieure ou égale au nombre réel.

Qu’en est-il lorsque le résultat est négatif ?

Si l’on fait une troncature, la partie entière de -3.4 est -3. La partie entière de -4.9 est -4.

On constate qu’avec cette méthode le sens de l’arrondi change pour les nombres négatifs : les nombres arrondis sont supérieurs ou égaux aux nombres réels.

Une autre alternative serait alors d’arrondir le nombre réel au nombre entier inférieur (arrondi vers -∞). Ainsi, l’arrondi de -3.4 serait -4 et celui de -4.9 serait -5. Ainsi, peu importe que le nombre à arrondir soit positif ou négatif, son arrondi est toujours égal ou inférieur.

Il y a donc deux façons d’arrondir un nombre à virgule qui nous intéresse et qui donnerait des résultats corrects : soit en effectuant une troncature(arrondi vers zéro), soit en effectuant un arrondi vers -∞.

Ces deux façons de faire aboutissent au même résultat pour les nombres positifs, mais à des résultats différents pour les nombres négatifs.

C’est cette différence de méthode d’arrondi qui débouche soit sur le calcul d’un reste de la division (troncature), soit sur le modulo (arrondi vers -∞).

En résumé :

L’opérateur modulo en C++

Voyons maintenant comment réagit l’opérateur modulo en C++, symbolisé par le symbole % :

cout << 27 % 24 << "\n" // affiche 3
cout << -1 % 24 << "\n" // affiche -1

On voit que l’opérateur modulo (%) est mal nommé : il ne calcule pas le modulo, mais le reste de la division entière. Ceci provient du fait qu’en C++, la division entière utilise la troncature
pour convertir un résultat réel en entier.

Pour calculer le modulo en C++, il faut donc écrire notre propre fonction, qui utilisera un arrondi vers -∞ :

int modulo(int Dividende, int Diviseur) {
   return Dividende - std::floor(static_cast<double>(Dividende)/Diviseur) * Diviseur;
}

La fonction floor() (de la bibliothèque cmath) effectue un aarrondi vers -∞.

Le static_cast<double>() permet de forcer la division à être effectuée sur des nombres réels. Sans cela, la division retournerait directement un résultat entier (obtenu par troncature
) et la fonction floor() n’aurait plus aucun effet.

Par souci de clarté, on pourrait également écrire notre propre fonction calculant le reste de la division, en utilisant une troncature :

int remainder(int Dividende, int Diviseur) {
   return Dividende - Dividende/Diviseur * Diviseur;
}

Mais vous l’avez compris, cette fonction fait double emploi avec l’opérateur %.

Excel et VBA

Excel propose la fonction MOD(), qui calcule bel et bien le modulo.

Par contre, il faut faire attention à l’opérateur Mod de VBA, qui calcule, comme son nom ne l’indique pas, le reste !

Dividende Diviseur Quotient Reste Modulo Fonction Excel MOD() Opérateur VBA Mod
27 24 1 3 3 3 3
24 24 1 0 0 0 0
15 24 0 15 15 15 15
0 24 0 0 0 0 0
-1 24 0 -1 23 23 -1

C’est bien beau, mais à quoi ça sert ?

Voici un exemple concret qui illustre bien l’intérêt de comprendre la différence entre le reste et le modulo. Nous allons réaliser un petit programme de codage/décodage au moyen du chiffre de César.

Le chiffre de César est une méthode de chiffrement très simple (et peu robuste). Elle consiste à remplacer chaque lettre d’une phrase par une lettre à distance fixe dans l’ordre de l’alphabet. Par exemple, avec un décalage de 3, la lettre A devient D, la lettre J devient M, etc.

Ainsi, la phrase BONJOUR LES AMIS, avec un décalage de 3, deviendra ERQMRXU OHV DPLV !

Pour implémenter dans un langage informatique cette méthode de chiffrement, il faut au préalable numéroter chaque lettre (lui donner un numéro), afin de pouvoir faire le calcul du décalage.

Lors du calcul du décalage, il faut tenir compte de l’aspect cyclique de la numérotation des lettres de l’alphabet : après la lettre Z (qui a le numéro 25), il faut reprendre à la lettre A (qui a le numéro 0). Cette difficulté est contournée par l’utilisation du modulo.

Voici une première implémentation en C++ de notre application :

// Codage/décodage au moyen du chiffre de César
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int modulo(int Dividende, int Diviseur);
int numeroDeLettre(char Letter);
char lettreDeNumero(int LetterNumber);
bool estUnCaractere(char Char);
string encodeCesar(string Phrase, int Shift);
string decodeCesar(string Phrase, int Shift);

// Programme principal
int main() {
    string Phrase;
    int Decalage = 0;

    // Saisie de la phrase et du décalage
    cout << "Phrase a coder : ";
    getline(cin, Phrase);

    // Converti la phrase en majuscules
    transform(Phrase.begin(), Phrase.end(), Phrase.begin(), ::toupper);

    cout << "Decalage : ";
    cin >> Decalage;

    // Codage et décodage
    string PhraseEncodee = encodeCesar(Phrase, Decalage);
    cout << "\nPhrase codee :  " << PhraseEncodee << "\n\n";

    return 0;
}

// Retourne le numéro de la lettre donnée en paramètre.
int numeroDeLettre(char Lettre) {
    return Lettre - 'A';
}

// Retourne la lettre correspondant au numéro donné en paramètre.
char lettreDeNumero(int NumeroDeLettre) {
    return NumeroDeLettre + 'A';
}

// Retourne un booléen indiquant si le caractère donné correspond à une
// lettre de l'alphabet.
// Par souci de simplification, les lettres accentuées sont ignorées.
bool estUnCaractere(char Caractere) {
    return Caractere >= 'A' && Caractere <= 'Z';
}

// Encode la chaîne passée en paramètre avec le décalage donné.
string encodeCesar(string Phrase, int Decalage) {
    string::iterator it = Phrase.begin();
    // Chaque caractère de la phrase est codé l'un après l'autre
    for(; it != Phrase.end(); it++) {
        if (estUnCaractere(*it)) {
            int NumeroDeLettre = numeroDeLettre(*it);
            int NumeroDeLettreDecalee = (NumeroDeLettre + Decalage) % 26;
            (*it) = lettreDeNumero(NumeroDeLettreDecalee);
        }
    }
    return Phrase;
}

Voici le résultat de ce petit programme :

Phrase a coder : COMMENT ALLEZ-VOUS ?
Decalage : 3

Phrase codee :  FRPPHQW DOOHC-YRXV ?

Press <RETURN> to close this window...

Le décodage, par contre, met en lumière la différence entre le modulo et le reste de la division entière. Si la lettre A (numéro 0) doit être décalée d’une position à gauche (-1), la lettre à obtenir est la lettre Z (numéro 25) et non pas le numéro -1, qui ne correspond à aucune lettre.

Dividende Diviseur Quotient Reste Modulo
25 26 0 25 25
26 26 0 0 0
0 26 0 0 0
-1 26 0 -1 25

C’est donc bel et bien le calcul du modulo qu’il faut utiliser et non pas celui du reste. En C++, il ne faut donc pas utiliser l’opérateur %, mais plutôt la fonction modulo() vue plus haut.

La fonction de décodage peut donc être écrite ainsi :

// Décode la chaîne passée en paramètre avec le décalage donné.
string decodeCesar(string Phrase, int Decalage) {
    string::iterator it = Phrase.begin();
    for(; it != Phrase.end(); it++) {
        if (estUnCaractere(*it)) {
            int NumeroDeLettreCodee = numeroDeLettre(*it);
            int NumeroDeLettreDecodee = modulo(NumeroDeLettreCodee - Decalage, 26);
            (*it) = lettreDeNumero(NumeroDeLettreDecodee);
        }
    }
    return Phrase;
}

Sources :

Wikipédia : modulo informatique

Wikipedia : modulo operation

The math forum : Mod function and Negative Numbers

L’arrondi

Friday, October 22nd, 2010

Introduction

Un arrondi est nécessaire lorsqu’un nombre d’une certaine précision, doit être converti en un nombre d’une moindre précision.

Typiquement, un arrondi doit être effectué lorsqu’un nombre à virgule est converti en un nombre entier.

Cette notion peut sembler toute simple. Nous avons tous appris en cours de math qu’un nombre à virgule s’arrondi de la façon suivante :

  1. si la partie décimale est inférieure à 0.5, le nombre est arrondi vers le bas (par exemple 1.3 ≈ 1)
  2. si la partie décimale est supérieure ou égale à 0.5, le nombre est arrondi vers le haut (par exemple 1.6 ≈ 2 ou encore 1.5 ≈ 2)

Un premier doute s’installe lorsqu’il s’agit d’un nombre négatif. Un arrondi vers le bas correspond-il a un arrondi vers un nombre plus positif ou plus négatif ?

D’autre part, est-ce réellement la seule façon d’arrondir un nombre à virgule ? Y a-t-il une façon plus juste qu’une autre ?

Lors de l’écriture d’un programme qui manipule des nombres ayant à être arrondis, il est nécessaire de connaître comment une fonction d’arrondi réalise l’opération et quel sera le résultat obtenu.

Pour commencer, voyons les différentes façons d’arrondir un nombre à virgule (appelé également nombre réel).

Arrondi vers le bas (arrondi vers -∞)

Le nombre réel est arrondi vers l’entier inférieur.

3.4 ≈ 3

-3.4 ≈ -4

Arrondi vers le haut (arrondi vers +∞)

Le nombre réel est arrondi vers l’entier supérieur.

3.4 ≈ 4

-3.4 ≈ -3

Arrondi par troncature (vers zéro)

Le nombre réel est arrondi vers l’entier suivant le plus proche de zéro. Concrètement, la partie décimale du nombre réel est simplement retirée.

3.4 ≈ 3

-3.4 ≈ -3

Arrondi vers les infinis (par éloignement de zéro)

Le nombre réel est arrondi vers l’entier suivant s’éloignant le plus de zéro.

3.4 ≈ 4

-3.4 ≈ -4

Arrondi au plus proche

Le nombre réel est arrondi vers l’entier le plus proche du nombre réel.

3.4 ≈ 3

3.6 ≈ 4

-3.4 ≈ -3

– 3.6 ≈ -4

Cette dernière forme d’arrondi pose problème lorsque la partie décimale est exactement à mi-chemin entre deux nombre entiers (par exemple 3.5 ou -3.5).

Dans ce cas, il existe plusieurs façons d’arrondir :

Arrondi vers le bas (vers -∞)

3.5 ≈ 3

-3.5 ≈ -4

Arrondi vers le haut (vers +∞)

Cette méthode d’arrondi est également appelée arrondi arithmétique asymétrique.

3.5 ≈ 4

-3.5 ≈ -3

Arrondi vers zéro

3.5 ≈ 3

-3.5 ≈ 3

Arrondi vers les infinis

Cette méthode d’arrondi est celle qui est certainement la plus communément utilisée en arithmétique. On parle également d’arrondi arithmétique symétrique.

3.5 ≈ 4

-3.5 ≈ -4

Arrondi au pair le plus proche (arrondi bancaire)

Si la partie entière est impaire, le nombre arrondi sera le nombre pair le plus proche.

Si la partie entière est paire, elle correspond au nombre arrondi.

3.5 ≈ 4

2.5 ≈ 2

-3.5 ≈ -4

-2.5 ≈ -2

Cette méthode élimine le biais qui survient en cas d’arrondi systématique vers les infinis (ou vers zéro).

Arrondi à l’impair le plus proche

Si la partie entière est paire, le nombre arrondi sera le nombre impair le plus proche.

Si la partie entière est impaire, elle correspond au nombre arrondi.

3.5 ≈ 3

2.5 ≈ 3

-3.5 ≈ -3

-2.5 ≈ -3

Cette méthode d’arrondi est très rarement utilisée, sauf lorsqu’il est important que -0.5 et 0.5 ne soient pas arrondis à zéro.

Arrondi stochastique

C’est le hasard (uniformément réparti) qui détermine si le nombre sera arrondi vers l’entier supérieur ou inférieur.

Comme pour l’arrondi au pair le plus proche, cette méthode élimine le biais d’arrondi, mais introduit une notion de hasard qui rend la reproduction de calculs impossible.

Arrondi alterné

L’arrondi est alternativement fait vers l’entier supérieur puis vers l’entier inférieur.

Résumé

nombre -2.6 -2.5 -2.4 -1.6 -1.5 -1.4 -0.6 -0.5 -0.4 0.4 0.5 0.6 1.4 1.5 1.6 2.4 2.5 2.6
vers +∞ -2 -2 -2 -1 -1 -1 0 0 0 1 1 1 2 2 2 3 3 3
vers -∞ -3 -3 -3 -2 -2 -2 -1 -1 -1 0 0 0 1 1 1 2 2 2
troncature -2 -2 -2 -1 -1 -1 0 0 0 0 0 0 1 1 1 2 2 2
vers les ∞ -3 -3 -3 -2 -2 -2 -1 -1 -1 1 1 1 2 2 2 3 3 3
au plus proche vers +∞ -3 -2 -2 -2 -1 -1 -1 0 0 0 1 1 1 2 2 2 3 3
vers -∞ -3 -3 -2 -2 -2 -1 -1 -1 0 0 0 1 1 1 2 2 2 3
vers zéro -3 -2 -2 -2 -1 -1 -1 0 0 0 0 1 1 1 2 2 2 3
vers les ∞ -3 -3 -2 -2 -2 -1 -1 -1 0 0 1 1 1 2 2 2 3 3
pair -3 -2 -2 -2 -2 -1 -1 0 0 0 0 1 1 2 2 2 2 3
impair -3 -3 -2 -2 -1 -1 -1 -1 0 0 1 1 1 1 2 2 3 3
stochastique -3 -3 ou -2 -2 -2 -2 ou -1 -1 -1 -1 ou 0 0 0 0 ou 1 1 1 1 ou 2 2 2 2 ou 3 3
alterné -3 -3 (-∞) -2 -2 -1 (+∞) -1 -1 -1 (-∞) 0 0 1 (+∞) 1 1 1 (-∞) 2 2 3 (+∞) 3

Note : lorsque un nombre négatif est arrondi à zéro, certaines implémentations préservent le signe devant le zéro : -0.5 ≈ -0, afin de distinguer un arrondi à zéro provenant d’une nombre négatif, d’un arrondi provenant d’un nombre positif.

Fonctions courantes d’arrondi

Chaque langage (et chaque bibliothèque de fonctions) met à disposition un certain nombre de fonctions d’arrondi.

J’ai tenté de réunir dans un tableau les différentes façons d’arrondir un nombre réel ainsi que les différentes fonctions proposées par un langage ou une bibliothèque particulière.

Je m’en suis tenu aux langages que j’utilise couramment : C++ (avec les bibliothèques standards), C++ avec la bibliothèque Qt, VBS et Java. J’y ai ajouté Excel (et donc Keynote, qui implémente les mêmes fonctions), que j’utilise également régulièrement.

méthode\langage VBScript C++ C++ et cmath C++ Qt Java et java.lang.math Excel
vers +∞ ceil() ceil()
vers -∞ Int floor() floor() INT() ENT()
vers zéro
(troncature)
Fix static_cast<int>() trunc() int() ROUNDDOWN() ARRONDI.INF()FLOOR() TRONQUE()
vers les ∞ ROUNDUP() ARRONDI.SUP()CEILING() PLAFOND()
au plus proche vers +∞ qRound round()
vers -∞
vers zéro
vers les ∞ FormatNumber1 round() ROUND() ARRONDI()
pair Round CByte CInt CLng rint() rint()
impair
stochastique
alterné

1Contrairement aux autres fonctions qui retournent un nombre, FormatNumber retourne une chaîne de caractères formatée selon certains paramètres donnés. Il reste néanmoins intéressant d’observer la méthode d’arrondi utilisé par cette fonction.

Ce tableau montre bien la confusion qui peut s’intaller : une fonction nommée Round va par exemple faire un arrondi au pair le plus proche en VBS, mais un arrondi arithmétique symétrique en C++ et avec Excel. La fonction équivalente en Java fera un arrondi arithmétique asymétrique, de même que la fonction qRound de Qt !


Sources :

Wikipedia : Rounding to integer

Wikipédia : Arrondi

Aide et support Microsoft : How To Implement Custom Rounding Procedures

Des cadres en ligne de commande

Wednesday, April 21st, 2010

Pour avoir de beaux cadres dans un programme Windows en mode console, voici les caractères à utiliser :

// cadre simple
std::cout << "ÚÄÂÄ¿\n";
std::cout << "³ ³ ³\n";
std::cout << "ÃÄÅÄ´\n";
std::cout << "³ ³ ³\n";
std::cout << "ÀÄÁÄÙ\n";

// cadre double
std::cout << "ÉÍËÍ»\n";
std::cout << "º º º\n";
std::cout << "ÌÍÎ͹\n";
std::cout << "º º º\n";
std::cout << "ÈÍÊͼ\n";

Ce qui affichera de zolis cadres !

Attention : cette façon de faire n’est pas portable, car elle dépend complètement du jeu de caractères utilisé par la ligne de commande.

cin et les erreurs

Wednesday, April 21st, 2010

Dans une application console, c’est l’objet cin qui est utilisé pour saisir une valeur au clavier. La valeur saisie est envoyée au moyen de l’opérateur de flux entrant (>>) vers la variable qui recevra la saisie clavier. Le type de la variable déterminera le type de donnée à saisir au clavier.

// Saisie d’un nombre entier
int NombreEntier = 0;
std::cin >> NombreEntier;

// Saisie d’un nombre réel
float NombreReel = 0.;
std::cin >> NombreReel;

// Saisie d’un caractère
char Caractere = 0;
std::cin >> Caractere;

Si l’utilisateur saisi autre chose que ce qui est attendu, cin passe en état d’échec.

Cela signifie que si l’utilisateur saisi une lettre alors que c’est un nombre entier qui est attendu, cin se met en état d’échec (failed state). Voici un exemple très simple qui démontre le problème :

#include <iostream>

int main() {
   int Nombre1 = 12345;
   int Nombre2 = 999;

   std::cout << "Entrez un premier nombre entier : ";
   std::cin >> Nombre1;
   std::cout << "Entrez un second nombre entier : ";
   std::cin >> Nombre2;

   std::cout << "Vous avez saisi les nombres " << Nombre1
             << " et " << Nombre2 << "\n";
   return 0;
}

Si ce qui est saisi ne ressemble pas à un nombre entier, le flux cin passe en état d’échec (ligne 8 ) et toutes les demandes de saisie ultérieures (ligne 10) rendront immédiatement la main au programme sans que rien ne se passe.

Si l’appel à cin est fait au sein d’une boucle (par exemple pour vérifier si le nombre saisi est compris dans un intervalle donné) et que cin passe en état d’échec, le programme tournera en boucle infinie.

#include <iostream>

int main() {
   int Nombre = 0;

   while (true) {
      std::cout << "Entrez un nombre compris entre 1 et 100 : ";
      std::cin >> Nombre;
      if ((Nombre >= 1) && (Nombre <= 100))
         break;
   }
   std::cout << "Vous avez saisi le nombre " << Nombre << "\n";
   return 0;
}

Pour éviter ce problème, il faut tester la valeur de retour du flux cin. Si celle-ci est fausse, c’est qu’une erreur s’est produite et que cin est en état d’échec. Il faut alors rétablir le flux cin en purgeant tout ce qu’il contient.

#include <iostream>
#include <limits>

int main() {
   int Nombre = 0;

   while (true) {
      std::cout << "Entrez un nombre compris entre 1 et 100 : ";
      if (!(std::cin >> Nombre)) {
         // Purge du flux cin
         std::cin.clear();
         std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
      }

      if ((Nombre >= 1) && (Nombre <= 100))
         break;
   }
   std::cout << "Vous avez saisi le nombre " << Nombre << "\n";
   return 0;
}

Voici l’exemple précédent réécrit pour tenir compte de saisies erronées. Les lignes 11 et 12 se chargent de purger le flux cin et de le remettre dans un état valide.

Bien sûr, il serait malvenu d’écrire tout ce code supplémentaire chaque fois que le flux cin est utilisé. Pour éviter ces répétitions, il suffit d’écrire une fonction de saisie d’un nombre entier, qui se charge de traiter l’état d’erreur du flux cin.

Selon les besoins, cette fonction pourra être plus ou moins complexe. Voici une version minimale :

// Fonction de saisie d'un nombre entier au clavier
//@return le nombre entier saisi, ou zéro en cas de saisie invalide.
int getInteger() {
   int Nombre = 0;
   if (!(std::cin >> Nombre)) {
      // Purge du flux cin
      std::cin.clear();
      std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
   }
   return Nombre;
}

Voici le premier programme de cette annexe réécrit de façon à utiliser la fonction ci-dessus :

#include <iostream>
#include <limits>

// Fonction de saisie d'un nombre entier au clavier
//@return le nombre entier saisi, ou zéro en cas de saisie invalide.
int getInteger() {
   int Nombre = 0;
   if (!(std::cin >> Nombre)) {
      // Purge du flux cin
      std::cin.clear();
      std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
   }
   return Nombre;
}

// Programme principal
int main() {
   int Nombre1 = 12345;
   int Nombre2 = 999;

   std::cout << "Entrez un premier nombre entier : ";
   Nombre1 = getInteger();
   std::cout << "Entrez un second nombre entier : ";
   Nombre2 = getInteger();

   std::cout << "Vous avez saisi les nombres " << Nombre1
             << " et " << Nombre2 << "\n";
   return 0;
}

Les dates

Monday, March 22nd, 2010

Lors de la pratique de son métier, un développeur sera assurément amené à manipuler des dates.

À moins d’une raison très particulière, il ne faudrait pas réinventer la roue et plutôt faire usage des classes prenant déjà en charge la problématique des dates (et de l’heure).

Qt, par exemple, met à disposition les classe QDate et QDateTime.

Mais lorsqu’on apprend la programmation, les exercices sur les dates sont des classiques. Voici ce qui est souvent demandé :

  • déterminer si une année donnée est bissextile ;
  • déterminer le jour de la semaine d’une date donnée ;
  • convertir l’année d’une date en chiffres romains (et vice-versa).

Je reviendrai certainement sur la conversion d’un chiffre arabe en chiffre romain (et vice-versa) dans un autre billet.

Déterminer si une année est bissextile

Pour le calendrier grégorien (celui que l’on utilise de nos jours), une année (le temps que met la Terre pour faire un tour complet autour du Soleil) dure 365.2425 jours.

Avec ce calendrier la méthode pour déterminer si une année donnée est bissextile est la suivante :

  • Une année est bissextile si elle se divise par 4.
  • Une année n’est pas bissextile si elle se divise par 100.
  • Toutefois, si elle se divise par 400, elle est bissextile.
bool isLeapYear(int Year) {
   return (Year % 400 == 0 || (Year % 4 == 0 && Year % 100 != 0) );
}

Mais ce calcul n’est valable qu’avec le calendrier grégorien. Or, celui-ci a été introduit le 15 octobre 1582 par le pape Grégoire XIII.

Pour toutes les années qui précèdent 1582, c’est le calendrier julien qui fait foi. Ce calendrier est basé sur une année de 365.25 jours, ce qui signifie qu’il y a une année bissextile tous les 4 ans.

Notre méthode de calcul peut donc être améliorée :

bool isLeapYear(int Year) {
   if (Year < 1582)
      return abs(Year) % 4 == 0;
   else
      return (Year % 400 == 0 || (Year % 4 == 0 && Year % 100 != 0) );
}

Déterminer le jour de la semaine

La méthode permettant de déterminer quel jour de la semaine est une date donnée est différente selon que la date fait partie du calendrier grégorien ou julien.

Le calendrier julien se termine le 4 octobre 1582. Le calendrier grégorien commence le 15 octobre 1582. Cela signifie que le jour qui suit la date du 4 octobre 1582 est le 15 octobre 1582. Les dates comprises entre le 5 et le 14 octobre 1582 n’existent pas.

prérequis : Jour (1 - 31), Mois (1-12), Année
variables : DécaleAn, MoisDécalé, An, NuméroJour : entiers
début
   DécaleAn <- (14 - Mois) / 12
   An <- Année - DécaleAn
   MoisDécalé <- Mois + 12 * DécaleAn - 2

   si (Année > 1582) ou (Année = 1582 et (Mois > 10) ou (Mois = 10 et Jour >= 15))) alors
      NuméroJour = (Jour + Année + An/4 - An/100 + An/400 + 31 * Mois / 12) modulo 7
   sinon
      si (Année < 1582) ou (Année = 1582 et (Mois < 10 ou (Mois = 10 et Jour <= 4))) alors
         NuméroJour = (5 + Jour + An + An / 4 + ( 31* Mois / 12) modulo 7
      sinon
         NuméroJour = erreur
      fin si
   fin si
fin

NuméroJour vaut 0 pour dimanche, 1 pour lundi, etc.

En C++, la fonction pourrait être la suivante :

int dayOfWeek(int Jour, int Mois, int Annee) {
   int DecaleAn = 14 - Mois / 12;
   int An = Annee - DecaleAn;
   int MoisDecale = Mois + 12 * DecaleAn - 2;
   int NumeroJour = 0;

   if ( (Annee > 1582) ||
        (Annee == 1582 && (Mois > 10) || (Mois == 10 && Jour >= 15))) )
      NumeroJour = (Jour + Annee + An/4 - An/100 + An/400 + 31 * Mois / 12) % 7;
   else if ( (Annee < 1582) ||
                (Année == 1582 && (Mois < 10 || (Mois == 10 && Jour <= 4))) )
      NumeroJour = (5 + Jour + An + An / 4 + ( 31* Mois / 12) % 7;
   else
      NumeroJour = -1; 

   return NumeroJour; // 0 : dimanche, 1 : lundi, etc. -1 : erreur
}

Pourquoi QList::count() retourne un int ?

Thursday, March 18th, 2010

Les utilisateurs de Qt4 ont peut-être remarqué que la méthode count() ou size() de QList (mais également d’autres classes comme QVector, QMap, etc) retourne un int (donc un entier signé pouvant représenter des valeurs négatives), alors qu’à première vue, un entier non-signé semblerait plus logique.

D’ailleurs, les classes équivalentes de Qt3 retournaient bien un entier non-signé (unsigned int ou uint). Pourquoi ce changement ?

Au premier abord, un entier non-signé semble plus correct qu’un entier signé pour représenter une quantité : une liste ne peut pas contenir un nombre d’éléments négatif. Toutefois à l’usage, il est fréquent de comparer un entier avec le nombre d’élément d’une liste, ce qui provoque à chaque fois un avertissement du compilateur (qui peut être supprimé en faisant un transtypage).

Mais au delà de la stricte application disant qu’une quantité ne peut pas être négative, la raison principale d’utiliser un entier signé est d’éviter des erreurs sournoises.

Par exemple, si count() retourne un entier non-signé, le code suivant fonctionne :

for (uint i = 0; i < count(); ++i)

Mais à l’opposé, le code ci-dessous ne fonctionne pas :

for (uint i = count() - 1; i >= 0; --i)

car si la liste est vide, count() retournera zéro, et au moment d’être décrémenté, il vaudra une valeur positive. C’est un problème sournoi qui ne saute pas aux yeux et qui provoque souvent des boucles quasi-infinies.

Par contre, si count() retourne un entier signé, les deux façons de faire ci-dessous fonctionnent, sans subtilité cachée :

for (int i = 0; i < count(); ++i)
for (int i = count() - 1; i >= 0; --i)

Trucs et astuces C++

Tuesday, February 2nd, 2010

Initialiser un tableau

Lorsqu’on déclare un tableau d’entiers, il arrive souvent que l’on préférerait que ses éléments soient initialisés à zéro.

Plutôt que de le faire manuellement dans une boucle :

int Tableau[30];

for (int i = 0; i < sizeof(Tableau)/sizeof(int); ++i)
   Tableau[i] = 0;

il est possible de l’initialiser directement ainsi :

int Tableau[30] = {};

Il est possible de n’initialiser que quelques premiers éléments avec des valeurs spécifiques. Les autres éléments seront automatiquement initialisés à zéro.

int Tableau[30] = { 543, 245, 738 };

endl et \n

En mode console, lorsqu’on souhaite faire un retour de chariot, quelle différence entre endl et \n ?

Tout d’abord, il faut préciser que \n est portable. Même si le retour de chariot est codé différemment selon les systèmes d’exploitation, l’implémentation des classes de flux (iostream) prend en charge ces différences.

Pour revenir à la différence, \n provoque un retour de chariot alors que endl provoque un retour de chariot et vide le flux de sortie (flush) ce qui garanti par exemple pour la sortie standard que le flux est immédiatement affiché.

Dans la plupart des cas, cette différence n’aura aucun impact sur le résultat obtenu sur la sortie standard. Elle peut avoir un léger impact sur la performance étant donné que endl fait plus de choses que \n.

Par contre, cette différence peut être importante si l’on travaille sur d’autres genres de flux. Par exemple si l’on envoie des informations sur un fichier de log et que l’on veut être sûr que ce log reflète l’état le plus récent du programme, alors l’usage de endl plutôt que \n permet de garantir que ce qui est envoyé dans le fichier de log l’est immédiatement.

Opérateur ternaire

L’opérateur ternaire est généralement utilisé sous cette forme :

string Texte = (Saisie == NombreMysterieux) ? "trouvé" : "raté";

Mais l’opérateur ternaire peut également être utilisé comme lvalue (valeur assignable) :

(A > B ? A : B) = 0;

ce qui est équivalent au code ci-dessous :

if (A > B)
   A = 0;
else
   B = 0;

Cette fonctionnalité peut néanmoins aboutir à un code illisible et dangereux !