Recherche de chaîne. - Algo - Programmation
Marsh Posté le 30-11-2011 à 10:35:57
Je dois avouer que j'ai pas trop compris ce que tu cherches à faire
Marsh Posté le 30-11-2011 à 12:19:22
Bonjour rufo
Je tire une chaîne aléatoire de 10 caractère en gros. Ca je sais le faire. Après je demande comment retrouver cette chaîne plus ou moins efficacement.
Marsh Posté le 30-11-2011 à 14:17:08
On est dans le domaine de la cryptanalyse, là, non?
Sans plus de détail, je dirais que tu fais du brute-force en tenant compte de la façon dont est construite ta chaîne : AAABBBCCCC ou A, B, C représente une lettre de a à z ou de 0 à 9.
Marsh Posté le 30-11-2011 à 14:40:28
Merci rufo,
Oui, mais la je voudrais savoir si c'est faisable en quelque minutes ou en quelque heures ?
Je précise que je dois trouver une chaîne de 10 caractères de a à z et 0 à 9.
Merci pour vos réponse.
Marsh Posté le 30-11-2011 à 16:32:53
Mais en fait je peux effectuer les opérations de comparaison "<" et >".
Je doit donc pourvoir gagner un poil déjà.
Marsh Posté le 30-11-2011 à 16:42:22
j'ai du mal à voir comment le < et > vont te servir Le < et > sur des chaînes, ça me paraît aléatoire suivant le langage de dév, tu risques de pas avoir le même comportement...
Marsh Posté le 30-11-2011 à 16:54:07
ben ce sont les opérateur supérieur et inférieur sur des chaînes.
Un trie lexicographique il me semble que ça s'appelle.
Non ?
Marsh Posté le 30-11-2011 à 19:37:13
Tu fais une boucle sur tes 10 caracteres
dans cette boucle tu appel une routine en lui passant l'index
du caractere que tu veux tester, si tu a 36 caracteres possibles,
au 1er appel tu test le caractere du milieu (le 18 em)
ta routine test si c'est le bon caractere si oui tu sort de ta routine
sinon si c'est < tu rappel la routine dans laquelle tu es (récurssivitée)
en lui passant comme caractere à tester le 9 em caractere (la moitié inferieur)
ou si c'est > tu lui passe le27em caractere (la moitié superieur)
etc...
Ca s'appel de la dicotomie récurssive.
C'est la methode la plus rapide (quelque seconde dans ton cas.
A part ca je ne comprend pas l'interet de ton progamme puisque tu connait deja le resultat.
Marsh Posté le 30-11-2011 à 19:45:51
Merci bien c_boy pour tout ça...
C'est pour un jeu ; C'est un artifice qui me permet de temporiser une opération. Et ce sera peut-être un contre la montre pour le joueur, style entrer les code avant que l'ordinateur les trouve.
Marsh Posté le 30-11-2011 à 20:02:37
Pas besoin de 10 boucles imbriquées, ni de récursivité, hein:
Le principe de l'algo: on a n roues crantées avec k crans, identiques, on fait avancer cran par cran la première, quand elle a fait un tour, et est revenue à 0, et la roue suivante avance d'un cran, etc
ça va nous donner toutes les combinaisons avec répétition de longueur n de nombres variant de 0 à k-1
Et pour chaque combinaison numérique, on transpose avec une correspondance entre les k crans -> k symboles de l'alphabet, pour obtenir un mot de longueur n dans l'alphabet
Code :
|
Si je fais size = 3, les mots sont générés en 5s sur ma bécane poussive
Si je fais size = 4, ça prend 3mn 15s, soit 39 fois plus
Je te laisse voir combien de temps ça prendra si tu fais size = 10
On peut peut être optimizer (tout écrire dans un buffer de taille 11 au lieu de faire des putchar, et écrire le mot complété, c'est à tester)
A+,
Marsh Posté le 30-11-2011 à 20:33:30
Alors 10 ça va faire longuet...
Je vais faire trois chaînes ; Deux de 3 et une de 4, soit 3mn, 25s à peu près.
Merci gilou ! T'as fait vite pour tester !
Merci pour l'algo aussi.
Marsh Posté le 30-11-2011 à 20:56:47
Le même code, mais en bufferisant au lieu d'utiliser putchar.
Code :
|
J'ai obtenu exactement les mêmes perfs (en seconde)
A+,
Marsh Posté le 30-11-2011 à 21:52:21
Merci bien gilou. je vais déjà essayer d'implémenter le premier algo avec Ada, je verrais ensuite avec le second.
Marsh Posté le 30-11-2011 à 23:16:35
a la base, l'algo c'est ça:
Code :
|
ça fait varier les k compteurs de 0, 0, ..., 0 à n, n, ..., n en faisant
0, 0, ..., 0
1, 0, ..., 0
2, 0, ..., 0
....
n, 0, ..., 0
0, 1, ..., 0
1, 1, ..., 0
2, 1, ..., 0
...
n, n, ..., n
1: On incrémente le premier compteur,
s'il a pas atteint la valeur max, on reboucle en 1
sinon, on remet le compteur a 0 et on propage la retenue au 2e compteur,
s'il le 2e a pas atteint la valeur max, on reboucle en 1
sinon, on remet le compteur a 0 et on propage la retenue au 3e compteur,
etc
et si tous les compteurs ont atteint la valeur max, on arrête
A+,
Marsh Posté le 10-12-2011 à 18:40:50
Mon code avec Ada, une tache avec une entrée start pour prendre la chaîne à chercher, et une stop, pour certifier la fin de l'ago.
Code :
|
Un algo pas si évident à transcrire, mais en tatonant finalement, j'y suis arrivé.
Marsh Posté le 18-12-2011 à 14:29:49
Pourquoi faire compliqué et en plus un truc qui marche pas.
Voilà la révision de mon code Ada, que je suis en train de tester plus longuement mais qui est celui que donne gilou, sans détour.
Je ne sais pas pourquoi j'avais pas fait ça du premier coup.
Code :
|
Bon, en espérant que ça marche à tous les coup, pas comme le précédent.
Marsh Posté le 29-11-2011 à 18:17:30
Bonjour,
J'espère ne pas être hors charte, c'est pour un jeu.
J'écris un jeu dans lequel je souhaiterais implémenter une protection par une clef que je devrai chercher automatiquement.
Si c'est possible, Je voudrais faire une clef composée de deux chaînes de 3 digit caractères de 36 valeurs plus une chaîne de 4 digit caractères des même valeurs.
Est-ce possible en quelque minutes (1h à 24h) ? Je ne me rends pas compte de la complexité ... O(10**36) ?
Comment trouver une chaîne donnée ?
Je ferai 10 boucles imbriquées si non.
Merci pour vos réponses.