Nombres harshad (version récursive)⚓︎
On s'interdit dans cet exercice d'utiliser
stretsum
Un entier naturel non nul \(n\) est dit harshad, si \(n\) est divisible par la somme des chiffres de \(n\) . Le nom de harshad a été donné par le mathématicien Dattatreya Ramachandra Kaprekar (1905 - 1986), il signifie "grande joie" en sanskrit.
On précise qu'un nombre entier \(b\) est un "diviseur" de \(a\) si le reste de la division euclidienne de \(a\) par \(b\) vaut \(0\).
Par exemple \(18\) est un nombre harshad car \(1+8\) divise \(18\). En effet \(18 =2\times (1+8)+0\).
Vous devez écrire une fonction harshad(n) prenant en argument un nombre entier positif n et vérifiant que c'est un nombre harshad. La fonction renverra True ou False selon les cas.
Il vous faudra tout d'abord écrire une fonction récursive somme_chiffres(n) calculant la somme des chiffres de l'entier positif n. On n'utilisera que des opérations mathématiques. On s'interdira donc de convertir n en une chaîne de caractères.
Exemple
>>> somme_chiffres(8)
8
>>> somme_chiffres(18)
9
>>> somme_chiffres(409)
13
>>> harshad(18)
True
>>> harshad(72)
True
>>> harshad(11)
False
Avec Python, on rappelle qu'il est possible de calculer le quotient d'un nombre n par 10 en faisant n // 10.
De même, n % 10 renvoie le reste de la division euclidienne de n par 10.
Exemple
>>> 409 % 10
9
>>> 409 // 10
40
>>> 40 % 10
0
>>> 40 // 10
4
def sommepy-undchiffres(n):bksl-nl if ...:bksl-nl ...bksl-nl else:bksl-nl ...bksl-nlbksl-nlbksl-nldef harshad(n):bksl-nl assert n > 0bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert sommepy-undchiffres(8) == 8bksl-nlassert sommepy-undchiffres(18) == 9bksl-nlassert sommepy-undchiffres(409) == 13bksl-nlassert harshad(18)bksl-nlassert harshad(72)bksl-nlassert harshad(11)bksl-nlbksl-nldef sommepy-undchiffres(n):bksl-nl if n == 0:bksl-nl return 0bksl-nl else:bksl-nl return n % 10 + sommepy-undchiffres(n // 10)bksl-nlbksl-nlbksl-nldef harshad(n):bksl-nl return n % sommepy-undchiffres(n) == 0bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert sommepy-undchiffres(8) == 8bksl-nlassert sommepy-undchiffres(18) == 9bksl-nlassert sommepy-undchiffres(409) == 13bksl-nlassert harshad(18)bksl-nlassert harshad(72)bksl-nlassert not harshad(11)bksl-nlbksl-nl
A
Commentaires⚓︎
{{ IDE('exo_corr') }}
Prenons un exemple : afin de calculer la somme des chiffres de \(409\) on doit additionner le chiffre des unités \(9\), celui des dizaines \(0\) et celui des centaines \(4\).
Le chiffre des unités vaut \(9\). C'est le reste de la division de \(409\) par \(10\). On l'obtient en Python en faisant 409 % 10.
Ce calcul effectué, on calcule le quotient de \(409\) par \(10\) : on obtient \(40\). On l'obtient en Python en faisant 409 // 10.
On peut alors recommencer la démarche (reste de la division suivie de quotient) jusqu'à ce que le quotient soit nul.
| Etape | Valeur de \(n\) | Reste de la division par \(10\) | Quotient de la division par \(10\) |
|---|---|---|---|
| 1 | \(409\) | \(9\) | \(40\) |
| 2 | \(40\) | \(0\) | \(40\) |
| 3 | \(4\) | \(4\) | \(0\) |
Le fonction somme_chiffres est récursive. Le cas de base est atteint lorsque l'argument n est nul. On renvoie alors 0.
Dans les autres cas (n strictement positif), on renvoie le chiffre des unités de n additionnés à la somme des chiffres du quotient de n par 10.
Pour \(409\) on fait donc :
La fonction harshad est simple : on se contente de tester si le reste de la division de n par somme_chiffres(n) est égal à 0. Si oui, le nombre est harshad, si non il ne l'est pas.
Z