Codez vos algorithmes proprement en C/C++

Arthur Charguéraud pour www.france-ioi.org

Ce document récapitule quelques techniques permettant de maximiser la clarté et la simplicité du code implémentant son algorithme. Le but est donc double : éviter d'introduire des bugs dans un premier temps, et avoir un code pouvant être relu facilement dans un second temps pour trouver les bugs restants. On fera tout de même attention à ne pas sacrifier significativement la performance de l'implémentation.

Avant de commencer, petite remarque s'adressant à ceux qui codent en C : compilez en C++. Il n'y a aucun inconvénient, et surtout trois gros avantages permettant d'obtenir au final un code plus clair :

• pouvoir utiliser la bibliothèque standard C++ (surtout hashmap et priority_queue, mais aussi min, max et sort),
• pouvoir déclarer ses variables là où elles sont initialisées,
• faciliter la déclaration et l'utilisation des struct.

Attention cependant, pour les entrées-sorties, il faut impérativement utiliser scanf et printf et non cin et cout qui peuvent être jusqu'à 10 fois plus lents.

Structure d'un source

1. #include des bibliothèques
2. constantes données dans le sujet
3. structures de données
4. fonctions de l'algorithme
5. la fonction main

Remarque : il n'est en général pas nécessaire d'écrire les prototypes des fonctions si vous les définissez dans le bon ordre.

Inclure les bibliothèques

Pour les fonctions d'entrées-sorties, il faut et suffit d'avoir la ligne :

#include <cstdio>

Pour les fonctions mathématiques, ajoutez :

#include <cmath>

Pour pouvoir utiliser la bibliothèque standard C, ajoutez :

#include <cstdlib>

Pour tout savoir sur l'utilisation de la bibliothèque standard C++, reportez-vous au cours qui traite spécialement du sujet.

Les constantes

On utilise le plus souvent des const int. Surtout pas de #define, pour trois raisons : on fait du C++ et pas du C, on type les constantes, on évite des problèmes de parenthésages.

Écrire le nom des constantes en lettres majuscules permet de bien les faire ressortir dans le source.

Petit exemple dans un graphe qui a au plus 500 sommets, chaque arc mesurant au plus 1000, on veut définir une constante pour mettre en œuvre la notion de distance infinie pour un plus court chemin dans ce graphe. Il suffit pour cela de prendre n'importe quelle valeur supérieure à (MAX_NB_NOEUDS-1)*MAX_LONG_ARC. On préfère prendre de la marge afin de détecter plus facilement d'éventuels bugs, et on ajoutera donc un facteur 10 à cette valeur.

const int MAX_NB_NOEUDS = 500;
const int MAX_LONG_ARC = 1000;
const int LONG_INFINIE = MAX_NB_NOEUDS * MAX_LONG_ARC * 10;

Les structures de données

Lorsqu'on programme juste un algorithme dans un seul fichier et en temps limité, on fait tout le contraire de ce que l'on ferait dans un vrai projet de programmation au niveau des structures de données. On déclare en effet toutes ces structures en global. Par exemple pour stocker la matrice d'adjacence d'un graphe qui contient au plus MAX_NB_NOEUDS = 1000 nœuds, on déclare en global :

int arcs[MAX_NB_NOEUDS][MAX_NB_NOEUDS];

Sauf cas exceptionnel avec des structures hautement dynamiques, on ne se sert pas du tout de new, encore moins de malloc. Et sauf si c'est vraiment ce que vous voulez faire, évitez de passer des tableaux en paramètre aux fonctions, ou de déclarer des tableaux à l'intérieur de ces fonctions.

On met aussi en global les variables associées aux structures globales, notamment leur taille, par exemple :

int nbNoeuds;
int arcs[MAX_NB_NOEUDS][MAX_NB_NOEUDS];

On définit également à cet endroit les structures. On compile en C++ pour ne pas avoir besoin de typedef. Par exemple :

struct case
{
   int x;
   int y;
};

Les fonctions utilitaires

Surtout, ne faites pas de #define pour coder les fonctions abs, min et max. En effet :

• Pour le faire bien, il faut mettre des parenthèses partout.
• Si l'on donne en argument à max des appels de fonctions, ces appels seront effectués deux fois au lieu d'une, ce qui peut poser de gros problèmes.
• Ces fonctions existent déjà dans les bibliothèques C et C++, donc on évite de les recoder et de laisser une erreur.

Pour pouvoir utiliser la fonction abs, ajoutez #include <cstdio> au début de votre source.

Pour pouvoir utiliser les fonctions min et max, ajoutez au début de votre source :

#include <algorithm>
using namespace std;

Les fonctions de l'algorithme

Le pseudo-code doit utiliser des fonctions qui ne dépassent pas 15 lignes de C++ (accolades exclues), pour les raisons suivantes :

• Lorsqu'il y a plus de lignes, il faut mettre des commentaires, alors que l'on pourrait simplement utiliser le nom des sous-fonctions pour s'y retrouver.
• Relire et débugger des fonctions indépendantes est bien plus facile.

Les fonctions d'entrée/sortie tiennent en général dans la fonction main, mais ce n'est pas toujours le cas. S'il y a besoin de plus de 15 lignes pour lire l'entrée, appeler la fonction principale de l'algorithme et afficher la sortie, alors on pourra considérer le déplacement de la lecture de l'entrée et/ou l'affichage de la sortie dans des fonctions auxiliaires.

La fonction main

Son code doit être clair et simple, pour donner d'un coup d'œil la structure du programme.

Codez toujours la fonction main en respectant ce schéma :

int main()
{
   ...
   return 0;
}

Si vous oubliez le return 0;, vous prenez le risque de voir votre programme rejeté par le juge en ligne. Écrivez donc toujours return 0; à la fin de main. Retourner une autre valeur ferait croire au juge en ligne que votre programme a mal fonctionné.

Dans le code

Déclaration des variables

Utiliser les mêmes noms de variables et de fonctions que dans le pseudo-code. Non seulement parce que l'un des objectifs du pseudo-code est de choisir de bons noms de variables, mais aussi parce qu'il sera plus facile de relire en parallèle le pseudo-code et le code si les variables portent le même nom dans les deux.

Déclarez une variable par ligne, sauf pour celles qui vont ensemble. Evitez :

int l, c, typeSalle[100][100];

int nbLigne, nbColonne, typeSalle[MAX_COTE][MAX_COTE];

int nbLigne, nbColonne;
int typeSalle[MAX_COTE][MAX_COTE];

Déclarez vos variables là où vous en avez besoin, et pas avant. Le but est de regrouper les choses qui vont ensemble. Le programme suivant lit la description d'un certain nombre de points dans le plan (des arbres dans un champ) et détermine la distance des deux arbres les plus éloignés. La bonne solution prend plus de lignes, mais est beaucoup plus facile à lire/comprendre/débugger, car on distingue vraiment les trois entités : lire l'entrée, calculer le max, afficher le max. Ainsi, évitez

int arbre1, arbre2, nbArbres, ecart, ecartMax = 0;
Point arbres[MAX_NB_POINTS];
scanf("%d", &nbArbres);
for (arbre1 = 0; arbre1 < nbArbres; arbre1++)
   scanf("%d%d", &arbres[arbre1].x, &arbres[arbre1].y);
for (arbre1 = 0; arbre1 < nbArbres; arbre1++)
   for (arbre2 = 0; arbre2 < nbPoints; arbre2++)
      if ((ecart = arbres[arbre1].distance(arbres[arbre2])) > ecartMax)
         ecartMax = ecart;
printf("%d\n", ecartMax);

et préférez

int nbArbres;
scanf("%d", &nbArbres);
Point arbres[MAX_NB_POINTS];
for (int arbre = 0; arbre < nbArbres; arbre++)
   scanf("%d%d", &arbres[arbre].x, &arbres[arbre].y);

int ecartMax = 0;
for (int arbre1 = 0; arbre1 < nbArbres; arbre1++)
   for (int arbre2 = 0; arbre2 < nbPoints; arbre2++)
   {
      int ecart = arbres[arbre1].distance(arbres[arbre2]);
      ecartMax = max(ecartMax, ecart);
   }

printf("%d\n", ecartMax);

Les entrées/sorties

Les entrées/sorties doivent être implémentées avec la bibliothèque C, et pas la bibliothèque C++ qui est beaucoup plus lente sous Linux (jusqu'à 10 fois !). Utilisez donc exclusivement des scanf et des printf.

Si vous souhaitez lire et écrire dans des fichiers, le plus simple est de rediriger l'entrée standard. L'exemple suivant lit un entier dans un fichier et en écrit la valeur dans un autre, en utilisant les fonctions scanf et printf :

#include <cstdio>

int main()
{
   int x;

   freopen("input.txt", "r", stdin);
   scanf("%d", &x);

   freopen("output.txt", "w", stdout);
   printf("%d\n", x);

   return 0;
}

Conclusion

Bien sûr, chacun a son style de programmation, avec ses petites habitudes. Mais en algorithmique, il n'y a pas de secret : pour y arriver il faut un code clair et simple, sinon on fait plus de bugs.