M1103 – TD2 – Exercice 5

Les représentations binaires de tous les entiers codés sur 3 bits sont les suivantes :

000
001
010
011

100
101
110
111

On remarque que les 8 chaînes générées se répartissent en deux groupes : toutes les chaînes commençant par ‘0’ puis toutes celles commençant par ‘1’. Dans chacun de ces groupes, et abstraction faite de ce premier caractère, les chaînes de caractères restantes sont les représentations binaires de tous les entiers codés sur 2 bits :

0 00
0 01

0 10
0 11

Dans chacun des deux sous-groupes, et abstraction faite des deux premiers caractères, les chaînes de caractères restantes sont les représentations binaires de tous les entiers codés sur 1 bit :

00 0
00 1

L’algorithme de construction est évidemment doublement récursif. La génération de toutes les représentations binaires de N bits, consiste à :

  1. placer ‘0’ en position 0 de la chaîne, puis générer toutes les représentations binaires des N – 1 bits restants,
  2. placer ‘1’ en position 0 de la chaîne, puis générer à nouveau toutes les représentations binaires des N – 1 bits restants.

La construction se fait dans une chaîne, de longueur N, qui est remplie au fur et à mesure et affichée seulement lorsqu’elle est pleine.

L’exécution de votre algorithme devra est similaire à la trace suivante (le caractère 'X' désigne une lettre inconnue) :

             XXX
          /        \ 
      0XX             1XX
     /    \          /   \
  00X      01X     10X    11X
 /  \     /  \   /   \   /  \ 
000 001 010 011 100 101 110 111

Ecrire la procédure doublement récursive RepresentBin (), qui génère dans une chaîne de taille N toutes les représentations binaires à partir de la position i, et les affiche à chaque fois que la chaîne est pleine. La chaîne ainsi que le rang i sont passés en paramètres.