B Le compte est bon en un clin d'oeil
Description
Bonjour,
Comme indiqué dans l'article "A Le compte est bon sur une page", voici une tentative d'évincer une bonne partie des solutions "équivalentes et longues", et de gagner en temps de calcul.
Le code obtenu tient sur le seul fichier "ClindOeil.html" de moins de 3 Ko.
A Le compte est bon sur une page.
Cette version provisoire calcule et affiche encore quelques "doublons" et ignore toujours les solutions approchantes.
Beaucoup de doublons proviennent du fait que certaines opérations sont commutatives (a+b=b+a, a×b=b×a, ...).
Une possibilité d'en élimer beaucoup est de ne considérer certaines opérations que lorsque a <= b.
Adaptons la fonction Cal(nbr,txt), tout en tenant compte des spécificités des différentes opérations:
Résultats:
Le nombre d'appels à la fonction Cal() diminue de 911197 à 187007 !
Le temps de calcul s'améliore bien, mais le nombre de doublons reste encore souvent trop grand !
Tenons compte de la "qualité" des solutions, c'est-à-dire ne retenons que celles qui sont "minimes" ou qui utilisent le moins d'opérations ou de plaques possibles.
Observez les instructions qui utilisent la nouvelle variable niv:
Pour simplifier l'écriture, j'ai introduit les deux fonctions Sol(op) et Recur(op) imbriquées dans Cal(nbr,txt).
Imbriquées (nested) pour éviter de passer en arguments toutes les variables de la fonction Cal(nbr,txt) utilisées.
Quand on a trouvé une solution (r==res) avec une certaine opération, on appelle Sol(op) qui, lorsque le niveau est meilleur, met à jour niv et supprime toutes les solutions plus longues trouvées auparavant.
Sinon, on essaye de trouver un meilleur résultat en appellant récursivement Cal(nbr,txt) à l'aide de Recur(op).
Résultats:
Avec cet exemple, le nombre de solutions affichées est "raisonnable" et le nombre d'appels à Cal() se réduit à 14890 !
Les doublons qui subsistent sont principalement dus à l'associativité d'opérations telles que
(a+b)+c = a+(b+c), (a×b)×c = a×(b×c), ...
et à la présence de plaques identiques au tirage ou pendant le calcul.
Une élimination plus sévère nécessiterait une "gestion" de l'ensemble des résultats partiels.
Remarques:
Les instructions qui concernent la variable nCal servent à compter le nombre d'appels à la fonction Cal() et sont donc provisoires.
La solution triviale (sans aucune opération) d'un tirage qui contient 100 avec le résultat 100 n'est pas détectée.
La prochaine extension "C Le compte est bon ou presque" traitera également les résultats les plus proches lorsqu'aucune solution exacte n'est trouvée.
Merci et bonne lecture ...
Testé avec: Chrome, Explorer, Firefox, Opera, Safari
Comme indiqué dans l'article "A Le compte est bon sur une page", voici une tentative d'évincer une bonne partie des solutions "équivalentes et longues", et de gagner en temps de calcul.
Le code obtenu tient sur le seul fichier "ClindOeil.html" de moins de 3 Ko.
A Le compte est bon sur une page.
Cette version provisoire calcule et affiche encore quelques "doublons" et ignore toujours les solutions approchantes.
Amélioration "commutativité"
Beaucoup de doublons proviennent du fait que certaines opérations sont commutatives (a+b=b+a, a×b=b×a, ...).
Une possibilité d'en élimer beaucoup est de ne considérer certaines opérations que lorsque a <= b.
Adaptons la fonction Cal(nbr,txt), tout en tenant compte des spécificités des différentes opérations:
function Cal(nbr,txt) {
var n=nbr.length-2,r;
for (var i=0,a=nbr[i]; i<nbr.length; a=nbr[++i]) {
var nb=nbr.slice(0);
nb.splice(i,1); // nbr sans l'élément a d'index i
for (var j=0,b=nb[j]; j<=n; b=nb[++j]) {
if (b>=a) { // évite beaucoup de doublons dus à la permutativité
if ((r=b+a)==res) str+=txt+b+"+"+a+"="+r;
else if (n>0) {nb[j]=r; Cal(nb,txt+b+"+"+a+"="+r+", "); nb[j]=b;}
if (a!=b) { // évite b-a=0
if ((r=b-a)==res) str+=txt+b+"-"+a+"="+r;
else if (n>0) {nb[j]=r; Cal(nb,txt+b+"-"+a+"="+r+", "); nb[j]=b;}
}
if (a>1) { // évite la multiplication et division par 1
if ((r=b*a)==res) str+=txt+b+"×"+a+"="+r;
else if (n>0) {nb[j]=r; Cal(nb,txt+b+"×"+a+"="+r+", "); nb[j]=b;}
if (b%a==0) { // division entière
if ((r=b/a)==res) str+=txt+b+"÷"+a+"="+r;
else if (n>0) {nb[j]=r; Cal(nb,txt+b+"÷"+a+"="+r+", "); nb[j]=b;}
}
}
}
}
}
}
Résultats:
24 plaques: [1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,25,50,75,100] 6 tirages: [1,10,50,100,1,5] 940 50+1=51, 100-1=99, 99-5=94, 94×10=940 50+1=51, 5+1=6, 100-6=94, 94×10=940 50+1=51, 100-5=95, 95-1=94, 94×10=940 50-1=49, 100-1=99, 99-5=94, 94×10=940 50-1=49, 5+1=6, 100-6=94, 94×10=940 50-1=49, 100-5=95, 95-1=94, 94×10=940 100-1=99, 99×10=990, 990-50=940 100-1=99, 99×10=990, 5+1=6, 990-50=940 100-1=99, 99×10=990, 5-1=4, 990-50=940 100-1=99, 50+1=51, 99-5=94, 94×10=940 100-1=99, 50-1=49, 99-5=94, 94×10=940 100-1=99, 5+1=6, 99×10=990, 990-50=940 100-1=99, 5-1=4, 99×10=990, 990-50=940 100-1=99, 99-5=94, 94×10=940 100-1=99, 99-5=94, 50+1=51, 94×10=940 100-1=99, 99-5=94, 50-1=49, 94×10=940 1+1=2, 50+10=60, 100×2=200, 200×5=1000, 1000-60=940 1+1=2, 50+10=60, 5×2=10, 100×10=1000, 1000-60=940 1+1=2, 50+10=60, 100×5=500, 500×2=1000, 1000-60=940 1+1=2, 100×10=1000, 1000-50=950, 5×2=10, 950-10=940 1+1=2, 100×10=1000, 5×2=10, 1000-50=950, 950-10=940 1+1=2, 100×10=1000, 5×2=10, 50+10=60, 1000-60=940 1+1=2, 100×10=1000, 5×2=10, 1000-10=990, 990-50=940 1+1=2, 100×2=200, 50+10=60, 200×5=1000, 1000-60=940 1+1=2, 100×2=200, 200×5=1000, 50+10=60, 1000-60=940 1+1=2, 100×2=200, 200×5=1000, 1000-10=990, 990-50=940 1+1=2, 100×2=200, 200×5=1000, 1000-50=950, 950-10=940 1+1=2, 5×2=10, 50+10=60, 100×10=1000, 1000-60=940 1+1=2, 5×2=10, 100×10=1000, 1000-50=950, 950-10=940 1+1=2, 5×2=10, 100×10=1000, 50+10=60, 1000-60=940 1+1=2, 5×2=10, 100×10=1000, 1000-10=990, 990-50=940 1+1=2, 5×2=10, 50+10=60, 100×10=1000, 1000-60=940 1+1=2, 5×2=10, 100×10=1000, 50+10=60, 1000-60=940 1+1=2, 5×2=10, 100×10=1000, 1000-10=990, 990-50=940 1+1=2, 5×2=10, 100×10=1000, 1000-50=950, 950-10=940 1+1=2, 100×5=500, 50+10=60, 500×2=1000, 1000-60=940 1+1=2, 100×5=500, 500×2=1000, 50+10=60, 1000-60=940 1+1=2, 100×5=500, 500×2=1000, 1000-10=990, 990-50=940 1+1=2, 100×5=500, 500×2=1000, 1000-50=950, 950-10=940 5+1=6, 50+1=51, 100-6=94, 94×10=940 5+1=6, 50-1=49, 100-6=94, 94×10=940 5+1=6, 100-1=99, 99×10=990, 990-50=940 5+1=6, 100-6=94, 94×10=940 5+1=6, 100-6=94, 50+1=51, 94×10=940 5+1=6, 100-6=94, 50-1=49, 94×10=940 5-1=4, 100-1=99, 99×10=990, 990-50=940 50+10=60, 1+1=2, 100×2=200, 200×5=1000, 1000-60=940 50+10=60, 1+1=2, 5×2=10, 100×10=1000, 1000-60=940 50+10=60, 1+1=2, 100×5=500, 500×2=1000, 1000-60=940 50+10=60, 1+1=2, 100×2=200, 200×5=1000, 1000-60=940 50+10=60, 1+1=2, 5×2=10, 100×10=1000, 1000-60=940 50+10=60, 1+1=2, 100×5=500, 500×2=1000, 1000-60=940 50+10=60, 100×5=500, 1+1=2, 500×2=1000, 1000-60=940 50+10=60, 100×5=500, 1+1=2, 500×2=1000, 1000-60=940 100×10=1000, 1+1=2, 1000-50=950, 5×2=10, 950-10=940 100×10=1000, 1+1=2, 5×2=10, 1000-50=950, 950-10=940 100×10=1000, 1+1=2, 5×2=10, 50+10=60, 1000-60=940 100×10=1000, 1+1=2, 5×2=10, 1000-10=990, 990-50=940 100×10=1000, 1000-50=950, 1+1=2, 5×2=10, 950-10=940 100×10=1000, 1000-50=950, 1+1=2, 5×2=10, 950-10=940 100×10=1000, 1+1=2, 5×2=10, 1000-50=950, 950-10=940 100×10=1000, 1+1=2, 5×2=10, 50+10=60, 1000-60=940 100×10=1000, 1+1=2, 5×2=10, 1000-10=990, 990-50=940 100×10=1000, 1+1=2, 1000-50=950, 5×2=10, 950-10=940 1+1=2, 100×2=200, 50+10=60, 200×5=1000, 1000-60=940 1+1=2, 100×2=200, 200×5=1000, 50+10=60, 1000-60=940 1+1=2, 100×2=200, 200×5=1000, 1000-10=990, 990-50=940 1+1=2, 100×2=200, 200×5=1000, 1000-50=950, 950-10=940 1+1=2, 5×2=10, 50+10=60, 100×10=1000, 1000-60=940 1+1=2, 5×2=10, 100×10=1000, 1000-50=950, 950-10=940 1+1=2, 5×2=10, 100×10=1000, 50+10=60, 1000-60=940 1+1=2, 5×2=10, 100×10=1000, 1000-10=990, 990-50=940 1+1=2, 5×2=10, 50+10=60, 100×10=1000, 1000-60=940 1+1=2, 5×2=10, 100×10=1000, 50+10=60, 1000-60=940 1+1=2, 5×2=10, 100×10=1000, 1000-10=990, 990-50=940 1+1=2, 5×2=10, 100×10=1000, 1000-50=950, 950-10=940 1+1=2, 50+10=60, 100×2=200, 200×5=1000, 1000-60=940 1+1=2, 50+10=60, 5×2=10, 100×10=1000, 1000-60=940 1+1=2, 50+10=60, 100×5=500, 500×2=1000, 1000-60=940 1+1=2, 100×10=1000, 5×2=10, 1000-50=950, 950-10=940 1+1=2, 100×10=1000, 5×2=10, 50+10=60, 1000-60=940 1+1=2, 100×10=1000, 5×2=10, 1000-10=990, 990-50=940 1+1=2, 100×10=1000, 1000-50=950, 5×2=10, 950-10=940 1+1=2, 100×5=500, 500×2=1000, 50+10=60, 1000-60=940 1+1=2, 100×5=500, 500×2=1000, 1000-10=990, 990-50=940 1+1=2, 100×5=500, 500×2=1000, 1000-50=950, 950-10=940 1+1=2, 100×5=500, 50+10=60, 500×2=1000, 1000-60=940 50+1=51, 100-1=99, 99-5=94, 94×10=940 50+1=51, 5+1=6, 100-6=94, 94×10=940 50+1=51, 100-5=95, 95-1=94, 94×10=940 50-1=49, 100-1=99, 99-5=94, 94×10=940 50-1=49, 5+1=6, 100-6=94, 94×10=940 50-1=49, 100-5=95, 95-1=94, 94×10=940 100-1=99, 50+1=51, 99-5=94, 94×10=940 100-1=99, 50-1=49, 99-5=94, 94×10=940 100-1=99, 5+1=6, 99×10=990, 990-50=940 100-1=99, 5-1=4, 99×10=990, 990-50=940 100-1=99, 99×10=990, 5+1=6, 990-50=940 100-1=99, 99×10=990, 5-1=4, 990-50=940 100-1=99, 99×10=990, 990-50=940 100-1=99, 99-5=94, 50+1=51, 94×10=940 100-1=99, 99-5=94, 50-1=49, 94×10=940 100-1=99, 99-5=94, 94×10=940 5+1=6, 50+1=51, 100-6=94, 94×10=940 5+1=6, 50-1=49, 100-6=94, 94×10=940 5+1=6, 100-1=99, 99×10=990, 990-50=940 5+1=6, 100-6=94, 50+1=51, 94×10=940 5+1=6, 100-6=94, 50-1=49, 94×10=940 5+1=6, 100-6=94, 94×10=940 5-1=4, 100-1=99, 99×10=990, 990-50=940 100-5=95, 50+1=51, 95-1=94, 94×10=940 100-5=95, 50-1=49, 95-1=94, 94×10=940 100-5=95, 95-1=94, 94×10=940 100-5=95, 95-1=94, 50+1=51, 94×10=940 100-5=95, 95-1=94, 50-1=49, 94×10=940 100-5=95, 50+1=51, 95-1=94, 94×10=940 100-5=95, 50-1=49, 95-1=94, 94×10=940 100-5=95, 95-1=94, 50+1=51, 94×10=940 100-5=95, 95-1=94, 50-1=49, 94×10=940 100-5=95, 95-1=94, 94×10=940 100×5=500, 1+1=2, 50+10=60, 500×2=1000, 1000-60=940 100×5=500, 1+1=2, 500×2=1000, 50+10=60, 1000-60=940 100×5=500, 1+1=2, 500×2=1000, 1000-10=990, 990-50=940 100×5=500, 1+1=2, 500×2=1000, 1000-50=950, 950-10=940 100×5=500, 50+10=60, 1+1=2, 500×2=1000, 1000-60=940 100×5=500, 50+10=60, 1+1=2, 500×2=1000, 1000-60=940 100×5=500, 1+1=2, 500×2=1000, 50+10=60, 1000-60=940 100×5=500, 1+1=2, 500×2=1000, 1000-10=990, 990-50=940 100×5=500, 1+1=2, 500×2=1000, 1000-50=950, 950-10=940 100×5=500, 1+1=2, 50+10=60, 500×2=1000, 1000-60=940 100÷5=20, 20-1=19, 50×19=950, 950-10=940 100÷5=20, 20-1=19, 50×19=950, 950-10=940 ==> 187007 appels à Cal()
Le nombre d'appels à la fonction Cal() diminue de 911197 à 187007 !
Le temps de calcul s'améliore bien, mais le nombre de doublons reste encore souvent trop grand !
Amélioration "solutions minimales"
Tenons compte de la "qualité" des solutions, c'est-à-dire ne retenons que celles qui sont "minimes" ou qui utilisent le moins d'opérations ou de plaques possibles.
Observez les instructions qui utilisent la nouvelle variable niv:
function Cal(nbr,txt) {
var n=nbr.length-2,r;
for (var i=0,a=nbr[i]; i<nbr.length; a=nbr[++i]) {
var nb=nbr.slice(0);
nb.splice(i,1); // nbr sans l'élément a d'index i
for (var j=0,b=nb[j]; j<=n; b=nb[++j]) {
if (b>=a) { // évite beaucoup de doublons dus à la permutativité
if ((r=b+a)==res) Sol("+"); else if (n>niv) Recur("+");
if (a!=b) { // évite b-a=0
if ((r=b-a)==res) Sol("-"); else if (n>niv) Recur("-");
}
if (a>1) { // évite la multiplication et division par 1
if ((r=b*a)==res) Sol("×"); else if (n>niv) Recur("×");
if (b%a==0) { // division entière
if ((r=b/a)==res) Sol("÷"); else if (n>niv) Recur("÷");
}
}
}
}
}
function Sol(op) { // solution exacte trouvée
if (n>niv) {niv=n; str="";} // solution plus simple: annulle les antérieures
str+=txt+b+op+a+"="+r; // ajoute la solution
}
function Recur(op) {nb[j]=r; Cal(nb,txt+b+op+a+"="+r+", "); nb[j]=b;}
}
Pour simplifier l'écriture, j'ai introduit les deux fonctions Sol(op) et Recur(op) imbriquées dans Cal(nbr,txt).
Imbriquées (nested) pour éviter de passer en arguments toutes les variables de la fonction Cal(nbr,txt) utilisées.
Quand on a trouvé une solution (r==res) avec une certaine opération, on appelle Sol(op) qui, lorsque le niveau est meilleur, met à jour niv et supprime toutes les solutions plus longues trouvées auparavant.
Sinon, on essaye de trouver un meilleur résultat en appellant récursivement Cal(nbr,txt) à l'aide de Recur(op).
Résultats:
24 plaques: [1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,25,50,75,100] 6 tirages: [1,10,50,100,1,5] 940 100-1=99, 99×10=990, 990-50=940 100-1=99, 99-5=94, 94×10=940 5+1=6, 100-6=94, 94×10=940 100-1=99, 99×10=990, 990-50=940 100-1=99, 99-5=94, 94×10=940 5+1=6, 100-6=94, 94×10=940 100-5=95, 95-1=94, 94×10=940 100-5=95, 95-1=94, 94×10=940 ==> 14890 appels à Cal()
Avec cet exemple, le nombre de solutions affichées est "raisonnable" et le nombre d'appels à Cal() se réduit à 14890 !
Les doublons qui subsistent sont principalement dus à l'associativité d'opérations telles que
(a+b)+c = a+(b+c), (a×b)×c = a×(b×c), ...
et à la présence de plaques identiques au tirage ou pendant le calcul.
Une élimination plus sévère nécessiterait une "gestion" de l'ensemble des résultats partiels.
Remarques:
Les instructions qui concernent la variable nCal servent à compter le nombre d'appels à la fonction Cal() et sont donc provisoires.
La solution triviale (sans aucune opération) d'un tirage qui contient 100 avec le résultat 100 n'est pas détectée.
Versions suivantes
La prochaine extension "C Le compte est bon ou presque" traitera également les résultats les plus proches lorsqu'aucune solution exacte n'est trouvée.
Merci et bonne lecture ...
Testé avec: Chrome, Explorer, Firefox, Opera, Safari
Codes Sources
A voir également
- B Le compte est bon en un clin d'oeil
- N nb nb n b vb v b - Forum Visual Basic 6
- Compter le Nb de nouveau mail dans Outlook avec VB - Forum Visual Basic
- Compter le nb de form ✓ - Forum Visual Basic 6
- Compte a rebours en ligne ✓ - Forum Visual Basic
- Amaguiz mon compte - Forum Java
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.