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
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
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
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.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2936
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
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
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;
- 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
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:
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 :
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 :
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
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
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.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2936
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
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.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 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;
- 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 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.
C'est ce que fait (en partie) mon algorithme lors du calcul de C0 et C1.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).
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.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2936
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
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
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
- 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 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.
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.
- zpalm
- Fonctionne à 9600 bauds
- Messages : 2936
- Enregistré le : 03 mai 2008 15:33
- Localisation : Grenoble
Re: Misez p'tit Optimisez n°83 : Fabuleuses fractions
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;