Défi: le compte est bon

Discutez d'informatique ici !
Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 5774
Enregistré le: 22 Nov 2007, 13:00

Défi: le compte est bon

par fatal_error » 21 Oct 2014, 20:46

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
la vie est une fête :)



Cliffe
Membre Rationnel
Messages: 955
Enregistré le: 12 Juin 2012, 14:25

par Cliffe » 21 Oct 2014, 23:07

tu as codé kkch déjà ?

Avatar de l’utilisateur
Rockleader
Vétéran
Messages: 2126
Enregistré le: 11 Oct 2011, 19:42

par Rockleader » 22 Oct 2014, 00:02

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^^
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
Zorro_X
Membre Naturel
Messages: 77
Enregistré le: 16 Avr 2012, 17:40

par Zorro_X » 27 Oct 2014, 14:45

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...

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 5774
Enregistré le: 22 Nov 2007, 13:00

par fatal_error » 27 Oct 2014, 15:23

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)
la vie est une fête :)

Avatar de l’utilisateur
Zorro_X
Membre Naturel
Messages: 77
Enregistré le: 16 Avr 2012, 17:40

par Zorro_X » 27 Oct 2014, 15:34

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 ?

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 5774
Enregistré le: 22 Nov 2007, 13:00

par fatal_error » 27 Oct 2014, 17:06

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!
la vie est une fête :)

Avatar de l’utilisateur
Zorro_X
Membre Naturel
Messages: 77
Enregistré le: 16 Avr 2012, 17:40

par Zorro_X » 29 Oct 2014, 01:11

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... ;)

Avatar de l’utilisateur
Rockleader
Vétéran
Messages: 2126
Enregistré le: 11 Oct 2011, 19:42

par Rockleader » 29 Oct 2014, 01:39

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:
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
Zorro_X
Membre Naturel
Messages: 77
Enregistré le: 16 Avr 2012, 17:40

par Zorro_X » 29 Oct 2014, 09:42

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... ;)

Avatar de l’utilisateur
ampholyte
Membre Transcendant
Messages: 3940
Enregistré le: 21 Juil 2012, 08:03

par ampholyte » 29 Oct 2014, 09:47

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
Membre Rationnel
Messages: 955
Enregistré le: 12 Juin 2012, 14:25

par Cliffe » 29 Oct 2014, 10:47

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.

Avatar de l’utilisateur
Rockleader
Vétéran
Messages: 2126
Enregistré le: 11 Oct 2011, 19:42

par Rockleader » 29 Oct 2014, 12:37

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 è_é
Cette histoire est entièrement vraie puisque je l'ai inventé du début à la fin !

Avatar de l’utilisateur
Zorro_X
Membre Naturel
Messages: 77
Enregistré le: 16 Avr 2012, 17:40

par Zorro_X » 29 Oct 2014, 14:41

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
Membre Rationnel
Messages: 955
Enregistré le: 12 Juin 2012, 14:25

par Cliffe » 29 Oct 2014, 14:48

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.

Avatar de l’utilisateur
fatal_error
Modérateur
Messages: 5774
Enregistré le: 22 Nov 2007, 13:00

par fatal_error » 29 Oct 2014, 15:02

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..
la vie est une fête :)

Cliffe
Membre Rationnel
Messages: 955
Enregistré le: 12 Juin 2012, 14:25

par Cliffe » 29 Oct 2014, 15:18

fatal_error a écrit: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.

fatal_error a écrit: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.

Avatar de l’utilisateur
ampholyte
Membre Transcendant
Messages: 3940
Enregistré le: 21 Juil 2012, 08:03

par ampholyte » 29 Oct 2014, 17:50

Cliffe a écrit: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
Membre Rationnel
Messages: 955
Enregistré le: 12 Juin 2012, 14:25

par Cliffe » 29 Oct 2014, 18:39

[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.

Avatar de l’utilisateur
ampholyte
Membre Transcendant
Messages: 3940
Enregistré le: 21 Juil 2012, 08:03

par ampholyte » 29 Oct 2014, 18:52

Cliffe a écrit: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.

 

Retourner vers ϟ Informatique

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 5 invités

Tu pars déja ?



Fais toi aider gratuitement sur Maths-forum !

Créé un compte en 1 minute et pose ta question dans le forum ;-)
Inscription gratuite

Identification

Pas encore inscrit ?

Ou identifiez-vous :

Inscription gratuite