Devoir de synthèse n°1 : récursivité, bases de numération, PGCD, matrice de bits

Exercice 1 : fonctions récursives (5 pts)

Une fonction est récursive quand elle s'appelle elle-même. On considère les deux définitions suivantes.

• Puissance(x, n) = 1 si n = 0, et x × Puissance(x, n - 1) sinon (x entier, n entier naturel).
• SommeChiffres(m) = m si m < 10, et (m mod 10) + SommeChiffres(m div 10) sinon (m entier naturel).

• 1) Écrire les deux fonctions récursives (2 pts).
• 2) Dérouler SommeChiffres(472) : donner la suite des appels, puis le résultat (1,5 pt).
• 3) Écrire une version de Puissance qui fait beaucoup moins d'appels en utilisant x^n = (x^(n div 2))² quand n est pair, et x × x^(n - 1) quand n est impair. Combien d'appels pour x^13 ? (1,5 pt)

Le programme principal lit x, n et m, puis affiche Puissance(x, n) et SommeChiffres(m). Pour 2, 10 et 472, il affiche :

1024
13

Exercice 2 : changement de base (6 pts)

Les chiffres d'un nombre écrit dans une base b (2 ≤ b ≤ 16) sont pris dans la chaîne « 0123456789ABCDEF ».

• 1) Écrire la fonction récursive DecVersBase(n, b) qui renvoie, sous forme de chaîne, l'écriture de l'entier naturel n en base b (2,5 pts).
• 2) Écrire la fonction BaseVersDec(ch, b) qui renvoie la valeur décimale de la chaîne ch écrite en base b (2,5 pts).
• 3) Vérifier à la main : écrire 255 en base 2 et en base 16 (1 pt).

Le programme principal lit n et b, affiche l'écriture de n en base b, puis lit une chaîne et sa base et affiche sa valeur décimale. Pour 255 et 2, puis FF et 16, il affiche :

11111111
255

Exercice 3 : PGCD, PPCM et fraction irréductible (5 pts)

L'algorithme d'Euclide repose sur la propriété : PGCD(a, b) = a si b = 0, et PGCD(a, b) = PGCD(b, a mod b) sinon.

• 1) Écrire la fonction récursive PGCD(a, b) (1,5 pt).
• 2) Dérouler PGCD(252, 105) en donnant tous les appels (0,5 pt).
• 3) En déduire la fonction PPCM(a, b) (1 pt).
• 4) Écrire un programme qui lit deux entiers a et b strictement positifs (saisie contrôlée) et affiche leur PGCD, leur PPCM et la fraction a/b rendue irréductible (2 pts).

Pour a = 12 et b = 18, le programme affiche :

PGCD : 6
PPCM : 36
Fraction irréductible : 2/3

Exercice 4 : une matrice de bits (4 pts)

Une matrice B de l lignes et c colonnes (1 ≤ l ≤ 8, 2 ≤ c ≤ 8) ne contient que des 0 et des 1 : chaque ligne est l'écriture en base 2 d'un entier naturel, le bit de poids fort étant dans la colonne 0. Par exemple, la ligne 1 0 1 1 représente 11.

• 1) Écrire la procédure RemplirBits(B, l, c) qui lit les éléments de B, chacun égal à 0 ou à 1 (saisie contrôlée) (1 pt).
• 2) Écrire la fonction ValeurLigne(B, i, c) qui renvoie la valeur décimale de la ligne i, sans calculer de puissance de 2 (1,5 pt).
• 3) Écrire le programme qui lit l et c (saisies contrôlées), remplit B, affiche la valeur de chaque ligne puis la somme de ces valeurs (1,5 pt).

Pour l = 3, c = 4 et les lignes 1 0 1 1, 0 1 1 0 et 1 1 1 1, le programme affiche :

Ligne 1 : 11
Ligne 2 : 6
Ligne 3 : 15
Somme : 32