 |
#1 - 09-02-2011 15:39:40
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
Nombre d'expresisons
On essaye régulièrement d'obtenir un nombre à l'aide d'opérations élémentaires et de d'opérandes (n'est ce pas ? )
1) Combien d'expressions différentes (même si elles sont égales après calcul) peut-on former avec n opérandes et k opérations (à deux paramètres, comme le sont + - / * ^ mod ...). NB : les parenthèses sont gratuites et utilisables à l'envi.
2) On ajoute la possibilité d'utiliser la concaténation, ou, ce qui revient au même, l'opération X#Y = 10X+Y, mais sans qu'elle compte dans les k opérations autorisées (tout pareil que dans le problème de Thedoums : ici)
Je crois que c'est trop dur...
#2 - 11-02-2011 09:45:05
- LeSingeMalicieux
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1298
- Lieu: Haute-Marne
Nobmre d'expressions
Je pense qu'on devrait pouvoir résoudre une partie du cas 1) à l'aide de la notation polonaise préfixée.
Dans cette notation, on place l'opérande à gauche des deux opérateurs.
Quelques exemples :
+ab équivaut à a+b
-c+ab équivaut à c - (a+b)
*+abc équivaut à (a+b) * c
/*cd+ab équivaut à (c*d) / (a+b)
Utilisons a, b, c, etc pour représenter des opérateurs quelconques et l'opérande +
Avec deux opérateurs, une seule expression possible :
+ab soit a+b
Avec trois opérateurs, deux expressions possibles :
+a+bc soit a + (b+c)
++abc soit (a+b) + c
Avec quatre opérateurs, trois expressions possibles :
++ab+cd soit (a+b) + (c+d)
+a+b+cd soit a + (b + (c+d))
+++abcd soit ((a+b) + c) + d
etc.
Maintenant, suivant le nombre d'opérandes utilisés (+, -, *, /, ^, etc), pour chaque cas cité ci-dessus, les possibilités croissent rapidement.
Ajoutons à cela qu'il faut ensuite se méfier des opérateurs qui représentent des fonctions non continues sur le domaine de définition (division par 0, racine d'un nombre négatif dans R, et j'en passe). La tâche devient très ardue !
Mais c'est sans doute une piste à creuser pour ceux qui ont un niveau bien supérieur au mien.
Avoir quatre mains, c'est plus pratique pour taper sur un clavier.
#3 - 11-02-2011 16:58:30
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
Nombre dd'expressions
Bien parti le Singe, mais ne te préoccupe pas des divisions par zéro, on veut juste le nombre d'expressions, même celle qui ne donnent pas de résultats.
En fait, l'idée est de savoir combien il faut faire d'essais si on veut résoudre un problème de type "le compte est bon" en essayant toutes les combinaisons, les combinaisons interdites étant des combinaisons quand même...
#4 - 12-02-2011 13:34:09
- LeSingeMalicieux
- Elite de Prise2Tete
- Enigmes résolues : 49
- Messages : 1298
- Lieu: Haute-Marne
Nombre d'expresions
Tiens, je m'aperçois déjà que j'ai oublié deux écritures possibles avec quatre opérandes. On a en fait cinq possibilités :
+a+b+cd soit a + (b + (c + d))
++ab+cd soit (a+b) + (c + d)
+a++bcd soit a + ((b + c) + d)
++a+bcd soit (a + (b + c)) + d
+++abcd soit ((a + b) + c) + d
En tout cas, avec n opérandes, on formera toujours des écritures avec n-1 opérateurs.
Sinon pour chaque écriture trouvée, on peut distribuer les n opérandes de n! façons.
par exemple, l'écriture +a+bc (qui utilise trois opérandes) peut différer de six (3!) façons :
+a+bc
+a+cb
+b+ac
+b+ca
+c+ab
+c+ba
Ensuite, pour chaque expression, suivant le nombre k d'opérateurs permis (+, -, *, /, etc), on aura donc k^(n-1) expressions différentes possibles.
Ce qui nous fait n! * k^(n-1) possibilités pour une seule écriture.
Ainsi :
- Pour n=2, on a une écriture possible (+ab), ce qui nous donne 1*2*k expressions différentes possibles.
- Pour n=3, deux écritures possibles (voir mon précédent post), ce qui nous donne 2*6*k² expressions différentes possibles.
- Pour n=4, cinq écritures possibles (sous réserve que j'en aie encore oubliées), soit 5*24*k^3 expressions possibles.
- etc
Qui a envie de généraliser ? 
Avoir quatre mains, c'est plus pratique pour taper sur un clavier.
#5 - 15-02-2011 11:58:48
- gasole
- Elite de Prise2Tete
- Enigmes résolues : 40
- Messages : 1117
- Lieu: Toulouse
nombre d'expressiond
Merci le Singe pour ta participation un peu isolée... cette question n'a pas enthousiasmé les foules on dirait...
Bon, on a [latex]n[/latex] opérandes noté [latex]a_1,...,a_n[/latex] et [latex]k[/latex] opérations notées [latex]*^1,...*^k[/latex] (on n'est pas obligé de tout utiliser), posons déjà [latex]p = \min(n,k+1)[/latex] et oublions les parenthèses un instant.
Une expression (sans parenthèses) sera de la forme :
[TeX]a_1 *^1 a_2... *^{p-1} a_p[/TeX]
et il y a [latex](n.(n-1)....(n-p+1)).(k.(k-1)....(k-p+2))[/latex] telles expressions, soit [latex]n!/(n-p)! \times k!/(k-p+1)![/latex]
venons-en aux parenthèses, il en faut deux par opérateurs : [latex](... *_i ...)[/latex] sauf les plus extérieures qu'on peut virer, soit [latex]2(p-1)-2 = 2p-4[/latex] parenthèses.
Le nombre de façon de distribuer [latex]2p-4[/latex] parenthèses, est le nombre de "mots de Dyck" de longueur [latex]2p-4[/latex] qui vaut précisément [latex]C_{p-2}[/latex] (le [latex]p-2[/latex]-ième nombre de Catalan, voir ici) et est défini par :
[TeX]C_{p-2}=\frac{(2p-4)!}{(p-2)! (p-1)!}[/TeX]
ce qui nous donne au total (et après quelques regroupements) :
[TeX](2p-4)!\times p.{n \choose p}\times (p-1) {k \choose (p-1)}[/TeX]
Voilà, histoire de clore ce sujet. Je laisse en suspens la possibilité de concaténer les opérandes.
Mots clés des moteurs de recherche
|
 |
Accueil
