Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Ici, on fait dans le petit, le LCD qui déchire sa race, on y cause même calculatrices quand on est en manque !

Modérateur : Politburo

Répondre
Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1860
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par C.Ret » 20 août 2018 21:42

Cela n'a l'air de rien…

Au premier coup d'œil, cela parait facile...

Mais, il n'en est rien…

J'ai trouvé pour vous un algorithme simple à expliquer… un algorithme qui ne manipule que des nombres entiers … mais qui va mettre à rude épreuve vos capacités à programmer et maitriser vos Calculettes ou Pockets préférés.

Surtout quand il va s'agir d'optimiser et minimiser tout cela.

L'Algorithme de Kaprekar est en réalité très simple, c'est plus un jeu qu'une transformation mathématiques (quoique ?), il réalise une transformation très simple d'un nombre en un autre et peut ainsi se répéter indéfiniment tout en ne manipulant toujours que des nombres entiers et n'utilisant qu'une opération mathématique simple (une sous traction) et un nombre très limité d'étapes dans son déroulement.

Peu d'étapes, des nombres (entier de surcroît), se répétant comme une suite à partir d'un unique argument, …
voilà quelque chose qui convient parfaitement à nos Calculettes, Pockets, ordinosaures ou programmables préférés, …
même aux plus vénérables ...


Il est tellement simple que l'Algorithme de Kaprekar peut être réalisé sur des nombres entiers en base décimale (base naturelle), mais aussi et sans complication ou amendement dans n'importe quelle autre base (binaire,octal, hexadécimal, quelconque b, …)

Pour ne pas nous embrouiller, nous nous contenteront d'appliquer cet excellant algorithme uniquement sur des nombres en base 10. Cela est bien suffisant. Cela évitera de nous fâcher. De plus, cela est compatible avec la très grande majorité des systèmes en nos possessions.

Bon, si certains d'entre vous, dont je connais l'esprit pervers et facessieux, auront besoin, pour implémenter cet algorithme, d'utiliser des ruses, des gruges, ou des chemins scabreux et détournés en exploitant transitoirement d'autres bases… Je les laisse libres de leurs choix, si cela permet de mieux faire… Mais les nombres initiaux utilisés en entrée ou produits en sorties finales ne devrons être qu'en base 10.

Mais je me fais du souci pour rien; l'Algorithme de Kaprekar est si simple que personne, oui vraiment personne, ne songera à empreinter de tels sentiers...


En effet, le but de ce M.P.O. est de produire le code le plus adapté, petit et optimiser pour votre (ou vos) calculatrice(s) ou pocket(s) préféré((e)s) qui permet d'appliquer l'Algorithme de Kaprekar décrit ci-dessous à un nombre donné et d'en afficher (ou imprimer) le résultat de la transformation. Puis, de facilement répéter ce processus en appliquant à nouveau l'Algorithme de Kaprekar sur ce nouveau nombre et ainsi de suite sous l'impulsion de l'utilisateur.

Evidemment, le choix du mode de saisie du nombre et du lancement de l'algorithme de transformation devra être indiqué et adapté à chaque système. L'idéal étant de ne pas avoir à re-saisir les nombres à chaque itération ou re-charger tout le programme à chaque itération.
Enfin, vous comprenez, j'espère, l'itération devra être relancée par un truc simple et efficace, une pression sur R/S, CONT, ENTER ou autre Lbl ou DEF, … ou je ne sais quel bouton ou partie de l'interface homme-machine... Le tout est de bien nous indiquer le procédé qui pourra être spécifique à chaque système mais devra être optimisé et bien pensé.


Vous allez vite voir que nous allons nous chamailler sur d'autres sujets. Car au sein de l'Algorithme de Kaprekar se cache un alien, un vice profond, une source d'ennuis, un Râhu indou, un monstre énorme et tordu, une mission impossible ?

Mais, j'en suis sûr, vous allez me démontrer que je me trompe, et qu'avant septembre, un code MPOïsé existera dans ce fils pour toutes les CASIO, SHARP, HP ou TI et autres Silicium ...



L’Algorithme de Kaprekar transforme un nombre entier en un autre. Il fut découvert en 1949 par le mathématicien indien Dattatreya Ramachandra Kaprekar pour les nombres de quatre chiffres, mais il peut être généralisé à tous les nombres.

Votre code devra donc être particulièrement efficace pour les nombres de quatre chiffres, mais devra être fonctionnel sur des nombres plus petits ou plus grands sans dépasser 10 chiffres cependant.
Il y aura donc deux catégories de codes :
Les codes de Catégorie A qui fonctionnent très bien avec des nombres de 1 à 10 chiffres
Les codes de Catégorie 4 qui fonctionnent exclusivement avec des nombres entiers de 4 chiffres
Tous les codes qui ne pourront être rattachés à l'une ou l'autre de ces deux catégories seront dit 'Hors-Catégorie' ou 'OFF' comme aux festivales.


Votre mission: implémenter de façon optimisée et efficace l'Algorithme de Kaprekar qui se définit comme suit :

L’algorithme de Kaprekar consiste à associer à un nombre quelconque n un autre nombre K(n) généré de la façon suivante :
  1. on considère un nombre entier n, écrit en base 10 ;
  2. on forme le nombre c en arrangeant les chiffres du nombre n dans l’ordre croissant
    et le nombre d en les arrangeant dans l’ordre décroissant ;
  3. on calcule K(n) = d – c et on affiche ou imprime ce résultat (en base 10);
  4. on itère ensuite le processus avec K(n) sous l'impulsion déclenchée par l'utilisateur.


Exemples:

Code : Tout sélectionner

En partant du nombre 5294 , on obtient successivement:
 K(5294) = 9542 - 2459 = 7083.
 K(7083) = 8730 -  378 = 8352.
 K(8352) = 8532 - 2358 = 6174.
 K(6174) = 7641 - 1467 = 6174 et ainsi de suite.

Code : Tout sélectionner

Si on commence avec 634, on obtient successivement 297, 693, 594, 495, 495, etc.
On obtient là aussi un nombre qui ne varie plus.

EDIT:
Avec 52, la séquence est la suivante : 52, 27, 45, 09, 81, 63, 27…

L'exemple ci-dessus est un mauvais exemple et ne correspond pas à l'algorithme demandé. En effet, 09 n'est pas un nombre à deux chiffres, c'est au mieux un vecteur à deux éléments ou une chaine de caractères. La séquence convenable devient :

Code : Tout sélectionner

Avec 52, la séquence est la suivante : 52, 27, 45, 9, 0, 0, 0… 

Préparez vite vos codes, nous allons débusquer tous les Râhu et faire d'étranges découvertes…
Dernière édition par C.Ret le 21 août 2018 06:42, édité 3 fois.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-15C | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator . .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2662
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par bernouilli92 » 20 août 2018 23:14

Voici une première version pour hp48g(x) :

Code : Tout sélectionner

M85: 
« 
  DUP LOG IP 1 + {}
  1 ROT
  START 
    OVER 10 MOD + SWAP 10 / IP SWAP
  NEXT 
  SWAP DROP
  SORT DUP 
  LIST→ 2
  START 
    10 * + 
  -1 STEP 
  SWAP REVLIST LIST→ 2
  START 
    10 * +
  -1 STEP 
  -
»
Taille : 155,5 octets
Pour l'utiliser : mettre un nombre N dans la pile et lancer M85 qui remplace le nombre N par K(N).
Fonctionne avec les nombres de 2 à 10 chiffres. Du coup pour l'instant il est hors catégorie.

Édit :
Voici une version corrigée qui fonctionne avec les nombres de 1 à 10 chiffres :

Code : Tout sélectionner

«
  IF DUP 0 >
  THEN 
    DUP XPON 1 + {} 1 ROT
    START 
      OVER 10 MOD + SWAP 10 / IP SWAP
    NEXT 
    SWAP DROP SORT
    IF DUP SIZE 1 >
    THEN 
      DUP LIST→ 2
      START
        10 * +
      -1 STEP 
      SWAP REVLIST LIST→ 2
      START 
        10 * +
      -1 STEP 
      -
    ELSE 
      DROP 0
    END
  END
»
Cette version fait 208 octets.
utiliser XPON à la place de LOG IP fait économiser 2,5 octets.
Dernière édition par bernouilli92 le 21 août 2018 15:18, édité 5 fois.
HP, Casio, Sharp, Psion, quelques TI et divers autres

Avatar de l’utilisateur
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2418
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par zpalm » 20 août 2018 23:43

bernouilli92 a écrit :
20 août 2018 23:14
Voici une première version pour hp48g(x) :
Bien vu. Mais ça ne marche pas quand on part de 52.... C'est le Râhu de C. Ret sur lequel je butte: K(9) n'est pas égal à K(09)!

Ma solution actuelle sur HP Prime, en une ligne ce qui permet de définir une fonction utilisateur sans passer par un programme (compatible avec l'application Prime gratuite) mais avec le même défaut:

Code : Tout sélectionner

EXPR(CHAR(REVERSE(SORT(ASC(STRING(Ans,1)))))+"-"+CHAR(SORT(ASC(STRING(Ans,1)))))
Dernière édition par zpalm le 20 août 2018 23:48, édité 1 fois.

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2662
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par bernouilli92 » 20 août 2018 23:47

K(09) n'existe pas. K(9) donne 0.
La fonction donne un résultat pour un entier donné. Peu importe les calculs qu'on a pu faire avant.

J'ai corrigé ma version. Elle fonctionne maintenant avec 52.
HP, Casio, Sharp, Psion, quelques TI et divers autres

Avatar de l’utilisateur
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2418
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par zpalm » 20 août 2018 23:51

bernouilli92 a écrit :
20 août 2018 23:47
K(09) n'existe pas. K(9) donne 0.
La fonction donne un résultat pour un entier donné. Peu importe les calculs qu'on a pu faire avant.

J'ai corrigé ma version. Elle fonctionne maintenant avec 52.
Tu obtiens cette séquence ?
C.Ret a écrit :
20 août 2018 21:42

Code : Tout sélectionner

Avec 52, la séquence est la suivante : 52, 27, 45, 09, 81, 63, 27… 

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2662
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par bernouilli92 » 20 août 2018 23:56

Non. Je n'obtiens pas cette séquence. Il y a une erreur dans le MPO. Ou alors il doit revoir son énoncé.

Édit : je n'ai rien dit. L'algorithme est correct, quoique un peu tordu avec cette notion de nombre de chiffres du premier nombre.
Il faut que je revoie ma copie.
HP, Casio, Sharp, Psion, quelques TI et divers autres

Avatar de l’utilisateur
bernouilli92
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2662
Inscription : 21 nov. 2012 14:03
Localisation : Ile de France

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par bernouilli92 » 21 août 2018 01:49

Voici une nouvelle version qui fonctionne correctement avec 52 en entrée.
Par contre il faut entrer le nombre sous forme de chaîne de caractères : "52"

Code : Tout sélectionner

« DUP SIZE → S
  «
    IF S 1 ==
    THEN 
      DROP "0"
    ELSE 
      {} 1 S
      START 
        OVER HEAD + 
        SWAP TAIL SWAP
      NEXT 
      SWAP DROP 
      SORT DUP REVLIST ∑LIST STR→
      SWAP ∑LIST STR→ - →STR
      WHILE 
        DUP SIZE S <
      REPEAT
        "0" SWAP +
      END
    END
  »
»
HP, Casio, Sharp, Psion, quelques TI et divers autres

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1860
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par C.Ret » 21 août 2018 06:22

Très juste, il y a une incohérence concernant la différence entre 9 et 09.

On obtient deux suites distinctes selon que l'on traite les nombres en tant que tel ou comme des chaines de caractères ou des vecteurs.

En tant que vecteur (ou chaine de caractères):

Code : Tout sélectionner

52 = 52 - 25 = 27.
27 = 72 - 27 = 45.
45 = 54 - 45 = 09.
09 = 90 - 09 = 81.
81 = 81 - 18 = 63.
63 = 63 - 36 = 27.
...
En tant que nombre entier:

Code : Tout sélectionner

52 = 52 - 25 = 27.
27 = 72 - 27 = 45.
45 = 54 - 45 = 9.
 9 =  9 -  9 = 0.
 0 =  0 -  0 = 0.

Comme nous voulons que cela fonctionne sur des calculettes et comme je trouve cette seconde version plus naturelle et conforme à la description ci-dessus de l'algorithme, nous retiendrons que 52 entraine la séquence 27, 45, 9, 0.

J'avais lu un peu vite et n'avait pas vu le 09 qui n'est pas un nombre !

J'édit donc le message initial :o (et je vais me plaindre sur la page discussion de l'article Wikipédia d'où provient ce copier-coller trop rapide).


45 est donc un nombre spécial qui nous fait perdre un chiffre et 0 nous fait tomber dans le néant.

Je n'avait pas vu l'astuce utilisée par les auteurs de l'article dont je me suis inspiré et je comprends mieux les tableaux qui indiquent vers quoi tendent les suites de nombres de Kaprekar en fonction de leur nombre de chiffres. Ces tableaux n'ont de sens que si l'on ne changent pas de nombre de chiffres. Hors ce n'est pas toujours le cas sauf à ajouter des 0 en préfixe aux nombres pour les considérer comme des nombre ayant plus de chiffres. Ce qui n'est pas naturel.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-15C | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator . .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2418
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par zpalm » 21 août 2018 07:19

C.Ret a écrit :
21 août 2018 06:22
Comme nous voulons que cela fonctionne sur des calculettes et comme je trouve cette seconde version plus naturelle et conforme à la description ci-dessus de l'algorithme, nous retiendrons que 52 entraine la séquence 27, 45, 9, 0.
Du coup ma solution précédente en 1 ligne pour la HP Prime est valable :D

Code : Tout sélectionner

EXPR(CHAR(REVERSE(SORT(ASC(STRING(Ans,1)))))+"-"+CHAR(SORT(ASC(STRING(Ans,1)))))
Sinon, avec la définition initiale, voici un programme qui accepte en entrée un nombre ou une chaine et qui retourne une chaine.
Par exemple: 52 Enter Kaprekar Enter donne "27", il suffit alors de presser Enter pour avoir le nombre suivant : "45", puis "09" puis "81" ...

Code : Tout sélectionner

EXPORT Kaprekar()
BEGIN
LOCAL n,l,s;
  n:=IFTE(TYPE(Ans),Ans,STRING(Ans,1));
  l:=SORT(ASC(n));
  s:=STRING(EXPR(CHAR(REVERSE(l))+"-"+CHAR(l)),1);
  WHILE DIM(s)<DIM(n) DO s:="0"+s;END;
  s;
END;
Note: A utiliser en mode Livre ou Algébrique, la répétition par Enter ne fonctionne pas en mode RPN.

Avatar de l’utilisateur
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2418
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par zpalm » 21 août 2018 13:26

EDIT: optimisation pour passer de 52 à 47 pas:

Voici une version pour HP-41 en 47 pas, et 13 registres (0 à 12). C’est un code de catégorie A qui fonctionne avec des nombres de 1 à 10 chiffres et qui retourne 0 pour K(9).
On extrait les chiffres un par un (boucle label 01) et on les classe par ordre décroissant (boucle label 02) dans les registres de 0 jusqu’à 9 en fonction du nombre de chiffres du nombre de départ. Ensuite on construit dans les registres 11 et 12 les nombres d et c de la formule (boucle label 03) avant de les soustraire.

Code : Tout sélectionner

01 LBL "K"
02 CLRG           // Efface les registres
03 ENTER
04 LOG
05 INT            // Nombre de chiffres du nombre en entrée -1
06 1 E-3
07 *              // Conversion en compteur de boucle
08 STO 10         //  et sauvegarde dans le registre 10
09 X<>Y
10 LBL 01         // Première boucle: extraction des chiffres
11 10
12 /
13 INT            // Nombre amputé du premier chiffre à droite
14 X<>Y
15 LASTx
16 FRC            // Premier chiffre à droite au format 0.a
17 LBL 02         // Boucle de sauvegarde par ordre décroissant 
18 RCL IND Y      //  dans les registres de 0 à 9
19 X<=Y ?         // Si le chiffre courant est > au nombre dans le registre courant
20 X<>Y           //  on permute
21 STO IND Z      //  pour stocker dans le registre courant le plus grand des deux
22 RDN            // On récupère le plus petit des deux
23 ISG Y          // On passe au registre suivant
24 GTO 02         // Boucle autant de fois que le nombre initial a de chiffres
25 RCL 10         // On récupère la valeur du compteur de boucles
26 RCL T          // On récupère le nombre amputé
27 X#0?           // S’il reste des chiffres à extraire
28 GTO 01         //  on boucle
29 10^X           // A la sortie de boucle on a 0 dans X	
30 10^X           //  on convertit cette valeur en 10 avec le minimum d’octets
31 LBL 03         // Boucle de génération des nombres c et d de la formule
                  //  R11 va contenir d (le nombre avec les chiffres par ordre décroissant)
                  //  R12 va contenir c (le nombre avec les chiffres par ordre croissant) au format 0.N 
32 ST/ 12         // On divise par 10 la valeur de R12 pour faire de la place pour le prochain chiffre : 0.0N
33 RCL IND Y      // On récupère le chiffre courant (par ordre décroissant) au format 0.a
34 ST+ 11         // On l’ajoute à R11 -> N.a
35 ST+ 12         //  et R12 -> 0.aN
36 RDN
37 ST* 11         // On multiplie R11 par 10 -> Na
38 ISG Y          // On passe au chiffre suivant
39 GTO 03
40 RCL 11         // On rappelle d
41 RCL Z          // A la fin de la boucle on a le nombre de chiffres dans la partie entière du compteur
42 INT
43 10^X
44 RCL 12         // On rappelle c au format 0.c
45 *              //  et on multiplie par  10^nombre de chiffres pour obtenir c
46 –              // On soustrait pour obtenir K(n)
47 END            // Le programme s’arrête avec le résultat dans X. Une pression sur Enter le relance 
Dernière édition par zpalm le 22 août 2018 16:14, édité 3 fois.

Ben
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 1027
Inscription : 21 août 2016 19:04

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par Ben » 21 août 2018 16:42

Voici le premier jet, sur un VIC-20 (je n'ai que ça sous le main pour le moment).
J'utilise un tableau à 10 positions pour compter les chiffres et je construis C et D à partir de ce tableau. Le programme prévoit de sortir quand N est à 0 ou égale au résultat précédent.

Code : Tout sélectionner

5 clr:dim v(10)
10 print "S"
20 input n
25 print n;"=";:b=int(log(n)/log(10))+1:f=0:d=0:c=0:s=n
30 e=int(n/10):e=n-10*e:n=int(n/10):v(e)=v(e)+1
50 if n>0 then 30
60 for i=0 to 9:if v(i)=0 then 80
70 d=d+i*10^f:f=f+1:c=c+i*10^(b-f)
75 v(i)=v(i)-1:if v(i)>0 then 70
80 next i
90 print d;"-";c:n=d-c
100 if n=0 then end
110 if n<>s then 25
La ligne 5 n'est pas obligatoire et on peut compter le nombre de chiffres dans la boucle plutôt qu'avec les LOG

Ben

Avatar de l’utilisateur
C.Ret
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1860
Inscription : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par C.Ret » 21 août 2018 19:12

bernouilli92 a écrit :
20 août 2018 23:14
Voici une première version pour hp48g(x) :
Je suis ravi de voir que les premiers codes qui apparaissent sont en RPL.
Malgré tous ces défauts, ce langage et cet environnement permet de facilement s'adapter aux contraintes du sujet. Pour preuve la facilité de produire des codes efficaces quelque soit les vicissitudes de l'énoncé.

Comme l'algorithme n'indique nulle part qu'il faut considérer le nombre de chiffre, j'en ai déduit qu'il était plus naturel de construire les nombres intermédiaires comme de vrais nombres et non des vecteur, tableau du chiffres de taille constante ou chaine de caractère.
zpalm a écrit :
21 août 2018 07:19
Du coup ma solution précédente en 1 ligne pour la HP Prime est valable :D
Oui sur son principe de fonctionnement. Par contre, je ne sais pas comment enchainer facilement les utilisations sans avoir à retaper les nombres à chaque appel.

Le programme proposé est sur ce point bien mieux, car il est facile de parcourir les suites de transformations par Kaprekar par une simple pression sur la touche ENTER.


Concernant la version HP-41, je vais relever ce défit. Malheureusement, le MPO84 et le traçage de sa comète a épuisé les batteries de mon HP-41C. Je rentre à l'instant du travail, j'ai affronté la circulation de cette fin de journée pour n'acheter que trois piles. J'oublie toujours que contrairement à un HP-28S, une HP-41 utilise 4 piles LR1.

Ben a écrit :
21 août 2018 16:42
Voici le premier jet, sur un VIC-20 (je n'ai que ça sous le main pour le moment).
J'utilise un tableau à 10 positions pour compter les chiffres et je construis C et D à partir de ce tableau. Le programme prévoit de sortir quand N est à 0 ou égale au résultat précédent.
Cela me fais plaisir, le Commodore VIC-20 a été mon premier ordinateur. j'ai beaucoup programmé, notamment mes premiers graphiques et sons, et quelques jeux. Heureusement, j'avais deux outils indispensables :
- la cartouche SUPER EXPANDEUR VIC-1211A qui doublait la mémoire disponible et surtout complétait le jeu d'instruction du BASIC pour les graphiques (GRAPHIC DRAW CIRCLE PAINT CHAR …), les manettes de jeux RJOY() PEN() et RPAD() ou les sons (SOUND et PRINT "[<-]ABCDEFG"
- un dataset et trois ou quatre cassette audio neuves qui servaient aussi avec l'interface CE-121 de mon SHARP PC-1211.

Sinon concernant le code, je compte bien utiliser la même stratégie pour battre zpalm sur HP-15C ou HP-41 dont voici un aperçu de la mise au point, ici sur Commodore C128D (émulé):
MPO 85 - Commodore C128D (80 col.).gif
MPO 85 - Commodore C128D (80 col.).gif (10.2 Kio) Consulté 794 fois
Comme on ne le voit pas sur cette image fixe, le curseur clignote au début de 6174.
On peut donc modifier à loisir l'entrée ou simplement presser sur RETURN ou ENTER afin que cette valeur soit prise en compte pour la transformation suivante. C'est d'ailleurs comme cela que l'on est arrivé à cet affichage par pressions successives de la touche RETURN.

Cela est possible grâce aux caractères en vidéo inverse dans les chaines du PRINT. Ben aura reconnu ces codes bizarres qui sont l'enregistrement des déplacements du curseur; ce sont les mêmes sur PET, CBM, VIC20, C64 et C128 !

Il aura reconnu aussi son algorithme (juste avec moins de variables, pas de LOG ou de ^, les boucles explicitées par DO/LOOP et les test éludés)
J'ai juste laissé un GOTO, je trouve que ça fait très eighties.


Je suis agréablement surpris je m'attendais à ce que les premiers codes ne soient que sur des machines permettant de facilement trier les chiffres (SORT) ou d'inverser l'ordre des listes (REVERSE). Or il y a déjà deux programmes émérites qui ne disposent d'aucun de ces avantages contemporains.
SHARP PC-1211 + CE-121 + CE-122. | VIC 20 Commodore 128D + Printer P-803. | TI-57 LCD | TI-74 BasiCalc | TI-92 II | HP-15C | HP-28S + HP82240A | HP-41C + (2 memory + stat + IR) modules. | HP Prime Wireless Graphing Calculator . .Sommaire des M.P.O.. . Sommaire du P.C.T.M. .

Avatar de l’utilisateur
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2418
Inscription : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par zpalm » 21 août 2018 21:24

C.Ret a écrit :
21 août 2018 19:12
zpalm a écrit :
21 août 2018 07:19
Du coup ma solution précédente en 1 ligne pour la HP Prime est valable :D
Oui sur son principe de fonctionnement. Par contre, je ne sais pas comment enchainer facilement les utilisations sans avoir à retaper les nombres à chaque appel.

Le programme proposé est sur ce point bien mieux, car il est facile de parcourir les suites de transformations par Kaprekar par une simple pression sur la touche ENTER.
Il faut définir une fonction utilisateur avec Shift Define :

Image

Puis on entre le nombre suivi de Enter pour le transférer dans Ans, et on appelle la fonction, il suffit ensuite de presser Enter pour avoir la suite des nombres:

Image

Pour avoir une fonction d'utilisation plus générale (ne reposant pas uniquement sur Ans) on peut remplacer Ans par N dans la définition de la fonction. Il faudra alors fournir un paramètre lors de l'appel de la fonction.
Dans l'exemple ci-dessus il faudra donc remplacer Kaprekar par Kaprekar(Ans).

cgh
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1852
Inscription : 30 août 2011 12:23
Localisation : Vous êtes ici -> .

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par cgh » 21 août 2018 23:02

Ma modeste contribution sur SHARP PC-1500 (A) bien sur ;)

Code : Tout sélectionner

10 Z=&7650
20 POKE Z+0,104,25,72,121,74,0,69,183,10,195
30 POKE Z+10,224,42,69,201,224,253,152,88,122,90
40 POKE Z+20,0,36,40,106,58,52,81,136,3,164
50 POKE Z+30,221,42,98,129,28,69,253,200,90,40
60 POKE Z+40,241,185,15,253,218,95,1,253,138,110
70 POKE Z+50,1,129,8,90,40,185,15,253,218,95
80 POKE Z+60,1,136,31,253,168,104,10,90,49,72
90 POKE Z+70,122,74,8,253,98,108,255,139,11,87
100 POKE Z+80,155,9,223,42,164,65,136,3,158,17
110 POKE Z+90,90,40,72,122,74,24,253,96,108,10
120 POKE Z+100,131,11,85,155,9,223,42,164,65,136
130 POKE Z+110,3,158,17,253,42,72,122,74,0,90
140 POKE Z+120,8,106,5,164,65,52,65,85,241,27
150 POKE Z+130,84,65,136,7,74,16,90,24,106,5
160 POKE Z+140,164,65,52,65,85,241,27,84,65,136
170 POKE Z+150,7,190,239,182,72,122,74,0,88,121
180 POKE Z+160,90,0,106,7,245,136,3,253,26,154
190 WAIT
200 INPUT "VOTRE NOMBRE ? ";A
210 IF A=-1THEN END
220 K=A:CALL Z
230 CLS :PRINT "K(";K;")=";A
240 IF A<>KTHEN 220
250 PRINT "K(N)=N... ";:GOTO 200
Entrez le programme BASIC suivant et faites RUN...
Entrez votre nombre (entre 0 et 9999999999) et vous aurez la suite... Quand K(n) vaut 0 ou K(n)=n, alors le programme vous demandera un nouveau nombre. Entrez -1 pour sortir.
PS: Le programme est en assembleur :ugeek: et se loge de &7650 a &76F9. Il utilise donc les variables E$ a O$. Il est entierement relogeable et fonctionne sur n'importe quel PC1500 sans module.
J'adore parler de rien, c'est le seul domaine où j'ai de vagues connaissances ! - Oscar Wilde
Ce n'est pas parce que les choses sont difficiles que nous n'osons pas. C'est parce que nous n'osons pas que les choses sont difficiles. - Sénèque

cgh
Fonctionne à 2400 bauds
Fonctionne à 2400 bauds
Messages : 1852
Inscription : 30 août 2011 12:23
Localisation : Vous êtes ici -> .

Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)

Message par cgh » 21 août 2018 23:36

Le source assembleur pour ceux qui seraient interesses...

Code : Tout sélectionner

	; Algorithme de Kaprekar
	; A=n ::= un nombre entier entre 0 et 9999999999, par ex 26845
	; CALL <addr>
	; A=K(n)
	.CODE
	LD	H,19
	LD	B,<_A
	LD	C,>_A

	; On verifie que le nombre n'est pas superieur a 9999999999
	LDI	(BC)
	CPA	&0A
	SBR	C,(E0)
	STA	L	; L contient le nombre de chiffres - 1

	; On verifie que le nombre n'est pas negatif
	LDI	(BC)
	SBR	NZ,(E0)

	PUSH	DE

	; On efface les registres arithmetiques XREG..SREG
	LD	D,<XREG
	LD	E,>XREG
	LDA	L
	STA	H
	LD	L,#58
	CLA

CLR_X_SREG:
	STI	(DE)
	DJC	CLR_X_SREG

	; Le nombre de chiffres + 1 dans L
	LDA	H
	INC	A
	STA	L

	; On compte les occurences des chiffres presents
	; Cela nous permettra de les ordonner
	; WREG+SREG contiennent le nombre d'occurences
	; 26845 donnera 0 0 1 0 1 1 1 0 1 0
SORT_A_to_WREG:
	DEC	L
	JR      NC,end_SORT_A_to_WREG
	LDI	(BC)
	PUSH	A
	LD	E,>WREG
	AEX
	AND	0F
	ADD	DE
	ADD	(DE),01
	POP	A
	CP	L,01
	JR	NC,NO_2ndDIGIT
	LD	E,>WREG
	AND	0F
	ADD	DE
	ADD	(DE),01
NO_2ndDIGIT:
	DJC	SORT_A_to_WREG
end_SORT_A_to_WREG:

	; On va ordonner les chiffres dans l'ordre decroissant
	; Ainsi 26845 deviendra 0806050402
	PUSH	HL
	LD	H,0A
	LD	E,>[+9]WREG
	LD	B,<ZREG
	LD	C,>ZREG
SORT_DESCENDING_TO_ZREG:
	DEC	H
	CP	H,&FF
	JR	Z,end_SORT_DESCENDING_TO_ZREG
	LDD	(DE)
	JR	Z,SORT_DESCENDING_TO_ZREG
	DEC	A
	STA	L
	LDA	H
nDIGIT_by_L_in_ZREG:
	STI	(BC)
	DJC	nDIGIT_by_L_in_ZREG
	JR	SORT_DESCENDING_TO_ZREG
end_SORT_DESCENDING_TO_ZREG:

	; On va ordonner les chiffres dans l'ordre croissant
	; Ainsi 26845 deviendra 0204050608
	LD	E,>WREG
	LD	B,<UREG
	LD	C,>UREG
SORT_ASCENDING_TO_UREG:
	INC	H
	CP	H,&0A
	JR	C,end_SORT_ASCENDING_TO_UREG
	LDI	(DE)
	JR	Z,SORT_ASCENDING_TO_UREG
	DEC	A
	STA	L
	LDA	H
nDIGIT_by_L_in_UREG:
	STI	(BC)
	DJC	nDIGIT_by_L_in_UREG
	JR	SORT_ASCENDING_TO_UREG
end_SORT_ASCENDING_TO_UREG:

	POP	HL
	LD	B,<XREG
	LD	C,>XREG
	LD	E,>ZREG
	LD	L,05
	; H contient le nombre de chiffres
	LDA	H
	STI	(BC)
	CLA
	STI	(BC)

	; On compacte le nombre ordonne descendant dans XREG
	; 0806050402 deviendra 86542
COMPACT_ZREG_TO_XREG:
	LDI	(DE)
	AEX
	OR	(DE)
	INC	DE
	STI	(BC)
	DJC	COMPACT_ZREG_TO_XREG

	LD	C,>YREG
	LD	E,>UREG
	LD	L,05
	; H contient le nombre de chiffres
	LDA	H
	STI	(BC)
	CLA
	STI	(BC)

	; On compacte le nombre ordonne ascendant dans YREG
	; 0204050608 deviendra 24568
COMPACT_UREG_TO_YREG:
	LDI	(DE)
	AEX
	OR	(DE)
	INC	DE
	STI	(BC)
	DJC	COMPACT_UREG_TO_YREG

	; XREG=XREG-YREG
	CALL	SUBSTRACT

	; On copie XREG vers la variable BASIC A
	LD	B,<XREG
	LD	C,>XREG
	LD	D,<_A
	LD	E,>_A
	LD	L,07
XREG_TO_A:
	LDI
	DJC XREG_TO_A

	; Restaure DE
	POP	DE
	RET
	.END
Le programme peut se loger n'importe ou (il n'est pas optimise a cause de cela). Il peut donc fonctionner sur tous les modeles de PC1500 avec ou sans module memoire.
Il utilise la variable BASIC A pour le nombre N. En sortie cette meme variable contiendra K(N).
Ainsi:

Code : Tout sélectionner

A=52
CALL &7650
A -> renvoit 27
CALL &7650
A -> renvoit 45
etc.
J'adore parler de rien, c'est le seul domaine où j'ai de vagues connaissances ! - Oscar Wilde
Ce n'est pas parce que les choses sont difficiles que nous n'osons pas. C'est parce que nous n'osons pas que les choses sont difficiles. - Sénèque

Répondre

Revenir vers « Tous les Pockets »