Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Modérateur : Politburo
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Ah! Une version assembleur! Je vais l'essayer ce soir
Vous avez remarqué, en tout cas pour les nombres à 4 chiffres, souvent, la suite se termine par 6174
EDIT: une petite stats qui ne sert à rien, mais dans 99% des cas, on trouve 6174! Plus exactement, on retrouve 8923 le chiffre 6174 sur les 9000
Vous avez remarqué, en tout cas pour les nombres à 4 chiffres, souvent, la suite se termine par 6174
EDIT: une petite stats qui ne sert à rien, mais dans 99% des cas, on trouve 6174! Plus exactement, on retrouve 8923 le chiffre 6174 sur les 9000
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2931
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Je viens de mettre à jour mon programme pour 41C: passage de 52 à 47 pas et ajout de commentaires.
-
- Fonctionne à 2400 bauds
- Messages : 2143
- Enregistré le : 30 août 2011 12:23
- Localisation : Vous êtes ici -> .
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Il est excellent ce petit programme !zpalm a écrit : ↑22 août 2018 16:13 Je viens de mettre à jour mon programme pour 41C: passage de 52 à 47 pas et ajout de commentaires.
Il y a ceux qui voient les choses telles qu'elles sont et se demandent pourquoi, et il y a ceux qui imaginent les choses telles qu'elles pourraient être et se disent... pourquoi pas? - George Bernard Shaw
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
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
-
- Fonctionne à 2400 bauds
- Messages : 2143
- Enregistré le : 30 août 2011 12:23
- Localisation : Vous êtes ici -> .
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Ce n'etait pas vraiment un MPO car il n'appartient pas a la rubrique, mais il y a deja eu des codes assembleurs comme pour ce challenge.
Il y a ceux qui voient les choses telles qu'elles sont et se demandent pourquoi, et il y a ceux qui imaginent les choses telles qu'elles pourraient être et se disent... pourquoi pas? - George Bernard Shaw
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
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
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2931
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Et aussi une version en microcode HP 41!
En attendant, voici une version WP 34S largement remaniée de mon programme pour 41C: grace à la puissance du jeu d'instructions de la WP 34S on passe de 47 à 29 pas et de 13 à 10 registres max utilisés. Seul le nombre de registres correspondant au nombre de chiffres du nombre en entrée est utilisé : par ex. pour un nombre de 4 chiffres les registres R00 à R03 sont utilisés, les autres ne sont pas modifiés.
Code : Tout sélectionner
01 LBL A
02 0 // Indice du premier registre
03 X<>Y
04 SDR 001 // Première boucle: extraction des chiffres
05 IP // Nombre amputé du premier chiffre à droite
06 RCL L
07 FP // Premier chiffre à droite au format 0.a
// Boucle de sauvegarde par ordre décroissant
08 STO->Z // Sauvegarde du chiffre courant dans le registre courant
09 INC Z // Registre suivant
10 RDN // On récupère le nombre amputé
11 X#0? // S’il reste des chiffres à extraire
12 BACK 008 // on boucle
// A la sortie de boucle on a 0 dans X, et le nombre de registres dans Y
13 x<>Y
14 SDR 002 // Compteur de registres pour R-SORT
15 R-SORT // On trie les registres par valeur croissante
16 RCL L // On récupère le nombre de registres
17 <>ZZXX // X=Y=0, Z=T=nombre de registres
18 DEC T // On décrémente T pour en faire un index du registre courant
// Boucle de génération des nombres c et d de la formule
// Y va contenir d (le nombre avec les chiffres par ordre décroissant)
// X va contenir c (le nombre avec les chiffres par ordre croissant) au format 0.N
19 SDR 001 // On divise par 10 la valeur de c pour faire de la place pour le prochain chiffre : 0.0N
20 RCL+->T // On ajoute à c le chiffre courant (par ordre décroissant) au format 0.a -> 0.aN
21 X<>Y // On permute c et d
22 RCL+->T // On ajoute à d le chiffre courant -> N.a
23 SDL 001 // On multiplie d par 10 -> Na
24 X<>Y // On permute c et d
25 DSL T // On passe au chiffre suivant
26 BACK 007
27 SDL->Z // On décale à gauche 0.c du nombre de chiffres pour obtenir c
28 – // On soustrait pour obtenir K(n)
29 END // Le programme s’arrête avec le résultat dans X. Une pression sur A le relance
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Bof, je le trouve un poil un peu long et il utilise un peu trop de registres et surtout des modules ou des HP-41 bien chères. Ah! Non zut, je confonds avec le listing ci-dessus pour la WPS !cgh a écrit : ↑22 août 2018 21:24Il est excellent ce petit programme !zpalm a écrit : ↑22 août 2018 16:13 Je viens de mettre à jour mon programme pour 41C: passage de 52 à 47 pas et ajout de commentaires.
Je propose 45 pas (avec le END final inclus comme il se doit), n'utilisant les registres R00 à R11 (soit douze registres) et ne nécessitant aucun module particulier, y compris module mémoire, même si vous ne possédez qu'une très modeste HP-41C. (Il vous faudra éventuellement 4 piles LR1 - mais bon tout le monde sait qu'il en faut 4 et pas 3 comme pour un HP-28S)
Pour lancer la première transformation, saisir le nombre à transformer puis presser [ XEQ ] [ Alpha ] [ M ][ P ][ O ][ ][ 8 ][ ][ 5 ]( Alpha ].
Les transformations suivantes sont obtenues simplement en pressant sur [ R/S ].
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
-
- Fonctionne à 2400 bauds
- Messages : 2143
- Enregistré le : 30 août 2011 12:23
- Localisation : Vous êtes ici -> .
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Il y a ceux qui voient les choses telles qu'elles sont et se demandent pourquoi, et il y a ceux qui imaginent les choses telles qu'elles pourraient être et se disent... pourquoi pas? - George Bernard Shaw
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
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
-
- Fonctionne à 2400 bauds
- Messages : 2143
- Enregistré le : 30 août 2011 12:23
- Localisation : Vous êtes ici -> .
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Dans ton programme, tu ne tries pas les chiffres mais tu comptes les occurences de ceux-ci et tu "recompose" les 2 nombres avec les chiffres en ordre decroissant et croissant. C'est ce que j'ai fait dans le programme assembleur pour PC-1500C.Ret a écrit : ↑23 août 2018 19:44 Je propose 45 pas (avec le END final inclus comme il se doit), n'utilisant les registres R00 à R11 (soit douze registres) et ne nécessitant aucun module particulier, y compris module mémoire, même si vous ne possédez qu'une très modeste HP-41C. (Il vous faudra éventuellement 4 piles LR1 - mais bon tout le monde sait qu'il en faut 4 et pas 3 comme pour un HP-28S)
Effectivement, cela s'avere plus simple, de plus, que je n'avais pas trop envie de me lancer dans un tri en "LH5801 in the text"
Il y a ceux qui voient les choses telles qu'elles sont et se demandent pourquoi, et il y a ceux qui imaginent les choses telles qu'elles pourraient être et se disent... pourquoi pas? - George Bernard Shaw
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
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
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Tout à fait, c'est d'ailleurs la même stratégie qu'utilise ben dans son code pour VIC-20 et donc aussi le même principe dans la version C128 que j'ai présentée.
Le comptage des occurrences d'entités ordonnées et en réalité la base du tri par comptage.
Les programmes de zpalm utilisent un tri à bulle (ou insertion ??) dont l'implémentation n'est pas plus difficile qu'un comptage et donne l'énorme avantage de construire un tableau trié, ce qui facilite grandement le calcul du résultat.
Le comptage des occurrences d'entités ordonnées et en réalité la base du tri par comptage.
Les programmes de zpalm utilisent un tri à bulle (ou insertion ??) dont l'implémentation n'est pas plus difficile qu'un comptage et donne l'énorme avantage de construire un tableau trié, ce qui facilite grandement le calcul du résultat.
Modifié en dernier par C.Ret le 21 févr. 2019 20:23, modifié 2 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
-
- Fonctionne à 2400 bauds
- Messages : 2143
- Enregistré le : 30 août 2011 12:23
- Localisation : Vous êtes ici -> .
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Il est vraiment marrant et interessant ce MPO...
Petite question: Quelles sont les applications de l'algorithme de Kaprekar ?
Petite question: Quelles sont les applications de l'algorithme de Kaprekar ?
Il y a ceux qui voient les choses telles qu'elles sont et se demandent pourquoi, et il y a ceux qui imaginent les choses telles qu'elles pourraient être et se disent... pourquoi pas? - George Bernard Shaw
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
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
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Je ne connais pas d'application à cet algorithme.
Ah! Ah! Et avec des nombres à trois chiffres, que disent les statistiques ?
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2931
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Tu as bien raison, mon programme est trop long et utilise trop de registres. Un petit coup de MPOisation et voici une version allégée pour 41C de base: 44 pas et 10 registres (R00 à R09) maximum*.C.Ret a écrit : ↑23 août 2018 19:44 Bof, je le trouve un poil un peu long et il utilise un peu trop de registres et surtout des modules ou des HP-41 bien chères. Ah! Non zut, je confonds avec le listing ci-dessus pour la WPS !
Je propose 45 pas (avec le END final inclus comme il se doit), n'utilisant les registres R00 à R11 (soit douze registres) et ne nécessitant aucun module particulier, y compris module mémoire, même si vous ne possédez qu'une très modeste HP-41C.
Une meilleure utilisation de la pile et du registre L permet de se passer des registres 10, 11 et 12 de la version précédente et au passage d'économiser trois pas de programme. Comme sur la 34S le programme n’utilise que le nombre de registres correspondant au nombre de chiffres du nombre en entrée : pour un nombre de 4 chiffres seuls les registres R00 à R03 sont utilisés.
Code : Tout sélectionner
01 LBL "K"
02 ENTER
03 LOG
04 INT // Nombre de chiffres du nombre en entrée -1
05 1 E-3
06 * // Conversion en compteur de boucles
07 CLRG // Efface les registres - à remplacer par CLRGX sur une 41CX*
09 X<>Y
09 LBL 01 // Première boucle: extraction des chiffres
10 10
11 /
12 INT // Nombre amputé du premier chiffre à droite
13 LASTx
14 FRC // Premier chiffre à droite au format 0.a
15 RCL Z // On récupère le compteur de boucles
16 STO L // On le stocke dans L pour la boucle suivante
17 LBL 02 // Boucle de sauvegarde par ordre décroissant dans les registres de 0 à 9
18 X<> IND L // On permute le registre courant avec la valeur initiale du compteur de boucles
19 X<=Y ? // Si le chiffre courant est > au nombre dans le registre courant
20 X<>Y // on permute
21 X<> IND L // pour stocker dans le registre courant le plus grand des deux et récupérer le compteur de boucles
22 ISG L // On passe au registre suivant
23 GTO 02 // Boucle autant de fois que le nombre initial a de chiffres
24 RCL Z // On récupère le nombre amputé
25 X#0? // S’il reste des chiffres à extraire
26 GTO 01 // on boucle
27 X<>Y // A la sortie de la boucle on a 0 dans X,Z,T et le compteur de boucles dans Y,
28 * // on prépare la pile pour la boucle finale :
29 10 // X=10, Y=0, Z=0, L=compteur de boucles
30 LBL 03 // Boucle de génération des nombres c et d de la formule
// Y/Z va contenir d (le nombre avec les chiffres par ordre décroissant)
// Z/T va contenir c (le nombre avec les chiffres par ordre croissant) au format 0.N
31 ST/ Y // On divise par 10 la valeur de c pour faire de la place pour le prochain chiffre : 0.0N
32 RCL IND L // On récupère le chiffre courant (par ordre décroissant) au format 0.a
33 ST+ Z // On l’ajoute à c -> N.a
34 ST+ T // et d -> 0.aN
35 RDN
36 ST* Z // On multiplie d par 10 -> Na
37 ISG L // On passe au chiffre suivant
38 GTO 03
39 LASTx // A la fin de la boucle on a le nombre de chiffres dans la partie entière du compteur
40 INT
41 Y^X
42 * // On multiplie .c par 10^nombre de chiffres pour obtenir c
43 – // On soustrait c de d pour obtenir K(n)
44 END // Le programme s’arrête avec le résultat dans X. Une pression sur Enter le relance
Pour l'alimentation en électricité de la 41, j'ai acheté ceci.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3419
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Joli !
J'aime bien deux choses :
J'aime, donc je pirate :
Avec beaucoup de mal et en m'inspirant du travail de zpalm, j'arrive à un programme de catégorie A qui utilise entre 2 et 11 registres selon le nombre de chiffres qui lui peut varier entre 1 et 10.
Il n'utilise que 39 pas de programme et les fonctions ISG et DSE. La fonction LOG est utilisée au début de la seconde partie pour mettre 1 dans la pile et 10 dans le registre LastX:
Ne cherchez pas de GTO 03, le LBL 03 ne sert que de NOP pour le DSE qui, quelque soit la valeur, doit continuer par l'instruction 036 DSE 00
Il y a en fait trois boucles:
J'aime bien deux choses :
- la façon dont les chiffres sont mis dans l'ordre avec les deux X<> IND L
- La façon de mettre au début ou à la fin de c et d en jouant sur le point décimal qui sert en fait de point d'insertion
J'aime, donc je pirate :
Avec beaucoup de mal et en m'inspirant du travail de zpalm, j'arrive à un programme de catégorie A qui utilise entre 2 et 11 registres selon le nombre de chiffres qui lui peut varier entre 1 et 10.
Il n'utilise que 39 pas de programme et les fonctions ISG et DSE. La fonction LOG est utilisée au début de la seconde partie pour mettre 1 dans la pile et 10 dans le registre LastX:
Ne cherchez pas de GTO 03, le LBL 03 ne sert que de NOP pour le DSE qui, quelque soit la valeur, doit continuer par l'instruction 036 DSE 00
Il y a en fait trois boucles:
- la boucle Lbl 00 qui décortique chiffre par chiffre le nombre donné en argument (dans X: au lancement),
- la boucle Lbl 01 qui trie les chiffres dans les registres et
- la boucle Lbl 02 qui construit les nombres D et C contenant respectivement les chiffres dans l'ordre décroissant et croissant.
Modifié en dernier par C.Ret le 01 sept. 2018 07:41, modifié 3 fois.
SHARP PC-1211 PC-1360 EL-5150 PC-E500 | Commodore C=128D | Texas Instruments Ti-57LCD Ti-74BASICalc Ti-92II Ti-58c Ti-95PROCalc Ti-30XPROMathPrint | Hewlett-Packard HP-28S HP-41C HP-15C HP-Prime HP-71B | CASIO fx-602p | NUMWORKS | Graphoplex Rietz Neperlog | PockEmul | Sommaire des M.P.O. | Ma...dov'il sapone.
Re: Misez p'tit, Optimisez - N°85 (L'Algorithme de Kaprekar)
Cette après-midi, je me suis dit que la FX-602P pouvait aussi faire ce genre de petit calcul, voici le premier jet:
101 Pas - 6 mémoires plus le tableau 10-19. Quand je vois que certains le font en 44 ou 45 pas, je me dis que j'ai encore pas mal de progrès à faire :-/
Code : Tout sélectionner
Min02 Sauf le monbre dans Mem02
1 Min06 Mem06 = 0 Coeff de multiplication par 10
20 MinF MemF=20 Borne du tableau pour le tri (0 à 9 +10)
0 Min04 Min05 Mem04 nombre chiffres croissant Mem05 Chiffres décroissants
LBL1 MR02 / 10 = INT * 10 = Min00 Mem00 Travail, contient le dernier chiffre du nombre
MR02 - MR00 + 10 = Min00 Tableau commence à la Mem10 (0=Mem10, 1=Mem11, ...)
1 IND M+00 Sert d'indexe pour ajouter 1 au tableau
MR02 / 10 = INT Min02 Enlève 1 chiffre au nombre
x=0 GOTO2 GOTO1
LBL2 10 Min00 Indexe du tableau
LBL3 IND MR00 x=0 GOTO4 Si la valeur du tableau =0 on passe
LBL5 MR04 * 10 + MR00 - 10 = Min04 Calcul la valeur du nombre en croissant
(MR00 - 10) * MR06 + MR05 = Min05 Calcul la valeur du nombre en décroissant
MR06 * 10 = Min06 Multiplie par 10 le Coeff
1 IND M-00 Soutrait 1 au tableau
IND MR00 x=0 GOTO4 GOTO5 Test si la valeur du tableau est à 0
LBL4 1 M+00 MR00 x=F GOTO6 GOTO3 Ajout 1 à l'indexe, jusqu'à 20
LBL6 MR05 - MR04 = Affiche le résultat