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

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

Message par C.Ret »

Merci zalpm pour ce partage de méthode. Il y a une ou deux idées intéressantes qui vont me permettre d'améliorer mon algorithme.

Mais aussi quelques indices qui me donne l'idée d'une approche radicalement différente liée essentiellement au format des combinaisons de fraction.


En tout cas, c'est sûr, il doit y avoir moyen de faire mieux que 6 jours et 4 secondes :)
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 »

J’ai optimisé mon premier programme pour HP Prime (celui sans récursion) en optimisant la boucle intérieure :
  • Remplacement de D2 par N2 qui a moins de chiffres, pour réduire le nombre de boucles
  • Détermination des valeurs minimum et maximum de N2 en fonction du nombre de chiffres de N1 et D1 (suivant la liste des formes de fractions retenues)
  • Optimisation du calcul de D2
Du coup il trouve maintenant les 104 solutions en 25’53’’ (au lieu de 2h53’ précédemment), ce qui est même significativement plus rapide que le programme parcourant de manière récursive les différentes combinaisons des chiffres de 0 à 9 (44'19'').

Code : Tout sélectionner

EXPORT MPO83()
BEGIN
  LOCAL N1,N2,D1,D2,s,a,b,t;
  LOCAL d,j,k,m1,m2;
  m1:=[[1023,102,102],[0,10,10]];                          // Valeur minimum de N2 en fonction du nombre de chiffres de N1 et D1
  m2:=[[9876,987,987],[0,987,98]];                         // Valeur maximum de N2 en fonction du nombre de chiffres de N1 et D1
  PRINT();t:=Time;L1:={};HFormat:=0;                       // Initialisation, format standard pour la conversion des entiers en string 
  FOR N1 FROM 1 TO 98 DO                                   // Le premier numérateur comporte 1 ou 2 chiffres
    j:=XPON(N1)+1;                                         // Nombre de chiffres de N1
    a:=ASC(STRING(N1));                                    // Liste des codes ASCII de chaque digit du numérateur
    IF EQ(a,UNION(a)) THEN                                 // Teste si tous les digits de N1 sont différents ( UNION(a) supprime les éléments dupliqués )
      FOR D1 FROM N1+1 TO 987 DO                           // Le premier dénominateur doit être supérieur au numérateur et comporter au maximum trois chiffres
        k:=XPON(D1)+1;                                     // Nombre de chiffres de D1
        b:=ASC(STRING(D1));                                // Liste des codes ASCII de chaque digit du dénominateur 
        IF EQ(b,UNION(b)) THEN                             // Teste si tous les digits de D1 sont différents ( UNION(a) supprime les éléments dupliqués ) 
          IF EQ(INTERSECT(a,b),{}) THEN                    // Teste si tous les digits sont différents entre N1 et D1
            d:=D1-N1;                                      // Calcul de D1-N1 pour préparer le calcul de D2 dans la boucle suivante
            FOR N2 FROM m1(j,k) TO m2(j,k) DO              // Les valeurs min et max du deuxième numérateur dépendent du nombre de chiffres de N1 et D1
              D2:= D1*N2/d;                                // Calcul du deuxième dénominateur à partir de N1, D1 et N2 pour que la somme des fractions soit 1
              IF FP(D2)==0 THEN                            // Test si D2 est entier ...
                IF (D2>=100) THEN                          //   ... et s'il a au moins trois chiffres
                  s:=CHAR(SORT(ASC(""+N1+D1+N2+D2)));      // Chaine de charactères comportant l'ensemble des digits de N1,D1,N2,D2 triés par ordre croissant 
                  IF s=="0123456789" THEN L1(0):=PRINT(N1+"/"+D1+"+"+N2+"/"+D2+"=1"); END;      // Si on a tous les chiffres de 0 à 9 on a une solution     
                END;           
              END;
            END;
          END;
        END; 
      END;
    END;
  END;
  PRINT(Time-t);
END;
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 »

Voilà un algorithme qui ressemble fort à celui que j'ai utilisé sur mon C= 128D !!

Avec cependant deux points peu différents et qui font toute la différence:
  • l'intervalle sur N1 est considérablement réduit, celui sur D1 un peu augmenté.
  • Toutes les valeurs sont parcourue et les répétitions impossible des chiffres sont testées à postèriori
Pour éviter de déterminer les doublons j'avais donné un rôle diffèrent entre N1/D1 (qui devait être inférieure ou égale à 1/2 ) et à N2/D2 (qui était donc inférieur ou égale à 0.5). IL en découlait que N1 < D1 <= 2*N1 et D2 > 2*N2, par contre l'intervalle que je parcourrais sur N1 était de ce fait bien trop étendu de 1 à 9876.


Ensuite, pour gagner un peu de temps, je ne boucle pas sur toutes les valeurs mais utilise un tableau pour mémoriser les chiffres déjà utilisés.

Les valeurs N1, D1 et D2 sont construites à partir de ce tableau (composé de 10 "flags" ) afin de n'utiliser qu'une fois chaque chiffre.
Pour cela, trois sous-programme sont utilisés :
  • INIT: qui permet d'initialiser une des variables à une valeur donnée en argument. Le résultat dans la variable ne sera égal à l'argument que si tous les chiffres nécessaires sont disponibles. Sinon, la variable sera initialisée à la première valeur possible supérieure à l'argument. Un indicateur d'erreur E signale les cas où l'initialisation n'a pu se faire (e% = -1), si la variable est égale à la valeur demandé (e% = 0) ou supérieur (e% = 1 )
  • INCR: qui permet d'incrémenter la variable vers la prochaine valeur numérique possible en fonction des chiffres encore disponibles. L'indicateur d'erreur e% est utilisé là aussi pour indiquer les impossibilités
  • CLEAR:qui vide la variable afin de rendre ses chiffres disponibles à nouveau
Ces trois sous-programme déterminent les chiffres disponibles à partir du même tableau F%() , utilisent le même indicateur d'erreur e% et partage les mêmes lignes de codes pour les opérations élémentaires sur les variables. A chaque instant, le nombre de chiffres restant et celui dans chaque variable sont connus car mis à jour au fur et à mesure par ces trois routines.

Une boucle FOR N1 = a TO b : ... : NEXT N1 devient alors une boucle INIT(N1,a) : DO UNTIL e%<0 OR N1>b : … : INCR(N1):LOOP:CLEAR(N1)

La source d'imprécision de mon algorithme provenait du fait que je calculais le coefficient K = B / ( B-A ) __ c'est à dire K = D1 / ( D1 - N1 ) ) __ ce qui me donnait directement la valeur pour D : D = C * K __ c'est à dire D2 = N2 * D1 / ( D1 - N1 ) __ Malheureusement, un test D = INT(D) était présent également et avec l'erreur d'arrondi sur K cela me fait passer à coté de certaines fractions.

Le coefficient K était également utilisé pour déterminer l'intervalle à scanner pour C __ c'est à dire N2 __ En effet connaissant le nombre de chiffres t% encore disponible dans la tableau F(), l'intervalle [ c0 c1 [ peut être déterminé en fonction du nombre de chiffres c% composant C, du nombre de chiffre encore disponible t% et du coefficient K à partir des deux formules : c0 = CEIL( MAX( 10^(c%-1) , (10^(t%-c%-1))/K )) et c1 = FLOOR(MIN( (10^c%)-1 , (10^(t%-c%)-1)/K )).

Pour chaque fraction A/B et donc pour un K donné, il n'existe qu'une seule valeur c% pour laquelle l'intervalle [ c0 c1 [ existe c'est à dire pour laquelle on a c1>c0.


Mon nouvel algorithme sera donc :

Code : Tout sélectionner

DIM F(0..9)=0:t%=10:INIT(A,1): DO                     // -------------------------------------Boucle sur A
:  INIT(B,A): DO UNTIL B>999 OR e%<0                  // -------------------------------------Boucle sur B
:  :  n=B-A : FOR k=1 TO t%-1                         // ----------------------------Détermine taille de C
:  :  :  c0=CEIL( MAX( 10^k/10 , B*10^(t%-k-1)/n ))  :  c1=FLOOR(MIN( 10^k-1  , B*(10^(t%-k)-1)/n ))
:  :  :  IF c1>c0 THEN                                // -----------------------------Intervalle pour C ok
:  :  :  :  INIT(C,c0): DO UNTIL C>c1 OR e%<0         // -------------------------------------Boucle sur C
:  :  :  :  :  d=C*B/n:IF A*d+C*B == B*d THEN         // --------------------------------Calcul et teste D
:  :  :  :  :  :  INIT(D,d):IF e%=0 AND t%=0 THEN PRINT A"/"B" + "C"/"D" = 1", 
:  :  :  :  :  :  CLEAR(D):ENDIF                      // -----------------------------------------Efface D
:  :  :  INCR(C):LOOP:CLEAR(C):EXIT FOR:ENDIF         // ----Boucle puis efface C et sort recherche taille
NEXT k:INCR(B):LOOP:CLEAR(B):INCR(A):LOOP UNTIL A>99  // ----------Boucle puis efface B avant boucle sur A
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 : 01 juin 2018 09:04 Ensuite, pour gagner un peu de temps, je ne boucle pas sur toutes les valeurs mais utilise un tableau pour mémoriser les chiffres déjà utilisés.

Les valeurs N1, D1 et D2 sont construites à partir de ce tableau (composé de 10 "flags" ) afin de n'utiliser qu'une fois chaque chiffre.
Pour cela, trois sous-programme sont utilisés
Je me suis posé la question de construire les valeurs D1 et N2 à partir des chiffres non utilisés, mais je me demande si cette mécanique ne prend pas au final beaucoup de temps et si le gain est vraiment important. J'aimerais bien voir ce que donne ton algorithme sur la HP Prime.

Je suis resté sur mon algorithme avec une nouvelle optimisation: pour limiter le nombre de valeurs à tester pour le deuxième numérateur (N2), j’utilise la fonction QPI() qui me retourne la fraction réduite correspondant à (1-N1/D1) dont j’extrais la valeur minimum de N2 et de D2, il suffit alors de tester les différents multiples de cette fraction réduite jusqu’à atteindre la valeur max de N2.

La durée d’exécution est réduite de 25’ à 6’15” soit un facteur 4 ! (29 fois plus rapide que la première version de mon programme).

Code : Tout sélectionner

EXPORT MPO83()
BEGIN
  LOCAL N1,N2,D1,D2,a,b,t,ld;
  LOCAL j,k,m1,m2,n,q,s1,s2;

  m1:=[[1023,102,102],[0,10,10]];                          // Valeur minimum de N2 en fonction du nombre de chiffres de N1 et D1
  m2:=[[9876,987,987],[0,987,98]];                         // Valeur maximum de N2 en fonction du nombre de chiffres de N1 et D1
  ld:="0123456789";                                        // Chaine des 10 chiffres de 0 à 9
  PRINT();t:=Time;L1:={};HFormat:=0;                       // Initialisation, format standard pour la conversion des entiers en string
  FOR N1 FROM 1 TO 98 DO                                   // Le premier numérateur comporte 1 ou 2 chiffres
    a:=ASC(STRING(N1));                                    // Liste des codes ASCII de chaque digit du numérateur
    IF SIZE(a)==SIZE(UNION(a)) THEN                        // Teste si tous les digits de N1 sont différents ( UNION(a) supprime les éléments dupliqués )
      j:=XPON(N1)+1;                                       // Nombre de chiffres de N1
      s1:=SUPPRESS(ld,STRING(N1));                         // Supprime des 10 chiffres de 0 à 9 ceux utilisé par N1
      FOR D1 FROM N1+1 TO 987 DO                           // Le premier dénominateur doit être supérieur au numérateur et comporter au maximum trois chiffres
        b:=ASC(STRING(D1));                                // Liste des codes ASCII de chaque digit du dénominateur 
        IF SIZE(b)==SIZE(UNION(b)) THEN                    // Teste si tous les digits de D1 sont différents 
          IF SIZE(INTERSECT(a,b))==0 THEN                  // Teste si tous les digits sont différents entre N1 et D1
            k:=XPON(D1)+1;                                 // Nombre de chiffres de D1
            s2:=SUPPRESS(s1,STRING(D1));                   // Supprime de la chaine s1 les chiffres utilisé par D1
            q:=QPI(1-N1/D1);N2:=numer(q);D2:=denom(q);     // Fraction réduite N2/D2, qui va servir pour limiter les valeurs de N2 à tester
            n:=CEILING(m1(j,k)/N2);                        // Valeur minimum de départ pour le multiplicateur de la fraction réduite
            WHILE N2*n<=m2(j,k) DO                         // On teste les différents multiples de la fraction réduite jusqu'à la valeur max du numérateur
              IF EQ(s2,CHAR(SORT(ASC(""+N2*n+D2*n)))) THEN L1(0):=PRINT(N1+"/"+D1+"+"+N2*n+"/"+D2*n+"=1"); END;      // Si on a tous les chiffres de 0 à 9 on a une solution   
              n:=n+1; 
            END;           
          END;
        END; 
      END;
    END;
  END;
  PRINT(Time-t);
END;
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 »

zpalm a écrit : 01 juin 2018 21:49 ... J'aimerais bien voir ce que donne ton algorithme sur la HP Prime...
Je n'ai pas eu le temps comme prévu cette fin de semaine.
Je vais le faire d'ici lundi soir.

Concernant le temps, je ne sais pas, l'astuce est d'avoir une sous-routine INCR qui est rapide. Les deux autres sont moins sollicitées.
zpalm a écrit : 01 juin 2018 21:49 Je suis resté sur mon algorithme avec une nouvelle optimisation: pour limiter le nombre de valeurs à tester pour le deuxième numérateur (N2), j’utilise la fonction QPI() qui me retourne la fraction réduite correspondant à (1-N1/D1) dont j’extrais la valeur minimum de N2 et de D2, il suffit alors de tester les différents multiples de cette fraction réduite jusqu’à atteindre la valeur max de N2.

La durée d’exécution est réduite de 25’ à 6’15” soit un facteur 4 ! (29 fois plus rapide que la première version de mon programme).
C'est ce que fait (en partie) mon algorithme lors du calcul de C0 et C1.


Dans mon code initial, la fonction QPI(a,b) était calculée K = B / ( B - A ) et mémorisée dans la variable K dont l'arrondi catastrophique des CBM 8 bits m'ont joué de vilains tours ! En quelque sorte K est l'inverse d'u QPI().

Par contre, je n'avance pas selon les multiples, il faut que j'y réfléchisse. Initialement je ne l'ai pas fait car je voulais utiliser une unique sous-routine INCR.

Pour A et B donnés, je calcule K = B / (B-A) ce qui me permet de déterminer l'intervalle [C0 C1[ pour C qui permet d'utiliser les t% chiffres restant.
Ensuite, pour chaque C parcouru dans l'intervalle [ C0 C1 [, je calculais D = K * C et vérifiais que D est entier (puisque je ne parcours pas C selon les multiples) et que tous les chiffres sont utilisés (t%=0) et que D est directement correctement construit (e%=0).


Cet algo est efficace, je suis passé de 6 jours 4 secondes à moins de 36h sur mon Commodore (heureusement émulé).



P.S.: Il y a des doublons dans la liste des fractions données ci-dessus, en particulier les fractions au format ##/### + ##/### = 1 qui apparaissent deux fois, une fois écrites a/b + c/d = 1 et une fois c/d + a/b = 1
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 : 02 juin 2018 15:09P.S.: Il y a des doublons dans la liste des fractions données ci-dessus, en particulier les fractions au format ##/### + ##/### = 1 qui apparaissent deux fois, une fois écrites a/b + c/d = 1 et une fois c/d + a/b = 1
Ah oui, je n'avais pas remarqué qu'il y avait 7 doublons... voici la liste des 97 fractions uniques:

Code : Tout sélectionner

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+4835/9670=1
1/2+4853/9706=1
1/2+4865/9730=1
1/4+7365/9820=1
1/6+7835/9402=1
1/7+4362/5089=1
2/4+3079/6158=1
2/6+3190/4785=1
2/7+5940/8316=1
2/7+6810/9534=1
2/9+5803/7461=1
3/6+1485/2970=1
3/6+2079/4158=1
3/6+2709/5418=1
3/6+2907/5814=1
3/6+4851/9702=1
3/127+496/508=1
4/5+1278/6390=1
4/5+1872/9360=1
4/356+792/801=1
5/104+693/728=1
6/324+795/810=1
6/534+792/801=1
7/9+1208/5436=1
7/9+1352/6084=1
7/54+893/1026=1
8/10+729/3645=1
8/10+927/4635=1
8/512+693/704=1
9/12+876/3504=1
9/351+684/702=1
10/28+369/574=1
10/45+287/369=1
10/45+728/936=1
10/96+473/528=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
15/30+486/972=1
16/32+485/970=1
17/89+504/623=1
18/90+276/345=1
18/90+372/465=1
19/57+308/462=1
19/58+273/406=1
21/96+375/480=1
24/63+507/819=1
24/96+531/708=1
27/54+309/618=1
27/81+306/459=1
27/81+630/945=1
29/58+307/614=1
29/87+310/465=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+148/296=1
35/70+481/962=1
36/81+405/729=1
36/81+540/972=1
38/61+207/549=1
38/76+145/290=1
38/76+451/902=1
38/95+426/710=1
39/51+204/867=1
39/65+284/710=1
42/87+315/609=1
45/61+208/793=1
45/90+138/276=1
45/90+186/372=1
45/90+381/762=1
46/92+185/370=1
48/96+135/270=1
48/96+351/702=1
54/87+231/609=1
56/84+109/327=1
56/84+307/921=1
56/428+93/107=1
56/832+97/104=1
57/92+140/368=1
57/204+98/136=1
59/236+78/104=1
63/728+95/104=1
70/96+143/528=1
74/89+105/623=1
79/83+60/1245=1
87/435+96/120=1
et les 7 doublons supprimés:

Code : Tout sélectionner

96/102+34/578=1
93/107+56/428=1
97/104+56/832=1
98/136+57/204=1
78/104+59/236=1
95/104+63/728=1
96/120+87/435=1
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 n'ai pas eut le temps de poster avant de partir pour le 22ième mini-pokéticaire.

Mais j'ai pû faire une version pour HP-Prime de mon programme pour Commodore C128D.

C'est une véritable usine à gaz. en fait, le code BASIC source utilise de façon assez simple des tableaux pour les valeurs et nombre de chiffre des numérateurs et dénominateurs ainsi que pour mémoriser les chiffres utilisés. L'idée était d'être très proche des pratique des RPN classique ce qui aurait permis d'adapter facilement au adressage indirect STO/RCL i et autres DSZ/IDZ ou DSG/ISG de ces systèmes.

Evidemment, le Commodore aurait pu fonctionner plus vite en utilisant les fonctions chaines de caractères LEFTRIGHT LEN et autres astuce dont notamment l'instruction de recherche de chaine INSTR.


Ce qui fait que le code pour la prime est assez lourd et inutilement alambiqué. Il permet cependant de trouver 96 couples de fractions fabuleuses en seulement 13'44". En cherchant à améliorer cette performance, je me retrouve à utiliser les instructions sur les UNIONS et INTERSECTION de liste comme le fait zpalm et donc à produire un code très similaire.
En fait utiliser des listes pour les variables et le chiffres utilisé rend les opérations plus lente que de compter normalement et contrôler à postériori la validité des solutions trouvées.

Par ailleurs le nombre de solutions trouvées dépend bien trop des erreur de d'arrondi et de la façon de faire certains calculs.

Ce qui m'a donné l'idée de changer ma façon de faire; de baser ma recherche sur la mémorisation des chiffres utilisées, mais ne plus parcourir les intervalles en incrémentant brutalement. Mais de baser la recherche sur le rapport K = B / (B-A) et les rapport limites C/D que l'on peut faire avec les chiffres restant (basé sur les valeur exacte de MIN(L) et MAX(L) (L étant le nombre de chiffre du numérateur ou dénominateur).
Je ne calcule plus D en fonction de A Bet C, mais cherche à construire simultanément C et D avec les quelques chiffres encore disponibles afin d'obtenir le rapport K.
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 »

J’ai ajouté la détection de doublons et j’ai un peu optimisé l’exécution de la boucle intérieure sans changer l’algorithme, ce qui me permet d’obtenir maintenant les 97 solutions en 3’57” (au lieu de 6’15”). Par contre le code est un peu plus long que précédemment ...

Code : Tout sélectionner

EXPORT MPO83()
BEGIN
  LOCAL N1,N2,D1,D2,a,b,t,ld;
  LOCAL j,k,m1,m2,n,q,s1,s2;
  LOCAL c,d;
 
  m1:=[[1023,102,102],[0,10,10]];                          // Valeur minimum de N2 en fonction du nombre de chiffres de N1 et D1
  m2:=[[9876,987,987],[0,987,98]];                         // Valeur maximum de N2 en fonction du nombre de chiffres de N1 et D1
  ld:="0123456789";                                        // Chaine des 10 chiffres de 0 à 9
  PRINT();t:=Time;L1:={};HFormat:=0;                       // Initialisation, format standard pour la conversion des entiers en string
  FOR N1 FROM 1 TO 98 DO                                   // Le premier numérateur comporte 1 ou 2 chiffres
    a:=ASC(STRING(N1));                                    // Liste des codes ASCII de chaque digit du numérateur
    IF SIZE(a)==SIZE(UNION(a)) THEN                        // Teste si tous les digits de N1 sont différents ( UNION(a) supprime les éléments dupliqués )
      j:=XPON(N1)+1;                                       // Nombre de chiffres de N1
      s1:=SUPPRESS(ld,STRING(N1));                         // Supprime des 10 chiffres de 0 à 9 ceux utilisé par N1
      FOR D1 FROM N1+1 TO 987 DO                           // Le premier dénominateur doit être supérieur au numérateur et comporter au maximum trois chiffres
        b:=ASC(STRING(D1));                                // Liste des codes ASCII de chaque digit du dénominateur
        IF SIZE(b)==SIZE(UNION(b)) THEN                    // Teste si tous les digits de D1 sont différents
          IF SIZE(INTERSECT(a,b))==0 THEN                  // Teste si tous les digits sont différents entre N1 et D1
            k:=XPON(D1)+1;                                 // Nombre de chiffres de D1
            s2:=SUPPRESS(s1,STRING(D1)); c:=SIZE(s2);      // Supprime de la chaine s1 les chiffres utilisé par D1
            q:=QPI(1-N1/D1);N2:=numer(q);D2:=denom(q);     // Fraction réduite N2/D2, qui va servir pour limiter les valeurs de N2 à tester
            FOR n FROM CEILING(m1(j,k)/N2) TO FLOOR(m2(j,k)/N2) DO          // Teste les  multiples de la fraction réduite de la valeur min à la valeur max de N2
              d:=XPON(N2*n)+XPON(D2*n)+2;                                   // Nombre de chiffres du multiple de la faction réduite
              IF c<d THEN BREAK; END;                                       // Si plus de chiffres que ce qui reste, on s’arrête
              IF c==d THEN                                                  // Si on a le bon nombre de chiffres ...
                IF EQ(s2,CHAR(SORT(ASC(""+N2*n+D2*n)))) THEN                // ... et tous les chiffres de 0 à 9 on a une solution 
                  IF NOT POS(L1,N2*n+"/"+D2*n+"+"+N1+"/"+D1+"=1") THEN      // On filtre les solutions en double
                    L1(0):=PRINT(N1+"/"+D1+"+"+N2*n+"/"+D2*n+"=1");         // On affiche la solution et on l’ajoute à L1
                  END; 
                END;
              END;
            END;          
          END;
        END;
      END;
    END;
  END;
  PRINT(Time-t);
END;
Répondre

Retourner vers « Tous les Pockets »