Le compte est bon

 

Un problème bien connu par tout le monde est le jeu télévisé "Le compte est bon". Rappelons le principe du jeu pour ceux qui ne le connaissent pas: on tire 6 nombres au hasard parmi les suivants "1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 25, 50, 75, 100" et un autre nombre entre 101 et 999. Il faut trouver le dernier nombre en faisant des opérations mathématiques sur les 6 premiers nombres en ne les utilisant qu'une fois. On reste dans le domaine des entiers naturels (donc positifs). On dispose de quatre opérations : " +, -, *, / ".

Supposons qu'on a seulement deux nombres; les opérations qu'on peut faire sur ces deux nombres sont les suivantes :

"n1 + n2" "n2 + n1"

"n1 - n2"             "n2 - n1"

"n1 * n2"             "n2 * n1"

"n1 / n2" si n1 est un multiple de n2          "n2 / n1" si n2 est un multiple de n1

On peut tout de suite diviser par 2 le nombre des opérations possibles. On se ramène pour cela au cas où n1 >= n2 :

"n1 + n2" est équivalent à "n2 + n1"

"n2 - n1" n'a pas de sens car cela donnerait un nombre négatif, donc il suffit de considérer "n1-n2"

"n1 * n2" est équivalent à "n2 * n1"

"n1 / n2" n'a de sens que si "n1 >= n2" et si n1 est un multiple de n2

Supposons maintenant qu'on a 3 nombres, par exemple 3, 9, 8. D'après ce qui précède, il faut que les nombres soient triés par ordre décroissant. Pour cela, nous allons les mettre dans un tableau, et on aura : 9, 8, 3. Nous allons travailler tout le long du programme avec seulement des paires de 2 nombres. Ici nous avons trois paires possibles :"9,8", "9,3", "8,3". Pour chacune de ces paires, on fait les quatre opérations et on obtient de nouveaux nombres qu'il faudra combiner avec celui qui reste. Pour mieux comprendre, nous allons détailler les opérations pour ce cas. Il ne faut pas oublier que les nombres sont rangés dans un tableau et que nous allons utiliser ce tableau :

Etude de la première paire :

9 + 8 = 17                                                          ¦ 1

    On a un nouveau tableau trié qui contient 2 nombres : 17, 3    ¦

    17 + 3 = 20                                                     ¦ 2

    17 - 3 = 14                                                     ¦ 3

    17 * 3 = 51                                                     ¦ 4

    Division impossible.                                            ¦

9 - 8 = 1                                                           ¦ 5

    On a un nouveau tableau trié qui contient 2 nombres : 3, 1     ¦

    3 + 1 = 4                                                       ¦ 6

    3 - 1 = 2                                                       ¦ 7

    3 * 1 = 3                                                       ¦ 8

    3 / 1 = 3                                                       ¦ 9

9 * 8 = 72                                                          ¦ 10

    On a un nouveau tableau trié qui contient 2 nombres : 72, 3    ¦

    72 + 3 = 75                                                     ¦ 11

    72 - 3 = 69                                                     ¦ 12

    72 * 3 = 216                                                    ¦ 13

    72 / 3 = 24                                                     ¦ 14

Division impossible.                                                ¦

                                                                    ¦

Etude de la deuxième paire :                                        ¦

9 + 3 = 12                                                          ¦ 15

    On a un nouveau tableau trié qui contient 2 nombres : 12, 8    ¦

    12 + 8 = 20                                                     ¦ 16

    12 - 8 = 4                                                      ¦ 17

    12 * 8 = 96                                                     ¦ 18

    Division impossible.                                            ¦

9 - 3 = 6                                                           ¦ 19

    On a un nouveau tableau trié qui contient 2 nombres : 8, 6     ¦

    8 + 6 = 14                                                      ¦ 20

    8 - 6 = 2                                                       ¦ 21

    8 * 6 = 48                                                      ¦ 22

    Division impossible.                                           ¦

9 * 3 = 27                                                          ¦ 23

    On a un nouveau tableau trié qui contient 2 nombres : 27, 8    ¦

    27 + 8 = 35                                                     ¦ 24

    27 - 8 = 19                                                     ¦ 25

    27 * 8 = 216                                                    ¦ 26

    Division impossible.                                            ¦

9 / 3 = 3                                                           ¦ 27

    On a un nouveau tableau trié qui contient 2 nombres : 8, 3     ¦

    8 + 3 = 11                                                      ¦ 28

    8 - 3 = 5                                                       ¦ 29

    8 * 3 = 24                                                      ¦ 30

    Division impossible.                                            ¦

                                                                    ¦

Etude de la troisième paire :                                       ¦

8 + 3 = 11                                                          ¦ 31

    On a un nouveau tableau trié qui contient 2 nombres : 11, 9    ¦

    11 + 9 = 20                                                     ¦ 32

    11 - 9 = 2                                                      ¦ 33

    11 * 9 = 99                                                     ¦ 34

    Division impossible.                                            ¦

8 - 3 = 5                                                           ¦ 35

    On a un nouveau tableau trié qui contient 2 nombres : 9, 5     ¦

    9 + 5 = 14                                                      ¦ 36

    9 - 5 = 4                                                       ¦ 37

    9 * 5 = 45                                                      ¦ 38

    Division impossible.                                            ¦

8 * 3 = 24                                                          ¦ 39

    On a un nouveau tableau trié qui contient 2 nombres : 24, 9    ¦

    24 + 9 = 33                                                     ¦ 40

    24 - 9 = 15                                                     ¦ 41

    24 * 9 = 216                                                    ¦ 42

    Division impossible.                                            ¦

Division impossible.                                                ¦

On peut donc en déduire l'algorithme général du programme :

1 - on fait un algorithme qui sélectionne une paire

2 - on fait une opération sur cette paire

3 - si on a trouvé le nombre voulu, on quitte l'algorithme

4 - on sauvegarde le tableau courant dans un tableau auxiliaire

5 - avec le nombre obtenu après l'opération on obtient un tableau auxiliaire plus petit d'un élément

6 - on trie le tableau auxiliaire

7 - on fait un appel récursif pour recommencer le raisonnement sur ce tableau

8 - si on n'a pas fini les quatre opérations, on boucle sur l'étape 2

9 - si on n'a pas fini toutes les paires, on boucle sur l'étape 1

Voyons maintenant quel est le temps d'exécution.

Si toutes les divisions étaient possibles, alors on aurait 60 opérations pour ces 3 nombres, ou trois paires, ce qui n'est pas énorme.

Pour 4 nombres n1, n2, n3, n4 on aurait 6 paires : n1 n2, n1 n3, n1 n4, n2 n3, n2 n4, n3 n4 et, pour chacune de ces paires, on obtiendrait trois sous-paires : par exemple "n1 n2" forme un nombre qui sera combiné avec n3 et avec n4 (c'est le cas ci-dessus, donc 60 combinaisons). Il faut envisager les quatre signes pouvant apparaître entre n1 et n2 donc, pour les trois nombres formés par "n1 n2", "n3", "n4", on a en tout 4*60=240 combinaisons possibles; comme on a six paires à 240 possibilités chacune, on a en tout 1440 possibilités; la croissance est énorme mais en réalité elle est bien inférieure à cause des divisions impossibles et aussi à cause de certaines soustractions, comme nous le verrons par la suite; donc il y a beaucoup de branches de l'arbre récursif qui ne sont pas exploitées.

En faisant le même raisonnement pour 5 nombres on aurait 10 paires à 4 possibilités chacune et à 1440 sous-possibilités, soit 57600 possibilités. Et enfin pour 6 nombres on a 15 paires à 4 possibilités chacune et à 57600 sous-possibilités chacune donc en tout 3.456.000.

En réalité, grâce aux divisions impossibles et grâce aux soustractions qui donnent un reste nul (si on a deux fois 25, alors on a 25 - 25 = 0, inutile de continuer à explorer dans cette direction) on n'explore que 60% des possibilités, c'est à dire environ 2 millions de possibilités.

Pour réduire le temps de réflexion, il faut faire le programme d'une manière différente, car ici on a beaucoup d'opérations qui se répètent comme :

- les opérations 2, 16 et 32, car a+b+c=a+c+b=b+c+a

- les opérations 13, 26 et 42 car a*b*c=a*c*b=b*c*a

Il faut aussi tenir compte de la façon de programmer : étant donné le nombre élevé de combinaisons il faut avoir le moins de procédures possibles, et avec le plus petit nombre de paramètres possible, car pendant la récursivité, le fait d'empiler les variables locales et les paramètres demande beaucoup de temps.

Dans le programme, nous avons dans le tableau "nombres", à l'indice 0, le nombre à trouver (ici 963) et ensuite tous les nombres tirés au hasard. C'est ce tableau qu'il vous faudra modifier pour trouver une solution à un autre problème.

Voici le programme :

 

type tab = array[0..6] of longint;
 
const signe: string[4] = '+-*/';
  nombres: tab = (963, 25, 5, 4, 3, 3, 1);
 
var trouve, echange: boolean;
  aa: longint;
  ii, jj: integer;
 
procedure operations(var t: tab; max: integer);
var i, j1, j2: integer;
  a: longint;
  t1: tab;
begin
  for i := 1 to 4 do
    for j1 := 1 to max - 1 do
      for j2 := j1 + 1 to max do
      begin
        case i of
          1: a := t[j1] + t[j2];
          2: a := t[j1] - t[j2];
          3: a := t[j1] * t[j2];
          4: begin
              a := t[j1] div t[j2];
              if t[j2] * a <> t[j1] then a := 0;
            end;
        end;
        if a > 0 then
        begin
          if a = t[0] then
          begin
                  //gotoxy(1,8-max);write(t[j1],signe[i],t[j2],'=',a);
            Form1.ListBox1.Items.Add(inttostr(t[j1]) + signe[i] + inttostr(t[j2]) + '=' + inttostr(a));
            trouve := true; exit;
          end;
          move(t, t1, 28);
          t1[j1] := a; t1[j2] := 0;
          repeat
            echange := false;
            for ii := 1 to max - 1 do
              if t1[ii] < t1[ii + 1] then
              begin
                aa := t1[ii]; t1[ii] := t1[ii + 1]; t1[ii + 1] := aa;
                echange := true;
              end;
          until not echange;
          operations(t1, max - 1);
          if trouve then
          begin
                  //gotoxy(1,8-max);write(t[j1],signe[i],t[j2],'=',a);
            Form1.ListBox1.Items.Add(inttostr(t[j1]) + signe[i] + inttostr(t[j2]) + '=' + inttostr(a));
            exit;
          end;
        end;
      end;
end;
 
procedure TForm1.Button1Click(Sender: TObject);
begin
  Screen.Cursor := crHourGlass;
  trouve := false;
  ListBox1.Clear;
  Application.ProcessMessages;
  operations(nombres, 6);
  Screen.Cursor := crDefault;
end;

 

Télécharger le code source Delphi