← Toutes les ressources pour les enseignants

Imprimer la fiche de l’élève Voir le corrigé

Corrigé pour l’enseignant

Des algorithmes avec un état

Recueillez quatre types d’indices : prédiction de l’état pertinent ; comportement dans des cas variés, y compris aux limites ; explication fondée sur la trace et l’état ; correction justifiée d’un écart. Évaluez chacun comme en développement, avec soutien ou autonome, sur papier ou selon la procédure approuvée de votre école. Réussir un défi prouve un comportement de la machine, pas la paternité du code ni une maîtrise complète. Acceptez les programmes équivalents corrects : le corrigé public est un modèle, pas l’unique réponse possible.

Matériel pédagogique public. Les solutions sont des exemples ; des programmes équivalents corrects peuvent aussi réussir les vérifications réelles.

16. Factorielle et invariants de boucle

Utilisez un accumulateur multiplicatif et expliquez pourquoi 0! vaut 1.

Ouvrir cette leçon →

1. Prévoir et tracer

Avant d’exécuter le programme d’essai, prévoyez sa sortie et tracez les trois premières instructions exécutées. Suivez les registres, les indicateurs ou la mémoire pertinents, selon le besoin. Avancez ensuite pas à pas pour comparer.

LOAD 4 R1
LOAD 1 R2
LOOP 4
LOAD R2
MUL R1
COPY R0 R2
LOAD R1
SUB 1
COPY R0 R1
RETURN
LOAD R2
PRINT
HALT

Ajouter les entrées à la file: Aucune

Initialiser la mémoire: Tous les octets sont initialement nuls

Corrigé de la prédiction d’essai

Sortie: 24

Instruction	PC avant	PC après	État pertinent	Sortie
LOAD	0	1	`{"registers":[0,4,0,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[]}`	Aucune
LOAD	1	2	`{"registers":[0,4,1,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[]}`	Aucune
LOOP	2	3	`{"registers":[0,4,1,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[{"start":2,"end":9,"remaining":4,"callDepth":0}],"memoryReads":[],"memoryWrites":[]}`	Aucune

2. Construire et vérifier

Lisez N de 0 à 6 et affichez N!. Utilisez une boucle et un accumulateur de multiplication.

Types d’instructions requis: INPUT, LOOP, MUL

Exemple de solution du défi

INPUT
COPY R0 R1
COPY R0 R3
LOAD 1 R2
LOOP R3
LOAD R2
MUL R1
COPY R0 R2
LOAD R1
SUB 1
COPY R0 R1
RETURN
LOAD R2
PRINT
HALT

Cas réels du vérificateur

Cas 1

Entrée: 0
Mémoire initiale: Tous les octets sont initialement nuls
Sortie attendue: 1

Cas 2

Entrée: 4
Mémoire initiale: Tous les octets sont initialement nuls
Sortie attendue: 24

Cas 3

Entrée: 6
Mémoire initiale: Tous les octets sont initialement nuls
Sortie attendue: 720

3. Expliquer la machine

Pourquoi l’accumulateur de produit commence-t-il à 1 ?

Raisonnement et note pédagogique

1 est l’élément neutre de la multiplication ; zéro itération donne 0! = 1. Commencer à 0 rendrait tous les produits nuls.

17. La suite de Fibonacci

Conservez deux valeurs précédentes et actualisez-les dans un ordre sûr.

Ouvrir cette leçon →

1. Prévoir et tracer

LOAD 1 R1
LOAD 1 R2
LOOP 8
LOAD R1
PRINT
ADD R2
COPY R2 R1
COPY R0 R2
RETURN
HALT

Ajouter les entrées à la file: Aucune

Initialiser la mémoire: Tous les octets sont initialement nuls

Corrigé de la prédiction d’essai

Sortie: 1, 1, 2, 3, 5, 8, 13, 21

Instruction	PC avant	PC après	État pertinent	Sortie
LOAD	0	1	`{"registers":[0,1,0,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[]}`	Aucune
LOAD	1	2	`{"registers":[0,1,1,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[]}`	Aucune
LOOP	2	3	`{"registers":[0,1,1,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[{"start":2,"end":8,"remaining":8,"callDepth":0}],"memoryReads":[],"memoryWrites":[]}`	Aucune

2. Construire et vérifier

Lisez N de 0 à 8. Affichez les N premières valeurs de Fibonacci en commençant par 1, 1. N’affichez rien pour N = 0.

Types d’instructions requis: INPUT, LOOP, ADD, COPY

Exemple de solution du défi

INPUT
COPY R0 R4
LOAD 1 R1
LOAD 1 R2
LOOP R4
LOAD R1
PRINT
ADD R2
COPY R2 R1
COPY R0 R2
RETURN
HALT

Cas réels du vérificateur

Cas 1

Entrée: 0
Mémoire initiale: Tous les octets sont initialement nuls
Sortie attendue: Aucune

Cas 2

Entrée: 1
Mémoire initiale: Tous les octets sont initialement nuls
Sortie attendue: 1

Cas 3

Entrée: 6
Mémoire initiale: Tous les octets sont initialement nuls
Sortie attendue: 1, 1, 2, 3, 5, 8

Cas 4

Entrée: 8
Mémoire initiale: Tous les octets sont initialement nuls
Sortie attendue: 1, 1, 2, 3, 5, 8, 13, 21

3. Expliquer la machine

Pourquoi remplacer trop tôt la première valeur précédente peut-il casser Fibonacci ?

Raisonnement et note pédagogique

Cela perd un opérande encore nécessaire ; préservez un résultat temporaire encore utile avant de déplacer la paire. Le départ correct est 1, 1.

18. Inverser un tampon mémoire

Copiez un tampon à l’envers avec des pointeurs source et destination.

Ouvrir cette leçon →

1. Prévoir et tracer

STORE 1 0
STORE 2 1
STORE 3 2
STORE 4 3
LOAD 3 R1
LOAD 16 R2
LOOP 4
LOAD [R1]
STORE R2
LOAD R1
SUB 1
COPY R0 R1
LOAD R2
ADD 1
COPY R0 R2
RETURN
HALT

Ajouter les entrées à la file: Aucune

Initialiser la mémoire: 0: 1, 1: 2, 2: 3, 3: 4

Corrigé de la prédiction d’essai

Sortie: Aucune

Instruction	PC avant	PC après	État pertinent	Sortie
STORE	0	1	`{"registers":[0,0,0,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[0]}`	Aucune
STORE	1	2	`{"registers":[0,0,0,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[1]}`	Aucune
STORE	2	3	`{"registers":[0,0,0,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[2]}`	Aucune

2. Construire et vérifier

Quatre octets sont préparés aux adresses 0 à 3. Copiez-les à l’envers aux adresses 16 à 19 sans modifier les originaux. Utilisez une boucle et des adresses dans les registres ; aucune sortie n’est requise.

Types d’instructions requis: LOOP, LOAD, STORE

Exemple de solution du défi

LOAD 3 R1
LOAD 16 R2
LOOP 4
LOAD [R1]
STORE R2
LOAD R1
SUB 1
COPY R0 R1
LOAD R2
ADD 1
COPY R0 R2
RETURN
HALT

Cas réels du vérificateur

Cas 1

Entrée: Aucune
Mémoire initiale: 0: 1, 1: 2, 2: 3, 3: 4
Sortie attendue: Aucune
Mémoire finale attendue: 0: 1, 1: 2, 2: 3, 3: 4, 16: 4, 17: 3, 18: 2, 19: 1
Lectures mémoire requises: 0, 1, 2, 3

Cas 2

Entrée: Aucune
Mémoire initiale: 0: 8, 1: 0, 2: 255, 3: 2
Sortie attendue: Aucune
Mémoire finale attendue: 0: 8, 1: 0, 2: 255, 3: 2, 16: 2, 17: 255, 18: 0, 19: 8
Lectures mémoire requises: 0, 1, 2, 3

Cas 3

Entrée: Aucune
Mémoire initiale: 0: 7, 1: 7, 2: 9, 3: 9
Sortie attendue: Aucune
Mémoire finale attendue: 0: 7, 1: 7, 2: 9, 3: 9, 16: 9, 17: 9, 18: 7, 19: 7
Lectures mémoire requises: 0, 1, 2, 3

3. Expliquer la machine

S’agit-il d’une inversion sur place ? Que faut-il garder inchangé ?

Raisonnement et note pédagogique

Non : la source 0 à 3 est copiée à l’envers vers 16 à 19. La source reste 1, 2, 3, 4 ; la destination devient 4, 3, 2, 1.