Chaînes d'addition en C

Voici un essai de solution du devoir maison numéro 2. Le code est en C, ce qui est sensiblement normal quand on recherche la vitesse et que l'algorithme est simple. Comprendre le C n'est pas bien difficile, quand on connaît Java.

Les deux programmes add et ext2 se compilent à l'aide de ce fichier Makefile, par les commandes :
# make add
# make ext2

Jusqu'à vingt

Le programme suit l'énoncé, avec les décisions d'implémentation suivantes : Bref, voici le code add.c. Il faut bien noter que ce code n'a rien de particulièrement subtil, à part l'usage des Patricia trees et la gestion mémoire par comptage de référence qui peut être ignorée en première lecture.

Au delà

L'extension proposée est également réalisée en C, source ext2.c.

L'idée est ici encore celle de l'énoncé. Une fonction explore parcours l'arbre « virtuel » de l'énoncé. Rapellons que les noeuds de cet arbre sont étiquetés par des entiers qui sont la somme des étiquettes de deux ancêtre. En outre, les étiquettes croissent quand on descend dans l'arbre. Ainsi, le sommet de l'arbre étant étiqueté par 1, il n'a qu'un fils étiqueté par 2, qui a deux fils étiquetés par 3 = 1+2 et 4 = 2+2.

Le type des éléments des chaînes est entier non-signé, comme c'est un peu long à écrire on le définit comme le type base.
typedef unsigned int base ;

Voici la signature de explore.
static unsigned int
explore(base d, base n, base *q, stack *st, base *vert, base* slant)
La fonction explore renvoie un compte des chaînes d'addition. L'entier d est la profondeur d'exploration ou plutôt la distance avant d'atteindre les feuilles de l'arbre. L'entier n est la cible, c'est-à-dire que l'on recherche les chaînes se terminant par n. L'argument q est un pointeur vers une case mémoire où ranger l'étiquette que nous allons trouver. Les étiquettes des ancêtres sont rangées en mémoire avant notre case, ainsi *(q-1) (qui veut dire q[-1] !) est l'étiquette du père, *(q-2) est celle du grand-père, etc. jusqu'au sommet d'étiquette 1. Les autres arguments correspondent à la gestion d'une pile (st) et aux diverses optimisations que je n'expliquerais pas (le premier article cité en référence dans l'énoncé les décrit largement).

Donc voici une version simplifiée de explore :
static unsigned int explore(base d, base n, base *q, stack *st) {
Cette version simplifiée est invoquée initialement par une fonction chain, chargée de trouver les chaine de taille k aboutissant en n.
static unsigned int chain(base k, base n) {
  base t[k+1] ; /* Allocation (en pile) du tableau des étiquettes */
  t[0] = 0 ; /* sentinelle */
  t[1] = 1 ; /* étiquette du sommet */
  return explore(k-1, n, t+2, ...) ;
}
L'idée, conforme à l'énoncé est d'appeler chain, sur tous les entiers k successifs à partir des bornes inférieures fonction de n, et ceci jusqu'à trouver des chaînes. En gros on aura :
  base k = borne(n)+1 ;
  unsigned int r = 0 ;
  do {
    r = chain(k,n) ;
    k++ ;
  } while (r == 0) ;
En sortie de boucle, k-2 vaut la taille des plus petites chaînes d'addition aboutissant en n (il faut soustraire 1 à cause de l'incrément supplémentaire k++ et encore 1 parceque le paramètre k de explore est en fait la taille de chaîne plus 1).

Mais venons-en au code de la fonction explore. On s'interesse d'abord au cas de base de la récursion : nous allons construire une chaîne de la taille voulue et dont le dernier élément est n.
  if (d <= 1) { /* Nous sommes arrivés */
    base *t, *tt ;
    for (t = q-1 ; ; t--) { /* parcourir les ancêtres jeune -> vieux */
      base x = *t ; /* x est l'étiquette d'un ancêtre */
      if (2*x < n)  /* fini car x est trop petit */
        break ;
      for (tt = t ; ; tt--) { /* *tt est un autre ancêtre (+ vieux que x)  */
        base s = x + *tt ; /* nouvelle étiquette potentielle */
        if (s < n) break ; /* *tt trop vieux, fini */
        if (s == n) {  /* trouvé ! */
          return 1 ;
        }
      }
    }
    return 0 ; /* pas trouvé */
À part quelques astuces de contrôle (break, return), le code n'est pas trop compliqué. Un point notable est l'utilisation de la décroissance des étiquettes pour abréger la recherche d'une somme valant n. Cela fonctionne totalement grâce à une sentinelle, la case mémoire qui précède l'étiquette du sommet contient zéro. Et donc on finira toujours par avoir 2 x < n (si n > 0), ou s = x + *ttn (par construction x < n comme on va le voir). Reste le cas n=1, d=1 traité un peu bizarrement (chaîne {0, 1, 1}), mais bon.

Voici maintenant l'étape inductive. On va d'abord calculer toutes les sommes de deux étiquettes d'ancêtres et les ranger à la queue-leu-leu dans une zone de mémoire ad-hoc. La gestion de cette zone de mémoire st ne sera pas décrite, on peut y ajouter un nouvel entier par st = insert(st, s) ; On saura ensuite la parcourir de st->fp à st->sp-1.

On limite les sommes à un intervalle pertinent compris entre la limite basse low et la limite haute high. Soit prev l'étiquette du père. Sans optimisation on peut poser low = prev+1 et high égal au minimun de 2*prev et n-1.

Donc nous pouvous calculer et insérer toutes les sommes de deux ancêtres, le code est en fait très similaire à celui du cas de base.
    for (t = q-1 ;  ; t--) {
      base x = *t ;
      base s ;

      if (2*x < low) break ;

      for (tt = t ; ; tt--) {
        s = x + *tt ;
        if (s <= high) break ;
      }
      while (s >= low) {
        st = insert(st, s) ;
        s = x + *--tt ;
      }
    }
Un fois de plus on utilise la présentation décroissante des ancêtres, mais le principal attrait de cette présentation est de faciliter l'utilisation des optimisations qui conduisent à un low plus grand.

Il peut sembler un peu inutile de calculer l'ensemble des sommes, puis de parcourir cet ensemble, mais cela permet de ne pas procéder à plusieurs appels récursifs quand un entier donné correspond à plusieurs sommes d'ancêtres.

Reste à parcourir les étiquettes possibles :
    r = 0 ;
    tt = st->sp ;
    for (t = st->fp ; t < tt ; t++) {
      *q = *t ; /* Ranger l'étiquette courante à sa place */
      r += explore(d-1, n, q+1, st) ; /* notez d-1, q+1 */
    }
Ainsi, en sortie de boucle, r vaut le nombre de chaînes trouvées. Si on ne cherche qu'une chaîne. On peut aussi écrire
    tt = st->sp ;
    for (t = st->fp ; t < tt ; t++) {
      *q = *t ;
      if (explore(d-1, n, q+1, st))
         return 1 ;
    }

Voilà ces quelques explications devraient permettre d'aborder le programme complet ext2.c. Le code le plus tordu est celui de la gestion mémoire, un tel code n'aurait pas de raison d'apparaître en Java.

Le programme est en fait assez polyvalent, il prend les options suivantes.
usage: ./ext2 [-vVcla] [n]
  -v, donne des diagnostics
  -V, encore plus de diagnostics
  -c, optimisations de type c (type a par défaut)
  -l, affiche les chaînes d'additions
  -a, affiche les tableaux c et d de l'énoncé

Ce document a été traduit de LATEX par HEVEA.