Accueil › Devoirs › Bac SI

Exercice 1 : fonctions récursives (6 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 (2 pts).
• 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 ? (2 pts)

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 (7 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 (3 pts).
• 2) Écrire la fonction BaseVersDec(ch, b) qui renvoie la valeur décimale de la chaîne ch écrite en base b (3 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 (7 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) (2 pts).
• 2) Dérouler PGCD(252, 105) en donnant tous les appels (1 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 (3 pts).

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

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

Correction détaillée

Sujet original écrit pour Mission Carthage, dans le style des devoirs de synthèse du bac Sciences de l'informatique.

Tout le programme : Bac Sciences de l'informatique