Petites enigmes
-
-
-
-
modifié 28/09/13 (13:30)L'énigme de cette semaine est la suivante :
on dispose de 6 tasses (2 rouges, 2 pourpres, 2 écarlates) et 6 soucoupes (2 rouges, 2 pourpres, 2 écarlates). On dispose au hasard les soucoupes sur les tasses. Quelle est la probabilité que chaque tasse soit une soucoupe de couleur différente de la sienne ?
Je donne également la réponse à celle de la précédente :# proc (8*8*8*8);;
0 = (8-8)
1 = (8/8)
2 = Sqrt(Sqrt((8+8)))
3 = Sqrt(((8/8)+8))
4 = Sqrt((8+8))
5 = ((8/8)+Sqrt((8+8)))
6 = (8-Sqrt(Sqrt((8+8))))
7 = (8-(8/8))
8 = 8
9 = ((8/8)+8)
10 = (Sqrt(Sqrt((8+8)))+8)
11 = (Sqrt(((8/8)+8))+8)
12 = (Sqrt((8+8))+8)
14 = ((8+8)-Sqrt(Sqrt((8+8))))
15 = ((8+8)-(8/8))
16 = (8+8)
17 = ((8/8)+(8+8))
18 = (Sqrt(Sqrt((8+8)))+(8+8))
20 = (Sqrt((8+8))+(8+8))
24 = (8+(8+8))
- : unit = ()
Le code Caml est normalement assez lisible et dispo ici. Il tourne assez vite.
--
Mouton, qui aime bien le rouge. -
-
modifié 28/09/13 (18:47)Mouton a écrit :
# proc (8*8*8*8);;
0 = (8-8)
1 = (8/8)
2 = Sqrt(Sqrt((8+8)))
3 = Sqrt(((8/8)+8))
4 = Sqrt((8+8))
6 = (8-Sqrt(Sqrt((8+8))))
7 = (8-(8/8))
8 = 8
9 = ((8/8)+8)
10 = (Sqrt(Sqrt((8+8)))+8)
12 = (Sqrt((8+8))+8)
16 = (8+8)
24 = (8+(8+8))
- : unit = ()
Tu respectes pas tes règles :
Mouton a écrit :
> On est obligé d'utiliser tous les 8, on peut employer plusieurs fois la même opération.
D'ailleurs c'est ce qui m'avait fait le plus chier dans l'affaire cette règle.
Sinon, je vois que mentalement j'avais presque tout sauf le 11.
___
![[*b]](http://img7.kraland.org/s/4F.gif)
Elune, moutonologue -
posté 28/09/13 (19:53)Elune Morningwood[62§o]Jumper a écrit :
> Tu respectes pas tes règles
Je m'attendais à cette remarque. 8 = sqrt(8*8), ce qui permet de rajouter des 8 sans problème, et donc je n'ai pas fait le rajout dans les arbres au moment de la présentation.
Sur le code, je l'ai pensé en itératif, donc je l'ai fait en itératif. J'avais fait du récursif très très maladroit (même dossier, autre fichier) avant, donc j'ai changé. Tu vois les choses comment en récursif ?
--
Mouton -
modifié 03/10/13 (13:35)En fait, ça rentre assez mal dans le schéma classique de la programmation dynamique. Il est plus simple d'énumérer les expressions comme tu le fais, tandis que si on appliquait bêtement le schéma classique, on essaierait de dire "je veux les solutions pour 4 huit, donc je vais d'abord chercher celles avec 1, 2 ou 3 huit".
Construire la liste des expressions est un processus récursif, je ne comprend pas bien comment tu es arrivé à en faire une boucle, qui te fera revenir plusieurs fois sur la même expression.
Une première version
Le tableau est assez creux, et itérer dessus est assez inefficace. C'est un argument supplémentaire en faveur de la récursivité. Mais au delà de ça, il reste des boucles dans le programme précédent, qui vont itérer sur beaucoup de vide. J'ai autorisé les valeurs à monter à 256 et il y a beaucoup de valeur inatteignables entre 1 et 256. Du coup, plutôt que d'itérer sur le tableau pour trouver des expressions déjà construites, je vais les stocker dans une liste et itérer la liste. En prime, ça simplifie un poil le programme.
Une seconde version
Sur ma machine, la première version termine en 4ms et la seconde en 2ms. On peut optimiser en utilisant ta remarque, (sqrt(8*8) = 8) ce qui réduirait le nombre d'expressions à stocker, mais requiert un chaînage un peu plus élaboré que les listes ocaml. -
posté 02/10/13 (17:43)Mouton a écrit :
> L'énigme de cette semaine est la suivante :
> on dispose de 6 tasses (2 rouges, 2 pourpres, 2 écarlates) et 6 soucoupes (2 rouges, 2 pourpres,
> 2 écarlates). On dispose au hasard les soucoupes sur les tasses. Quelle est la probabilité
> que chaque tasse soit une soucoupe de couleur différente de la sienne ?Spoiler
___
Elune, moutonologue -
![[:]]](http://img7.kraland.org/s/04.gif)
