Le compte est bon !
dans Arithmétique
Hello,
dans cette période de confinement où je n'ai rien à foutre, j'essayais de m'interroger sur une problématique de math appliqué à l'informatique.
Vous connaissez surement l'émission des chiffres et des lettres : on a 7 nombres donnés, et on doit trouver le moyen d'arriver à la valeur la plus proche possible du 7ème nombre en utilisant toutes les opérations qu'on veut (les divisions doivent être entières) sur les 6 premiers nombres (dans l'ordre qu'on veut).M
J'aimerais trouver un algorithme qui résoudrait ce problème. Alors oui, en théorie, je pourrais tester toutes les combinaisons possibles entre les 6 nombres, mais je ne crois pas que ce soit possible dans un temps limité de quelques secondes.
Alors j'essaye de réfléchir à la bonne stratégie à adopter. Quels opérations à privilégier, et comment réaliser un algorithme qui tienne la route.
Mais j'avoue être un peu dépassé. Avez-vous une idée ?
Merci des retours
dans cette période de confinement où je n'ai rien à foutre, j'essayais de m'interroger sur une problématique de math appliqué à l'informatique.
Vous connaissez surement l'émission des chiffres et des lettres : on a 7 nombres donnés, et on doit trouver le moyen d'arriver à la valeur la plus proche possible du 7ème nombre en utilisant toutes les opérations qu'on veut (les divisions doivent être entières) sur les 6 premiers nombres (dans l'ordre qu'on veut).M
J'aimerais trouver un algorithme qui résoudrait ce problème. Alors oui, en théorie, je pourrais tester toutes les combinaisons possibles entre les 6 nombres, mais je ne crois pas que ce soit possible dans un temps limité de quelques secondes.
Alors j'essaye de réfléchir à la bonne stratégie à adopter. Quels opérations à privilégier, et comment réaliser un algorithme qui tienne la route.
Mais j'avoue être un peu dépassé. Avez-vous une idée ?
Merci des retours
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Quant à l’algorithme, j’imagine une fonction et une récursivité, pour enchaîner.
Algorithme digne d’une brute. Sans réfléchir.
1) Sélectionner une paire parmi 6 : 15 possibilités
2) Choisir une opération : 4 possibilités
3) Sélectionner une paire parmi 5: 10 possibilités
4) Choisir une opération : 4 possibilités
...
En tout le nombre de possibilités est 2764800.
Trouver dans quels cas on peut échanger les opérateurs sans changer le résultat.
Par exemple $155 = (25 \times 6) + 5 = (25 + 6) \times 5 $
JLT écrivait : http://www.les-mathematiques.net/phorum/read.php?5,1966544,1966558#msg-1966558
[Inutile de recopier l'avant dernier message. Un lien suffit. AD]
Non plus que ça. D'une, parce que on n'est pas obligé d'utiliser les 6 nombres, et 2, parce que la soustraction et division ne sont pas commutatives, donc en vrai on a 6 opérations possibles.
Et si ces résultats (obtenus avec des passage par « les nombres interdits ») n’existent que par ces chemins interdits.
Bon si ce n’est pas clair, pardon...
il n'y a que 4 opérations en pratiquant ainsi :
* Choisir un nombre
* Choisir une opération
* choisir un nombre et faire l'opération
* Comparer au résultat et conserver le plus proche et son calcul; Arrêt si trouvé.
* Choisir une opération
* choisir un nombre et faire l'opération
* Comparer au résultat et conserver le plus proche et son calcul; Arrêt si trouvé.
* Choisir une opération
* choisir un nombre et faire l'opération
* Comparer au résultat et conserver le plus proche et son calcul; Arrêt si trouvé.
* Choisir une opération
* choisir un nombre et faire l'opération
* Comparer au résultat et conserver le plus proche et son calcul; Arrêt si trouvé.
* Choisir une opération
* choisir un nombre (plus de choix) et faire l'opération
* Comparer au résultat et conserver le plus proche et son calcul; Arrêt
Donc au maximum 6*4*5*4*4*4*3*4*2*4*1 = 737280 opérations. Et souvent moins.
En programmant correctement, on parcourra correctement l'arborescence de ces opérations, et c'est très rapide pour un ordinateur. Comme on dispose de 15 secondes, il aura le temps de trouver.
Cordialement.
Il y a plein d'optimisations possibles : Si mes 6 nombres sont a, b, c, d, e, e , les 2 derniers sont identiques, ça diminue drastiquement le nombre de combinaisons. Idem si mes 6 nombres sont a, b, c, d, e, a+b
Trouver un algorithme qui trouve le résultat, avec un minimum de calculs, c'est un challenge intéressant. (minimum de calculs, ça veut dire minimum de pistes testées, et donc, toutes choses égales par ailleurs, temps le plus court)
Pour la division, il me semble que dans les règles on doit avoir des nombres entiers à chaque étape, donc on est obligé de diviser le plus grand par le plus petit.
On n'est pas obligé d'utiliser les six nombres, mais on regarde tous les nombres obtenus lors des étapes intermédiaires, et on prend le plus proche.
je ne crois pas que ces opérations soient interdites (le règlement ne le dit pas), mais utiliser des négatifs n'est généralement pas utile. Par exemple le compte (1-4)*25*(7-10) se fait plus simplement par (4-1)*25*(10-7); de même (1-4)+25 se fait par 25-4+1.
Dans ce que j'ai vu, Renardeau n'en utilise jamais, ni des rationnels non entiers. Mais le règlement n'en parle pas.
Cordialement
Si si, c'est tout à fait possible. Il y a quelques années, je l'avais codé en python. Ça examine toutes les possibilités en une seconde ou deux.
À noter qu'on peut élaguer l'arbre de recherche en ne faisant que les opérations dont le résultat est un entier naturel (on ne fait pas $a-b$ si $b>a$, on ne fait pas $\dfrac{a}{b}$ si $a$ n'est pas divisible par $b$).
[Inutile de recopier un message présent sur le forum. Un lien suffit. AD]
Ah je comprends ton point de vue.
Mais ca n'est pas complet, à mon sens.
Tu ne peux pas faire le calcul
(A*B)+(C*D) avec ton algo, par exemple, ou alors je n'ai pas compris.
https://www.dcode.fr/compte-est-bon
Exemple : on part de la racine de l'arbre qui est [3,100,10,6,7,6]. De là, on peut (en ajoutant les 2 premiers), aller au sommet [103,10,6,7,6], ou (en multipliant les 2 premiers) à [300,10,6,7,6], etc. Ensuite, de chacun de ces sommets, on peut aller à ..., etc.
On parcourt tout l'arbre, en mémorisant les opérations effectuées sur le chemin, et on renvoie à la fin ce qui amène au plus près du résultat.
Le plus proche est 2/7 si je ne me trompe pas.
Par contre pour trouver le bon compte, je crois qu’utiliser un 2/7 n’apporte rien dans le sens où on trouvera un autre enchaînement possible...
Avec : 1 ; 1 ; 2 ; 14
Trouver : 21.
Le site suivant est un régal pour ce fil : https://www.dcode.fr/compte-est-bon
Edit : Je vois que Fin de partie avait déjà cité ce site.
J'ai trouvé la même chose que JLT 2764800.
Pour éliminer le problème soulevé par Lucas078 on commence par ordonner les nombres dans l'ordre décroissant.
Cordialement.
On peut se poser plein d'autres questions avec les plaques proposées par Sylvain ( il me semble en plus que le chiffre des centaines de la cible ne doit pas être 0 ) .
1°) Existe-t-il une cible qu'on peut atteindre quel que soit le tirage des 7 plaques ?
2°) Quelle est la pire cible possible ( la plus difficile à atteindre ) ?
3°) Quel est le pire tirage possible pour les 7 plaques ( 100,100,100, ... me semble un bon candidat ) .
Domi
Cordialement.
(*) après, on peut faire ce qu'on veut ici :-)
Merci pour ces conseils.
Bon contre en moyenne c'est calculé en 38s en moyenne, c'est beaucoup mais moins que ce que je pensais au départ.
Je peux ptet optimiser, mais j'enlèverais ptet 10%, ca restera à 34, 35s.
Mais ce n’est peut-être pas le règlement exhaustif (?).
Domi
Comment obtenir $21$ avec $1,5,6,7$ ?
Réponse: $\dfrac{6}{1-\dfrac{5}{7}}$
Essaie avec seulement des entiers !!...
Cordialement,
Rescassol
Domi
J'ai essayé de mettre des dates de mémoire, et je me suis planté de 10 ou 15 ans environ pour chacun des 3 !
... parmi les spectateurs.
Domi
Rien n'empêchait de faire $y=b-a$ au lieu de $x=a-b$, puis d'utiliser $-y$ au lieu d'utiliser $x$ dans la suite du calcul.
Tout calcul qui passe par un entier négatif peut être remplacé par un calcul conforme aux règles.
Domi
On a les mêmes 24 plaques : 2 plaques pour chacun des nombres 1 à 10, 1 plaque pour chacun des nombres 25, 50, 75, et 100.
On tire 7 plaques parmi ces 24 plaques.
7 plaques au lieu de 6 dans la variante connue.
Et on tire 2 nombres entre 100 et 999.
Le but du jeu est de 'reconstituer ces 2 derniers nombres', chaque plaque étant utilisée au maximum une fois.
Exemple :
A partir des plaques 2 3 5 8 10 10 et 50, obtenir les nombres 186 et 510
Solution : $50*10+10=510$ puis $510/3+(2*8)=186$
Pour atteindre le 2ème résultat 186, on peut réutiliser le 1er résultat (510) , mais pas forcément.
Cf 2ème exemple :
A partir des mêmes plaques 2 3 5 8 10 10 et 50, obtenir les nombres 210 et 424
Solution : $(10*10+5)*2=210$ et $(50+3)*8=424$
Aucune des plaques utilisées dans le 2ème calcul n'avait été utilisée dans le premier.
On part du principe que les 7 plaques et les 2 nombres sont choisis de sorte qu'il y ait au moins une solution.