Compétition: Jeu Chiffres sans Lettres

Bonjour,

On m'a demandé de construire une procédure récursive pour "résoudre" le jeu de chiffres et lettres et plus précisément: les chiffres sans lettres:)

Je m'explique:
il s'agit de trouver une suite finie d'opérations arithmétiques simples {+, -, x, /} appliquées chacune (pas nécessairement toutes) sur des couples de nombres choisis parmi 5 nombres positifs (exemple: 5, 12, 7, 50, 100) pour aboutir (si c'est possible) au résultat qui est un nombre entier positif.
Respecter plusieurs contraintes à savoir:
1. un nombre est utilisée une seule fois.
2. le résultat d'une opération peut être utilisé, mais une seule fois aussi.
3. les opérations de division donnant naissance à des nombre rationnels est interdites.



Exemple:
Construire 99 avec les nombres {1, 2, 3, 4, 5}
La solution est cette suite d'opérations:
4 x 5 = 20
3 + 2 = 5
5 x 20 = 100
100 - 1 = 99 <----- nombre trouvé.

L'objectif est d'implémenter une procédure récursive qui prend les {1, 2, 3, 4, 5} avec leur 99 et nous donne une solution au problème.

Bon courage.

Complément:

Dans le cas où il est impossible de trouver la
solution exacte, l'algorithme devrait fournir le nombre le plus proche
de la solution.

C'est un peu très dur comme défi !!!
J'essaierai d'abord de penser "sans récursivité"
c moin dur pour moi

Une version très prometteuse postée par manianis dans le forum:
http://programmation.megabb.com/

Pour voir le site web de manianis:
http://manianis.sitesled.com/

Code:


program chiffres;

const
    MAXNB = 6;   

type
    EltRech = record
        val : integer;
        text : string[80];
    end;
    TabEltRech = Array [0..MAXNB] of EltRech;

var obj, best_delta : integer;

procedure Saisie_Tab(Var nbnb : integer; Var obj : integer ; Var jeu : TabEltRech);
var i : integer;
begin
    Writeln('Entrée des valeurs');
    repeat
        Write('Nombre de nombres (<', MAXNB,') :');
        Readln(nbnb)
    until (nbnb <= MAXNB);
    for i := 0 to (nbnb - 1) do
    begin
        Write('Entier ', i, ' : ');
        Readln(jeu[i].val);
        Str(jeu[i].val, jeu[i].text);
    end;
    jeu[nbnb].val := 0;
    Writeln('Entrée du résultat escompté');
    Write('Résultat = '); Readln(Obj);
end;

procedure Tri_Tab(nbnb : integer ; var jeu : TabEltRech);
var i, j, max : integer;
    swap : EltRech;
begin
    for i:=0 to nbnb - 2 do
    begin
        max := i;
        for j := i+1 to nbnb - 1 do
            if (jeu[j].val > jeu[max].val) then max := j;
       
        if (max <> i) then
        begin
            swap := jeu[max];
            jeu[max] := jeu[i];
            jeu[i] := swap;
        end;
    end;
end;

function cherche(var jeu : TabEltRech):Boolean;
var i, j, k, nbout : integer;
    big, small : integer;
    tbig, tsmall : string[80];
   
    jeulocal : TabEltRech;
begin
    i := 0;
    while (jeu[i].val <> 0) do
    begin
        if (abs(jeu[i].val - obj)
        begin
            best_delta := abs(jeu[i].val - obj);
            Writeln(jeu[i].text, '=', jeu[i].val);
            if jeu[i].val = obj then
            begin
                cherche := True;
                Exit;
            end;
        end;
       
        j := i + 1;
        while (jeu[j].val <> 0) do
        begin
            nbout := 1;
           
            k := 0;
            while (jeu[k].val <> 0) do
            begin
                if (k <> i) and (k <> j) then
                begin
                    jeulocal[nbout].val := jeu[k].val;
                    jeulocal[nbout].text := jeu[k].text;
                    nbout := nbout + 1;
                end;
               
                k := k + 1;
            end;
            jeulocal[nbout].val := 0;
            if (jeu[i].val>jeu[j].val) then
            begin
                big := jeu[i].val;
                small := jeu[j].val;
                tbig := jeu[i].text;
                tsmall := jeu[j].text;
            end
                else
                    begin
                        big := jeu[j].val;
                        small := jeu[i].val;
                        tbig := jeu[j].text;
                        tsmall := jeu[i].text;
                    end;
            jeulocal[0].val := big + small;
            jeulocal[0].text := '(' + tbig + '+' + tsmall + ')';
            if (cherche(jeulocal)) then
            begin
                Cherche := True;
                Exit;
            end;
            if (big <> small) then
            begin
                jeulocal[0].val := big - small;
                jeulocal[0].text := '(' + tbig + '-' + tsmall + ')';
                if (cherche(jeulocal)) then
                begin
                    Cherche := True;
                    Exit;
                end;
            end;
            jeulocal[0].val := big * small;
            jeulocal[0].text := tbig + '*' + tsmall;
            if (cherche(jeulocal)) then
            begin
                Cherche := True;
                Exit;
            end;
            if (big mod small <> 0) then
            begin
                jeulocal[0].val := big div small;
                jeulocal[0].text := '(' + tbig + '/' + tsmall + ')';
                if (cherche(jeulocal)) then
                begin
                    Cherche := True;
                    Exit;
                end;
            end;

            j := j + 1;
        end;

        i := i + 1;
    end;
    Cherche := False;
end;

var jeu : TabEltRech;
    nbnb : integer;
    i : integer;
begin
    Saisie_Tab(nbnb, obj, jeu);
    Tri_Tab(nbnb, jeu);
   
    best_delta := abs(obj - jeu[0].val);
    if cherche(jeu) then
        Writeln('Solution Exacte Trouvée !')
    else
        Writeln('Solution Apprcohée Trouvée !');
    Readln;
end.


Tout commentaire sera la bienvenue.

Admin a écrit:Une version très prometteuse postée par manianis dans le forum:
...
Tout commentaire sera la bienvenue.

Merci Nabil.

De rien. Très prochainement, je vais commenter avec détails cette version.
L'essentiel de tout ça, c'est le partage des connaissances.

Je vais poster ma version en C++ dans quelques jours.
Et je vais par la suite l'améliorer.

Mon objectif c'est de dépasser la limite de 6 nombres, voire, atteindre des dimension bcp plus larges (N=10, 15, 20...) sans étouffer l'ordinateur et sans avoir recours aux fichiers...

voilà ce que je vois comme défi...

En utilisant la récursivité vous finirez toujours par étouffer l'ordinateur. Il devra y avoir une solution itérative.
çà c'est le vrai défit.

Oui, certainement ca va être de l'itératif.
Mais à mon avis, le défi c'est comment organiser les données, et ne pas tout mettre dans la mémoire pour pouvoir explorer la profondeur de l'arbre des possibilités, qui est trop gigantesque lorsque N=10 par exemple.

J'ai fait un simple calcul du nombre de possibilité lorsque N=10,
tiens c'est 6.742.112.993.280 opérations arithmétiques: si je me trompe pas c'est 6.742 milliards et quelques centaines de millions opérations.

Je n'ai pas une grande idée sur les algorithmes génétiques mais dans de tels cas on utilise ce type d'algorithme afin d'obtenir une solution.

Je crois que c'est une idée originale le fait dutilizé les Algo génétiques dans un jeu...

ca devrait être passionnant !!!

je vais m'y pencher un peu avant l'aïd et voir comment ça peut se faire.

une kestion: est-ce qu'on peut résoudre le problème d'une façon parallèle ???? plusieurs PC qui parcours l'arbre en parallèles??

j'espère que c pa des connerie ce ke je sui entrain de dire lool

Oui çà peut se faire.

Mais, à ce que je comprends bien Nabil souhaiterai limiter l'utilisation des ressources du système et ne veut pas avoir recours aux fichiers.

Mais, le paraléllisme reste toujours une trés bonne option.

Oui tout à fait manianis.
On reformule toujours l'objectif du "concours"...
d'ailleurs je suis à la recherche d'une autre appellation à la place de "concours" parceque c pas vraiment un concours

mais bonh, l'objectif que je vois c'est:

Développer une solution informatique du jeu adapté Chiffres sans Lettres de façon à ce qu'une solution est toujours donnée, avec un temps de calcul raisonnable même si la dimension du problème est large (N = 20, 30 ...)

Sachant qu'actuellement, le jeu standard a une dimension N=6 au maximum.

Vous pouvez reformuler/modifier l'énoncé de l'objectif pour qu'il soit plus rigoureux et plus clair.

Il est trés clair tel qu'il est énoncé.

Calcul de la complexité du jeu Chiffres sans Lettres

Actuellement, je me propose de trouver une formule mathématique qui indique la complexité du problème: le nombre maximal d'opérations arithmétiques (+, -, x, /) qu'on doit faire pour aboutir à la solution du jeu.
La formule dépend de la taille N du problème.

Exemple
Lorsque N = 2, on a initialement deux nombres (ex: 5, 15) et un nombre
Résultat (ex: 3). Le nombre maximal d'opérations qu'on peut faire est
4. En effet, on peut faire soit:

Addition: 5+15 = 15+5 = 20
Soustraction: 15 - 5 = 10
Multiplication: 15 x 5 = 5 x 15 = 75
Division: 15 / 5 = 3

Donc, pour N=2, la complexité du problème est 4.
Pour N=3, chaque couple de nombre donne naissance à 4 nouveau nombre au max, et fait disparaitre 2 nombres, etc...


à suivre...

Pour chaque K nombres, on doit choisir tous les sous-ensembles formés de deux nombres. Donc, chaque ensemble de k nombres donne naissance à C(k,2) couples où C(k,2) est la combinaison de 2 éléments parmi k éléments. Voir le cours de dénombrement.

c'est une piste pour commencer la formule qui est un peu difficile à mon avis.

Je remercieeeee Nabil pour le bon sujet de calcul de complexité qu'il a proposé. J'ai fouillé tout le net et je n'ai trouvé aucune réponse. C'est de l'original.

Une tentative de résolution (5ir men blech)...

Au début, on a N nombres.

On doit former tout les ensembles de 2 nombres pour des ultérieures opérations arithmétiques.

Au max, on a: C(N,2) couples. Soit C(N,2)=N(N-1)/2 couples.

Chaque couple donne naissance, après (au max) quatres opérations de calcul, à 4 nouveaux nombres.

Soit la création de 4C(N,2)=2N(N-1) nouveaux nombres.

etc... c'est correct? ????

salut,
comment on calcul le nombre exact d'opérations alors qu'on ne peut pas savoir d'avance si un nombre est divisible par un notre ou non!

Lorsqu'on joue avec 100 Nombres, combien il y'a de possibilités au MAX ?
C'est-à-dire, la taille maximale de l'arbre de recherche?

methodiX a écrit:Lorsqu'on joue avec 100 Nombres, combien il y'a de possibilités au MAX ?
C'est-à-dire, la taille maximale de l'arbre de recherche?

Depuis plusieurs jours, on n'a pas animé ce sujet. Pourtant il est très intéressant à mon avis. Il requiert plusieurs connaissances et un peu de temps libre

C'est un peu dur Nabil.

La plupart des tunisiens et des tunisiennes détestent les maths

j'ai beaucoup aimé le sujet pourtant que j'ai pas une grande connaissance pour les algo génetiques

Hélas, on n'a pas suffisamment de membres actifs et disponibles pour résoudre ce problème, et participer...

Il faut trouver un autre moyen pour motiver les gens et diffuser l'information inter-forums.