Partage

[Exercices] Venez vous entraîner !

Ce mois: Parseur de fonctions mathématiques

21 octobre 2008 à 19:47:28

GurneyH -> j'avais déjà pensé à procéder comme ça, mais je ne connaissait pas de fonction pour isoler partie entière et partie décimale, et quand on essaye à la main on rencontre des problème d'approximation de l'ordre de 10^-10.
D'où tient tu la fonction fmod ?

Nanoc -> merci bien, je vais voir ce que je peux faire
22 octobre 2008 à 12:29:26

Salut,

Darkelfe, pour fmod, j'ai simplement fait une recherche dans les bibliothèques standards. J'ai trouvé une solution, je me sert toujours de puissance de dix, mais sans isoler la partie décimale (donc plus besoin de fmod...)

Sinon, si tu souhaites vraiment isoler la partie décimale tu peux essayer:

long partieEntiere;
double partieDecimale;
partieEntiere=static_cast<long>nombre;
partieDecimale=nombre-partieEntiere;


Ensuite, à toi de jouer... :lol:

a++
Zeste de Savoir, le site qui en a dans le citron !
27 octobre 2008 à 18:33:51

bwarf ... pas un mots sur la complexitée dans la correction ? (et les méthodes alternatives inutiles ? :p )
28 octobre 2008 à 14:44:19

Post complexe.


Effectivement. Je n'ai pas touché mot de la complexité simplement, parce que l'algorithme proposé est certainement le plus efficace possible. On pourrait le rendre plus rapide en créant en premier un tableau avec la liste des mots et en supprimant à ce moment-là les mots dont la taille dépasse la longueur du tirage.

Algo 1



Regardons ça de manière plus mathématique. Soit <math>\(n\)</math> le nombre de mots dont la taille ne dépasse pas celle du tirage. Soit <math>\(k\)</math> la longueur du tirage. La complexité pire cas (c'est-à-dire si tous les mots du dico sont non-valides et ont tous <math>\(k\)</math> lettres) est alors en <math>\(O(n*k^2)\)</math>.
Le meilleure cas (si tous les mots du dico font 1 lettre qui n'est pas dans le tirage!) est en <math>\(O(n*k)\)</math>. Ces deux cas étant deux extrêmes, on se situe en général entre les deux. Le paramètre le plus important étant <math>\(n\)</math> puisque <math>\(k\)</math> est souvent fixé et que la qualité du programme dépend de la taille du dictionnaire.
On obtient donc globalement une complexité en <math>\(O(n)\)</math>.
Ceci pouvant être amélioré un peu en triant les mots par taille et de ne pas continuer à chercher dans les mots de <math>\(k-1\)</math> lettres si on a trouvé un mot en <math>\(k\)</math> lettres.
L'algorithme donné s'exécute quasi-instantanément et il n'est donc pas forcément nécessaire à ce stade de chercher mieux.

Algo 2



Mais comme nous sommes des perfectionnistes, nous voulons chercher mieux. Nous allons donc essayer d'améliorer le facteur <math>\(n\)</math> dans la complexité. Nous devons effectuer une recherche dans une liste d'éléments. Une recherche peut s'effectuer en <math>\(O(log(n))\)</math> ce qui est mieux que ce que nous avons. Le problème, c'est que pour faire cela, il va préallablement falloir trier la liste d'éléments pour effectuer la recherche avec cette "rapidité". Et c'est là que deux problèmes se posent:
1) Comment définir un critère de tri (comment écrire operator< ?)
2) Comment trier de manière à ce qu'au total on reste en dessous de O(n) ?

Clairement, il faudra définir un nouveau critère de tri pour chaque recherche puisque chaque cas est différent.
La 2 est problématique. Les meilleurs tris génériques sont en O(n*log(n)) et es tris spécifiques (tri par panier,...) peuvent se faire en O(n). Ce ne sera donc asymptotiquement pas meilleur que l'algo "naïf".
De plus implémenter un critère de tri sera très difficile.

Algo 3



Une autre solution pourrait être de générer tous les mots possibles à partir d'un tirage donné. Si l'on a <math>\(k\)</math> lettres différentes, on peut écrire <math>\(k!\)</math> "mots" différents. (Voir plus si il n'y a pas de solution en <math>\(k\)</math> lettres dans le dico). Pour <math>\(k=9\)</math>, on arrive à <math>\(362 880\)</math> "mots" de 9 lettres différents. Ce nombre est en fait plus grand parce qu'il faut tenir compte des mots ne faisant pas 9 lettres.
Il faudra ensuite chercher dans le dico si chacun des mots de la liste existe en français ou non. Ce qui veut dire qu'on se retrouve en <math>\(O(log(n)*k!*k)\)</math>. Le dernier "*k" est dû au fait que les tests lors de la recherche sont en général en O(k).
Cet algo sera donc plus efficace que le premier si <math>\(log(n)*k! *k < n*k^2\)</math>. C'est-à-dire si <math>\(n=323578\)</math> et donc <math>\(ln(n) = 12\)</math>, on est plus efficace avec l'algo 3 qu'avec l'algo 1 si <math>\(k! < 27000 k\)</math>. C'est-à-dire si <math>\(k<9\)</math>. Ces calculs étant plus qu'approximatif puisqu'on ne connait pas les constantes présentes dans les 2 expressions "O(...)". Mais on remarque que pour des grand k, l'algo 1 sera plus efficace pour un dictionnaire donné. Et certainement pour des k<8 ou même k<7 si l'on tient compte du pire cas qui fait que la meilleure solution n'est pas en k lettres. (Le pire cas de l'algo 1 tient compte de ce fait).
De plus cet algorithme nécessite <math>\(k! * k\)</math> octets en mémoire (1 lettre = 1 octet) pour stocker tous les mots possibles. Soit plus de 3 Mo pour 9 lettres (en plus du dico) et cette taille augmentant exponentiellement. Cette solution n'est donc rapidement plus viable. Pour 12 lettres, il faut 5Go. Alors que la version "naïve" ne nécessite pas de place mémoire en plus du dictionnaire.
Il est également possible de ne pas stocker les éléments et de directement les traiter, au quel cas cette dernière remarque perd tout son sens.

AMHA, l'algo proposé est le meilleur. Je vous ai fait part ici de deux autres algos pas trop mauvais qui m'étaient venus à l'esprit. On peut peut-être faire mieux. Si c'est le cas, n'hésitez pas à proposer votre solution.
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
28 octobre 2008 à 16:55:34

Euh, tu t'y prends bizarrement si tu as besoin de plus de 3 Mo pour la seconde méthode ...
Ensuite :
- pas besoin de trier le dico, qui l'est déjà ...donc c'est du O(log(n)*k!)
- avec la derniere solution, j'arrive a du O(c) pour le chargement du dico (avec 'c' nombre de caractères du dico) + O(k!*r) pour r tirage, contre du O(c*r) pour toi


Le second algo est donc plus efficace si k!<c, c'est le cas ici ... mais alors que la complexitée de ton algo ne bouge pas trop quand on augmente la taille du tirage, la complexitée du mien explose ...
Pour la complexitée en mémoire ... ben je charge tout le dico + le fichier au même moment, toi tu n'utilises que le fichier tel quel non ?

j'attends aussi une meilleur idée ... ça me parais globalement bourrin comme algos ...
28 octobre 2008 à 17:03:06

Dans tous les cas, il faut charger le dico en mémoire. Donc on en tient pas compte pour le calcul de la complexité de l'algo.

Tu mélanges la solution 2 et la 3. Dans la 3 (la tienne), il n'y a pas de tris comme tu le dis. Mais après avoir généré les k! mots il faut quand même vérifier que chaque mot se trouve dans le dictionnaire. Ce qui se fait en effet en O(k!*log(n)). Je corrige. Pour les 3Mo, c'est simplement 9! * 9 octets.
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
28 octobre 2008 à 19:14:25

Je vous soumets une idée qui me passe par la tête (je vous le dis déjà je ne suis pas un pro sur les complexités):

La premère étape consiste à passer du unique fichier texte qui contient les mots par un fichier par mot (on ne ferait bien sûr que les mots dont la taille <= k), chaque fichier aurait le nom d'un mot. Mais il y a un désavantage, ça prend du temps, mais si cette préconstruction est déjà faîte ou faîte qu'une fois (au redémarrage du progamme elle ne se fait plus) la suite ira plus vite.

La deuxième et dernière étape consiste à générer les mots un par un (O(k!)) et tester si le mot (fichier) existe via une fonction du style:
bool Exists(const std::string &Word) {
    return !std::ifstream(Word.c_str()).fail();
}
ps: Ce n'est pas la meilleure méthode pour tester si un fichier existe.
L'ouverture du fichier étant direct (O(1)) la recherche du mot est très rapide.

Conclusion: On obtient une complexité en O(k! * 1) soit O(k!), si bien sûr l'étape de préconstruction est déjà faîte.
28 octobre 2008 à 19:16:29

N'aurait-on pas plutôt intérêt à trier le dico? Je veux dire : on vire tout les mots ayant des tirets, tout les mots à une lettre (on aura forcément deux lettres utilisable dans un tirage selon moi).
Sa gagnerai d'un en taille mémoire quand on charge le dico et de deux en test dans l'algorithme.
28 octobre 2008 à 20:13:48

@Chlab_lak, ce n'est qu'une variante du 3. La recherche lorsque tu essayes d'ouvrir le flux se fait en O(log(n)*k) puisque il faut chercher parmis n éléments et un test d'égalité entre deux fichiers se fera en O(k).

@Goten: Oui, mais étant donné un dico "parfait", quel algo est le plus efficace ?
Comme je l'ai précisé, je suppose qu'on a supprimé tous les mots avec plus de k lettres au préalable. Les mots de 1 lettres sont négligeables puisqu'il y en a que 26 (au maximum) sur les 300'000 du fichier.
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
28 octobre 2008 à 20:25:00

euh ... d'où vient le log ? j'ai pas de log dans mon arbre ...

j'ai une fonction recursive brutale qui donne les lettres (donc !k*k operations (j'avais oublié le k))
et à chaque fois que j'en choisis une , je vérifie en O(1) (en véritable O(1) hein ... c'est une comparaison de char ) et je passe à la suivante si il faut ...

et sinon Goten, il faut gérer les mots avec des tirets, si tu as baba au rhum, tu dois pouvoir faire le mot baba-au-rhum :)

autre remarque sur ton code nanoc, ton test pour voir si la taille d'un mot en comptant les tirets est valide est pire qu'inutile ...
En effet, tu fais 3c (c=nombre de caractère du mot) opérations (comptage + strlen + vérifications du mot) au lieu de c (vérifications du mot) :-°
(évidemment ça ne rentre pas en compte dans la complexité, mais je préfère prévenir ... si jamais c devais devenir gros ... :) )

edit2: je coinche pour ton histoire de mémoire ... je stock un seul candidats à la fois ... ce serait idiot de tous les stocker !
mon algo, mis à part l'arbre lexico prend autant de mémoire que le tient !

en gros , j'ai une fonction récursive qui génère les combinaisons lettres par lettres, et qui a chaque lettres avance dans l'arbre (ou pas). Arrivé à une profondeur de k, si je suis sur une fin de mot, j'affiche le mot... c'tout, je stock rien
28 octobre 2008 à 20:32:25

Autant pour moi... je me référais au jeu télévisuel, où là il n'y pas de tiret.. (à ma connaissance en tout cas... mais n'étant pas un grand fan).
28 octobre 2008 à 21:03:23

Citation : Dakeyras Khan

euh ... d'où vient le log ? j'ai pas de log dans mon arbre ...



La recherche dans un arbre et/ou le déplacement se fait en O(log(n)).

Citation : Dakeyras Khan


j'ai une fonction recursive brutale qui donne les lettres (donc !k*k operations (j'avais oublié le k))
et à chaque fois que j'en choisis une , je vérifie en O(1) (en véritable O(1) hein ... c'est une comparaison de char ) et je passe à la suivante si il faut ...



Tout à fait.

Citation : Dakeyras Khan


edit2: je coinche pour ton histoire de mémoire ... je stock un seul candidats à la fois ... ce serait idiot de tous les stocker !
mon algo, mis à part l'arbre lexico prend autant de mémoire que le tient !



J'avais premièrement compris que tu stockais toutes les k! chaines avant de les tester une à une. Ce qui est stupide. C.f. mon edit du post.

Citation : Dakeyras Khan


en gros , j'ai une fonction récursive qui génère les combinaisons lettres par lettres, et qui a chaque lettres avance dans l'arbre (ou pas). Arrivé à une profondeur de k, si je suis sur une fin de mot, j'affiche le mot... c'tout, je stock rien



Justement, avancer dans un arbre ne se fait pas en O(1).

Pour ce qui est de mon code, j'ai privilégié la lisibilité. Mais il est vrai qu'on peut faire plus rapide en gardant le même algo et donc la même complexité.
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
28 octobre 2008 à 22:59:55

euh ?
avancer dans un arbre se fait en O(1) ...
c'est passer de la racine à une feuille (et seulement dans un arbre binaire équilibré) qui se fait en O(log(n)) ... ici, j'ai juste un déréférencement de pointeur (pas sur du nom ... bref, je change de noeud :p ) à faire ... donc O(1)

pour la mémoire, de quel édit parles-tu ?

sinon, pour le coup du tiret... en quoi des lignes supplémentaires rendent-elles un code plus lisible ?
while(mot.find('-',posTiret) != string::npos)  //Tant qu'il y a un tiret dans le mot a partir de la position courante
        {
            posTiret = mot.find('-',posTiret)+1; //On recupere la position pour la prochaine recherche
            ++nbTirets;                          //Et on incremente le compteur
        }

        //On soustrait au nombre de lettres le nombre de tirets puisque le tirage n'a pas de tirets
        nbLettres-=nbTirets;

        //Si le mot a trop de lettres, on passe au suivant puisque il ne peut pas etre solution
        if (nbLettres > TAILLE_TIRAGE )
            continue;

        //On cree un tableau qui permet d'indiquer si chacune des lettres du tirage est utilisee
        bool utilisee[TAILLE_TIRAGE]={false};

        //On commence par supposer que l'on peut ecrire le mot a partir du tirage
        bool motvalide=true;

        //On parcourt les lettres du mot
        for ( unsigned int i=0; i<mot.size(); i++ )
        {
            //Si c'est un tiret on saute a la lettre suivante puisqu'on a pas de tiret dans le tirage
            if(mot[i] == '-')
                continue;

            //On commence par supposer que la lettre du mot n'est PAS dans le tirage
            bool lettrevalide=false;

            //On parcourt les lettres du tirage
            for (unsigned int j=0; j<tirage.size(); ++j )
            {
                //Si la lettre du tirage correspond a la lettre du mot ET qu'on a pas encore utilise cette lettre du tirage
                if ( mot[i]==tirage[j] && utilisee[j]==false )
                {
                    //On montre que la lettre a ete utilisee
                    utilisee[j]=true;
                    //Et on valide la lettre
                    lettrevalide=true;
                    //On sort de la boucle pour passer a la lettre suivante du mot
                    break;
                }
            }

            //Si une lettre est non-valide le mot est non valide donc on passe au mot suivant
            if ( !lettrevalide )
            {
                motvalide=false;
                break;
            }
        }


=> devient ça :

//On cree un tableau qui permet d'indiquer si chacune des lettres du tirage est utilisee
        bool utilisee[TAILLE_TIRAGE]={false};

        //On commence par supposer que l'on peut ecrire le mot a partir du tirage
        bool motvalide=true;

        //On veut que toutes les lettres du tirages soient utilisées, on utilise un compteur
        unsigned int nbUtilisee=0;
        unsigned int tailleMot=mot.size();
        //On parcourt les lettres du mot
        for ( unsigned int i=0; i<tailleMot); i++ )
        {
            //Si c'est un tiret on saute a la lettre suivante puisqu'on a pas de tiret dans le tirage
            if(mot[i] == '-')
                continue;

            //On commence par supposer que la lettre du mot n'est PAS dans le tirage
            bool lettrevalide=false;

            //On parcourt les lettres du tirage
            for (unsigned int j=0; j<tirage.size(); ++j )
            {
                //Si la lettre du tirage correspond a la lettre du mot ET qu'on a pas encore utilise cette lettre du tirage
                if ( mot[i]==tirage[j] && utilisee[j]==false )
                {
                    //On montre que la lettre a ete utilisee
                    utilisee[j]=true;
                    //Et on valide la lettre
                    lettrevalide=true;

                    //On a utilise une lettre de plus
                    nbUtilisee++;

                    //On sort de la boucle pour passer a la lettre suivante du mot
                    break;
                }
            }

            //Si une lettre est non-valide le mot est non valide donc on passe au mot suivant 
            if ( !lettrevalide)
            {
                motvalide=false;
                break;
            }
        }

        if(nbutilisee<tailleMot)
        {
             motvalide=false;
        }



29 octobre 2008 à 1:38:11

Citation : Dakeyras Khan

euh ?
avancer dans un arbre se fait en O(1) ...
c'est passer de la racine à une feuille (et seulement dans un arbre binaire équilibré) qui se fait en O(log(n)) ... ici, j'ai juste un déréférencement de pointeur (pas sur du nom ... bref, je change de noeud :p ) à faire ... donc O(1)



Pour passer de la chaine "ASDFGTHP" à "ASDFGTHQ" qui sont deux feuilleurs distinctes, il faut se déplacer dans un arbre, ce qui se fait en O(log(n)) dans le cas général. Je ne peux que te renvoyer que vers les ouvrages de références.

Citation : Dakeyras Khan


pour la mémoire, de quel édit parles-tu ?



Du premier post sur la complexité.

Citation : Dakeyras Khan


sinon, pour le coup du tiret... en quoi des lignes supplémentaires rendent-elles un code plus lisible



En rien. Je n'ai pas non plus prétendu avoir la meilleure solution au niveau du code. Il faut cependant faire attention au fait que la longueur importante est le nombre de lettres correspond donc à a longueur du mot moins le nombre de tirets. Ceci à son importance lors du stockage des solutions potentielles. "sous-marin" n'est pas mieux que "marsouins", ce qui explique ma démarche. Mais apperement la tienne est plus efficace.
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
31 octobre 2008 à 12:22:19

Solution d'août



Bonjour tout le monde ! Il est temps que je dévoile après beaucoup de retard, une solution pour l'exercice du mois d'août. Vous avez été 5 à m'envoyer une solution, ce qui montre que cet exercice était plus difficile.
Voici une solution possible.

Partie "Papier-Crayon"



Cet exercice est principalement un exercice d'algorithmique. Il est donc nécessaire de passer par une partie de réflexion avant de se lancer dans la rédaction sinon, on est sûr de se perdre en cours de route.

Comme pour les lettres, on peut décomposer le problème en 2 parties différentes, la création d'un tirage et la recherche d'une solution.

Création d'un tirage

Créer un tirage est assez simple puisque cela consiste à choisir des éléments dans une liste donnée et ensuite à tirer au hasard un total à atteindre. Cela n'a posé de problème à personne.

Recherche d'une solution

Checher une solution est par contre plus difficile. Nous allons simplifier le problème en commençant par répondre à la question suivante: "Etant donné un tirage et un total, est-il possible d'arriver au total ?" La réponse sera OUI ou NON.
Comment faire cela ? Prenons un exemple.
Tirage : 3 3 10 8 7 25
Total : 550

Un humain devant ce problème, va se dire, par exemple: "Si j'arrive à 55, alors j'utilise le 10 pour faire 55*10 = 550". Il va donc se créer mentalement un nouveau problème qui serait "Comment arriver à 55 avec 3,3,8,7,25". Et là il va se dire, ok 55=48+7 et donc va se poser la question "Comment arriver à 48 avec 3,3,8 et 25" Et ainsi de suite. Si par malchance il n'y arrive pas, il revient en arrière et essaye une nouvelle supposition. Par exemple "55 = 52+3" et se posera la question "Comment arriver à 52 avec 3,8,7 et 25".
Finalement, il arrivera à la solution:
3+3 = 6
6*8 = 48
48+7 = 55
55*10 = 550

ou à une autre solution (si elle existe) selon les suppositions qu'on a fait. L'être humain a "un sens" des mathématiques et il verra rapidement que certaines opérations n'ont pas de sens. Par exemple faire 550 = 5500 / 10 et essayer d'arriver à 5500. L'ordinateur, lui, n'a pas d'intuition mathématique. Par contre il calcule beaucoup plus vite. Il peut donc se permettre d'essayer toutes les solutions !

L'algorithme utilisé est le même mais sans faire de suppositions "humaines".

Etant donné un tirage, on va combiner deux éléments du tirage avec une opération et créer un nouveau tirage avec le résultat du calcul des deux éléments et de l'opération. Et on recommence jusqu'à ce qu'il y ait plus qu'un élément dans le tirage qui est le total à atteindre. Si ce n'est pas le total, on recommence avec une nouvelle opération.


Programmation



Il est maintenant temps de passer à la partie "codage" de l'exercice.

On commence par définir quelques constantes qui serviront de paramètres au jeu.

const unsigned int NOMBRES_CHIFFRES = 14;  //Nombres de chiffres "tirables"
const unsigned int CHIFFRES[NOMBRES_CHIFFRES ] = {1,2,3,4,5,6,7,8,9,10,25,50,75,100}; 
const unsigned int TAILLE_TIRAGE = 6;   //Nombres de chiffres d'un tirage
const unsigned int SOLUTION_MIN = 100;  //Total minimum
const unsigned int SOLUTION_MAX = 999;  //Total maximum


La partie génération d'un tirage est assez simple, je vous donne donc le code commenté directement.

//Fonction qui renvoit un entier au hasard entre min et max
unsigned int hasard(unsigned int min,unsigned int max)
{
    const double x = static_cast<double>(rand())/RAND_MAX;

    return static_cast<unsigned int>(x * (max-min))+ min;
}

//Fonction qui renvoit un tableau d'entier contenant un tirage
vector<unsigned int> creeTirage()
{
    vector<unsigned int> tirage(TAILLE_TIRAGE);//Création d'un tableau de chiffres

    //Pour chaque case, on tire au hasard parmi les chiffres du jeu
    for (unsigned int i(0);i<TAILLE_TIRAGE;++i)
        tirage[i] = CHIFFRES[hasard(0,NOMBRES_CHIFFRES)];

    return tirage;
}


Pour la recherche de solution, commencons par le cas où la seule opération autorisée serait l'addition. On peut alors écrire la fonction de la manière suivante:

bool chercherSolution(vector<unsigned int>& tirage,unsigned int taille, unsigned int total,)
{
    //On parcourt tous les chiffres du tirage
    for (unsigned int i(0);i<taille;++i)
    {
        //Si la case correspond a la solution, on renvoit true puisque une solution est possible
        if (tirage[i] == total)
            return true;

        //On parcourt les autres lettres du tirage
        for (unsigned int j(i+1);j<taille;++j)
        {
            //On calcule la somme des deux elements du tirage i et j
            int res = tirage[i] + tirage[j];

            //On sauvegarde les valeurs de i et de j
            int backup_i = tirage[i];
            int backup_j = tirage[j];

            //Et on modifie notre tirage en mettant dans la case de i le resultat de l'addition
            tirage[i] = res;
  
            //Et on echange la place de j et du dernier element.
            tirage[j] = tirage[taille-1];

            //On se retrouve ici avec un tableau de la forme 
            //res, 2 , 3, 4, 5 , j
            //Et donc si on prend les (taille-1 = 5) premiers elements on a un nouveau probleme a resoudre

            //Si ce nouveau probleme mene a une solution
            if (chercherSolution(tirage,taille-1,total,solution))
            {
                //C'est que le calcul qu'on a fait (l'addition) mene a une reponse. On renvoit donc true
                return true;
            }

            //On remet en place ce que l'on a modifie
            tirage[i] = backup_i;
            tirage[j] = backup_j;

        //On passe au j suivant (si celui la n'a rien donne)
        }
    //On passe au i suivant (si celui la n'a rien donne)
    }

    //Si on est arrive la c'est qu'il y a pas de solution donc on renvoit false
    return false;
}


Remarquez le fait qu'on utilise pas size() mais un parametre "taille" pour le tableau. Cela permet d'utiliser que la première partie du tableau pour créer les nouveaux problèmes.


On peut alors ajouter les autres opérations dans la boucle intérieure pour avoir toutes les combinaisons possibles.

L'opération "/" est un peu ennuyeuse. Il faut faire attention aux divisions par zéro et surtout, l'opération n'est pas forcément celle qu'un humain ferait. C'est la division entière. Cela donne parfois des résultats un peu bizarres mais corrects.


Afficher la solution.



Ceci ajoute une difficulté (encore) à l'exercice. Premièrement, on va devoir mettre des entiers dans des strings. Cela n'est pas un problème, mais il faut juste savoir comment faire, en l'occurence utiliser des sstream.

string solution;
ostringstream flux;
flux << backup_i<< " / " << backup_j << " = " << res << "\n";
solution = flux.str();


Deuxièmement, il ne faut afficher quelque chose que si l'on arrive à une solution, et l'on ne sait pas a priori si le fait d'additionner les deux premiers nombres du tirage mènera à une solution. Il faut donc construire une chaine de caractère que l'on remplira si on arrive à une solution et pas faire directement de l'affichage. Notre fonction renvoit un bool, il faut donc ajouter un paramètre supplémentaire à la fonction pour qu'elle puisse "renvoyer" ou ici, modifier, une chaine reçue en argument.

bool chercherSolution(vector<unsigned int>& tirage,unsigned int taille, unsigned int total,string& solution)


L'écriture dans la chaine se fait alors dans le "if" de la manière suivante:
if (chercherSolution(tirage,taille-1,total,solution))
{
  ostringstream flux;
  flux << backup_i<< " + " << backup_j << " = " << res << "\n";
  solution = flux.str()+solution;
  return true;
}


On arrive donc au code suivant pour la fonction:

bool chercherSolution(vector<unsigned int>& tirage,unsigned int taille, unsigned int total,string& solution)
{
    //On parcourt tous les chiffres du tirage
    for (unsigned int i(0);i<taille;++i)
    {
        //Si la case correspond a la solution, on renvoit true puisque une solution est possible
        if (tirage[i] == total)
            return true;

        for (unsigned int j(i+1);j<taille;++j)
        {
            int res = tirage[i] + tirage[j];
            int backup_i = tirage[i];
            int backup_j = tirage[j];

            tirage[i] = res;
            tirage[j] = tirage[taille-1];

            if (chercherSolution(tirage,taille-1,total,solution))
            {
                ostringstream flux;
                flux << backup_i<< " + " << backup_j << " = " << res << "\n";
                solution = flux.str()+solution;
                return true;
            }

            res = backup_i - backup_j;
            tirage[i] = res;
            tirage[j] = tirage[taille-1];

            if (chercherSolution(tirage,taille-1,total,solution))
            {
                ostringstream flux;
                flux << backup_i<< " - " << backup_j << " = " << res << "\n";
                solution = flux.str()+solution;
                return true;
            }

            res = backup_i * backup_j;
            tirage[i] = res;
            tirage[j] = tirage[taille-1];

            if (chercherSolution(tirage,taille-1,total,solution))
            {
                ostringstream flux;
                flux << backup_i<< " * " << backup_j << " = " << res << "\n";
                solution = flux.str()+solution;
                return true;
            }

            if (backup_j != 0)
            {
                res = backup_i / backup_j;
                if (res!=0)
                {
                    tirage[i] = res;
                    tirage[j] = tirage[taille-1];

                    if (chercherSolution(tirage,taille-1,total,solution))
                    {
                        ostringstream flux;
                        flux << backup_i<< " / " << backup_j << " = " << res << "\n";
                        solution = flux.str()+solution;
                        return true;
                    }
                }
            }

            tirage[i] = backup_i;
            tirage[j] = backup_j;
        }
    }

    //Si on est arrive la c'est qu'il y a pas de solution
    return false;
}


Comment trouver une solution approchée ?



Malheureusement, il est des cas où l'on arrive pas à une solution exacte et où l'on doit trouver une solution approchée. Le "truc" est alors d'utiliser la même fonction avec comme paramètre pour le total, les nombres voisins de la solution que l'on aimerait atteindre.

//Recherche d'une solution
    if (chercherSolution(tirage,TAILLE_TIRAGE,solution,calculs))
    {
        cout << "Une solution exacte a ete trouvee: " << endl;
        cout << calculs;
    }
    else //On cherche une solution approchee
    {
        int decalage(1);

        //Tant qu'on trouve pas de solution
        while (! chercherSolution(tirage,TAILLE_TIRAGE,solution+decalage,calculs))
        {
            //On cherche plus loin en alternant +1,-1,+2,-2,+3,-3,...
            if (decalage < 0)
                decalage = -decalage+1;
            else
                decalage = -decalage;
        }

        //Jusqu'a ce que finalement on trouve une solution
        cout << "Une solution approchee (" << solution+decalage << ") a ete trouvee: " << endl;
        cout << calculs;
    }


Ouf :-° On est au bout. Pour finir, voici une solution complète:

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

const unsigned int NOMBRES_CHIFFRES = 14;  //Nombres de chiffres "tirables"
const unsigned int CHIFFRES[NOMBRES_CHIFFRES ] = {1,2,3,4,5,6,7,8,9,10,25,50,75,100};
const unsigned int TAILLE_TIRAGE = 6;   //Nombres de chiffres d'un tirage
const unsigned int SOLUTION_MIN = 100;  //Total minimum
const unsigned int SOLUTION_MAX = 999;  //Total maximum


//Fonction qui renvoit un entier au hasard entre min et max
unsigned int hasard(unsigned int min,unsigned int max)
{
    const double x = static_cast<double>(rand())/RAND_MAX;

    return static_cast<unsigned int>(x * (max-min))+ min;
}

//Fonction qui renvoit un tableau d'entier contenant un tirage
vector<unsigned int> creeTirage()
{
    vector<unsigned int> tirage(TAILLE_TIRAGE);//Création d'un tableau de chiffres

    //Pour chaque case, on tire au hasard parmi les chiffres du jeu
    for (unsigned int i(0);i<TAILLE_TIRAGE;++i)
        tirage[i] = CHIFFRES[hasard(0,NOMBRES_CHIFFRES)];

    return tirage;
}

bool chercherSolution(vector<unsigned int>& tirage,unsigned int taille, unsigned int total,string& solution)
{
    //On parcourt tous les chiffres du tirage
    for (unsigned int i(0);i<taille;++i)
    {
        //Si la case correspond a la solution, on renvoit true puisque une solution est possible
        if (tirage[i] == total)
            return true;

        for (unsigned int j(i+1);j<taille;++j)
        {
            int res = tirage[i] + tirage[j];
            int backup_i = tirage[i];
            int backup_j = tirage[j];

            tirage[i] = res;
            tirage[j] = tirage[taille-1];

            if (chercherSolution(tirage,taille-1,total,solution))
            {
                ostringstream flux;
                flux << backup_i<< " + " << backup_j << " = " << res << "\n";
                solution = flux.str()+solution;
                return true;
            }

            res = backup_i - backup_j;
            tirage[i] = res;
            tirage[j] = tirage[taille-1];

            if (chercherSolution(tirage,taille-1,total,solution))
            {
                ostringstream flux;
                flux << backup_i<< " - " << backup_j << " = " << res << "\n";
                solution = flux.str()+solution;
                return true;
            }

            res = backup_i * backup_j;
            tirage[i] = res;
            tirage[j] = tirage[taille-1];

            if (chercherSolution(tirage,taille-1,total,solution))
            {
                ostringstream flux;
                flux << backup_i<< " * " << backup_j << " = " << res << "\n";
                solution = flux.str()+solution;
                return true;
            }

            if (backup_j != 0)
            {
                res = backup_i / backup_j;
                if (res!=0)
                {
                    tirage[i] = res;
                    tirage[j] = tirage[taille-1];

                    if (chercherSolution(tirage,taille-1,total,solution))
                    {
                        ostringstream flux;
                        flux << backup_i<< " / " << backup_j << " = " << res << "\n";
                        solution = flux.str()+solution;
                        return true;
                    }
                }
            }

            tirage[i] = backup_i;
            tirage[j] = backup_j;
        }
    }

    //Si on est arrive la c'est qu'il y a pas de solution
    return false;
}


int main()
{
    srand(time(0));

    //Choix d'une solution a atteindre
    unsigned int solution = hasard(SOLUTION_MIN,SOLUTION_MAX + 1);

    // Creation d'un tirage
    vector<unsigned int> tirage = creeTirage();

    //Affichage de la donnee
    cout << "Nombre a atteindre: " << solution << endl << endl;
    cout << "Nombres a disposition: ";

    for (unsigned int i(0);i<TAILLE_TIRAGE;++i)
        cout << tirage[i] << " ";
    cout << endl << endl;

    //La chaine qui contiendra les calculs effectues
    string calculs;

    //Recherche d'une solution
    if (chercherSolution(tirage,TAILLE_TIRAGE,solution,calculs))
    {
        cout << "Une solution exacte a ete trouvee: " << endl;
        cout << calculs;
    }
    else //On cherche une solution approchee
    {
        int decalage(1);

        //Tant qu'on trouve pas de solution
        while (! chercherSolution(tirage,TAILLE_TIRAGE,solution+decalage,calculs))
        {
            //On cherche plus loin en alternant +1,-1,+2,-2,+3,-3,...
            if (decalage < 0)
                decalage = -decalage+1;
            else
                decalage = -decalage;
        }

        //Jusqu'a ce que finalement on trouve une solution
        cout << "Une solution approchee (" << solution+decalage << ") a ete trouvee: " << endl;
        cout << calculs;
    }


    return 0;
}


Ce programme est plus complexe que les précédents notamment à cause de la récursivité. N'hésitez pas à l'essayer chez vous, par exemple en ajoutant des "cout" partout pour voir ce qui se passe exactement et pour voir l'état du tableau à chaque étape.

Posez des questions si vous avez besoin de plus de détails !
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
31 octobre 2008 à 16:28:50

Juste une chose, pouviez-vous pour la prochaine fois faire de programmes un peu moins compliqué plz ? :p
31 octobre 2008 à 18:20:04

Oui j'ai en gros compris comment ça marchait, mais pour trouver la solution c'est une autre paire de manches :p .
31 octobre 2008 à 19:10:55

Oui :) Je me suis rendu compte un peu tard que cet exercice était trop difficile.

Par contre le dernier sur les fractions devrait être faisable par tout le monde.
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
31 octobre 2008 à 19:16:24

Oui oui celui-ci est nettement plus simple (la preuve j'ai donné une solution :D ). En fait c'est surtout l'algorithmique qui est difficile ^^ ...
31 octobre 2008 à 19:20:27

Citation : gymnopaul

Oui oui celui-ci est nettement plus simple (la preuve j'ai donné une solution :D ). En fait c'est surtout l'algorithmique qui est difficile ^^ ...



Pour cet exercice entièrement d'accord. Par contre pour l'exercice sur les lettres, je pense que la plupart des gens ont les connaissances requises pour y arriver.
Ce qu'il faut principalement comprendre, c'est que c'est pas derrière son PC qu'on va trouver comment faire. Toujours commencer par un exemple à la main. C'est la seule manière d'y arriver.
Co-auteur du cours de C++. ||| Posez vos questions sur le forum ||| Me contacter.
31 octobre 2008 à 22:51:38

et juste pour savoir quand sort la soluce de l'exo "des chiffres" ?

merci
1 novembre 2008 à 1:36:16

Nanoc s'est trompé de lien dans son post de correction et cela a induit en erreur, il a édité. C'est bien la correction de "Des chiffres..." que tu as sous les yeux. :p
1 novembre 2008 à 2:06:22

Citation : crys'

Nanoc s'est trompé de lien dans son post de correction et cela a induit en erreur, il a édité. C'est bien la correction de "Des chiffres..." que tu as sous les yeux. :p


ok merci :)
1 novembre 2008 à 10:29:32

et la complexitée en O(4^n) ?
ça apprendra aux gens à la calculer, ce serais pas mal :)
et je suis pas fan de ta fonction récursive, je vais voir si je peux faire mieux ...

voilà ce que ça me donne, ça fait a peu près 30 lignes de moins,évidemment, ça affiche les opérations à l'envers mais bon c'est trivial d'inverser donc bon...
c'est aussi un peu plus lent que ton code j'imagine, (mais la complexitée est évidemment la même) puisque j'ajoute une constante 6 pour le tableau de bool :)
#include <cstdlib>
#include <cstdio>

int tirage[6]={3,3,10,8,7,25};
bool utilise[6];
int cible=550;

bool chercher(int id,int total){
    if (total==cible)
        return true;
    if (id==6)
        return false;
    for (int i=0;i<6;i++){
        if (!utilise[i]){
            utilise[i]=true;
            if (chercher(id+1,total+tirage[i])){
                printf("%d + %d = %d\n",tirage[i],total,total+tirage[i]);
                return true;
            }
            else if (chercher(id+1,total*tirage[i])){
                printf("%d * %d = %d\n",tirage[i],total,total*tirage[i]);
                return true;
            }
            else if (chercher(id+1,total-tirage[i])){
                printf("%d - %d = %d\n",tirage[i],total,total-tirage[i]);
                return true;
            }
            else if (tirage[i]!=0 && chercher(id+1,total/tirage[i])){
                printf("%d / %d = %d\n",tirage[i],total,total/tirage[i]);
                return true;
            }
            utilise[i]=false;
        }
    }
    return false;
}

int main(void)
{

    if (chercher(1,tirage[0]))
        printf("\n possible\n");
    else
        printf("\npas possible\n");
    return 0;
}


1 novembre 2008 à 12:54:18

Dakeyras Khan, ta solution contient deux erreurs:
- elle accepte de diviser même quand ce n'est pas divisible
- elle ne sait pas résoudre (2+3)*(2+3)*5*5=625

Dans un niveau de récursion, il faut retirer 2 nombres du tableau, les combiner en un nouveau nombre que l'on injecte dans le tableau, et recommencer (avec un tableau qui a perdu une place)
C++: Blog|FAQ C++ dvpz|FAQ fclc++|FAQ Comeau|FAQ C++lite|FAQ BS| Bons livres sur le C++| PS: Je ne réponds pas aux questions techniques par MP.
1 novembre 2008 à 13:13:49

c'est possible, j'ai fait ça vite et sur un seul exemple(j'ai même oublié de mettre un utilise[0]=true ...)
pour les divisions, pareil, j'ai juste vérifié que c'étais pas un 0 , je vais corriger ça si tu veux...

j'ai pas trop compris le deuxième problème, je vais regarder
edit: ah certes ... j'ai fait de la merde :D
bon, je vais corriger ça ;)
4 novembre 2008 à 14:24:58

Bonjour,

je me demande comment faire pour trouver la fraction a partir de l'entier, car j'ai fait un truc du genre :
12 est le nombre de départ est ma fraction est 12/1 !


Du coup, pour les fractions en décimal, c'est problème ( sinon 0,5/1 :-° ).

EDIT : j'ai trouvé l'algo mais pour le mettre en code, c'est difficile !
EDIT 2 : je sais
Anonyme
4 novembre 2008 à 15:03:28

@Jivaa, les fractions sont faites pour ne pas avoir de décimales.

Si tu as des problèmes avec un exo, crée un nouveau topic, c'est plus pratique.
5 novembre 2008 à 13:25:41

Bonjour,

Question a Nanoc : On est obligé de faire tout les cas (pour les Fraction) ?