Misez p'tit Optimisez n°83 : Fabuleuses fractions
Modérateur : Politburo
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Misez p'tit Optimisez n°83 : Fabuleuses fractions
En utilisant exactement une seule fois tous les chiffres entre 0 et 9 inclus, il est possible de construire deux fractions dont la somme fait très exactement 1.
Il y a de nombreuses solutions, certaines sont simples à déterminer, d'autres un peu plus compliquées. Ce qui est sûr , c'est que cela est certainement plus simple si vous laisser faire votre Calculette ou Pocket préféré(e(s)) et les chargiez de les trouver pour vous, voir même si cela est possible de vous en imprimer la liste.
Comme moi, vous avez certainement d'autres choses à faire pour ce week-end comme par exemple profiter du beau temps ou faire quelques vide-greniers.
Mais, je suis quand même curieux de voir quels codes vous donneriez à vos programmables pour mener à bien cette opération et ainsi construire de la façon la plus efficace la liste la plus exhaustive de ces fabuleuses fractions ?
P.J.: En guise d'illustration, deux couples de fractions fabuleuses :
Il y a de nombreuses solutions, certaines sont simples à déterminer, d'autres un peu plus compliquées. Ce qui est sûr , c'est que cela est certainement plus simple si vous laisser faire votre Calculette ou Pocket préféré(e(s)) et les chargiez de les trouver pour vous, voir même si cela est possible de vous en imprimer la liste.
Comme moi, vous avez certainement d'autres choses à faire pour ce week-end comme par exemple profiter du beau temps ou faire quelques vide-greniers.
Mais, je suis quand même curieux de voir quels codes vous donneriez à vos programmables pour mener à bien cette opération et ainsi construire de la façon la plus efficace la liste la plus exhaustive de ces fabuleuses fractions ?
P.J.: En guise d'illustration, deux couples de fractions fabuleuses :
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 à 75 bauds
- Messages : 28
- Enregistré le : 14 avr. 2017 14:45
- Localisation : Paris
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
Hello,
je viens de venir à bout de ce mpo en trichant totalement puisque j'ai fait mon programme en c sur un pc relativement récent (3-4h de labeur pour près de 120 lignes quand-même !)
J'avais commencé en basic sur un PC-G850V et ai vite été limité par exemple par les nombres maximum d'imbrication de boucles (qu'on peut certes contourner en remplaçant les FOR NEXT par des boucles "manuelles" avec des GOTO)
Mon programme trouve 634 couples de fractions, (sachant que mathématiquement, il y en a moins car des solutions faisant intervenir 1/2 = 2/4 = 3/6 sont comptées autant de fois. Dis autrement, pas de simplification des fractions). C.Ret, tu trouves le même nombre de solutions ?
Il y a peut-être une approche plus simple mais il me semble que l'on ne peut pas échapper au problème de générer l'ensemble des permutations de 10 chiffres (il y en a 10!=3628800) et j'ai voulu l'écrire sans récursivité d'où 10 boucles imbriquées pour installer chaque chiffre de 0 à 9 dans une des 10 positions disponibles. Après, je découpe chaque permutation en 4 paquets pour former les 2 numérateurs et dénominateurs candidats (84 combinaisons possibles) puis je regarde si les deux fractions ainsi composées répondent.
Il s'agit d'une approche totalement bourrine avec exploration de toutes les possibilités alors que quelques considérations mathématiques simples devraient permettent de réduire l'espace de recherche je pense.
Quelques couples de fractions non triviales trouvées :
34/51 + 269/807
795/810 + 6/324
678/904 + 13/52
Prochaine étape : porter le code c sur un pocket (en basic ou c) et voir en combien de temps ça tourne car sur un pc récent, le résultat est quasi instantané !
C.Ret, je serais preneur d'un algorithme non récursif permettant de générer les permutations simplement
Edit : je m'aperçois que mon programme ramène aussi les solutions où 0 est en première position de la permutation : les fractions trouvées dans ce cas n'utilisent pas le 0 car 0n = n mais c'est pas trop dur à éliminer des solutions renvoyées
je viens de venir à bout de ce mpo en trichant totalement puisque j'ai fait mon programme en c sur un pc relativement récent (3-4h de labeur pour près de 120 lignes quand-même !)
J'avais commencé en basic sur un PC-G850V et ai vite été limité par exemple par les nombres maximum d'imbrication de boucles (qu'on peut certes contourner en remplaçant les FOR NEXT par des boucles "manuelles" avec des GOTO)
Mon programme trouve 634 couples de fractions, (sachant que mathématiquement, il y en a moins car des solutions faisant intervenir 1/2 = 2/4 = 3/6 sont comptées autant de fois. Dis autrement, pas de simplification des fractions). C.Ret, tu trouves le même nombre de solutions ?
Il y a peut-être une approche plus simple mais il me semble que l'on ne peut pas échapper au problème de générer l'ensemble des permutations de 10 chiffres (il y en a 10!=3628800) et j'ai voulu l'écrire sans récursivité d'où 10 boucles imbriquées pour installer chaque chiffre de 0 à 9 dans une des 10 positions disponibles. Après, je découpe chaque permutation en 4 paquets pour former les 2 numérateurs et dénominateurs candidats (84 combinaisons possibles) puis je regarde si les deux fractions ainsi composées répondent.
Il s'agit d'une approche totalement bourrine avec exploration de toutes les possibilités alors que quelques considérations mathématiques simples devraient permettent de réduire l'espace de recherche je pense.
Quelques couples de fractions non triviales trouvées :
34/51 + 269/807
795/810 + 6/324
678/904 + 13/52
Prochaine étape : porter le code c sur un pocket (en basic ou c) et voir en combien de temps ça tourne car sur un pc récent, le résultat est quasi instantané !
C.Ret, je serais preneur d'un algorithme non récursif permettant de générer les permutations simplement
Edit : je m'aperçois que mon programme ramène aussi les solutions où 0 est en première position de la permutation : les fractions trouvées dans ce cas n'utilisent pas le 0 car 0n = n mais c'est pas trop dur à éliminer des solutions renvoyées
- ledudu
- Fonctionne à 14400 bauds
- Messages : 5646
- Enregistré le : 26 mars 2009 13:07
- Localisation : Ile de France
- Contact :
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
Salut,
Marrant, je me suis aussi attaqué aujourd'hui à ce MPO spécial Hp-prime tant le nombre de combinaisons est important.
J'ai travaillé en basic sur une casio fx-790p reliée à une FP-40.
Mon algo est différent.
J'ai commencé par étudier les solutions de la forme ijk / lmn + op / qr = 1 (avec i,l, o et q <>0).
Je génère pas à pas ijk, lmn et qr (8 boucles for next en éliminant les mauvaises solutions au passage), je calcule op=(1-ijk / lmn) X qr et je vérifie que op est entier et correspond aux deux derniers chiffres dispos.
Pour limiter la combinatoire, je sais que 0<i<l.
Inutile de vous dire que ça tourne encore et que je n'aurai pas les résultats ce soir.
Marrant, je me suis aussi attaqué aujourd'hui à ce MPO spécial Hp-prime tant le nombre de combinaisons est important.
J'ai travaillé en basic sur une casio fx-790p reliée à une FP-40.
Mon algo est différent.
J'ai commencé par étudier les solutions de la forme ijk / lmn + op / qr = 1 (avec i,l, o et q <>0).
Je génère pas à pas ijk, lmn et qr (8 boucles for next en éliminant les mauvaises solutions au passage), je calcule op=(1-ijk / lmn) X qr et je vérifie que op est entier et correspond aux deux derniers chiffres dispos.
Pour limiter la combinatoire, je sais que 0<i<l.
Inutile de vous dire que ça tourne encore et que je n'aurai pas les résultats ce soir.
Code : Tout sélectionner
Les solutions sont croissantes sur ijk) :
105 / 623 + 74 / 89 = 1
109 / 327 + 56 / 84 = 1
135 / 270 + 48 / 96 = 1
-
- Fonctionne à 2400 bauds
- Messages : 2362
- Enregistré le : 16 févr. 2008 23:34
- Localisation : Paris 20ème
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
Beau problème "fermé" comme je les aime.
Je me permets de répondre : le truc quand on est limité par le nombre de boucles imbriquées ou la non-récursivité, c'est de poser une boucle simple sur le nombre de combinaisons (for i=0 to 10!-1, par exemple) et de déterminer à l'intérieur de la boucle la combinaison à laquelle l'index fait référence (ici, placer le 0 parmi 10 positions, le 1 parmi les 9 restantes, etc. en faisant des "quotient entier + reste" sur i). J'imbriquerais une seconde boucle pour le découpage de la combinaison des 10 chiffres en quatre blocs (là, la détermination des paquets est un peu plus délicate).Sharpounet a écrit : ↑13 mai 2018 19:23C.Ret, je serais preneur d'un algorithme non récursif permettant de générer les permutations simplement
Programmeur abscons.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
Intéressant tout cela.
Pour ma part, je me suis lancé sur une HP-29C (simulée).
Mon algorithme de recherche est basé sur l'étude des intervalles où une solution est possible. Les deux fractions a/b et c/d ayant un rôle parfaitement symétrique, je me suis imposé une condition supplémentaire entre a/b et c/d afin de ne pas parcourir deux fois l'ensemble des solutions.
En fait le nombre de fractions solution de a/b + c/d = 1 étant quasiment infini, je me base surtout sur la contrainte très forte de n'utiliser qu'une et une seule fois exactement chaque chiffre.
Pour le moment, mon simulateur d'HP-29C m'imprime aussi les solutions n'utilisant qu'une partie des chiffres. Mais ce n'est pas (encore) très rapide.
En gros, b est fortement borné entre a et 2a, c est libre mais doit commencer assez haut pour avoir une chance d'utiliser les dix chiffres et d est minoré par 2.c mais il est calculé à partir des trois autres. Reste juste alors à vérifier qu'il est composé des bons chiffres pour compléter le jeu imposé.
Pour ma part, je me suis lancé sur une HP-29C (simulée).
Mon algorithme de recherche est basé sur l'étude des intervalles où une solution est possible. Les deux fractions a/b et c/d ayant un rôle parfaitement symétrique, je me suis imposé une condition supplémentaire entre a/b et c/d afin de ne pas parcourir deux fois l'ensemble des solutions.
En fait le nombre de fractions solution de a/b + c/d = 1 étant quasiment infini, je me base surtout sur la contrainte très forte de n'utiliser qu'une et une seule fois exactement chaque chiffre.
Pour le moment, mon simulateur d'HP-29C m'imprime aussi les solutions n'utilisant qu'une partie des chiffres. Mais ce n'est pas (encore) très rapide.
En gros, b est fortement borné entre a et 2a, c est libre mais doit commencer assez haut pour avoir une chance d'utiliser les dix chiffres et d est minoré par 2.c mais il est calculé à partir des trois autres. Reste juste alors à vérifier qu'il est composé des bons chiffres pour compléter le jeu imposé.
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 à 75 bauds
- Messages : 28
- Enregistré le : 14 avr. 2017 14:45
- Localisation : Paris
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
@jxano : merci pour ta suggestion pour la génération des permutations qui m'a donnée une autre idée d'algorithme avec seulement 2 niveaux de boucles imbriquées, une boucle de 1023456789 à 9876543210, puis un rangement de chaque chiffre dans un tableau (j'ai utilisé une autre méthode en passant par des chaines de caractères) puis un comptage du nombre de chiffres différents dans le nombre. Si ça fait moins de 10, ce n'est pas une permutation.
Code super compact !
Si a[0..9] est le tableau contenant les dix chiffres dont on cherche à savoir s'ils sont tous différents, v[0..9] le tableau des chiffres utilisés :
v[k]=1 si le chiffre k est présent dans le nombre de 10 chiffres, 0 sinon.
for(j=0;j<10;j++) v[j]=0;
compte=0;
for(j=0;j<10;j++) v[a[j]]=1;
for(j=0;j<10;j++) compte+=v[j];// si compte = 10 : c'est une permutation
Par contre, c'est beaucoup plus lent.Je suis encore en c sur mon pc récent. Sur un pocket, ça doit méchamment ramer !
Code super compact !
Si a[0..9] est le tableau contenant les dix chiffres dont on cherche à savoir s'ils sont tous différents, v[0..9] le tableau des chiffres utilisés :
v[k]=1 si le chiffre k est présent dans le nombre de 10 chiffres, 0 sinon.
for(j=0;j<10;j++) v[j]=0;
compte=0;
for(j=0;j<10;j++) v[a[j]]=1;
for(j=0;j<10;j++) compte+=v[j];// si compte = 10 : c'est une permutation
Par contre, c'est beaucoup plus lent.Je suis encore en c sur mon pc récent. Sur un pocket, ça doit méchamment ramer !
-
- Fonctionne à 2400 bauds
- Messages : 2362
- Enregistré le : 16 févr. 2008 23:34
- Localisation : Paris 20ème
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
Ma calculatrice me donne une combinaison de 10 chiffres toutes les 9 secondes, autant dire que ce n'est pas avec elle que je vais trouver beaucoup de solutions au problème posé. Mais à chaque tour de boucle, une combinaison tombe.
Code : Tout sélectionner
10 PRINT "PERMUT 10": CLEAR
12 DIM T(9):F= FACT10
20 FOR I=0 TO F-1
22 FOR J=0 TO 9:T(J)=-1: NEXT J
24 H=I
26 FOR J=10 TO 1 STEP -1
28 Q= INT(H/J):R=H-Q*J:H=Q:K=0
30 IF R=0 THEN IF T(K)=-1 THEN T(K)=J-1: GOTO 40
32 IF T(K)=\-1 THEN K=K+1: GOTO 30 -- le signe "différent" est un = barré sur Casio fx-790P
34 R=R-1:K=K+1: GOTO 30
40 NEXT J
42 PRINT : FOR J=0 TO 9: PRINT T(J);: NEXT J
44 NEXT I
Programmeur abscons.
- ledudu
- Fonctionne à 14400 bauds
- Messages : 5646
- Enregistré le : 26 mars 2009 13:07
- Localisation : Ile de France
- Contact :
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
Mon programme BASIC tourne depuis 4 jours.
J'ai fait un programme bourrin en Python sur mon portable Lenovo.
Résultat : toutes les combinaisons en 30''.
Je trouvais ça plus rigolo sur le pocket.
J'ai fait un programme bourrin en Python sur mon portable Lenovo.
Résultat : toutes les combinaisons en 30''.
Je trouvais ça plus rigolo sur le pocket.
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
Avec un algorithme naïf, comme le nombre de combinaisons à tester par calcul exhaustif est affreusement grand, j'ai essayé de construire aléatoirement des fractions avec des chaînes de caractères, en espérant tomber par hasard sur une solution. Si les solutions n'étaient pas trop rares, on pourrait en trouver une relativement rapidement. Malheureusement, c'est super long ! Cela dit, comme c'est un MPO, et que ce programme très inefficace ne prend que 15 lignes sur Casio PB1000, j'ose vous le montrer :
Le tableau A$() contient 4 chaînes de caractères qui représentent les deux fractions A / B et C / D. Le compteur K sert à afficher quelque chose qui s'incrémente, pour faire patienter, pendant l'interminable calcul.
J'ai fait tourner ce programme sur l'émulateur de Piotr Piatek en mode overclocké. Et si la calculatrice passe en veille après le calcul, vous pouvez la rallumer et passer tout de suite à l'affichage du résultat par un "RUN 140" en mode Basic :
En le lançant plusieurs fois, on obtient des solutions différentes.
Code : Tout sélectionner
10 DIM A$(4):K=0
20 FOR J=0 TO 3:A$(J)="":NEXT
30 FOR I=0 TO 9:J=INT(RND(-1)*4)
40 P=INT(RND(-1)*2):IF P=0 THEN 60
50 A$(J)=RIGHT$(STR$(I),1)+A$(J):GOTO 70
60 A$(J)=A$(J)+RIGHT$(STR$(I),1)
70 NEXT I
80 FOR J=0 TO 3:L=LEN(A$(J))
90 IF L=0 OR L>4 OR LEFT$(A$(J),1)="0" THEN 20
95 NEXT J
100 A=VAL(A$(0)):B=VAL(A$(1)):IF A>B THEN 20
110 C=VAL(A$(2)):D=VAL(A$(3)):IF C>D THEN 20
120 K=K+1:CLS:PRINT K
130 IF A*D+B*C<>B*D THEN 20
140 PRINT A;"/";B;"+";C;"/";D;"=1"
J'ai fait tourner ce programme sur l'émulateur de Piotr Piatek en mode overclocké. Et si la calculatrice passe en veille après le calcul, vous pouvez la rallumer et passer tout de suite à l'affichage du résultat par un "RUN 140" en mode Basic :
En le lançant plusieurs fois, on obtient des solutions différentes.
Modifié en dernier par dprtl le 28 mai 2018 20:43, modifié 1 fois.
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
Je dois l'avouer, en rédigeant ce MPO, je ne mettais pas rendu compte que trouver toutes ces fabuleuses fractions était aussi long !
Le programme de ledudu tourne depuis 4 jour, celui sur mon HP-29C virtuelle tourne depuis dix jours …
Et je trouve l'idée de dprti très intéressante, car aucun de mes programmes n'est aussi court !
Mon pauvre C=128D met une semaine pour me trouver 95 couples de fractions. Il paraitrait qu'il en existe 96 en tout ?
Ce brave et laborieux Commodore doit en manquer une à cause de sa prodigieuse tendance à faire des erreurs d'arrondi
Le programme de ledudu tourne depuis 4 jour, celui sur mon HP-29C virtuelle tourne depuis dix jours …
Et je trouve l'idée de dprti très intéressante, car aucun de mes programmes n'est aussi court !
Mon pauvre C=128D met une semaine pour me trouver 95 couples de fractions. Il paraitrait qu'il en existe 96 en tout ?
Ce brave et laborieux Commodore doit en manquer une à cause de sa prodigieuse tendance à faire des erreurs d'arrondi
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.
- dprtl
- Fonctionne à 1200 bauds
- Messages : 463
- Enregistré le : 27 janv. 2013 00:26
- Localisation : Strasbourg
- Contact :
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
Pour la PB1000, si tu regardes mon test à la ligne 130, je limite les erreurs d'arrondis en ne faisant pas de division. Pour additionner deux fractions, A/B + C/D, on multiplie les dénominateurs :
Code : Tout sélectionner
130 IF A*D+B*C<>B*D THEN 20
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
C'est une voie que je vais emprunter avec mon C128D.
Je n'y avais pas pensé plus tôt, je vais devoir tout recommencer alors que j'obtiens maintenant les 95 paires de fractions fabuleuses en moins de 5 secondes :
Je n'y avais pas pensé plus tôt, je vais devoir tout recommencer alors que j'obtiens maintenant les 95 paires de fractions fabuleuses en moins de 5 secondes :
- Fichiers joints
-
- 2018-05-28_r.png (50.09 Kio) Vu 13931 fois
Modifié en dernier par C.Ret le 28 mai 2018 23:34, modifié 1 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.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2935
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
Wahou !! moins de 5s !! Je m'échine sur un programme pour ma HP Prime qui me donne 99 paires en 2h53mn
- C.Ret
- Fonctionne à 9600 bauds
- Messages : 3422
- Enregistré le : 31 mai 2008 23:43
- Localisation : N 49°22 E 6°10
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
OUi, mais c'est de la gruge, c'est en réalité exactement 6 jours et 4 secondes !!!
Sauf avec ce code :
Mais, c'est le plus court et donc le plus adapté à un MPO.
Demain j'essaye mon algorithme sur la prime
Sauf avec ce code :
Code : Tout sélectionner
10 DATA 1,-2,-3485,-3548,-3845,-4538,-4685,-4835,-4853,4865,-4,7365,-6,7835,7
11 DATA 4362,2,-4,3079,-6,3190,-7,-5940,6810,9,5803,3,-6,-1485,-2079,-2709,-2907
12 DATA 4851,127,496,4,-5,-1278,1872,356,792,5,104,693,6,-324,795,534,792,7,-9
13 DATA -1208,1352,54,893,8,-10,-729,927,512,693,9,-12,876,351,684,10,-28,369
14 DATA -45,-287,728,96,473,12,-54,609,-60,748,96,-357,735,13,-26,485,52,678,15
15 DATA 30,486,16,32,485,17,89,504,18,90,-276,372,19,-57,308,58,273,21,96,375
16 DATA 24,-63,507,96,531,27,-54,309,81,-306,630,29,-58,307,87,310,31,62,485,32
17 DATA -48,169,80,417,34,-51,269,578,96,35,70,-148,481,36,81,-405,540,38,-61
18 DATA 207,-76,-145,451,95,426,39,-51,204,65,284,42,87,315,45,-61,208,90,-138
19 DATA -186,381,46,92,185,48,96,-135,351,54,87,231,56,-84,-109,307,-428,93,832
20 DATA 97,57,92,140,59,236,78,63,728,95,70,96,143,74,89,105,87,435,96
100 TI$="000000":DO:READ A:DO:READ B:DO:READ C:D=ABS(C*B)/(ABS(B)-A):PRINT
A"←/"ABS(B)"+"ABS(C)"←/"D,:LOOP WHILE C<0:LOOP WHILE B<0:LOOP UNTIL A>75:PRINT TI$"S";
Demain j'essaye mon algorithme sur la prime
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 : 2935
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
Pour éviter de tester toutes les combinaisons, je me suis intéressé à la composition des fractions. En effet on a un total de 10 chiffres à répartir entre les numérateurs et dénominateurs des deux fractions. On peut représenter les fractions par le nombre de chiffres, par exemple 1/2+3548/7096 est de la forme : 1/1+4/4. Pour chaque forme possible j'ai regardé la valeur maximum de la première fraction et celle de la deuxième fraction et j'ai éliminé les formes pour lesquelles la somme des valeurs maximum était inférieure à 1.
Par exemple pour 1/1 + 4/4 la valeur maximum de la première fraction est 8/9, donc la deuxième fraction ne doit pas être inférieur à 1/9, ce qui est vrai avec par exemple 7654/1023.
Par contre pour les fractions de la forme 1/1 + 3/5 la valeur maximum de la deuxième fraction est 987/10234 ce qui est inférieur à 1/9, la somme de deux fractions de cette forme ne peut donc pas valoir 1.
Du coup, si je ne me suis pas trompé, j'ai retenu 6 formes de fractions qui peuvent potentiellement donner 1:
1/1+4/4, 1/2+3/4, 1/3+3/3, 2/2+3/3, 2/2+2/4, 2/3+2/3
On s'aperçoit que si l'on cherche des fractions du type N1/D1 + N2/D2, alors N1 est < à 98 ( 2 chiffres maximum), D1 est < à 987 (3 chiffres maximum) et D2 dépend de la valeur de D1 mais a au moins 3 chiffres.
J'ai donc écrit ce premier programme sur HP Prime qui m'a donné 99 solutions différentes en 2h53mn:
La formule utilisée pour calculer le deuxième numérateur à partir des 3 autres nombres: N2:=(1-N1/D1)*D2 peut générer des erreurs d'arrondi, je l'ai donc remplacée par : N2:=(D1*D2-N1*D2)/D1 qui m'a donné 104 solutions: les 99 précédentes plus 5 nouvelles.
En cherchant à optimiser le temps d'exécution j'ai cherché à générer les différentes permutations des 10 chiffres de 0 à 9 pour éviter de tester des combinaisons où l'on retrouve plusieurs fois le même chiffre.
Pour cela je me suis inspiré de ce programme: print all permutations of a given string en appliquant les astuces ci-dessus pour réduire les combinaisons à tester. Ce qui m'a donné un programme plus long que le précédent mais beaucoup plus rapide puisqu'il trouve les 104 solutions en 44'19'' sur la calculatrice et 1'29'' sur l'émulateur:
Voici la liste des 104 solutions trouvées:
Par exemple pour 1/1 + 4/4 la valeur maximum de la première fraction est 8/9, donc la deuxième fraction ne doit pas être inférieur à 1/9, ce qui est vrai avec par exemple 7654/1023.
Par contre pour les fractions de la forme 1/1 + 3/5 la valeur maximum de la deuxième fraction est 987/10234 ce qui est inférieur à 1/9, la somme de deux fractions de cette forme ne peut donc pas valoir 1.
Du coup, si je ne me suis pas trompé, j'ai retenu 6 formes de fractions qui peuvent potentiellement donner 1:
1/1+4/4, 1/2+3/4, 1/3+3/3, 2/2+3/3, 2/2+2/4, 2/3+2/3
On s'aperçoit que si l'on cherche des fractions du type N1/D1 + N2/D2, alors N1 est < à 98 ( 2 chiffres maximum), D1 est < à 987 (3 chiffres maximum) et D2 dépend de la valeur de D1 mais a au moins 3 chiffres.
J'ai donc écrit ce premier programme sur HP Prime qui m'a donné 99 solutions différentes en 2h53mn:
Code : Tout sélectionner
EXPORT MPO83()
BEGIN
LOCAL N1,N2,D1,D2,s,a,b,t;
PRINT();t:=Time;L1:={};
FOR N1 FROM 1 TO 98 DO
a:=ASC(STRING(N1));
IF EQ(a,UNION(a)) THEN
FOR D1 FROM N1+1 TO 987 DO
b:=ASC(STRING(D1));
IF EQ(b,UNION(b)) THEN
IF EQ(INTERSECT(a,b),{}) THEN
FOR D2 FROM IFTE(D1>99,987,9876) DOWNTO 102 DO
N2:=(1-N1/D1)*D2;
IF (N2>=10) THEN
IF FP(N2)==0 THEN
s:=CHAR(SORT(ASC(""+N1+D1+N2+D2)));
IF s=="0123456789" THEN s:=N1+"/"+D1+"+"+N2+"/"+D2+"=1";L1(0):=s;PRINT(s); END;
END;
END;
END;
END;
END;
END;
END;
END;
PRINT(Time-t);
END;
En cherchant à optimiser le temps d'exécution j'ai cherché à générer les différentes permutations des 10 chiffres de 0 à 9 pour éviter de tester des combinaisons où l'on retrouve plusieurs fois le même chiffre.
Pour cela je me suis inspiré de ce programme: print all permutations of a given string en appliquant les astuces ci-dessus pour réduire les combinaisons à tester. Ce qui m'a donné un programme plus long que le précédent mais beaucoup plus rapide puisqu'il trouve les 104 solutions en 44'19'' sur la calculatrice et 1'29'' sur l'émulateur:
Code : Tout sélectionner
LOCAL st;
check_ff(a,b,c)
BEGIN
LOCAL d,s;
d:=c*b/(b-a);
IF fp(d)==0 THEN
IF d>99 THEN
IF CHAR(SORT(ASC(""+a+b+c+d)))=="0123456789" THEN
s:=a+"/"+b+"+"+c+"/"+d+"=1";
IF POS(L1,s)==0 THEN PRINT(s);L1(0):=s; END;
END;
END;
END;
END;
check(s)
BEGIN
LOCAL a,b,c;
a:=EXPR(s(1,1));b:=EXPR(s(2,1));c:=EXPR(s(3,4)); // 1/1 + 4/4
IF b>0 THEN check_ff(a,b,c) END;
a:=EXPR(s(1,1));b:=EXPR(s(2,2));c:=EXPR(s(4,3)); // 1/2 + 3/4
IF b>9 THEN check_ff(a,b,c) END;
a:=EXPR(s(1,1));b:=EXPR(s(2,3));c:=EXPR(s(5,3)); // 1/3 + 3/3
IF b>99 THEN check_ff(a,b,c) END;
a:=EXPR(s(1,2));b:=EXPR(s(3,2));c:=EXPR(s(5,3)); // 2/2 + 3/3
IF b>9 THEN check_ff(a,b,c) END;
a:=EXPR(s(1,2));b:=EXPR(s(3,2));c:=EXPR(s(5,2)); // 2/2 + 2/4
IF b>9 THEN check_ff(a,b,c) END;
a:=EXPR(s(1,2));b:=EXPR(s(3,3));c:=EXPR(s(6,2)); // 2/3 + 2/3
IF b>99 THEN check_ff(a,b,c) END;
END;
// Function to swap characters in a string
swap(s,x,y)
BEGIN
LOCAL temp;
temp := s(x,1);
s:=REPLACE(s,x,s(y,1));
s:=REPLACE(s,y,temp);
RETURN s;
END;
// Function to check permutations of string
// This function takes three parameters:
// 1. String
// 2. Starting index of the string
// 3. Ending index of the string.
permute(s,l,r)
BEGIN
LOCAL j,k;
IF (l == r-2) THEN
check(s);
ELSE
k:=l+st;st:=0;
FOR j FROM k TO r DO
permute(swap(s,l,j), l+1, r);
END;
END;
END;
// Main program
EXPORT MPO83b()
BEGIN
LOCAL str:="0123456789",t;
t:=Time;
PRINT();
st:=1;L1:={};
permute(str, 1, DIM(str));
PRINT (Time-t);
END;
Code : Tout sélectionner
10/28+369/574=1
10/45+287/369=1
10/45+728/936=1
10/96+473/528=1
1/2+3485/6970=1
1/2+3548/7096=1
1/2+3845/7690=1
1/2+4538/9076=1
1/2+4685/9370=1
1/2+4853/9706=1
1/2+4865/9730=1
1/2+4835/9670=1
12/54+609/783=1
12/60+748/935=1
12/96+357/408=1
12/96+735/840=1
13/26+485/970=1
13/52+678/904=1
1/4+7365/9820=1
15/30+486/972=1
16/32+485/970=1
1/6+7835/9402=1
1/7+4362/5089=1
17/89+504/623=1
18/90+372/465=1
18/90+276/345=1
19/57+308/462=1
19/58+273/406=1
21/96+375/480=1
2/4+3079/6158=1
24/63+507/819=1
24/96+531/708=1
2/6+3190/4785=1
27/54+309/618=1
2/7+5940/8316=1
2/7+6810/9534=1
27/81+630/945=1
27/81+306/459=1
2/9+5803/7461=1
29/58+307/614=1
29/87+310/465=1
3/127+496/508=1
31/62+485/970=1
32/48+169/507=1
32/80+417/695=1
34/51+269/807=1
34/578+96/102=1
35/70+481/962=1
35/70+148/296=1
3/6+2079/4158=1
3/6+2709/5418=1
3/6+2907/5814=1
3/6+4851/9702=1
3/6+1485/2970=1
36/81+405/729=1
36/81+540/972=1
38/61+207/549=1
38/76+451/902=1
38/76+145/290=1
38/95+426/710=1
39/51+204/867=1
39/65+284/710=1
42/87+315/609=1
4/356+792/801=1
4/5+1278/6390=1
4/5+1872/9360=1
45/61+208/793=1
45/90+381/762=1
45/90+138/276=1
45/90+186/372=1
46/92+185/370=1
48/96+351/702=1
48/96+135/270=1
5/104+693/728=1
54/87+231/609=1
56/428+93/107=1
56/832+97/104=1
56/84+307/921=1
56/84+109/327=1
57/204+98/136=1
57/92+140/368=1
59/236+78/104=1
6/324+795/810=1
63/728+95/104=1
6/534+792/801=1
74/89+105/623=1
7/54+893/1026=1
70/96+143/528=1
78/104+59/236=1
79/83+60/1245=1
7/9+1352/6084=1
7/9+1208/5436=1
8/10+729/3645=1
8/10+927/4635=1
8/512+693/704=1
87/435+96/120=1
9/12+876/3504=1
93/107+56/428=1
9/351+684/702=1
95/104+63/728=1
96/120+87/435=1
96/102+34/578=1
97/104+56/832=1
98/136+57/204=1