M1103 – TD2 – Exercice 1

Rappel : un palindrome est “un mot, un vers, une phrase que l’on peut lire dans les deux sens” (dictionnaire Larousse).

Ecrire la fonction IsPalindrome() qui renvoie vrai si la chaîne qui lui est passée en paramètre est un palindrome de façon itérative.

On peut aussi en donner la définition récursive suivante :

  1. un mot est un palindrome si sa première et sa dernière lettre sont identiques et si le reste du mot est lui-même un mot palindrome,
  2. un mot d’une seule lettre est un palindrome,
  3. une chaîne vide sera considérée, par extension, comme un palindrome.

Ecrire la fonction IsPalindrome() qui renvoie vrai si la chaîne qui lui est passée en paramètre est un palindrome de façon récursive.

M1103 – TD2 – Exercice 2

On peut donner la définition du calcul d’une puissance d’un nombre de façon récursive comme suit :

Soit x un nombre réel et n un entier relatif. Alors :

  1. xn = 1 si n = 0
  2. xn = 0 si x = 0 (et n ≠ 0)
  3. xn = 1 / (x-n) si n < 0
  4. xn = x * xn-1 sinon

    En vous inspirant de la fonction Factorielle () montrée en cours, écrire la fonction récursive PuissEntRecurs () qui renvoie le résultat xn, x et n étant passés en paramètres.

M1103 – TD2 – Exercice 3

Les nombres romains sont constitués de suites des caractères M, D, C, L, X, V et I, représentant respectivement 1000, 500, 100, 50, 10, 5 et 1. Le calcul de la valeur décimale est très simple lorsque les symboles se présentent dans l’ordre décroissant : il suffit de faire la somme des valeurs des symboles rencontrés. Par exemple, la chaine de caractères MMCVI représente la valeur 2106 (1000 + 1000 + 100 + 5 + 1.

En revanche, lorsque certains symboles sont inversés, il faut les soustraire au symbole suivant. Par exemple, la chaine de caractères CM représente 900 (1000 – 100), et IV représente 4 (5 – 1).

La récursivité offre une élégante solution à ce problème :

  1. si un nombre romain est constitué d’un seul caractère, sa valeur est égale à celle de ce caractère.
  2. la valeur d’un nombre romain est égale à la valeur du premier caractère + la valeur du nombre romain restant, si la valeur de ce premier caractère est supérieure ou égale à celle de son suivant (le deuxième, donc). Par exemple :
        MMXI = M + (MXI) = 
                    MXI = M + (XI)
                               XI = X + (I)
                                         I = 1
                                    10 + 1 = 11
                          1000 + 11 = 1011
              1000 + 1011 = 2011
        2011
    
  3. la valeur d’un nombre romain est égale à la valeur du nombre romain restant après le premier caractère – la valeur du premier caractère, si la valeur de ce caractère est inférieure à celle de son suivant, Par exemple :
        MCMIX = M + (CMIX) = 
                     CMIX = (MIX) - C
                             MIX  = M + (IX)
                                         IX = (X) - I
                                               10
                                              (10 - 1) = 9
                                    1000 + 9 = 1009
                             1009 - 100 = 909
                1000 + 909 = 1909
        1909
    

On suppose qu’existe la fonction ValChRomain() qui renvoie la valeur numérique correspondant au caractère romain qui lui est passé en paramètre.

Ecrire la fonction ValNbRomain() qui renvoie la valeur numérique correspondant à un nombre romain qui lui est passé en paramètre sous forme d’un string. On supposera qu’une chaîne vide a pour valeur 0 et que la chaîne passée en paramètre est valide.

M1103 – TD2 – Exercice 4

Faites la trace de l’algorithme suivant en considérant l’appel LS ("","abc");

Algorithm Ls
Input: X and Y two string 
Output:
if (Y.size() == 0) then {
    cout << X; 
    return;
}
char tmp =Y.last ();
Y .pop_back ();
LS(X,Y); 
string Z = X + tmp; 
LS(Z,Y); 

Déduisez la sortie.

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.

M1103 – TD2 – Exercice 6

Le problème dit des “Tours de Hanoi” peut être vu comme un exercice récréatif, un casse-tête, un jeu mathématique, … Il fait l’objet d’une abondante littérature sur Internet, présentant à la fois la légende d’où il serait issu, de nombreuses animations illustrant sa résolution, des variantes et de savants développements mathématiques … Sa résolution est une très simple et intéressante application récursive de parcours infixé d’arbre !

    Le problème

Le jeu est constitué de 3 pieux (ou pivots), et de N anneaux de diamètres strictement décroissants enfilés initialement sur l’un des pieux et constituant une “tour”. Il s’agit de faire passer les N anneaux du pieu initial sur l’un des deux autres pieux, en respectant les règles suivantes :

  1. les anneaux ne peuvent être déplacés qu’un seul à la fois,
  2. seul l’anneau du dessus d’une tour peut être déplacé,
  3. un anneau peut être prélevé de n’importe quelle tour et enfilé sur n’importe quel autre pieu à condition qu’il ne soit jamais posé sur un anneau de diamètre inférieur.

Le jeu consiste à effectuer le moins de déplacements possible !

Ecrire la procédure récursive Hanoi() qui décrit les mouvements élémentaires des disques. Elle reçoit en paramètres-données :

  1. le nombre d’anneaux de la tour à déplacer,
  2. les identifiants (un simple caractère) des pieux respectivement initial, final et intermédiaire.

Construire l’arbre des appels.