Défi

**ti-ben** · 31/01/2005, 08h41

Bonjour à tous,

J'essaie d'écrire un algo pour trouver la solution mathématique suivante:

j'ai 6 nombres entiers tirés au hasard. Ces nombres peuvent être de 1 à 10, ou 25, 50, 75 et 100. Avec ces nombres et les 4 opérateurs il faut trouver la formule pour atteindre un autre nombre random entre 100 et 999.

Exemple:

75 8 7 9 4 3 pour faire 347

La solution serait 75*4 + 7*8 - 9 Il peut y en avoir plusieurs évidemment.

Quelqu'un a une idée?

**moi et mon pc** · 31/01/2005, 09h56

la je vois pas mais tu veut un prog pour tricher a l'émission "des chiffres et des lettres " et remplacer Bertrand Renard ou quoi ?

**ti-ben** · 31/01/2005, 10h46

En fait j'ai recréé le jeu en Delphi. J'arrive à donner la liste des mots possibles aux lettres, ça c'est facile mais donner la solution aux jeu des chiffres, alors là c'est pas évident...

**tesla** · 31/01/2005, 10h58

Il n'y a pas de "formule" pour ce problème.

Différentes approches :
- Si le nombre à deviner est premier, tu ne peux employer que des additions ou soustractions.
Examine le nombre à deviner en essayant de trouver par lesquels des 6 nombres il peut être divisé.

**ti-ben** · 31/01/2005, 11h08

Il y a surement une formule puisque le jeu électronique donne la solution sur demande....

**ti-ben** · 31/01/2005, 11h16

J'ai trouvé ça, ça semble être la solution mais je ne connais pas le PERL, quelqu'un pourrais me le transcrire en Delphi?

http://users.skynet.be/chricat/ChiffresLettres.html

Merci.

**Médiat** · 31/01/2005, 11h37

Envoyé par ti-ben

J'ai trouvé ça, ça semble être la solution mais je ne connais pas le PERL, quelqu'un pourrais me le transcrire en Delphi?

Et quand tu as fini de manger, tu m'appelles, je ferais la vaisselle !

Le programme est aussi en C ! Ce devrait être facile à transcrire en Delphi !

**korntex5** · 31/01/2005, 12h24

Voila ma solution tudututu tudutu le compte est bon j'ai inventé pour toi en 1h chrono une solution a base d'aléatoire dite méthode combinaisons aléatoires
on peu améliorer mais c pas mal et ça finis toujours par arriver au bon résultat

Code sous delphi

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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
 
unit chiffres;
 
////////////////////////////////////////////////////////////////////////////////
//         Algorithme de Jérôme JEAN-MARAULT(KORNTEX5)                //
//         dit de calcul par combinaisons aléatoires                            //
////////////////////////////////////////////////////////////////////////////////
 
interface
 
uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, StdCtrls;
 
type
  TForm1 = class(TForm)
    Edit1: TEdit;
    Edit2: TEdit;
    Edit3: TEdit;
    Edit4: TEdit;
    Edit5: TEdit;
    Edit6: TEdit;
    Edit7: TEdit;
    Edit8: TEdit;
    Button1: TButton;
    Button2: TButton;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private
    { Déclarations privées }
  public
    function ajoute(nombre1,nombre2:string):string;
    function soustrait(nombre1,nombre2:string):string;
    function multiplie(nombre1,nombre2:string):string;
    function divise(nombre1,nombre2:string):string;
    procedure initliste;
  end;
 
var
  Form1: TForm1;
  calculencours:String;
  MeilleurResult:String='999999';
  ListeDesChiffres:Tstringlist;
  Stop:boolean;
implementation
 
{$R *.dfm}
 
 
 
procedure TForm1.initliste;
begin
//création de la liste des chiffres
  ListeDesChiffres.Add(edit1.text);
  ListeDesChiffres.Add(edit2.text);
  ListeDesChiffres.Add(edit3.text);
  ListeDesChiffres.Add(edit4.text);
  ListeDesChiffres.Add(edit5.text);
  ListeDesChiffres.Add(edit6.text);
end;
 
procedure TForm1.Button1Click(Sender: TObject);
var
    result,nombre1,nombre2:string;
    i,j,k,l:integer;
    ResultatTrouve:boolean;
begin
try
  ResultatTrouve:=false;
  Stop:=false;
  ListeDesChiffres:=Tstringlist.Create;
  initliste();
   Randomize;
  j:=random(ListeDesChiffres.Count);
  result:=ListeDesChiffres[j];
  ListeDesChiffres.Delete(j);
 
  while (not ResultatTrouve) or (ListeDesChiffres.Count<>0) or stop do
  begin
    application.ProcessMessages;
   try
     if ListeDesChiffres.Count=0 then
     begin
         initliste();
         Randomize;
         j:=random(ListeDesChiffres.Count);
         result:=ListeDesChiffres[j];
         ListeDesChiffres.Delete(j);
         calculencours:='';
     end;
 
       Randomize;
       j:=random(ListeDesChiffres.Count);
       nombre1:=ListeDesChiffres[j];
       ListeDesChiffres.Delete(j);
       nombre2:=result;
   except
 
   end;
     Randomize;
     i:=random(4);  //choix du type d'opération +-*/
     case I of
      0: begin     //adition
          result:=Ajoute(nombre1,nombre2);
          calculencours:=calculencours + nombre1 + '+' + nombre2 + '=' + result+ '; ';
         end;
      1: begin     //Soustraction
          Randomize;
          k:=random(1); //choix du sens de l'opération
          if (k=0)and(nombre1<>nombre2) then
          begin
            result:=Soustrait(nombre1,nombre2);
            calculencours:=calculencours+nombre1+' - '+nombre2+ '=' + result+ '; ';
          end
          else if (nombre1<>nombre2) then
          begin
            result:=Soustrait(nombre2,nombre1);
            calculencours:=calculencours+nombre2+' - '+nombre1+ '=' + result+ '; ';
          end;
         end;
      2: begin     //MULTIPLCAION
          result:=Multiplie(nombre1,nombre2);
          calculencours:=calculencours+nombre1+' * '+nombre2+ '=' + result+ '; ';
         end;
      3: begin     //Divison
          Randomize;
          k:=random(1);   //choix du sens de l'opération
          if (k=0)and(nombre2<>'0') then
          begin
            result:=divise(nombre1,nombre2);
            calculencours:=calculencours+nombre1+' / '+nombre2+ '=' + result+ '; ';
          end
          else if nombre1<>'0' then
          begin
            result:=Divise(nombre2,nombre1);
            calculencours:=calculencours+nombre2+' / '+nombre1+ '=' + result+ '; ';
          end;
         end;
     end;
    //comparaison résultat en cours et objectif
    if abs(strtofloat(edit7.text)-strtofloat(result))
        <
       abs(strtofloat(edit7.text)-strtofloat(MeilleurResult)) then
    begin
      edit8.Text:=calculencours;
      MeilleurResult:=result;
    end;
    if MeilleurResult=edit7.text then
      ResultatTrouve:=true;
  end;
  ListeDesChiffres.Free;
except
 
end;
 
end;
 
 
 
 
 
procedure TForm1.Button2Click(Sender: TObject);
begin
  Stop:=true;
end;
 
function TForm1.divise(nombre1, nombre2: string): string;
begin
  result:=floattostr(strtofloat(nombre1) / strtofloat(nombre2));
end;
 
function TForm1.multiplie(nombre1, nombre2: string): string;
begin
  result:=floattostr(strtofloat(nombre1) * strtofloat(nombre2));
end;
 
function TForm1.soustrait(nombre1, nombre2: string): string;
begin
  result:=floattostr(strtofloat(nombre1) - strtofloat(nombre2));
end;
 
function TForm1.ajoute(nombre1, nombre2: string): string;
begin
  result:=floattostr(strtofloat(nombre1) + strtofloat(nombre2));
end;
 
end.

**dagoba** · 31/01/2005, 13h32

python est tres simple a apprendre
va voir c pas difficile

du moins plus que le pascal

**Laurent Gomila** · 31/01/2005, 13h53

J'avais vu une application des algorithmes génétiques pour la résolution de ce problème, je ne sais pas si c'est une solution pertinente (j'ai jamais approfondi la chose) mais ça peut être une piste.

**Nemerle** · 31/01/2005, 17h11

Envoyé par tesla

Il n'y a pas de "formule" pour ce problème.

Différentes approches :
- Si le nombre à deviner est premier, tu ne peux employer que des additions ou soustractions.
Examine le nombre à deviner en essayant de trouver par lesquels des 6 nombres il peut être divisé.

13 = 4 * 3 + 1

**tesla** · 01/02/2005, 10h48

Ce que je voulais dire :
L'idée la plus simple pour trouver le nombre N c'est de trouver x et y tels que x * y = N. Impossible si N est premier.
La technique fréquemment utilisée par les candidats humains c'est d'approcher N en trouvant les couples (a, b) tq N = ab + r. Puis de voir comment en combinant les 6 chiffres on peut se rapprocher de a, b et r.

**SKZ81** · 02/02/2005, 03h04

Non loulou24, ni algo génétique, ni recuit simulé, ni d'ailleurs aucune autre des heuristiques proposées jusqu'à présent n'est valables, dans la mesure ou une heuristique est une recherche approximée qui ne peut ni assurer que la solution optimale (selon des critères de compacité (simplicité) de l'expression, en plus de la justesse par exemple) à été trouvée mais surtout sont incapable de détecter une absence de solution (impossibilité de terminaison, d'où le button2 de l'algo delphi proposé). Même si la solution approximative est souvent satisfaisante, je trouve qu'un tel algo ne répond pas aux spéfications fonctionnelles qu'on est en droit de poser (être sûr de trouver la solution exacte la plus simple en un temps fini). On a tout le temps de reflexion du joueur dans le cas interactif pour mouliner dans un thread.

Donc, seule la solution proposée sur le site que tu as trouvé, ti-ben, est valable. Par contre je connais pas le delphi, ni le perl, ceci dis je veux bien t'aider à interpréter le C. Pose des questions sur les éléments de syntaxes que tu comprends pas, en parallèle écris l'algo en pseudo-code, deux avantages :
- tu y gagnera à comprendre l'algo et en prime une initiation au C (ou au perl si tu préfères)
- Je me fatigurai moins à t'expliquer les choses qu'à traduire le code
- D'autres peuvent t'aider
- c'est le principe du forum !

En plus quand aura dans les mains un algo qui fonctionne en delphi, tu pourra intégrer une astuce :
Utiliser une liste triée des nombres utilisables pour le calcul.
En effet, tu pourrais (si je me plante pas), à chaque pas, orienter la recherche, et gagner un facteur 1/2 sur chaque pas, soit un facteur 32 au total. J'ai estimé ça à la louche, et ça demande de la recherche (même pas sûr que ça puisse aboutir, mais ça m'interesse).
Par contre je vais pas le faire si ça sert à rien j'ai d'autres priorités, si tu n'es pas motivé.

J'attend de pied ferme tes questions !

[edit]
tesla : ispice de shadock, va

[/edit]

**scarabee** · 02/02/2005, 09h18

Si ca t'amuse, j'ai fait des progs pour jouer aux chiffres et lettres en trichant un peu pendant que je m'ennuyais au bureau

ICI

Si ca t'interesse, je dois pouvoir retrouver mes sources.

**ti-ben** · 02/02/2005, 15h20

Bonjour Scrabee,

En effet ça m'intéresse puisque ton application donne le résultat avec les opérations pour y arriver. C'est justement ce que je cherche à faire.

Si tu pouvais le retrouver ce serait gentil.

Merci.