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
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;
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.
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 ...
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.
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:
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.
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.
@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.
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
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é.
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 ) à 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;
}
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 ) à 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.
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.
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:
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 !
Oui oui celui-ci est nettement plus simple (la preuve j'ai donné une solution ). 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.
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.
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.
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;
}
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'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
bon, je vais corriger ça
* Un wrapper C++ pour sqlite * Une alternative a boost units