Écrire des algorithmes sur les multiples et les diviseurs - Exercice 2

15 min
25
Sans utiliser l'opérateur %, on propose la fonction suivante, où aa et bb sont des entiers naturels et bb n'est pas nul.
Question 1

On exécute est_multiple2(23, 5). Recopier et compléter le tableau d'état de la variable a ci-dessous, puis donner la valeur renvoyée.

Correction
À chaque passage dans la boucle, on enlève 55 à a, tant que a est supérieur ou égal à 55 : a vaut successivement 2323 , 1818 , 1313 , 88 et 33 .
Comme 3<53\lt 5 , la boucle s'arrête. La fonction renvoie la valeur du test 3 == 0, qui est faux.
est_multiple2(23, 5) renvoie False : 2323 n'est pas un multiple de 55 , car 23=5×4+323=5\times 4+3 .
Question 2

Même question pour est_multiple2(35, 7).

Correction
a vaut successivement 3535 , 2828 , 2121 , 1414 , 77 , puis 00 . Comme 0<70\lt 7 , la boucle s'arrête après 55 passages, et le test 0 == 0 est vrai.
est_multiple2(35, 7) renvoie True : 35=7×535=7\times 5 .
Question 3

Expliquer pourquoi cette fonction répond bien à la question « aa est-il un multiple de bb ? ».

Correction
  • Effectuer la division euclidienne de l'entier naturel aa par l'entier naturel non nul bb, c'est écrire a=b×q+ra=b\times q+r, où le quotient qq et le reste rr sont des entiers naturels, avec 0≤r<b0\leq r\lt b.
  • aa est un multiple de bb si et seulement si le reste rr est nul.
Notons a=b×q+ra=b\times q+r , avec 0≤r<b0\leq r\lt b , la division euclidienne de aa par bb .
La boucle enlève bb à a tant que le résultat reste positif ou nul : elle l'enlève exactement qq fois, et il reste rr , qui est strictement inférieur à bb . Dans l'exemple de la question 1 : 23=5×4+323=5\times 4+3 , il y a 44 passages et il reste 33 .
La valeur de a à la fin de la boucle est donc le reste de la division euclidienne de aa par bb .
La fonction renvoie True exactement lorsque ce reste est nul, c'est-à-dire lorsque aa est un multiple de bb .

Signaler une erreur

Aide-nous à améliorer nos contenus en signalant les erreurs ou problèmes que tu penses avoir trouvés.

Connecte-toi ou crée un compte pour signaler une erreur.