RA-FAlgorithmes récurrents et arithmétiques

Reconnaissance d'algorithmes arithmétiques (produit, somme, Euclide)

Idée directrice

Forme calquée sur l'exercice 2 de 2018 : cinq algorithmes arithmétiques F1–F5 (produit par additions, multiplications répétées, somme d'intervalle, plus grand diviseur commun par soustractions / par restes type Euclide), validation V/F. L'échantillon ne compte que cette session pour cette grille ; on ne la présente pas comme un invariant de toutes les années.

Ce qui aide à reconnaître la démarche

« Valider V/F : produit a×b, multiplications répétées, plus grand diviseur commun, somme des entiers de [a..b] »

Besoin d’un point de départ ? Voir la méthode

Lire d'abord ce que calcule chaque Fi (accumulateur, boucle, condition d'arrêt).
Ne cocher que V ou F : le barème 2018 n'acceptait pas d'autre forme de réponse sur la grille.
Distinguer produit, multiplications répétées, somme et diviseur commun : quatre rôles distincts.

Les pièges à vérifier dans ta démarche

Attribuer F5 au produit parce qu'il « manipule a et b » ; confondre multiplications répétées (F2) et produit par additions (F1) ; marquer une seule case alors que plusieurs Fi peuvent convenir (comme F4 et F5 pour le diviseur commun en 2018).

Sujet principal

Exercice — valider des propositions sur cinq algorithmes arithmétiques

10 questionsCorrigé masqué

On considère cinq algorithmes F1 à F5 opérant sur deux entiers a et b strictement positifs, donnés en base décimale :

F1 — accumule a, b fois (produit par additions répétées).
F2 — multiplie a par lui-même b fois.
F3 — additionne tous les entiers de l'intervalle [a..b].
F4 — calcule le plus grand diviseur commun par soustractions successives.
F5 — calcule le plus grand diviseur commun par restes successifs (méthode d'Euclide).

Valider chacune des propositions suivantes en mettant V si elle est correcte ou F si elle est fausse :

Pour obtenir le produit a × b, on peut utiliser F1.
Pour obtenir a multiplié par lui-même b fois, on peut utiliser F2.
Pour obtenir le plus grand diviseur commun de a et b, on peut utiliser F4 et F5.
Pour obtenir la somme des entiers de [a..b], on peut utiliser F3.
Pour obtenir le produit a × b, on peut utiliser F5 (Euclide).

Justifier en une ou deux phrases le verdict de la proposition 3 en reliant F4/F5 à l'algorithme d'Euclide.

Voir la correction commentéeAprès avoir posé votre démarche

Pour cet exercice, seules les réponses V / F (ou Vrai / Faux) sont attendues sur la grille, plus une courte justification pour la proposition 3.

Proposition	Verdict
1. produit via F1	V
2. multiplications répétées via F2	V
3. plus grand diviseur commun via F4 et F5	V
4. somme de `[a..b]` via F3	V
5. produit via F5 (Euclide)	F

Justification de la proposition 3. F4 et F5 calculent tous deux le plus grand diviseur commun : F4 remplace le plus grand des deux nombres par leur différence (a, b) → (a−b, b), F5 le remplace par le reste de la division (a, b) → (b, a mod b) ; les soustractions répétées de F4 produisent exactement les restes de F5, l'algorithme d'Euclide n'est que la version accélérée. Le résultat commun est le PGCD, ce qui rend la proposition vraie.

Lecture rapide des rôles : F1 ↔ produit ; F2 ↔ multiplications répétées ; F3 ↔ somme d'intervalle ; F4/F5 ↔ diviseur commun (Euclide / variante).

Changer d’énoncé, garder le raisonnement

Choisis un seul transfert après le sujet principal. Qu’est-ce qui change ? Quel résultat ou quelle méthode peux-tu réutiliser ? Les autres exercices restent disponibles pour une prochaine séance.

Exercices d'entraînement — une nuance à la fois

1 Lire une boucle avant de lui donner un nom

Entraînement 01 / 04

Lire une boucle avant de lui donner un nom

1 questionCorrigé masquéEn cours de relecture

On considère deux fonctions sur des entiers strictement positifs a et b. Les arguments sont passés par valeur. div est la division entière et mod donne le reste. Voici les algorithmes complets :

0) DEF FN F(a,b:entier):entier
1) s ← 0
2) TantQue b > 0 faire
     Si b mod 2 = 1 alors s ← s+a FinSi
     a ← 2*a
     b ← b div 2
   FinTantQue
3) F ← s
4) Fin F

0) DEF FN G(a,b:entier):entier
1) TantQue b ≠ 0 faire
     r ← a mod b ; a ← b ; b ← r
   FinTantQue
2) G ← a
3) Fin G

Pour l’appel F(7,6), établir la trace de (a,b,s) avant la boucle puis après chaque tour. Calculer ensuite G(7,6). Attribuer V ou F à chaque proposition et justifier : (1) F calcule toujours le PGCD de ses deux entrées ; (2) F et G donnent toujours le même résultat ; (3) F calcule le produit des deux entrées. Pour (3), justifier le rôle par la conservation de s+a*b à chaque tour, en distinguant b pair et b impair.

Cet exercice et sa correction sont en cours de relecture. Tu peux les consulter ; l’exercice n’est pas encore proposé en séance.

Voir la correction commentéeAprès avoir posé votre démarche

Trace. F : (7,6,0) → (14,3,0) → (28,1,14) → (56,0,42). La valeur retournée est 42. Pour G : (7,6) → (6,1) → (1,0), donc la valeur retournée est 1.

Verdicts. (1) F : le PGCD de 7 et 6 vaut 1, tandis que F retourne 42. (2) F : les deux fonctions diffèrent déjà sur ce même couple. (3) V : la preuve qui suit vaut pour toutes les entrées positives, contrairement à une simple vérification numérique.

Rôle général de F. Si b=2q, s est inchangé et le nouveau produit a*b vaut (2a)q=ab. Si b=2q+1, le nouveau s vaut s+a et le nouveau produit vaut (2a)q=ab−a : leur somme reste s+ab. Au début, s=0, donc cette somme est le produit des entrées. À la fin b=0, elle vaut s seul : F retourne bien ce produit. La boucle termine car b devient b div 2, strictement plus petit tant qu’il est positif. G est l’algorithme d’Euclide ; manipuler les mêmes entrées ne donne pas le même rôle.

2 Drill RA-F.2 — cinq fonctions pour n! et xⁿ : l'initialisation p ← 0 et les versions qui ne se trompent qu'en n = 0

Entraînement 02 / 04

Drill RA-F.2 — cinq fonctions pour n! et xⁿ : l'initialisation p ← 0 et les versions qui ne se trompent qu'en n = 0

5 questionsCorrigé masqué

Soient Fact(n) et Puiss(x, n) deux fonctions qui calculent respectivement n! (avec 0! = 1) et $x^n$ , où n est un entier naturel et x un réel. On donne les cinq fonctions F1 à F5 ci-dessous. Dans chacune, i est un entier ; p est un entier dans F1, F3 et F5, un réel dans F2 et F4.

Fonction F1 (n : Entier) : Entier
DEBUT
    p ← 0
    Pour i de 1 à n Faire
        p ← p * i
    Fin Pour
    Retourner p
FIN

Fonction F2 (x : Réel, n : Entier) : Réel
DEBUT
    p ← x
    Pour i de 2 à n Faire
        p ← p * x
    Fin Pour
    Retourner p
FIN

Fonction F3 (n : Entier) : Entier
DEBUT
    p ← n
    Pour i de 2 à n-1 Faire
        p ← p * i
    Fin Pour
    Retourner p
FIN

Fonction F4 (x : Réel, n : Entier) : Réel
DEBUT
    p ← 1
    Pour i de 1 à n Faire
        p ← p * x
    Fin Pour
    Retourner p
FIN

Fonction F5 (n : Entier) : Entier
DEBUT
    p ← 1
    Pour i de 2 à n Faire
        p ← p * i
    Fin Pour
    Retourner p
FIN

Donner la valeur retournée par F1(n), F3(n) et F5(n) pour n = 0, n = 1 et n = 4, puis par F2(2, n) et F4(2, n) pour n = 0, n = 1 et n = 5.
Parmi les fonctions F1 à F5, déterminer celle qui correspond à la fonction Fact et celle qui correspond à la fonction Puiss.
Valider chacune des propositions suivantes par la lettre V si elle est correcte ou F sinon.
1. F3 et F5 retournent la même valeur pour tout entier n ≥ 1.
2. Il suffit de remplacer p ← 0 par p ← 1 dans F1 pour obtenir une fonction qui calcule n! pour tout entier naturel n.
3. F2 calcule $x^n$ pour tout entier naturel n.
4. Dans F4, remplacer la boucle par Pour i de 2 à n Faire ne change pas le résultat.
On admet que $\cos(x)$ est la somme des termes $(-1)^k \dfrac{x^{2k}}{(2k)!}$ pour k = 0, 1, 2, … Écrire une fonction CalculCos(x : Réel, m : Entier) qui retourne la somme des m premiers termes, en utilisant Fact et Puiss sans les réécrire.
Un camarade écrit la même fonction CalculCos en utilisant F2 à la place de Puiss et F3 à la place de Fact. Que se passe-t-il dès le premier terme ? Pourquoi une version qui ne se trompe que pour n = 0 est-elle inacceptable ici ?

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : exécuter chaque boucle à la main. « Pour i de a à b » ne fait aucun tour quand a > b : pour n = 0 et n = 1, la valeur retournée est donc l'initialisation de p.

n	0	1	4
F1(n)	0	0	0
F3(n)	0	1	24
F5(n)	1	1	24

n	0	1	5
F2(2, n)	2	2	32
F4(2, n)	1	2	32

F1 part de 0 et tout produit par 0 reste nul. F3 part de n : pour n = 0 sa boucle est vide et elle retourne 0. F2 part de x : pour n = 0 et n = 1 sa boucle est vide et elle retourne x.

2. Idée : une fonction ne correspond à Fact ou à Puiss que si elle est juste pour toutes les valeurs permises, n = 0 compris.

Fact : F5. p vaut 1 puis est multiplié par 2, 3, …, n ; pour n = 0 et n = 1 la boucle est vide et la fonction retourne 1 = 0! = 1!. Commencer la boucle à 2 est sans danger ici, puisque multiplier par 1 ne change rien.
Puiss : F4. p vaut 1 puis est multiplié n fois par x ; pour n = 0 elle retourne 1 = $x^0$ .
F1 est éliminée pour toute valeur ; F3 et F2 ne sont éliminées que par n = 0, mais cela suffit.

3. Idée : pour dire V, raisonner sur tous les tours ; pour dire F, un seul contre-exemple suffit.

a) V. Pour n ≥ 2, F3 part de n et multiplie par 2, …, n − 1 : elle obtient 2 × 3 × … × n = n!. Pour n = 1 sa boucle est vide et elle retourne 1 = 1!.
b) V. Avec p ← 1, F1 multiplie par 1, 2, …, n : elle retourne n!, et 1 pour n = 0.
c) F. F2(x, 0) retourne x au lieu de $x^0 = 1$ (par exemple F2(2, 0) = 2).
d) F. Pour n ≥ 2, la boucle ne fait plus que n − 1 tours et donne $x^{n-1}$ : F4(2, 5) vaudrait 16 au lieu de 32.

4. Idée : le terme de rang k est $(-1)^k x^{2k}/(2k)!$ ; les m premiers termes correspondent à k = 0, …, m − 1 ; le signe alterne d'un terme au suivant.

Fonction CalculCos (x : Réel, m : Entier) : Réel
DEBUT
    s ← 0
    signe ← 1
    Pour k de 0 à m-1 Faire
        s ← s + signe * Puiss(x, 2*k)
                  / Fact(2*k)
        signe ← -signe
    Fin Pour
    Retourner s
FIN

Objet	Type/Nature	Rôle
s	Réel	somme partielle
signe	Entier	vaut 1 ou −1
k	Entier	rang du terme

Contrôle : pour m = 1 on obtient 1 ; pour m = 2, $1 - x^2/2$ . Pour x = 0,5 et m = 3, la somme vaut 337/384 ≈ 0,877604, proche de cos(0,5) ≈ 0,877583.

5. Idée : regarder quels arguments CalculCos passe réellement aux deux fonctions.

Le premier terme (k = 0) demande Puiss(x, 0) / Fact(0), qui devient F2(x, 0) / F3(0) = x / 0 : division par zéro, la fonction ne peut pas s'exécuter. Même avec la bonne Fact, F2 donnerait x comme premier terme au lieu de 1. Le développement de cos utilise les exposants 0, 2, 4, … : la valeur n = 0 est donc réellement demandée. Une somme n'utilisant que des exposants impairs, comme celle de sin(x), n'aurait jamais appelé F2 avec n = 0 ; c'est pourquoi on juge une version sur tout son domaine, et non sur un seul usage.

3 Drill RA-F.3 — cinq séquences pour un terme Uₙ : n à la place du rang, boucle qui démarre trop tard, registre jamais mis à jour

Entraînement 03 / 04

Drill RA-F.3 — cinq séquences pour un terme Uₙ : n à la place du rang, boucle qui démarre trop tard, registre jamais mis à jour

5 questionsCorrigé masqué

Soit la suite U définie par $U_0 = 2$ et $U_n = 3U_{n-1} - n$ pour tout entier naturel n ≥ 1.

Les cinq séquences suivantes prétendent calculer $U_n$ pour un entier n ≥ 0 déjà saisi ; le résultat est la valeur finale de u. t est un tableau d'entiers de taille suffisante ; u, v et i sont des entiers.

S1
t[0] ← 2
Pour i de 1 à n Faire
    t[i] ← 3 * t[i-1] - i
Fin Pour
u ← t[n]

S2
t[0] ← 2
Pour i de 1 à n Faire
    t[i] ← 3 * t[i-1] - n
Fin Pour
u ← t[n]

S3
u ← 2
Pour i de 2 à n Faire
    u ← 3 * u - i
Fin Pour

S4
v ← 2
Pour i de 1 à n Faire
    u ← 3 * v - i
Fin Pour

S5
v ← 2
Pour i de 1 à n Faire
    u ← 3 * v - i
    v ← u
Fin Pour
u ← v

Quel est l'ordre de récurrence de la suite U ? Calculer les premiers termes $U_1$ , $U_2$ , $U_3$ et $U_4$ .
Donner la valeur finale de u obtenue par chacune des cinq séquences pour n = 3.
Mettre V si la séquence calcule correctement $U_n$ pour tout entier n ≥ 0, F sinon.
Pour n = 1, les séquences S2 et S4 donnent la bonne valeur. Que peut-on en conclure ? Que contient u après S4 lorsque n = 0 ?
Valider par V ou F chacun des entêtes suivants pour une fonction qui retourne $U_n$ (n ≥ 0) :
1. Fonction Terme (n : Entier) : Réel
2. Fonction Terme (n : Réel) : Entier
3. Fonction Terme (n : Entier) : Entier
4. Fonction Terme (n : Réel) : Réel

Voir la correction commentéeAprès avoir posé votre démarche

1. $U_n$ ne dépend que de $U_{n-1}$ : suite récurrente d'ordre 1, une seule valeur initiale.

$U_1 = 3 \times 2 - 1 = 5$ ; $U_2 = 15 - 2 = 13$ ; $U_3 = 39 - 3 = 36$ ; $U_4 = 108 - 4 = 104$ .

2. Idée : tracer chaque séquence pour n = 3 et comparer avec $U_3 = 36$ .

Séquence	S1	S2	S3	S4	S5
u pour n = 3	36	15	9	3	36

S2 : t[1] = 6 − 3 = 3, t[2] = 9 − 3 = 6, t[3] = 18 − 3 = 15.
S3 : la boucle commence à i = 2 : u = 6 − 2 = 4, puis u = 12 − 3 = 9.
S4 : v reste égal à 2 ; seul le dernier tour compte : u = 6 − 3 = 3.

Séquence	S1	S2	S3	S4	S5
Réponse	V	F	F	F	V

S1 est correcte : chaque case t[i] se calcule à partir de t[i − 1] avec le rang i ; pour n = 0 aucun tour, u = t[0] = 2.
S2 soustrait n au lieu du rang i à chaque tour : elle n'est juste que pour n ≤ 1.
S3 saute le calcul de $U_1$ : pour n = 1 elle retourne 2 au lieu de 5.
S4 ne met jamais v à jour : chaque tour repart de $U_0$ et u vaut 6 − n.
S5 est correcte : v glisse d'un terme au suivant ; pour n = 0, u ← v donne 2.

4. Idée : une valeur juste ne valide pas une séquence ; une valeur fausse suffit à l'éliminer. Pour n = 1, soustraire n ou i revient au même et v vaut encore $U_0$ : S2 et S4 tombent juste par coïncidence. Dès n = 2, S2 donne 10 et S4 donne 4 au lieu de 13. Pour n = 0, S4 n'exécute aucun tour : u n'a jamais reçu de valeur, ce qui élimine aussi la proposition S4 pour ce cas.

5. a) F ; b) F ; c) V ; d) F. Le paramètre n est un rang, donc un entier (il sert de borne à la boucle Pour). Le résultat est entier, car chaque terme s'obtient par produit et différence d'entiers. Une relation contenant une division, comme $U_n = 1 + 1/U_{n-1}$ , imposerait au contraire un résultat réel.

4 Drill RA-F.4 — deux propositions, une seule équivalente : l'ordre de la concaténation, et le test qui ne départage rien

Entraînement 04 / 04

Drill RA-F.4 — deux propositions, une seule équivalente : l'ordre de la concaténation, et le test qui ne départage rien

5 questionsCorrigé masqué

Soit la fonction Double qui retourne l'entier obtenu en écrivant deux fois chacun des chiffres d'un entier strictement positif x, dans le même ordre. Exemple : Double(472) = 447722.

Fonction Double (x : Entier) : Entier
DEBUT
    s ← 0
    p ← 1
    Tant que (x ≠ 0) Faire
        r ← x mod 10
        s ← s + r * 11 * p
        p ← p * 100
        x ← x div 10
    Fin Tant que
    Retourner s
FIN

T.D.O.L : r, s et p sont des entiers.

On donne deux propositions d'algorithme d'une fonction Inconnue ; une seule est équivalente à la fonction Double. Dans les deux, ch et chx sont des chaînes.

Proposition A

Fonction Inconnue (x : Entier) : Entier
DEBUT
    ch ← Convch(x)
    chx ← ""
    Tant que (ch ≠ "") Faire
        chx ← ch[0] + ch[0] + chx
        ch ← Effacer(ch, 0, 1)
    Fin Tant que
    Retourner Valeur(chx)
FIN

Proposition B : identique à la proposition A, sauf l'instruction de concaténation, remplacée par chx ← chx + ch[0] + ch[0].

Dresser le tableau d'exécution de Double(305) : valeurs de r, s, p et x à la fin de chaque tour de la boucle, puis la valeur retournée.
Pour chaque proposition, donner le résultat de l'instruction Ecrire(Inconnue(5293)).
En déduire la proposition équivalente à la fonction Double.
Un élève n'a testé les deux propositions qu'avec x = 1221. Quels résultats a-t-il obtenus ? Pourquoi ce test ne permettait-il pas de conclure ? Pour quels entiers x les deux propositions donnent-elles le même résultat ?
Que retourne la proposition écartée pour x = 120 ? Et Double(120) ?

Voir la correction commentéeAprès avoir posé votre démarche

1. Idée : x mod 10 extrait le chiffre des unités, r * 11 l'écrit deux fois, et p avance de deux rangs (× 100) pour placer la paire suivante à gauche.

Tour	r	s	p	x
début	–	0	1	305
1	5	55	100	30
2	0	55	10000	3
3	3	330055	1000000	0

On retourne 330055. Au tour 2 la paire « 00 » n'ajoute rien à s, mais p est tout de même multiplié par 100 : c'est ce qui garde les deux zéros au milieu.

2. Idée : dans la proposition A, chaque paire est placée devant ce qui est déjà construit ; dans B, derrière.

	Proposition A	Proposition B
Résultat	33992255	55229933

A : chx prend successivement "55", "2255", "992255", "33992255". B : "55", "5522", "552299", "55229933".

3. Double(5293) = 55229933 : la proposition B est équivalente à Double. Ce résultat élimine la proposition A, qui double les chiffres mais les écrit aussi dans l'ordre inverse.

4. Idée : un test ne peut qu'éliminer ; il doit être choisi pour séparer les candidats. Pour x = 1221, les deux propositions affichent 11222211. Renverser un entier symétrique (qui se lit de la même façon dans les deux sens) ne le change pas : A et B donnent le même résultat exactement pour ces entiers-là. Il fallait tester un entier non symétrique, comme 5293.

5. La proposition A construit "11", puis "2211", puis "002211", et Valeur("002211") = 2211 : les zéros passés en tête sont perdus. Double(120) = 112200, ce que donne aussi la proposition B.

Relier ce raisonnement au bac

Choisis une filière pour voir les sujets qui étayent ce scénario.

Tu écris. Tu continues.

Où veux-tu aller ?

Reconnaissance d'algorithmes arithmétiques (produit, somme, Euclide)

Exercice — valider des propositions sur cinq algorithmes arithmétiques

Changer d’énoncé, garder le raisonnement

Exercices d'entraînement — une nuance à la fois

Lire une boucle avant de lui donner un nom

Drill RA-F.2 — cinq fonctions pour n! et xⁿ : l'initialisation p ← 0 et les versions qui ne se trompent qu'en n = 0

Drill RA-F.3 — cinq séquences pour un terme Uₙ : n à la place du rang, boucle qui démarre trop tard, registre jamais mis à jour

Drill RA-F.4 — deux propositions, une seule équivalente : l'ordre de la concaténation, et le test qui ne départage rien

Relier ce raisonnement au bac