RA-EAlgorithmes récurrents et arithmétiques

Comptage des chiffres d'un entier (trace + rôle + conversion)

Idée directrice

Forme calquée sur l'exercice 2 de 2019 : séquence Tant que (x Div 10 ≠ 0), trace pour trois valeurs, rôle (nombre de chiffres en base décimale), puis séquence équivalente par conversion Convch + Long. C'est l'exercice court arithmétique attesté ; pas un problème modulaire.

Ce qui aide à reconnaître la démarche

« Compléter le tableau nb pour x ∈ {5403, 176, 3} » ; « Donner le rôle (nombre de chiffres) » ; « séquence équivalente sans structure itérative (Convch + Long) »

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

Relancer la séquence à part pour chaque valeur de x (ne pas enchaîner les trois sur la même variable).
Le cas x < 10 fixe nb = 1 sans entrer dans la boucle.
Équivalent non itératif officiel 2019 : Convch puis Long.

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

Compter une itération de trop pour les puissances de 10 ; écrire x MOD 10 au lieu de x Div 10 ; oublier que pour x = 3 on a nb = 1.

Sujet principal

Exercice — nombre de chiffres d'un entier

3 questionsCorrigé masqué

Soit x un entier naturel écrit en base décimale. On exécute la séquence algorithmique suivante :

nb ← 1
Tant que (x Div 10 ≠ 0) faire
   nb ← nb + 1
   x ← x Div 10
Fin tant que

Pour chacune des valeurs de x parmi 5403, 176 et 3, indiquer la valeur finale de nb après exécution de la séquence (en repartant à chaque fois de la valeur initiale de x).
Donner le rôle de cette séquence.
Écrire une séquence algorithmique équivalente sans boucle, en utilisant la conversion de l'entier décimal en chaîne de caractères (Convch) puis Long.

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

1. Valeurs finales de nb

x	nb
5403	4
176	3
3	1

Trace sommaire pour x = 5403 : nb=1 puis divisions successives 5403 → 540 → 54 → 5 ; à chaque quotient non nul on incrémente nb, d'où nb = 4. Pour x = 3, 3 Div 10 = 0 dès le test : la boucle ne s'exécute pas, nb reste 1.

2. Rôle. Cette séquence permet de déterminer le nombre de chiffres d'un entier x donné (écriture en base décimale).

3. Séquence équivalente sans boucle

Convch(x, xch)
nb ← Long(xch)

On convertit l'entier en chaîne, puis on prend la longueur de cette chaîne : c'est le nombre de chiffres. Toute solution correcte fondée sur la même idée de conversion est acceptable.

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 Transfert — deux séquences pour compter les chiffres d'un entier : celle qui se trompe sur zéro

Entraînement 01 / 01

Transfert — deux séquences pour compter les chiffres d'un entier : celle qui se trompe sur zéro

4 questionsCorrigé masquéEn cours de relecture

Soit x un entier naturel écrit en base décimale. Pour compter ses chiffres, deux séquences algorithmiques sont proposées ; Div désigne le quotient de la division entière.

{ Séquence 1 }                     { Séquence 2 }
nb ← 1                             nb ← 0
Tant que (x Div 10 ≠ 0) faire      Tant que (x ≠ 0) faire
   nb ← nb + 1                        nb ← nb + 1
   x ← x Div 10                       x ← x Div 10
Fin tant que                       Fin tant que

Compléter, pour chaque séquence, le tableau d'exécution donnant les valeurs successives de x et de nb pour x = 1000, puis la valeur finale de nb pour chacune des valeurs 0, 9, 10 et 1000 (on repart à chaque fois de la valeur initiale de x).
Les deux séquences ont-elles le même rôle ? Préciser pour quelle valeur de x elles diffèrent et laquelle donne le nombre de chiffres correct dans ce cas ; justifier à partir du test de la boucle.
Corriger la séquence 2 en ne changeant que sa structure itérative, sans ajouter de test conditionnel Si, pour qu'elle donne le résultat correct sur tous les entiers naturels.
Écrire une séquence équivalente à la séquence 1 sans structure itérative, par conversion de l'entier en chaîne de caractères (Convch) puis utilisation de Long. Expliquer pourquoi cette version est en accord avec la séquence 1, et non avec la séquence 2, pour x = 0.

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

1. Idée : dérouler chaque boucle en écrivant le test avant chaque tour.

Séquence 1 pour x = 1000 : nb = 1 ; 1000 Div 10 = 100 ≠ 0 → nb = 2, x = 100 ; 100 Div 10 = 10 ≠ 0 → nb = 3, x = 10 ; 10 Div 10 = 1 ≠ 0 → nb = 4, x = 1 ; 1 Div 10 = 0 → arrêt.

`x`	1000	100	10	1
`nb` (séq. 1)	1	2	3	4

Séquence 2 pour x = 1000 : nb = 0 ; 1000 ≠ 0 → nb = 1, x = 100 ; → nb = 2, x = 10 ; → nb = 3, x = 1 ; 1 ≠ 0 → nb = 4, x = 0 ; 0 ≠ 0 faux → arrêt.

`x`	1000	100	10	1	0
`nb` (séq. 2)	0	1	2	3	4

Valeur finale de la variable nb pour chaque x :

`x`	0	9	10	1000
`nb` séquence 1	1	1	2	4
`nb` séquence 2	0	1	2	4

2. Idée : le rôle se lit sur la valeur retournée ; un seul contre-exemple suffit à séparer les deux séquences.

Sur 9, 10 et 1000, les deux séquences retournent le nombre de chiffres de x. Elles diffèrent pour x = 0 : la séquence 1 retourne 1, la séquence 2 retourne 0. L'écriture décimale de zéro comporte un chiffre, donc seule la séquence 1 a le rôle attendu : cette séquence permet de déterminer le nombre de chiffres d'un entier naturel x quel qu'il soit, zéro compris. La raison est dans le test : la séquence 1 part de nb = 1 (tout entier a au moins un chiffre) et ne compte que les chiffres supplémentaires, révélés par un quotient non nul ; la séquence 2 part de nb = 0 et compte un chiffre par tour de boucle, mais avec x = 0 le test x ≠ 0 est faux dès le départ : aucun tour, aucun chiffre compté. La séquence 2 compte le nombre de divisions nécessaires pour annuler x, ce qui coïncide avec le nombre de chiffres seulement si x ≠ 0.

3. Idée : pour compter au moins un chiffre, il faut une boucle qui exécute son corps avant de tester.

nb ← 0
Répéter
   nb ← nb + 1
   x ← x Div 10
Jusqu'à (x = 0)

La boucle Répéter … Jusqu'à effectue au moins un tour : pour x = 0, un tour donne nb = 1 et x = 0 Div 10 = 0, arrêt, résultat 1. Pour x = 1000, quatre tours (x : 100, 10, 1, 0) donnent nb = 4. Cette version retourne le nombre de chiffres pour tout entier naturel, sans test Si.

4. Idée : la longueur de l'écriture décimale est le nombre de chiffres, y compris pour zéro.

Convch(x, xch)
nb ← Long(xch)

On convertit l'entier en une chaîne de caractères puis on prend sa longueur. Pour x = 0, Convch produit la chaîne "0", qui contient un caractère : nb = 1, comme la séquence 1. Pour x = 1000, la chaîne "1000" a quatre caractères : nb = 4. Cette séquence sans boucle est donc équivalente à la séquence 1 sur tous les entiers naturels ; elle n'est pas équivalente à la séquence 2, qui rend 0 pour x = 0. Deux séquences ne sont « équivalentes » que si elles retournent la même valeur pour toutes les données autorisées, pas seulement pour les exemples de la trace.

Relier ce raisonnement au bac

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

Tu écris. Tu continues.