Compétition: Jeu Chiffres sans Lettres

Rappel du premier message :

Bonjour,

On m'a demandé de construire une procédure récursive pour "résoudre" le jeu de chiffres et lettres et plus précisément: les chiffres sans lettres:)

Je m'explique:
il s'agit de trouver une suite finie d'opérations arithmétiques simples {+, -, x, /} appliquées chacune (pas nécessairement toutes) sur des couples de nombres choisis parmi 5 nombres positifs (exemple: 5, 12, 7, 50, 100) pour aboutir (si c'est possible) au résultat qui est un nombre entier positif.
Respecter plusieurs contraintes à savoir:
1. un nombre est utilisée une seule fois.
2. le résultat d'une opération peut être utilisé, mais une seule fois aussi.
3. les opérations de division donnant naissance à des nombre rationnels est interdites.



Exemple:
Construire 99 avec les nombres {1, 2, 3, 4, 5}
La solution est cette suite d'opérations:
4 x 5 = 20
3 + 2 = 5
5 x 20 = 100
100 - 1 = 99 <----- nombre trouvé.

L'objectif est d'implémenter une procédure récursive qui prend les {1, 2, 3, 4, 5} avec leur 99 et nous donne une solution au problème.

Bon courage.

J'ai pu déterminer le nombre de possibilités pour un problème de taille N = 100. C'est extrêmement grand comme nombre !!!!

C(100)
=

5,5204805000758006605059230615641 x 10^343

Que quelqu'un valide svp!

Methodix: regarde en haut, j'ai posté la réponse. et la tienne est très correcte.

Pour être sur de ta formule, essaie de calculer C(200) ?
On fera un rapprochement plutard.

d'après la formule que j'ai trouvée:

C(200) = 2,4987132603109855819420681306645 x 10^807

EXACT. ta formule a l'air d'être correcte:)

salut tout le monde,
je suis un nouveau membre. j'ai lu le sujet,il m'a attiré c'est genial
je voudrais participer mais avant tout j'aimerais que qq m'explique la démarche suivie par les intervenant. par exemple pourquoi : les arbres, algorithmes génétiques ...
Si qq veut me contacter :kammari.yusri@gmail.com
peut être je peux donner le plus à ce sujet.

yuskam a écrit:salut tout le monde,
je suis un nouveau membre. j'ai lu le sujet,il m'a attiré c'est genial
je voudrais participer mais avant tout j'aimerais que qq m'explique la démarche suivie par les intervenant. par exemple pourquoi : les arbres, algorithmes génétiques ...
Si qq veut me contacter :kammari.yusri@gmail.com
peut être je peux donner le plus à ce sujet.

Salut yuskam,
Nous sommes heureux que tu sois parmi nous dans ce forum.
Si tu veux bien, présente-toi en publique dans la rubrique Présentez-vous.
A part ça, essaie de poser des questions concernant ce sujet...

Bonjour Nabil, je vois que ton jeu est super si seulement j'arrive à trouver la solution, je ne suis pas aussi fort au math mais j'adore les calculs, bonne journée 3amek Neji

Nombre de problèmes solubles

Sur 11.918.700 problèmes au total, il y a 10.871.986 problèmes solubles, contre 1.046.714 insolubles. Attention toutefois, tous ces problèmes ne sont pas équiprobables, car par exemple le tirage 1;2;3;4;5;6 apparait 64 fois plus souvent que 1;1;2;2;3;3 : il faut donc en tenir compte pour calculer la probabilité qu’un problème soit soluble.
Probabilité qu'un problème soit soluble

La probabilité qu’un problème soit soluble est de 113.554.259/121.136.400 (le dénominateur est 134.596*900), soit environ 93,7 % (cette fraction ne se simplifie que par 7).
Etude des problèmes insolubles

Sur un total de 11.918.700 problèmes, on a vu ci-dessus que 10.871.986 sont solubles. On peut compléter ce résultat en notant que parmi les problèmes insolubles :

*
744.562 peuvent être approchés à 1 près
*
100.767 à 2 près
*
36.158 à 3 près
*
19.461 à 4 près
*
12.102 à 5 près

Le pire cas est un unique problème que l’on ne peut approcher qu’à 918 près : c’est bien sûr 1;1;2;2;3;3 ⇒ 999 (le maximum que l’on peut obtenir est (2 1)*(2 1)*3*3=81).
Etude des problèmes insolubles en termes de probabilités

En tenant maintenant compte du fait que tous les tirages ne sont pas équiprobables : on a vu plus haut que la probabilité qu’un problème soit soluble est d’environ 93,7%. Celle qu’on puisse l’approcher à 1 près est d’environ 4,5%, à 2 près 0,6%, à 3 près 0,2%. Au total, plus de 99% des problèmes peuvent être approchés au plus à 3 près.
Résultats sur les comptes
Nombre de tirages permettant d'obtenir un compte donné

Le record est détenu conjointement par 100, 102, 104 et 108 : 13240 tirages sur 13243 permettent d’obtenir ces comptes (mais ce ne sont pas les mêmes).

De l’autre côté, seuls 9017 tirages sur 13243 permettent d’obtenir 947 (qui est un nombre premier). Puis viennent 941 avec 9045 tirages, et 967 avec 9166 tirages.
Probabilité que l'on puisse obtenir un compte donné

Si l’on s’intéresse maintenant aux probabilités, seul 108 est obtenu avec la probabilité maximale de 134.593/134.596 soit environ 99,998%. 105 obtient 134.588, et 100, 102 et 104 sont à égalité avec 134.587.

De l’autre côté, c’est toujours 947 le plus défavorisé : il n’est obtenu que 98.598/134.596 soit environ 73,3% du temps. Viennent ensuite 941 avec 98.768 et 933 avec 99.658.
Résultats sur les tirages
Tirages permettant d'obtenir le maximum de comptes

Sur les 13243 tirages, 1226 permettent de réaliser tous les comptes entre 100 et 999. Si on trie les tirages par ordre lexicographique, le plus petit est 1;2;3;4;5;100 et le plus grand 8;9;9;10;25;75.

En termes de probabilités, on obtient qu’étant donné un tirage, on a 24.524/134.596 chances qu’il permette d’obtenir tous les comptes, soit environ 18,2%.
Tirages permettant d'obtenir n comptes

Les tirages les moins prolifiques permettent d’obtenir respectivement 0,1,5 et 8 comptes (le seul tirage ne permettant d’obtenir aucun compte entre 100 et 999 étant bien sûr 1;1;2;2;3;3).

A l’opposé, si on a vu ci-dessus que 1226 tirages permettent d’obtenir tous les comptes, sur un total de 13243 tirages, il y en a 582 qui permettent d’en obtenir 899 (pour une probabilité de 6,7%) et 454 qui permettent d’en obtenir 898 (pour une probabilité de 4,6%).

Pour avoir une idée de la répartition, plus de 50% des tirages permettent d’obtenir au moins 888 comptes sur 900.

TRES PASSSIONNNANNNT !!!!

attendez ma version recursive d'ici le weekend inchalah

bonjour
en fait le nombre de possibilité ce n'est pas tout court 4 a la puissance N-1???car l'arbre de choix est un arbre quaternaire de hauteur N et une possibilité c'est un parcours d'une branche de l'arbre vers la feuille,donc le nombre de possibilité est egale au nombre de feuilles!
On peut montrer par recurrence que nb_feuilles=4puissance hauteur-1 sur l'arbre quaternaire.
On a la primitive Arbre qui prend un sommet x et 4 arbres quaternaires et retourne un arbre quaternaire de sommet x.
Induction:arbre reduit a une feuille =>la hauteur est h=1 et nb_feuilles=1=(4 puissance h-1)
Supposons vrai pour 4 arbres A1,A2,A3,A4 de hauteur H(notre arbre de choix est complet) et montrons que c'est vrai pour AQ=Arbre(x.A1,A2,A3,A4)=>nb_feuilles(AQ)=Somme(i=1->4,nb_feuilles(Ai))=(4puissance(H-1))*4=(4puissance H)
or hauteur(AQ)=1+max(hauteur Ai)=1+H,donc on est arrivé a nb_feuilles(AQ)=(4puissane hauteur AQ-1).donc le nombre de possibilité c bien 4puissance N-1.

personne ne veut me repondre :/ c pas grave je vais pas dire que vous m'avez ignoré,je vais dire que je suis plus fort hihihih.
A propos le nombre de possibilité j'ai dit que c 4puissance N-1,c pas tout a fait ca,car ce nombre est le nombre de possibilité si on impose au joueur d'utiliser le 1er entier au debut puis le 2eme....donc le nombre total de possibilité et 4puissance N-1 *fact(N)..
Mais il existe des possibilités qu'on peut ignorées:
*l'addition et la multiplication sont commutatives alors que dans notre arbre il existe des possibilités qui sont des multiplication pures ou des additions pures qui ne font rien que permuter les entiers=>on reduit le nombre de possibilités de 2*fact(N).
*le resultat ne peut pas etre negatif,meme un resultat intermediaire donc on elimine les branches ou une racine est plus petites que la valeur de la racine de son fils,pareil les cas des divisions qui menent a une valeur non entiere

tu as pris en compte le cas des opérations illégales telles que la division par zéro... etc.

salut
j'ai pas ecrit 2 longues paragraphes pour avoir une reponse de quelques mots!je vous ai donné le nombre de possibilité en justifiant ma reponse,je m'attendais que vous etudiez ma reponse.
Bon je vois pas d'erreurs dans ma demonstration.
Et propos les divisions par zero oui tu as raisons je l'ai pas pris en compte :/
pour le moment j'ai construit l'arbre de choix "debile" qui contient toutes les possibilités et dés que je finis mes partiels mercredi je vais me repencher pour ajouter les ameliorations.
Ne vous inquietez pas nchalah je vais trouver un bon algo