Critère de divisibilité par 3⚓︎
Divisibilité par 3
Un entier est divisible par 3 si la somme de ses chiffres est elle-même divisible par 3.
On peut donc utiliser un algorithme récursif.
- Les cas de base sont les entiers à 1 chiffre.
- On pourra utiliser la fonction
somme_chiffrevu précédemment pour le cas général.
Exercice
Donnez une fonction récursive est_divisible_par_3 qui détermine si un entier n est divisible par \(3\).
def sommepy-undchiffres(n):bksl-nl """Renvoie la somme des chiffres de l'entier positif n"""bksl-nl if n < 10:bksl-nl return nbksl-nl else:bksl-nl return sommepy-undchiffres(n // 10) + (n % 10)bksl-nlbksl-nldef estpy-unddivisiblepy-undparpy-und3(n):bksl-nl """Détermine si n est divisible par 3"""bksl-nl ... # ← à compléterbksl-nlbksl-nlbksl-nlassert estpy-unddivisiblepy-undparpy-und3(6) == Truebksl-nlassert estpy-unddivisiblepy-undparpy-und3(7) == Falsebksl-nlassert estpy-unddivisiblepy-undparpy-und3(516) == Truebksl-nlassert estpy-unddivisiblepy-undparpy-und3(567898765) == Falsebksl-nlbksl-nl
Réponse
def est_divisible_par_3(n):
"""Détermine si n est divisible par 3"""
cas_base = [True, False, False] * 4
if n < 12:
return cas_base[n]
else:
return est_divisible_par_3(somme_chiffres(n))
On a étendu à 12 cas de base, avec un tableau codé en dur, qui n'est calculé qu'une seule fois à la création de la fonction.
On aurait pu écrire aussi
def est_divisible_par_3(n):
"""Détermine si n est divisible par 3"""
if n < 10:
return n in [0, 3, 6, 9]
else:
return est_divisible_par_3(somme_chiffres(n))
La première version est légèrement plus rapide ; la seconde plus facile à lire.
Les deux styles se défendent.
Divisibilité par 9
Un entier est divisible par 9 si la somme de ses chiffres est elle-même divisible par 9.
On pourra donc construire un algorithme similaire.