Défi: le compte est bon

[fatal_error]

Hello,

Je vous propose le défi suivant:
Vous connaissez tous le compte est bon.
Vous avez déjà probablement codé l'algorithme pour trouver la solution (plus précisément, une solution)
Mais...
Pouvez vous en trouver une en un temps acceptable? L'algorithme doit obligatoirement trouver la solution si elle existe et l'afficher et indiquer qu'elle n'existe pas autrement

Je pose la base à 10 plaques dans la minute.
Est apprécié, un code source qui compile (avec eventuellement les dépendances indiquées s'il devait y en avoir), pour que nous puissions également vérifier le résultat...
mais le plus important est l'algorithme

Pour rappel:
une soustraction ne peut donner un résultat négatif
une division ne peut donner un nombre non entier
voir les règles "le compte est bon" par exemple ici http://www.lucas-nussbaum.net/writings.php?lceb

edit: je vous propose la liste suivante:
1 2 213 8 9 18 107 82 90 12
Compte à atteindre:1000000

[Cliffe]

tu as codé kkch déjà ?

[Rockleader]

Moi je me suis toujours demandé à quoi ressemblait l'algo pour faire ça, alors si jamais vous en avez un indépendant de tout langage je suis preneur^^

[Zorro_X]

une recherche dans un arbre d'états, alimentée éventuellement par une heuristique sur le nombre de nombres utilisés ne te suffirait pas ? avec la puissance de nos machines actuelles, même sur un smartphone tu dois pouvoir avoir quelque chose qui te trouve un résultat optimal en quelques millisecondes...

[fatal_error]

même sur un smartphone tu dois pouvoir avoir quelque chose qui te trouve un résultat optimal en quelques millisecondes...

pas si sûr...
mais l'énoncé est pas très bien posé.
Il faudrait plutot majorer le temps de trouver une solution optimale si elle existe.
(idem worst case)

[Zorro_X]

C'est sur, la combinatoire est tout de même assez grande (4 opérations, une dizaine de nombres, ...). Mais que veut dire pour toi "solution optimale" ? c'est lorsque tous les nombres sont utilisés je suppose ? ou il y a autre chose en plus ?

[fatal_error]

pardon je me suis (encore) torché par optimale, j'entend le compte est trouvé. Peu importe qu'elle mette en jeu tous les nombres de départ ou pas, mais il ne faut pas trouver une solution approchée si une solution existe!

[Zorro_X]

ok, merci pour ces précisions, t'as déjà un algo qui tourne en 3 lignes ou tu cherches quelque chose qui marche ?
Enfin, je ne vois pas trop d'algo "simple", il me semble que pour être couvrant il n'y a que le parcours d'un arbre d'états... après réflexion je ne suis même pas sur qu'une heuristique apporte quelque chose d'utile...
En faisant un rapide calcul (qui peut donc être erroné), pour 10 nombres et 4 opérations, je tombe sur un arbre d'environ 2.5x10e11 états, ca commence à faire du monde... mais étant donné que c'est du calcul entier, ca peut aller vite quand même... à tester... dès que j'ai un peu de temps, j'essaie de pondre un truc... ;)

[Rockleader]

Sa veut dire que pour résoudre un problème de ce genre on est obligé de faire toutes les opérations possibles et voir les résultats obtenu à chaque fois ?


Il y a deux cas à gérer il me semble.

1- On ne trouve pas forcement une solution à chaque fois.


2- Si on trouve une solution il faut qu'elle soit la plus rapide possible, il faudrait donc arriver à anticiper les calculs à faire selon le défi de Fatal pour améliorer la rapidité.
Et là franchement je vois pas du tout comment faire ça è_é


Éventuellement il y a le rapport coût/ressources à prendre en compte. N'est il pas mieux de trouver rapidement une solution approchée qu'une solution (éventuellement exacte mais qui pourrait ne pas exister) qui serait par conséquent beaucoup plus coûteuse en ressource temporelle.




Honnêtement ça me dépasse, mais si vous avez des codes sources à proposer je me ferais une joie d'y jeter un oeil :zen:

[Zorro_X]

Salut Rockleader, un parcours d'états c'est bien ce que tu dis : essayer toutes les combinaisons possibles. Ca se fait sous la forme de ce qu'on appelle "un graphe", les "arbres" font partie des "graphes". Les graphes (et les arbres) sont des façons de structurer une analyse de données, tu les retrouves dans les calcul de chemin d'un GPS ou les jeux "tour par tour" (échecs, Monopoly, etc...).
Le problème, comme ici en apparence, c'est qu'il y a beaucoup de combinaisons possibles, parfois même beaucoup trop, et dans ce cas on utilise souvent ce qu'on appelle une "heuristique", qui n'est rien d'autre qu'une fonction qui permet d'estimer si on est sur la bonne voie (ou pas) selon des critères parfois empiriques, mais ca fonctionne plutôt bien en général, par contre cela ne garantit pas de trouver la meilleure solution, seulement de s'approcher d'une... ;)
Pour le code, je pondrais certainement quelque chose durant ce Week-end, là je n'ai pas beaucoup de temps... ;)

[ampholyte]

Bonjour,

Si tu veux voir à quoi ressemble une solution possible : http://codes-sources.commentcamarche.net/source/100582-c-le-compte-est-bon-ou-presque (je n'ai pas vérifier s'il fonctionne correctement ou non)

Il y a également un site : http://le.compte.est.bon.free.fr/ avec un autre algo qui utilise les graphes.

Tu peux peut-être t'en inspirer Rockleader pour faire ton propre code mais en C cette fois :p.

[Cliffe]

Quel est l'intérêt d'une heuristique pour ce genre de problème ?
On cherche une solution exacte ou rien, aucun intérêt d'avoir une solution approchée.

[Rockleader]

J'étudie les graphes cette année, mais je dois bien avouer que pour le moment je ne vois pas vraiment d'intérêt...le prof n'arrête pas de nous pondre des définitions sur les graphes depuis le début de l'année, mais au final on sait pas à quoi ça sert :mur:



Cela ne pourrait il pas se représenter aussi sous la forme d'un automate ? Je sais pas si ça peut se coder facilement après un automate, mais il me semble qu'on est bien dans l'idée de passer d'un état à un autre avec une opération x ou y.



EDIT: Réflexion faite, un automate avec 10 entrées ce serait vraiment bizarre è_é

[Zorro_X]

Cliffe, l'heuristique n'est pas là pour trouver une "solution approchée", mais pour optimiser le parcours d'état, en quelque sorte "le guider" ver ce qui, à priori, semble une bonne solution... ca sert surtout à écarter les "branches pourries" où il semble flagrant que rien de bon ne va en sortir, c'est donc plutôt de l'optimisation qu'autre chose... ;)
Par ailleurs, j'ai lu sur l'un des sites proposés par ampholyte qu'un parcours récursif s'y prêtait bien... vu la taille et surtout la profondeur d'un tel arbre, ca risque de faire exploser la pile d'appels ce qui n'est pas génial... mais ca simplifierait en effet un peu le codage...
Enfin, Rockleader, un graphe, comme je disais plus haut, ce n'est qu'une représentation d'un ensemble d'états liés entre eux. C'est très utile en informatique de les maitriser, car c'est utilisé pour beaucoup de choses ! Un exemple simple et concret : un arbre qui contiendrait toutes les possibilités de jeu du morpion, cela permet d'y jouer contre l'ordinateur qui sait alors comment jouer pour tenter de gagner à son tour... ;)

[Cliffe]

Oui mais l'idée c'est quand même de parcourir l'arbre en entier.

Moi je pars du principe qu'il faut trouver toutes les solutions.

[fatal_error]

Oui mais l'idée c'est quand même de parcourir l'arbre en entier.

oui et non.
ca dépend ce que symbolise ton arbre.

par exemple si tu parcours 3+4, tu ne parcours pas 4+3..

Toute la question à mon sens, c'est de trouver des meilleurs cut que la commutativité de l'addition, et la non possibilité d'avoir des valeurs négatives (pour la soustraction) par exemple...
Mais également, de mémoriser certains embranchements qui ne mènent nulle part (ce n'est qu'une idée, rien de concret)

On peut envisager de résoudre ca de manière parallèle, avec l'approche "classique" mais c'est pas très intéressant..

[Cliffe]

par exemple si tu parcours 3+4, tu ne parcours pas 4+3..

Toute la question à mon sens, c'est de trouver des meilleurs cut que la commutativité de l'addition, et la non possibilité d'avoir des valeurs négatives (pour la soustraction) par exemple...

Oui c'est évident tout ça.

certains embranchements qui ne mènent nulle part

C'est juste impossible à savoir ça.
Le mieux que tu puisse faire pour un noeud c'est de regarder les valeurs min et max que tu puisses obtenir et vérifier que la valeur souhaitée soit comprise entre.

[ampholyte]

C'est juste impossible à savoir ça.
Le mieux que tu puisse faire pour un noeud c'est de regarder les valeurs min et max que tu puisses obtenir et vérifier que la valeur souhaitée soit comprise entre.

En fait il y a déjà plusieurs coupures que tu peux faire :

- Commutativité addition a + b et b + a

- Commutativité multiplication 3 * 4 et 4 * 3

- Pour la soustraction : différence < 0 (même à 0 à la limite)

- Pour la division, si le modulo est différent de 0

Pour ces 4 quatre faciles à obtenir, on ira dans des cas impossibles ou déjà fait.

[Cliffe]

[quote="ampholyte"]En fait il y a déjà plusieurs coupures que tu peux faire :

- Commutativité addition a + b et b + a

- Commutativité multiplication 3 * 4 et 4 * 3

- Pour la soustraction : différence |S| + \prod \limits_{x \in P} x[/TEX] on peut supprimer le noeud N. ( correspond à l'entier rechercher).


Exemple : Si je cherche à obtenir 1000 avec les numéros 2, 3 et 4 : on a 1000 > 2*3*4=24.

[ampholyte]

Oui ça a été dit dans le premier post. On cherche d'autres cut la.

Moi je propose, pour un noeud , on note les ensembles et .
Alors si : on peut supprimer le noeud N. ( correspond à l'entier rechercher).


Exemple : Si je cherche à obtenir 1000 avec les numéros 2, 3 et 4 : on a 1000 > 2*3*4=24.

Ok je comprends mieux le type de cut que tu recherches.

Après on peut également supposer que l'algo qui génère le nombre à obtenir et les nombres à chercher ne donne pas des cas extrêmes (à confirmer). Je pense que les nombres à utiliser respectent ta règle du min / max.

Par exemple avec les nombres à utiliser, il calcule le min / max et effectue le random sur cet interval.