Bonjour,
j'ai récemment programmé un algorithme "brute force" en C++ pour générer toutes les chaines possibles jusqu'à qu'il trouve celle voulue.
Cependant j'ai un problème, le temps pour la recherche est trop élevé :
Les données de temps :
~0.0001 secondes pour trouver 9
~0.0014 secondes pour trouver 99
~0.0657 secondes pour trouver 999
2.84972 secondes pour trouver 9999
122.367 secondes pour trouver 99999
4922.98 secondes pour trouver 999999
Au dessus je n'ai pas encore réussi à avoir un résultat.

Je vais donc tenté de vous expliquer l'algorithme de ma création utilisé pour cela, tout cela sans communiquer de code car les modérateurs me l'ont formellement interdit dans le respect de la législation et des règles du forum.

Pour situer l'utilisation voici l'header de la classe (sans le code de brute force) :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
11
12
13
class BruteForce
{
    public:
		BruteForce(std::string scope = "abcdefghijklmnopqrstuvwxyz0123456789", std::string startCombination = "", int increaseEach = 1);
		~BruteForce();
		std::string GetNext(); // Call this method to get the next combination
 
	private:
        std::string m_scope;
        std::string m_combination;
        vector<int> m_values;
        int         m_increaseEach;
};
Pour récupérer la combinaison suivante j'appelle donc GetNext(), grâce à une boucle, qui renvoie donc une chaine (par exemple : "aaz").


Algorithme :
J'utilise trois tableaux de variable, un tableau de caractères pouvant prendre tous les caractères du deuxième (le tableau des caractères à tester) et un troisième tableau de nombres qui sauvegarde la valeur (l'index) de chaque caractère de chaque emplacement de la chaine de caractère.

Ensuite dans "GetNext()", je boucle en partant de la dernière case de mon tableau de nombres et je l'incrémente si il ne dépasse pas le caractère maximal du tableau des caractères à tester, sinon je le remet à zéro et j'incrémente le suivant. Ceci jusqu'à la fin (tant que cela est nécessaire). Durant cette boucle, je vérifie si tous les caractères sont égaux à la valeur maximal du tableau des caractères à tester.
Une fois la boucle fini, si tous les caractères sont égaux à la valeur maximal du tableau des caractères à tester, je les remets tous à zéro et j'ajoute une case que je met, elle aussi, à zéro. (je pourrais générer la chaine en même que je boucle plus haut mais même avec cela, je ne pense pas que cela rendrait mon algorithme complètement optimisé)

Une fois cela fait je génère la chaine que je renvoi à la fin de "GetNext()".

Voila pour l'algorithme. J'ai précédemment cherché sur le net des codes, des algorithme, mais il sont rares et ceux que j'ai trouvé je n'ai pas réussi à comprendre leur fonctionnement et à les adapté à ma situation (appelé grâce à une boucle la fonction pour récupérer la prochaine valeur).


Je poste uniquement mon problème algorithmique, et ceci dans un but pédagogique pour progresser dans l'algorithmique et dans la sécurité informatique ainsi que dans des concepts mathématiques nouveau pour moi.

Je vous remercie donc pour l'aide que vous pourrez m'apporter ainsi que pour le temps que vous avez consacré à la lecture de ces lignes.

Merci d'avance.