Misez p'tit Optimisez n°83 : Fabuleuses fractions

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

Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par C.Ret »

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 :
mpo83_hp_1.png
mpo83_hp_1.png (2.65 Kio) Vu 14230 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.
Sharpounet
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 28
Enregistré le : 14 avr. 2017 14:45
Localisation : Paris

Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par Sharpounet »

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
Avatar du membre
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5622
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par ledudu »

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.

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
jxano
Fonctionne à 2400 bauds
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

Message par jxano »

Beau problème "fermé" comme je les aime.
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
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).
Programmeur abscons.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par C.Ret »

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é.
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.
Sharpounet
Fonctionne à 75 bauds
Fonctionne à 75 bauds
Messages : 28
Enregistré le : 14 avr. 2017 14:45
Localisation : Paris

Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par Sharpounet »

@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 !
jxano
Fonctionne à 2400 bauds
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

Message par jxano »

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.
Avatar du membre
ledudu
Fonctionne à 14400 bauds
Fonctionne à 14400 bauds
Messages : 5622
Enregistré le : 26 mars 2009 13:07
Localisation : Ile de France
Contact :

Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par ledudu »

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. :oops:
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par dprtl »

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 :

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"
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 :

Image

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.
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par C.Ret »

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 :x
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.
Avatar du membre
dprtl
Fonctionne à 1200 bauds
Fonctionne à 1200 bauds
Messages : 463
Enregistré le : 27 janv. 2013 00:26
Localisation : Strasbourg
Contact :

Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par dprtl »

C.Ret a écrit : 28 mai 2018 20:28 Ce brave et laborieux Commodore doit en manquer une à cause de sa prodigieuse tendance à faire des erreurs d'arrondi :x
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
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par C.Ret »

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 :
Fichiers joints
2018-05-28_r.png
2018-05-28_r.png (50.09 Kio) Vu 13878 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.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2917
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par zpalm »

C.Ret a écrit : 28 mai 2018 23:18 j'obtiens maintenant les 95 paires de fractions fabuleuses en moins de 5 secondes :
8O 8O 8O Wahou !! moins de 5s !! Je m'échine sur un programme pour ma HP Prime qui me donne 99 paires en 2h53mn :(
Avatar du membre
C.Ret
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 3400
Enregistré le : 31 mai 2008 23:43
Localisation : N 49°22 E 6°10

Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par C.Ret »

OUi, mais c'est de la gruge, c'est en réalité exactement 6 jours et 4 secondes !!!

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";
Mais, c'est le plus court et donc le plus adapté à un MPO.

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.
Avatar du membre
zpalm
Fonctionne à 9600 bauds
Fonctionne à 9600 bauds
Messages : 2917
Enregistré le : 03 mai 2008 15:33
Localisation : Grenoble

Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions

Message par zpalm »

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:

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;
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:

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;
Voici la liste des 104 solutions trouvées:

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
Répondre

Retourner vers « Tous les Pockets »