[MPO n° 76] Période de quotient
Modérateur : Politburo
- Marge
- Fonctionne à 14400 bauds
- Messages : 6190
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
[MPO n° 76] Période de quotient
Un petit MPO entre les fêtes, ça vous va ? (non, pas de contrepet ! ce n'est pas faute d'avoir cherché... )
Il s'agit ici de réaliser le programme le plus court, sur la machine de votre choix, qui permette de trouver la période d'un quotient de division euclidienne.
Soit N et D deux entiers naturels, il s'agit donc de trouver Q qui est le résultat de leur division N/D, Q étant exprimé sous la forme d'un nombre réel avec immanquablement une période d'une longueur correspondant au maximum à D. Par exemple, 13/7= 1,857142857...
Le programme doit reconnaître la période, et n'afficher que le résultat "sec" : 1,857142 dans notre exemple.
Pour ne pas compliquer les choses, je propose de se limiter aux diviseurs inférieurs à la taille de l'affichage de la machine choisie.
À vos bécanes !
(Merci à l'auteur de la division euclidienne pour les Nuls pour cette idée de MPO )
Sommaire des MPO
Il s'agit ici de réaliser le programme le plus court, sur la machine de votre choix, qui permette de trouver la période d'un quotient de division euclidienne.
Soit N et D deux entiers naturels, il s'agit donc de trouver Q qui est le résultat de leur division N/D, Q étant exprimé sous la forme d'un nombre réel avec immanquablement une période d'une longueur correspondant au maximum à D. Par exemple, 13/7= 1,857142857...
Le programme doit reconnaître la période, et n'afficher que le résultat "sec" : 1,857142 dans notre exemple.
Pour ne pas compliquer les choses, je propose de se limiter aux diviseurs inférieurs à la taille de l'affichage de la machine choisie.
À vos bécanes !
(Merci à l'auteur de la division euclidienne pour les Nuls pour cette idée de MPO )
Sommaire des MPO
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: [MPO n° 76] Période de quotient
Voici ma première version, assez limitée, pour Casio PB-1000 :
A défaut d'être universelle, elle fonctionnera au moins sur les divisions par 7. En réalité, je ne recherche que la première ré-occurence du premier chiffre après la virgule (variable C). Son intérêt principal, c'est que c'est la première proposition à être publiée !
Code : Tout sélectionner
10 INPUT"N";N
20 INPUT"D";D
30 Q=N/D:PRINT Q
40 I=0:C=0
50 FOR E=0 TO 20:F=10^(9-E):D=INT(Q/F)*F
60 IF D<=0 THEN 120
70 K=INT(D/F):IF D>=1 THEN PRINT RIGHT$(STR$(K),1);:GOTO 110
80 IF C=0 THEN C=K:PRINT".";:PRINT RIGHT$(STR$(K),1);:GOTO 110
90 IF C=K THEN END
100 PRINT RIGHT$(STR$(K),1);
110 Q=Q-D
120 NEXT E
- bernouilli92
- Fonctionne à 14400 bauds
- Messages : 5270
- Enregistré le : 21 nov. 2012 13:03
- Localisation : Ile de France
Re: [MPO n° 76] Période de quotient
Voici ma version pour hp48 en 124 octets:
Par contre cela ne fonctionnent pas pour certains couples qui ne donnent pas une période (exemple 1/2) -> boucle infinie
Code : Tout sélectionner
« DUP2 / -> A B Q
« 0
DO
1 +
UNTIL
DUP ALOG
A * B MOD B / FP
Q FP
- ABS
,0000000001 <
END
ALOG Q DUP FP ROT / -
»
»
HP, Casio, Sharp, Psion, quelques TI et divers autres
- Marge
- Fonctionne à 14400 bauds
- Messages : 6190
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: [MPO n° 76] Période de quotient
Chapeau, messieurs, voilà de bonnes propositions de départ pour cette période de fêtes... à améliorer cependant !
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
- Marge
- Fonctionne à 14400 bauds
- Messages : 6190
- Enregistré le : 01 oct. 2008 14:39
- Localisation : En bas, tout au fond à gauche.
Re: [MPO n° 76] Période de quotient
Je dois reconnaître que ce n'est pas évident... sur une HP-29c ! je viens de m'arracher les cheveux pendant une paire d'heures.
Une bonne soixantaine de pas de programme sont déjà pris pour mettre en forme l'affichage - eh oui, pas d'adressage indirect pour l'affichage, il faut routiner ( ) ainsi :
... et encore, j'ai raccourci, parce que le test entre deux nombres différents de 0 se fait par la mise dans la pile des entiers successifs...
Il reste donc moins de 40 pas pour le reste. Mais je n'abandonne pas ! cela dit, ce sera peut-être pour après les fêtes, j'ai une valise à préparer, moi.
Une bonne soixantaine de pas de programme sont déjà pris pour mettre en forme l'affichage - eh oui, pas d'adressage indirect pour l'affichage, il faut routiner ( ) ainsi :
Code : Tout sélectionner
LBL 8
RCL 0 (l'index du nombre de chiffres à afficher sur la 29)
x supérieur à 0 ?
GOTO 0
RCL 3 (Q dans mon cas)
FIX 0
RTN
LBL 0
x supérieur à 1 ?
GOTO 0
RCL 3
FIX 1
RTN
LBL 0
x supérieur à 2 ?
GOTO 0
RCL 3
FIX 2
RTN
etc.
Il reste donc moins de 40 pas pour le reste. Mais je n'abandonne pas ! cela dit, ce sera peut-être pour après les fêtes, j'ai une valise à préparer, moi.
3 hommes, 3 demis, un 3a... Magnéto, Serge !
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
Quelques-uns de mes petits programmes pour machines Hewlett-Packard :
15C : Knight's Tour ;
29C : (k-)Permutations, Combinations, Linear Regression and Pseudo-random number ;
34C : Hanoi Towers - Automatic & Manual resolutions ;
67__: A L I E N .
♣ ♦ « Boris », c'était juste Maurice enrhumé. ♥ ♠
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: [MPO n° 76] Période de quotient
Voilà un bon sujet pour un MPO !
Et qui tombe à pic pour tester les programmes pour FX-702P de Thierry Loiseau (Fraction et réduction illimitées pour Noël)
Voici, dans un premier temps ma contribution pour SHARP PC-1360 qui me permet de vérifier que
13/ 7 = 1,857142 = 1, 857142 857142 857142...
19/ 14 = 1,3571428 = 1,3 571428 571428 571428...
57/ 55 = 1,036 = 1,0 36 36 36 36 36 36 36 36...
951130/ 90000 = 10,5681 = 10,568 1 1 1 1 1 1 1 1 1 1 1 1...
10/ 3 = 3,3 = 3, 3 3 3 3 3 3 3 3 3 3 3 3 3 3...
1/ 8 = 0,125 = 0,1250 = 0,125 0 0 0 0 0 0 0 0 0...
Cette version est la plus longue, mais c'est aussi la plus facile à lire.
En effet, A et B sont les termes de la fraction A/B à décomposer.
Le principe de l'algorithme est de réaliser pas à pas la division de A par B en mémorisant les restes dans le tableau R().
N est le nombre de restes déjà mémorisés. L'indice I est utilisé pour rechercher le nouveau reste dans le tableau R().
Les indices N et I seront utilisés pour extraire les décimales fixes d.ddd et répétées rrrrrr du quotient A/B
En cas de reste nul, la division "tombe juste", il n'y a pas de décimales répétées; dans ce cas n et i sont égaux.
Il peut arriver aussi que la division ne prenne jamais fin. dans ce cas, le programme s'arrête à la ligne 2: sur une erreur de dépassement de l'indice du tableau R().
Pour faire court ( c'est un MPO), je ne vais pas plus loin qu'une vingtaine des restes calculés (un maximum de 9 ou 10 décimales pour chacun des deux registres du résultats).
Et la version pour PC-1211/1210/1212 :
Cette version suit rigoureusement le même algorithme, cependant, les noms de registres sont déplacés en début de l'alphabet afin de réserver les registres F, G, H, ... etc au stockage des restes.
L'indice 6 qui apparaît dans le code correspond à la variable F où est mémorisé le premier reste R(0)
A et B correspondent comme pour la version 1360 à A et B, seul A est divisé par B afin de profiter de la multiplication implicite du 1211 et éviter un certain nombre de parenthèses
Par contre C est dans un premier temps le registre Q puis la partie fixe d.dddd du résultat
De même D et E correspondent aux indices n et i puis aux facteurs nécessaires à l'extraction des décimales fixes et répétées du résultat.
Et la version pour HP-28S (et autres RPL compatibles)
Les variables locales a et b correspondent à A et B des version BASIC.
L'avantage du HP28S est qu'il possède une instruction MOD.
La liste des restes et mémorisée dans une liste et l'instruction POS est utilisée pour y localiser un reste déjà rencontré ou détecter un reste nul.
Mis à part la détection des restes nuls, l'algorithme est exactement le même, mais le code est structuré très différemment car le RPL n'autorise pas les GOTO en spaghettis du BASIC !
P.S.:
Evidemment, ce programme est plus long et plus compliqué que celui posté par bernoulli92
Je ne sais pas si c'est parce que je l'ai utilisé sur une HP-28S au lieu d'une Hp-48, mais je n'ai pas obtenu de résultat pour 19/14 et les autres fractions.
Seules les fractions sans partie décimale fixe semblent convenir !...
Le mien est bien plus long, mais il convient tant que les parties fixes et répétés ne cumulent pas plus des 12 chiffres (10 sur les SHARP) du pocket.
Si cette limite est un problème, j'ai à ma disposition une autre version qui peut déterminer beaucoup beaucoup beaucoup + de décimales !
Je suis actuellement sur la version pour HP-41C qui ressemblera beaucoup à la version PC-1211 car il faut un peu ruser pour utiliser à bon escient l'adressage indirect des registres.
Et qui tombe à pic pour tester les programmes pour FX-702P de Thierry Loiseau (Fraction et réduction illimitées pour Noël)
Voici, dans un premier temps ma contribution pour SHARP PC-1360 qui me permet de vérifier que
13/ 7 = 1,857142 = 1, 857142 857142 857142...
19/ 14 = 1,3571428 = 1,3 571428 571428 571428...
57/ 55 = 1,036 = 1,0 36 36 36 36 36 36 36 36...
951130/ 90000 = 10,5681 = 10,568 1 1 1 1 1 1 1 1 1 1 1 1...
10/ 3 = 3,3 = 3, 3 3 3 3 3 3 3 3 3 3 3 3 3 3...
1/ 8 = 0,125 = 0,1250 = 0,125 0 0 0 0 0 0 0 0 0...
Code : Tout sélectionner
LIST
1: DIM R(19) : INPUT A,B : N=0 , Q=A
2: I=N , R(N)=Q-B* INT (Q/B) , Q=10*R(N) : IF Q GOTO 4
3: IF R(I)=R(N) LET I=10^I , C= INT (A*I/B)/I , D= INT ((A/B-C)*10^N) : PRINT C;" ";D;".." : END
4: IF I LET I=I-1 : GOTO 3
5: N=N+1 : GOTO 2
RUN
? 951130
? 90000
10.568 1...
RUN
? 17
? 14
1.2 142857...
En effet, A et B sont les termes de la fraction A/B à décomposer.
Le principe de l'algorithme est de réaliser pas à pas la division de A par B en mémorisant les restes dans le tableau R().
N est le nombre de restes déjà mémorisés. L'indice I est utilisé pour rechercher le nouveau reste dans le tableau R().
Les indices N et I seront utilisés pour extraire les décimales fixes d.ddd et répétées rrrrrr du quotient A/B
En cas de reste nul, la division "tombe juste", il n'y a pas de décimales répétées; dans ce cas n et i sont égaux.
Il peut arriver aussi que la division ne prenne jamais fin. dans ce cas, le programme s'arrête à la ligne 2: sur une erreur de dépassement de l'indice du tableau R().
Pour faire court ( c'est un MPO), je ne vais pas plus loin qu'une vingtaine des restes calculés (un maximum de 9 ou 10 décimales pour chacun des deux registres du résultats).
Et la version pour PC-1211/1210/1212 :
Code : Tout sélectionner
1:INPUT A,B:C=A,A=A/B,D=6
2:E=D,A(D)=C-B*INT (C/B,C=10A(D):IF C GOTO 4
3:IF A(D)=A(E) LET E=10^E/Ӕ6,D=10^D/Ӕ6,C=INT AE/E:PRINT C,INT AD-CD:END
4:IF E>6 LET E=E-1:GOTO 3
5:D=D+1:GOTO 2
où Ӕ correspond à l'exponentiel EE obtenu directement sur le clavier (touche [ Exp ] ) :)
L'indice 6 qui apparaît dans le code correspond à la variable F où est mémorisé le premier reste R(0)
A et B correspondent comme pour la version 1360 à A et B, seul A est divisé par B afin de profiter de la multiplication implicite du 1211 et éviter un certain nombre de parenthèses
Par contre C est dans un premier temps le registre Q puis la partie fixe d.dddd du résultat
De même D et E correspondent aux indices n et i puis aux facteurs nécessaires à l'extraction des décimales fixes et répétées du résultat.
Et la version pour HP-28S (et autres RPL compatibles)
Code : Tout sélectionner
« → a b
« a { 0 } a et liste des restes
WHILE
SWAP b MOD 10 * calcul reste suivant
DUP2 POS NOT vérifie que ce reste n'existe pas déjà (ou est nul)
REPEAT
SWAP OVER + ajoute ce reste à la liste et répète le calcul
END
OVER SIZE 1 - ALOG 10^n facteur pour extraction des chiffres répétés
ROT ROT POS 2 - i indice du reste déjà rencontré
IF DUP 0 <
THEN DROP DUP 10^n (facteur pour arrondi fraction fixe quand reste est nul)
ELSE ALOG END 10^i (facteur pour arrondi fraction fixe quand reste non nul)
a OVER * b / IP SWAP / d.dd arrondi fraction fixe
a b / OVER - ROT * IP rrrrr extraction groupe de chiffres répétés
2 →LIST » » { d.dd rrrrr } mise en forme affichage dans une liste
L'avantage du HP28S est qu'il possède une instruction MOD.
La liste des restes et mémorisée dans une liste et l'instruction POS est utilisée pour y localiser un reste déjà rencontré ou détecter un reste nul.
Mis à part la détection des restes nuls, l'algorithme est exactement le même, mais le code est structuré très différemment car le RPL n'autorise pas les GOTO en spaghettis du BASIC !
P.S.:
Evidemment, ce programme est plus long et plus compliqué que celui posté par bernoulli92
Je ne sais pas si c'est parce que je l'ai utilisé sur une HP-28S au lieu d'une Hp-48, mais je n'ai pas obtenu de résultat pour 19/14 et les autres fractions.
Seules les fractions sans partie décimale fixe semblent convenir !...
Le mien est bien plus long, mais il convient tant que les parties fixes et répétés ne cumulent pas plus des 12 chiffres (10 sur les SHARP) du pocket.
Si cette limite est un problème, j'ai à ma disposition une autre version qui peut déterminer beaucoup beaucoup beaucoup + de décimales !
Je suis actuellement sur la version pour HP-41C qui ressemblera beaucoup à la version PC-1211 car il faut un peu ruser pour utiliser à bon escient l'adressage indirect des registres.
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.