Misez p'tit Optimisez n°93 : somme récursive des chiffres d'un entier (racine digitale)

[Danny]

Hello,

Je propose un petit sujet sympa qui n'a pas déjà été traité a priori :

Le calcul de la somme des chiffres composant un entier, de façon récursive jusqu'à n'obtenir plus qu'un chiffre.
Par exemple f(1337) = 5 , car 1 + 3 + 3 + 7 = 14 , puis 1 + 4 = 5.

Comme d'hab, essayez d'éviter de chercher sur les internets sinon vous allez vite trouver la méga astuce pour calculer ça super rapidement

(même ma Casio fx-3900P avec ses 100 pas peut le faire )


Sommaire des MPO

[cgh]

Hyper rapido, pas trop optimise non plus !
Pour HP41:

Code : Tout sélectionner

   01 LBL "SN"
   02 LBL 00
   03 STO 00
   04 LBL 01
   05 CLX
   06 STO 01
   07 LBL 02
   08 RCL 00
   09 X=0?
   10 GTO 03
   11 10
   12 /
   13 INT
   14 STO 00
   15 LASTX
   16 FRC
   17 10
   18 *
   19 ST+ 01
   20 GTO 02
   21 LBL 03
   22 9
   23 RCL 01
   24 X>Y?
   25 GTO 00
   26 END

Il suffit de faire NNNNNN dans X, XEQ SN, et X contient la somme des chiffres de l'entier sur 1 chiffre.

[cgh]

Une version sans registre (juste la pile) pour HP41. Meme mode operatoire que le programme precedent:

Code : Tout sélectionner

   01 LBL 01
   02 0
   03 X<>Y
   04 LBL 02
   05 X=0?
   06 GTO 00
   07 10
   08 /
   09 INT
   10 LASTX
   11 FRC
   12 10
   13 *
   14 ST+ Z
   15 RDN
   16 GTO 02
   17 LBL 00
   18 RDN
   19 LBL "SN"
   20 9
   21 X<>Y
   22 X>Y?
   23 GTO 01
   24 END

[Danny]

Méthode de bourrin, c’est un bon début

[C.Ret]

Le calcul de la somme des chiffres composant un entier, de façon récursive jusqu'à n'obtenir plus qu'un chiffre.
Par exemple f(1337) = 5 , car 1 + 3 + 3 + 7 = 14 , puis 1 + 4 = 5.

Sympa ce petit MPO, je n'ai pas besoin d'aller sur un quelconque Internet pour me souvenir du principe d'une preuve par neuf !
Je suis donc allé pomper sur le MPO n°9 qui a un sujet assez semblable.
Mais l'idée ici est d'être récursif. Je sors donc mon HP-28S.

Code : Tout sélectionner

SRdC: « → n « IF n 10 < THEN n  ELSE n MPO9 SRdC » » 

L'idée est que la somme des chiffres des nombres ne comprenant qu'un seul chiffre est justement ce nombre/chiffre.
La récurrence est que l'on utilise la méthode du MPO n°9 jusqu'à obtenir un nombre suffisamment petit

Per exemple, on peut prendre pour méthode du MPO n°9 le code que nous avait proposé Gilles59 le 22 octobre 2011 à 13:30 ou le code suivant que j'ai composé, à l'instant, en m'inspirant de celui que Gilles.59 proposait pour CASIO fx-602p :

Code : Tout sélectionner

MPO9: « CL∑ WHILE DUP REPEAT 10 MOD LAST ROT ∑+ / IP END DROP TOT »

On a alors 1337 SRdC qui renvoie bien 5 (et qui laisse une matrice '∑DAT' contenant [[ 4 ][ 1 ]] )

On peut aussi combiner les deux codes pour obtenir quelque chose de plus court, mais c'est alors une méthode itérative.

Code : Tout sélectionner

« DO CL∑ WHILE DUP REPEAT 10 MOD LAST ROT ∑+ / IP END DROP TOT UNTIL DUP 10 < END »

Evidemment, on peut aussi faire encore « bien BienBienBien » plus court avec une méthode algébrique. C'est prouvé ! Le seul problème est lorsque l'on obtient un résultat nul qu'il faut interpréter comme étant bien neuf. Mais c'est hors sujet

[cgh]

Nouvelle version optimisee... Je ne me souvenais plus que MOD etait disponible...

Code : Tout sélectionner

   01 LBL "SN"
   02 LBL 01
   03 0
   04 X<>Y
   05 LBL 02
   06 STO Z
   07 10
   08 MOD
   09 ST+ Y
   10 ST- Z
   11 RDN
   12 X<>Y
   13 LASTX
   14 /
   15 X#0?
   16 GTO 02
   17 9
   18 RCL Z
   19 X>Y?
   20 GTO 01
   21 END

En ligne 15 X#0? est X different 0?

[Danny]

Ah oui, je me disais aussi qu’il doit bien y avoir un MOD sur une HP-41

Bon pour l’instant personne ne triche, ça fait plaisir

[C.Ret]

Une version sans registre (juste la pile) pour HP41. Meme mode operatoire que le programme precedent:

C'est une bonne idée de n'utiliser que la pile. Ensuite, l'HP-41C connait l'instruction MOD (*), on peut donc comme sur l'HP-28S simplifier le code.
La notion de récurrence pose cependant problème. Les HP-41 ne supportent que 6 niveaux d'appel de sous-procédures.

Voici donc une version itérative :

Code : Tout sélectionner

01  LBL "SIdC"  0
03  LBL 01  ALOG  ALOG  x>y?  GTO 03  CLX
09  LBL 02  RCL Y  INT  x=0?  GTO 01  10  ST/ T  MOD  +  GTO 02
19  LBL 03  RDN  END

Utilisation 1337 [XEQ][alpha]SRdC[alpha] affiche 5,0000

On peut simplifier un peu en réorganisant la séquence. Ce qui en fait presque une méthode par récurrence, en fait récurrence de queue car l'appel se fait par la dernière instruction. J'ai donc remplacé XEQ "SRdC" RTN par un simple GTO "SRdC"

Code : Tout sélectionner

01  LBL "SRdC
02    0  X<>Y
04    LBL 01  STO Z  10  ST/ T  MOD  ST+ Y  X<> L  X<> Z  INT  x>0?  GTO 01
15    RDN  x>y?  GTO "SRdC
18  END

Dont la TRACE avec pour exemple 1337 donne bien le principe de fonctionnement et met en évidence l'appel récursif de "SRdC" en bas de la seconde page:

MPO93 HP41C Trace 1337.gif (102.44 Kio) Vu 11281 fois

(*) Le temps que je rédige et mon post a croisé les votres

[badaze]

Ca doit être faisable sur TI 57 LED en 33 pas. J’ai écrit le programme mais j’ai la flemme de le taper !

[Danny]

Dont la TRACE avec pour exemple 1337 donne bien le principe de fonctionnement et met en évidence l'appel récursif de "SRdC" en bas de la seconde page:
MPO93 HP41C Trace 1337.gif

Pas mal ta trace, c’est fait avec quoi ?

[C.Ret]

Avec mon imprimante. je mets mon HP-41C en mode TRACE et s'imprime sur le papier thermique chaque opération que je saisie ou chaque instruction d'un programme.

MPO93 HP82240A Trace of 1337 SRdC (part of).jpg (62.74 Kio) Vu 11269 fois

L'exécution avec 1337 produit alors un enregistrement papier qui fait bien 37 cm de long. Mais ça permet d'avoir sous les yeux tout le déroulement du code. C'est pratique pour les dé-buggages et mises au point.

Par contre, scanner les 37 cm de ruban c'est un peu fastidieux, j'ai donc recopier dans un bon traitement de texte (Excel en fait ) et y ajoutant les valeurs des registres T: Z: et Y: ainsi que le listing du programme. Sur le papier ne s'imprime que le contenu du registre X ou ALPHA, mes saisies et les instructions de la colonne Cmd:
Les fontes permettent d'avoir un bon rendu des différents éléments et indique où les trouver (fonte ROMAN pource qui est imprimé et fontes 14-segments pour ce qui s'affiche sur l'HP-41C. Le reste c'est du HP Simplified Light pour pas se prendre trop la tête.

[Danny]

Wow, je pensais que ça venait d’un émulateur

[badaze]

Pour la TI 57. A peine testé. Plante si j'ai des nombres de plus de 6 chiffres. Admirez la TI 57. Peu sont aussi pimpantes au bout de 40 ans !



EDIT : Oopps. J’ai oublié RCL 0 après le second xy.

[Marge]

[Ythunder]

C'est quel langage ce code ?