[VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Staple1600

XLDnaute Barbatruc
Bonjour à tous

Je cherche à réaliser sous VBA la chose suivante:

Lister les solutions possibles de ce jeu:
24 Game - Solutions to the 24 Game
C'est à dire : avec les opérateurs de base +,-,*,/,(,) : trouver 24 avec 4 chiffres de( 1à 9 ) tiré au hasard

Un petit cadeau pour ceux qui sauront m'aider (car malheureusement les maths et moi on a pas trop d'accointances )
[flash]http://www.novelgames.com/flashgames/game.swf?id=73[/flash]

Dernière édition:

Staple1600

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Re

Un petit up avant de mouliner la soupe Pas de matheux sur le forum aujourdh'hui ?

En attendant de vous lire, je m'en retourne exceller.

Tibo

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Salut JM,

Question macro, pas question de compter sur moi Sinon, je me souviens que l'ami José (JMPS) qui nous manque, avait concocté un petit barbatruc à sa façon pour trouver des solutions pour le jeu du Compte est bon

A toi de voir si tu peux y trouver ton bonheur

Bonne soirée

@+

Staple1600

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Bonsoir Tibo

Si tu veux tenter par formules , pas de problème.

PS: j'ai trouvé sur le net un classeur (anglophone) qui fonctionne que par formules
(mais en listant sur feuille toutes les solutions
plus de 5000 lignes)

Je voudrais essayer de faire une version VBA (en utilisant une autre méthode)

(Je posterai le lien plus tard , histoire de vous laisser utiliser vos neurones , vous les formulistes émérites du forum)

Staple1600

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Bonsoir à tous

Voilà ou j'en suis

Les différentes opérations possibles

° = + ou / ou * ou -

x1 à x4 = chiffres de 1 à 9

x1°x2°x3°x4

(x1°x2)°(x3°x4)

((x1°x2)°x3)°x4

(x1°(x2°x3))°x4

C'est pour la suite que je coince.

Si les matheux du forum pouvaient me filer un coup de main.

Merci.

PS: en complément d'information, pierrejean m'avait aidé dans ce fil

qui était les prémisses de celui-ci

Dernière édition:

job75

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Bonsoir Staple, Tibo,

Pour les 3 opérateurs utilisés, il y a déjà 4x4x4=64 possibilités.

Avec pour chacune tes 4 possibilités de parenthèses, cela fait 64x4=256 cas à écrire. C'est trop...

Comme de toute façon il faut tirer au hasard les x1-x2-x3-x4 parmi 9 chiffres, je pense qu'une solution est de tirer au hasard aussi les opérateurs (pas les parenthèses), afin d'établir le texte de la formule puis de l'évaluer.

Le texte de la formule sera entré à la suite des précédents dans la feuille de calcul, avec 2 conditions :
- que l'évaluation donne pour résultat 24
- qu'il ne soit pas déja présent dans la feuille.

Et on fait tourner la bécane jusqu'à ce que la liste ne varie plus.

Ce n'est pas très matheux, mais on devrait trouver ainsi toutes les possibilités.

Bonne nuit.

Dernière édition:

Staple1600

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Bonsoir job75

D'après le site que je citais
From these 2099520 expressions 14754 expressions give 24 as outcome, occurring at 404 different combinations
24 Game - Solutions to the 24 Game: Appendix a

(ici liste des solutions)

Il y donc 404 combinaisons de chiffres de de 1 à 9 qui donnent 24

Je voudrais que l'algorithme VBA les trouve tout seul.

Mais je coince pour générer les expressions mathématiques en VBA.

PS: si cela peut vous aider à m'aider voici la grille des solutions sous Excel

Fichiers joints

• 5.8 Ko Affichages: 163
Dernière édition:

job75

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Re Staple,

Si tu veux trouver les combinaisons de chiffres, ce n'est pas très compliqué puisque pour chaque formule étudiée on connaît bien sûr la combinaison.

On entrera donc dans la feuille les combinaisons, avec les conditions dont j'ai parlé.

A+

Dernière édition:

job75

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Bonjour Staple, le forum,

Plutot que de faire des tirages aléatoires, on peut aussi par des boucles étudier tous les cas possibles :

- chiffres 9x9x9x9=6561
- opérateurs 4x4x4=64
- parenthèses 4

Total 6561x64x4=1679616 cas

C'est un peu moins que ce que tu indiques (2099520), en fait il doit y avoir 5 cas pour les parenthèses.

A+

Dernière édition:

tototiti2008

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Bonjour à tous,

Staple : les chiffres de 1 à 9 sont-ils forcément différents les uns des autres ?

tototiti2008

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Un essai,

Je n'ai évidement rien compris à la jolie démonstration mathématique, mais cependant, j'ai essayé...
le problème est que plusieurs solutions sont équivalentes, mais là c'est un peu trop compliqué pour moi

Fichiers joints

• 17.2 Ko Affichages: 155
• 17.2 Ko Affichages: 153
• 17.2 Ko Affichages: 156

Staple1600

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Bonjour à tous

Merci de vous intéresser au problème.

tototiti2008: merci pour ton classeur

D'après ce que j'ai compris il peut y avoir plusieurs fois le même chiffre.

Dans le classeur que j'ai joint précédemment il y a les 404 permutations
non redondantes qui aboutissent à 24
(je parle des chiffres sans les opérateurs)

J'aimerais arriver à ce que l'algorithme n'est pas besoin de données stockées en dur sur la feuille.

Pour stocker les opérateurs, j'ai pensé à cela:
op=Mid("*+/-()",int(Rnd*6)+1)

job75

je suis d'acord avec toi sur les 6561
(Mais sur ces 6561, il faut sortir celles qui aboutissent à 24 )

C'est ce que je trouve avec ce code
Code:
Sub permut()'ligne 1 à ligne 6561 remplies
Dim i&, j&, k&, l&, m&, cpt&
cpt = 1
For j = 1 To 9
For k = 1 To 9
For l = 1 To 9
For m = 1 To 9
Cells(cpt, 1) = j & k & l & m
cpt = cpt + 1
Next
Next
Next
Next
End Sub
PS: Question au matheux: il s'agit de permutations ou de combinaisons

Dernière édition:

Staple1600

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Re

Job75: tu n'es pas d'accord avec cette formule ?

Ainsi, étant donné une série de quatre chiffres et d'un ensemble de trois opérations arithmétiques il ya 5 expressions différentes.
Ainsi, le nombre de possibilités d'expressions avec quatre chiffres de un à neuf, et trois opérations arithmétiques est

Dernière édition:

tototiti2008

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Oui, moi j'avais trouvé 7 cas en comptant celui sans parenthèses

Staple1600

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Re

tototiti2008: tu veux dire quoi par 7 cas ?

7 expressions mathématiques régulières ?

tototiti2008

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

re,
7 positions différentes des parenthèses dans une expression de 4 chiffres et 3 opérateurs.
si A, B, C et D les chiffres
si % les opérateurs, quels qu'ils soient :

1) A%B%C%D
2) (A%B)%C%D
3) A%B%(C%D)
4) (A%B)%(C%D)
5) (A%B%C)%D
6) A%(B%C%D)
7) A%(B%C)%D

Edit : c'est pas de ça dont vous parliez ? j'ai tapé complètement à côté ? Dernière édition:

job75

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Salut Staple, tototiti

Comme Staple l'a bien compris, l'étude de la mise en place des parenthèses est fondamentale dans ce problème. Comme indiqué dans mon post précédent, il y a 5 cas possibles, mais pour en être sûr, il faut le démontrer et les trouver.

Une 1ère remarque est que les parenthèses ne sont utiles que pour regrouper des additions ou des soustractions. Pour cette raison, il n'y a pas à étudier les cas de paires de parenthèses imbriquées.

Une 2ème remarque est que la multiplication est commutative, mais pas la division.

Cas de regroupement de 2 chiffres :
(x1°x2)°x3°x4
x1°(x2°x3)°x4
x1°x2°(x3°x4)===> pas nécessaire, car le cas précédent étudie les mêmes possibilités (cf 2ème remarque)
(x1°x2)°(x3°x4)

Cas de regroupement de 3 chiffres :
(x1°x2°x3)°x4
x1°(x2°x3°x4)

Finalement donc les 5 cas de parenthèses à étudier sont :

(x1°x2)°x3°x4
x1°(x2°x3)°x4
(x1°x2)°(x3°x4)
(x1°x2°x3)°x4
x1°(x2°x3°x4)

Il n'est pas nécessaire d'étudier le cas sans parenthèses x1°x2°x3°x4
car ses possibilités sont étudiées dans les cas avec parenthèses.

A+

Edit : excuse-moi tototiti, dans la préparation de mon post, je n'avais pas vu le tien. Tout à fait d'accord avec toi, seulement 2 des 7 cas ne sont pas nécessaires.

Dernière édition:

Risleure

XLDnaute Occasionnel
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Bonjour Staple, le Forum

Staple qui pose une question, je regarde car d'habitude c'est plutot lui qui y répond Bref je regarde et cela ressemble à un défi dont l'utilité n'est pas immédiate mais j'aime bien.

Donc est-ce du même jeu dont parle le lien ?
24 Game - Solutions to the 24 Game

Il y a un code Java et C qui semble résoudre ce jeu.

Je n'ai malheureusement pas le temps et très probablement pas les compétences mais je m'abonne à ce fil pour suivre avec attention le développement de cette affaire.

Courage

job75

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Re, salut Risleure,
Pour répondre a Staple, je ne vois pas le raisonnement qui amène à la formule que tu indiques, mais elle est certainement juste. Les grandes parenthèses représentent des nombres de combinaisons.
A+

Staple1600

XLDnaute Barbatruc
Re : [VBA] Maths -algorithm- "The 24 Game" aide demandée (combinaisons/permutations)

Rebonsoir à tous

Risleure: oui c'est le lien que j'indiquais dans mon fil de 17h25.

J'ai bien vu le progam en C mais je n'ai pas regardé les sources, j'essaye d'abord de trouver avec votre aide.

Je ne sais si la bonne solution est de stocker toutes les formules possibles dans un tableau (array)

(c'est ce que j'avais commencé à faire
d'ou ce premier post ou pierrejean avait eu le dernier mot (merci à lui)

Pour le moment, j'étudie encore le code de tototiti2008 et j'attends vos propositions.

Voici également un code trouvé sur le net qui pourrait nous aider.

Code:
Option Base 1
Option Explicit
Global Big_Array() As String
Dim CurrentRow As Long

Public Sub test()
'auteur: Ger Plante
Dim x As Variant 'this will store each number
Dim y() As String ' this will store the operators
Dim Op_Index1 As Integer 'an index for the operator
Dim Op_Index2 As Integer 'an index for the operator
Dim Op_Index3 As Integer 'an index for the operator
Dim my_formula As String 'a string to construct the formula
Dim Permutations() As String 'an  array to store the permutations of the numbers
Dim Base_Numbers As String 'the numbers to check seperated by a comma
Dim iLoop As Integer
Dim iloop2 As Integer
Dim InString As String 'temp string used in creating the permutatons.

ReDim y(4)
y(1) = "+"
y(2) = "-"
y(3) = "*"
y(4) = "/"

'Base_Numbers = "1,2,3,4,5,6"
Base_Numbers = "1,2,3,4"
x = Split(Base_Numbers, ",")

'create all permutations of these numbers (Factorial of the number of numbers)
ReDim Permutations(WorksheetFunction.Fact(UBound(x) + 1))
ReDim Big_Array(WorksheetFunction.Fact(UBound(x) + 1))
For iLoop = LBound(x) To UBound(x)
InString = InString + Chr(48 + iLoop)
Next iLoop
CurrentRow = 1
Call GetPermutation("", InString) 'creates a big array to store permutations

For iLoop = LBound(Big_Array) To UBound(Big_Array)
For iloop2 = 0 To UBound(x)
Permutations(iLoop) = Permutations(iLoop) & x(Mid(Big_Array(iLoop), iloop2 + 1, 1)) & ","
Next iloop2
Permutations(iLoop) = Left(Permutations(iLoop), Len(Permutations(iLoop)) - 1)
Next iLoop

Worksheets(1).Columns("A:B").ClearContents

For iLoop = 1 To UBound(Permutations)
x = Split(Permutations(iLoop), ",")
'if x has four numbers, then there will be three operators to use.
For Op_Index1 = LBound(y) To UBound(y)
For Op_Index2 = LBound(y) To UBound(y)
For Op_Index3 = LBound(y) To UBound(y)
my_formula = x(0) & y(Op_Index1) & x(1) & y(Op_Index2) & x(2) & y(Op_Index3) & x(3)
Worksheets(1).Range("A" & Worksheets(1).Range("A65535").End(xlUp).Row + 1).Value = my_formula & "="
Worksheets(1).Range("B" & Worksheets(1).Range("B65535").End(xlUp).Row + 1).Value = "=" & my_formula
Next Op_Index3
Next Op_Index2
Next Op_Index1
Next iLoop

Worksheets(1).Columns("A:B").AutoFit

End Sub

Sub GetPermutation(x As String, y As String)
'   The source of this algorithm is unknown
' copied from ozgrid on 01 June 2006
Dim i As Integer, j As Integer
j = Len(y)
If j < 2 Then
Big_Array(CurrentRow) = x & y
CurrentRow = CurrentRow + 1
Else
For i = 1 To j
Call GetPermutation(x + Mid(y, i, 1), _
Left(y, i - 1) + Right(y, j - i))
Next
End If
End Sub