Discussion :

[alex_fomine]

Bonsoir,
Je suis à la recherche de solution pour ce problème mathématique: Utiliser la totalité des neufs chiffres de 1 à neuf (chacun remplace une seule lettre ) pour remplacer correctement les lettres de a à i et avoir une égalité correcte dans :
a/(bc) + d/(ef) + g/(hi) = 1

où (bc) , (ef) et (hi) sont des écritures décimales et non des produits. ( ie: (bc)=10xb+c , ...)

Je voudrais écrire un programme Pascal qui peut tester toutes les permutations possibles et afficher celles qui sont des solutions, à partir de la liste 123456789.

Je ne suis qu'un amateur en programmation, j'ai essayé mais j'ai pas réussi et j'ai besoin de votre aide.

Merci d'avance,
Alex

[tbc92]

Le prof qui t'a proposé cet exercice est un bon prof. C'est un exercice intéressant. Un bon prof comme ça, on ne va pas saboter son travail, en te donnant la solution toute faite à son exercice. Tu as fait quoi pour chercher la solution ?

[alex_fomine]

Merci tbc92 !
Je suis un amateur trop vieux et trop loins du temps de l'apprentissage.. L'exercice est un défi lancé par un ami. auquel j'ai pensé longuement pour trouver rigoureusement une solution.
mais je n'ai pas réussi. voila pourquoi je voudrai renouer avec mon vieux Turbo7 et chercher une solution.

@ tbc92,

j'ai pas voulu tester sa directement en effectuant une boucle for sur tous les entiers de 111111111 à 999999999
Je veux me limiter aux permutations seulement

[tbc92]

Si tu testes tous les entiers de 111111111 à 999999999 , tu vas avoir les entiers comme 111111120 donc avec le chiffre 0 --> hors-périmètre. Et tu vas avoir les entiers comme 111111111 , donc répétition du chiffre 1, donc hors périmètre. Tu vas tester énormément de combinaisons hors-périmètre.

Si tu testes les nombres a de 1 à 9 , b de 1 à 9, avec b différent de a, c de 1 à 9, avec c différent de a et de b ... etc etc, tu vas diviser le temps de traitement par 3000 environ.

Un programme 'brutal', fait en appliquant le conseil ci-dessus, va aller très vite et te donner la liste des réponses en moins d'une seconde.

Tu peux même te limiter aux cas où a<d et d<g ... pour des raisons de 'symétrie'.

[wiwaxia]

Bonjour,

Il te faut définir un tableau de 9 entiers, dont tu pourras éliminer à chaque combinaison testée les termes déjà utilisés, et à ne pas réemployer.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
TYPE TabE = ARRAY[1..9] OF Byte;
CONST Lini: TabE = (1, 2, 3, 4, 5, 6, 7, 8, 9);
VAR Liste: TabE:
// Initialisation de la variable
Liste:= Lini;

Il te faut ensuite procéder à l'énumération des combinaisons, à priori très nombreuses - il y en a théoriquement 9! = 362880 - cela reste encore raisonnable, mais 9⁹ = 387420489 si l'on n'élimine pas les termes identiques, et ce sera alors très long ...

L'expression de la somme S = a/(bc) + d/(ef) + g/(hi) autorisant la permutation des 3 termes, tu peux imposer la restriction:
a < d < g qui évitera la sortie de termes identiques (comme on te l'a déjà suggéré); c'est ce qu'effectuera la triple boucle:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
FOR a:= 1 TO 7 DO
  FOR d:= (a + 1) TO 8 DO
    FOR g:= (d + 1) TO 9 DO 
      BEGIN
        ...
      END;

À ce stade, il ne te reste plus que 6 termes et tu peux envisager de travailler sur une liste réduite, que l'on peut établir de la façon suivante:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
PROCEDURE CalcLi(Xu, Xv, Xw, Xm: Byte; VAR L_6: TabE);
  VAR i, k: Byte;
  BEGIN
    k:= 0; 
    FOR i:= 1 TO Xm DO
      IF (i<>Xu) AND ((i<>Xv) AND (i<>Xw)) THEN 
        BEGIN
          Inc(k); L_6[k]:= i
        END;
 
    WHILE (k<9) DO BEGIN
                     Inc(k); L_6[k]:= 0
                   END
  END;

Le programme deviendrait:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
FOR a:= 1 TO 7 DO
  FOR d:= (a + 1) TO 8 DO
    FOR g:= (d + 1) TO 9 DO 
      BEGIN
        CalcLi(a, d, g, 9, Liste);
        ...
      END;

et il ne resterait plus qu'à travailler sur 6 termes (b, c, e, f, h, i), en les combinant encore 3 par 3, et en éliminant à mi-parcours les 3 valeurs sorties d'une façon semblable
Ici cependant, l'énumération répond à des contraintes différentes.

# Autre variante: au lieu de calculer la somme des quotients S = a/(bc) + d/(ef) + g/(hi) , tu pourrais envisager celui du produit S' = S*(bc)*(ef)*(hi) = a*(ef)*(hi) + d*(bc)*(hi) + g*(bc)*(ef) ,
résultat entier pour lequel la vérification de l'égalité S' = (bc)*(ef)*(hi) ne pose pas de difficulté.

Code à vérifier - j'ai pu laisser passer des erreurs.

[Flodelarab]

Bonjour

Dénombrons.
On tire 9 chiffres parmi 9, dans l'ordre, et sans répétition; c'est donc un arrangement.
Il s'agit même d'une factorielle puisque tous les éléments sont concernés.
9! = 362880

Sauf que les 3 termes de la somme sont permutables. (puisque l'addition est commutative)
Donc il y a 6 fois moins d'ordres puisque placer 3 parmi 3 dans l'ordre et sans répétition est aussi un arrangement, et même une factorielle. 3!=6.

Il y a donc 362880 / 6 = 60480 sommes uniques.

Largement faisable en force brute par un ordinateur.

En classant les numérateurs par ordre croissant, tu dois pouvoir t'en sortir sans trop réfléchir.

et il ne resterait plus qu'à travailler sur 6 termes (b, c, e, f, h, i), en les combinant encore 3 par 3, et en éliminant à mi-parcours les 3 valeurs sorties d'une façon semblable

Ah oui. Je n'avais pas pensé à ça.
6/12=7/14 donc on risque de faire 2 fois la même sous-séquence.

Mais si ce n'est pas les mêmes nombres, ce n'est pas la même réponse.
Donc on ne peut pas simplifier.