Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1500 connectés 

  FORUM HardWare.fr
  Programmation
  Algo

  Recherche de chaîne.

 


 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

Recherche de chaîne.

n°2113895
Profil sup​primé
Posté le 29-11-2011 à 18:17:30  answer
 

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.

mood
Publicité
Posté le 29-11-2011 à 18:17:30  profilanswer
 

n°2113982
rufo
Pas me confondre avec Lycos!
Posté le 30-11-2011 à 10:35:57  profilanswer
 

Je dois avouer que j'ai pas trop compris ce que tu cherches à faire :/


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°2114024
Profil sup​primé
Posté le 30-11-2011 à 12:19:22  answer
 

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.

n°2114047
rufo
Pas me confondre avec Lycos!
Posté le 30-11-2011 à 14:17:08  profilanswer
 

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. ;)


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°2114051
Profil sup​primé
Posté le 30-11-2011 à 14:40:28  answer
 

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.

n°2114056
Profil sup​primé
Posté le 30-11-2011 à 16:32:53  answer
 

Mais en fait je peux effectuer les opérations de comparaison "<" et >". [:dawa]
Je doit donc pourvoir gagner un poil déjà.

n°2114059
rufo
Pas me confondre avec Lycos!
Posté le 30-11-2011 à 16:42:22  profilanswer
 

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...


---------------
Astres, outil de help-desk GPL : http://sourceforge.net/projects/astres, ICARE, gestion de conf : http://sourceforge.net/projects/icare, Outil Planeta Calandreta : https://framalibre.org/content/planeta-calandreta
n°2114062
Profil sup​primé
Posté le 30-11-2011 à 16:54:07  answer
 

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 ?


Message édité par Profil supprimé le 30-11-2011 à 16:54:33
n°2114084
c_boy
Posté le 30-11-2011 à 19:37:13  profilanswer
 

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.

n°2114085
Profil sup​primé
Posté le 30-11-2011 à 19:45:51  answer
 

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.

mood
Publicité
Posté le 30-11-2011 à 19:45:51  profilanswer
 

n°2114086
gilou
Modérateur
Modzilla
Posté le 30-11-2011 à 20:02:37  profilanswer
 

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 :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. int main(void) {
  5.     char alphabet[] = "0123456789abcdefghijklmnopqrstuvwxyz";  // les lettres à permuter
  6.     int  size = 10; // taille du mot de sortie
  7.     int *compteurs;    // car on ne peut allouer un buffer statique, size n'étant pas fixe
  8.     compteurs = malloc(size * sizeof(int));
  9.     if (compteurs) {
  10. int alphamax = sizeof alphabet - 1;
  11. int i;
  12. clock_t start, end;
  13. start = clock();
  14. for (i = 0; i < size; ++i) { compteurs[i] = 0; } // les compteurs à 0
  15. do {
  16.     /* on ecrit le mot correspondant aux valeurs dans le tableau buffer */
  17.     for (i = size - 1; i >= 0; --i) {
  18.  putchar(alphabet[compteurs[i]]);
  19.     }
  20.     putchar('\n');
  21.     /* boucle qui incrémente successivement les entiers de buffer */
  22.     for (i = 0; i < size; ++i) {
  23.  if (++compteurs[i] < alphamax) // on incrémente le compteurs courant et on arrete
  24.      break;
  25.  else
  26.      compteurs[i] = 0;  // raz et incrémentation du compteur suivant autour de boucle
  27.     }
  28. } while (i < size);
  29. end = clock();
  30. free(compteurs);
  31. printf("Temps ecoule: %f\n", ((end - start) / CLOCKS_PER_SEC));
  32. return 0;
  33.     }
  34.     else {
  35. printf("Pas assez de memoire pour allouer un tableau de %d entiers!\n", size);
  36. return -1;
  37.     }
  38. }

 
 
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+,


Message édité par gilou le 30-11-2011 à 20:08:02

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
n°2114092
Profil sup​primé
Posté le 30-11-2011 à 20:33:30  answer
 

Alors 10 ça va faire longuet... [:dawa]
Je vais faire trois chaînes ; Deux de 3 et une de 4, soit 3mn, 25s à peu près.
[:dawa] Merci gilou ! T'as fait vite pour tester !  :jap:
Merci pour l'algo aussi.
 
 

n°2114100
gilou
Modérateur
Modzilla
Posté le 30-11-2011 à 20:56:47  profilanswer
 

Le même code, mais en bufferisant au lieu d'utiliser putchar.

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. int main(void) {
  5.     char alphabet[] = "0123456789abcdefghijklmnopqrstuvwxyz";  // les lettres à permuter
  6.     int  size = 4; // taille du mot de sortie
  7.     int *compteurs;    // car on ne peut allouer un buffer statique, size n'étant pas fixe
  8.     compteurs = malloc(size * sizeof(int));
  9.     if (compteurs) {
  10. char *buffer = malloc(size + 1);
  11. if (buffer) {
  12.     int alphamax = sizeof alphabet - 1;
  13.     int i;
  14.     clock_t start, end;
  15.     start = clock();
  16.     for (i = 0; i < size; ++i) { compteurs[i] = 0; } // les compteurs à 0
  17.     buffer[size] = 0; // \0 en fin de buffer
  18.     do {
  19.  /* on ecrit le mot correspondant aux valeurs dans le tableau buffer */
  20.  for (i = 0; i < size; ++i)  {
  21.      buffer[i] = alphabet[compteurs[i]];
  22.  }
  23.     printf("%s\n", buffer);
  24.  /* boucle qui incrémente successivement les entiers de buffer */
  25.  for (i = 0; i < size; ++i) {
  26.      if (++compteurs[i] < alphamax) // on incrémente le compteurs courant et on arrete
  27.   break;
  28.      else
  29.   compteurs[i] = 0;  // raz et incrémentation du compteur suivant autour de boucle
  30.  }
  31.     } while (i < size);
  32.     end = clock();
  33.     free(compteurs);
  34.     printf("Temps ecoule: %f\n", ((end - start) / CLOCKS_PER_SEC));
  35.     return 0;
  36. }
  37. else {
  38.     printf("Pas assez de memoire pour allouer un tableau de %d caracteres!\n", size+1);
  39.     return -1;
  40. }
  41.     }
  42.     else {
  43. printf("Pas assez de memoire pour allouer un tableau de %d entiers!\n", size);
  44. return -1;
  45.     }
  46. }


J'ai obtenu exactement les mêmes perfs (en seconde)
A+,


---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
n°2114117
Profil sup​primé
Posté le 30-11-2011 à 21:52:21  answer
 

Merci bien gilou. je vais déjà essayer d'implémenter le premier algo avec Ada, je verrais ensuite avec le second.

n°2114126
gilou
Modérateur
Modzilla
Posté le 30-11-2011 à 23:16:35  profilanswer
 

a la base, l'algo c'est ça:

Code :
  1. for (i = 1; i <= k; ++i) { i-eme compteur <- 0 } // k compteurs numériques initialisés a 0
  2. do {
  3.       // on passera ici avec chacune des valeur dans les k compteurs numériques
  4.       // Si on veut en faire quelque chose, appel de fonction ou autre, c'est ici qu'il faut le faire
  5.       for (i = 1; i <= k; ++i) {
  6.            i-eme compteur <- valeur(i-eme compteur) + 1
  7.           if (valeur(i-eme compteur) <= n)
  8.               break;
  9.          else
  10.               i-eme compteur <- 0
  11.     }
  12. } while (i <= k);


ç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+,


Message édité par gilou le 30-11-2011 à 23:45:48

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
n°2115920
Profil sup​primé
Posté le 10-12-2011 à 18:40:50  answer
 

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 :
  1. -- Ada language --
  2.   task body Borg_Type is
  3.      Launch_Code : String_Access;
  4.      Alphabet   : String := "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  5.      position    : array (1..10) of Positive := (others => 1);
  6.      Index, k : Positive := 1;
  7.      Code : String(1..10) := (others => '0');
  8.   begin
  9.      accept Start(Code : in String) do
  10.         position := (others => 1);
  11.         Launch_Code := new String ' (Code);
  12.         K := Launch_Code'Length;
  13.      end Start;
  14.  
  15.      loop
  16.         for J in Launch_Code'Range loop
  17.            Put(Alphabet(Position(J)));
  18.            Code(J) := Alphabet(Position(J));
  19.         end loop;
  20.  
  21.         if Code(Launch_Code'range) = Launch_Code.all then
  22.            New_Line;
  23.            exit;
  24.         else
  25.            Put(Character'Val(13));
  26.         end if;
  27.  
  28.         while index <= K loop
  29.            Position(Index) := Position(Index) + 1;
  30.            if Position(Index) <= Alphabet'Length then
  31.               exit;
  32.            else
  33.               Position(1..index) :=  (others => 1);
  34.               Position(index) :=  Position(index) + 1;
  35.            end if;
  36.            Index := Index + 1;
  37.         end loop;
  38.         exit when Index > K;
  39.         Index := 1;
  40.      end loop;
  41.  
  42.      accept Stop;
  43.   end Borg_Type;


Un algo pas si évident à transcrire, mais en tatonant finalement, j'y suis arrivé.


Message édité par Profil supprimé le 14-12-2011 à 10:27:10
n°2117091
Profil sup​primé
Posté le 18-12-2011 à 14:29:49  answer
 

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 :
  1. task body Borg_Type is
  2.      Launch_Code : String_Access;
  3.      Alphabet   : String := "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  4.      position    : array (1..10) of Positive := (others => 1);
  5.      Index, k : Positive := 1;
  6.      Code : String(1..10) := (others => '0');
  7.      End_Of_Task : Boolean := False;
  8.   begin
  9.  
  10.      while not End_Of_Task Loop
  11.         select
  12.            accept Start(Code : in String) do
  13.               position  := (others => 1);
  14.               Launch_Code := new String ' (Code);
  15.               K := Launch_Code'Length;
  16.            Text_Io.New_Line;
  17.            end Start;
  18.         or
  19.            accept Stop do
  20.               End_Of_Task := True;
  21.            end Stop;
  22.         end select;
  23.         while not End_Of_Task loop
  24.         
  25.         for J in Launch_Code'range loop
  26.            Put(Alphabet(Position(J)));
  27.            Code(J) := Alphabet(Position(J));
  28.         end loop;
  29.         
  30.         if Code(Launch_Code'Range) = Launch_Code.all then
  31.            exit;
  32.         else
  33.            Put(Character'Val(13));
  34.         end if;
  35.         select
  36.               accept Stop do
  37.                  End_Of_Task := True;
  38.               end Stop;
  39.            else
  40.            for I in Launch_Code'range loop
  41.           Position(I) := Position(I) + 1;
  42.           if Position(I) <= Alphabet'Length then
  43.              exit;
  44.           else          
  45.              Position(I) := 1;          
  46.           end if;            
  47.            end loop;              
  48.            end select;
  49.         end loop;
  50.      end loop;
  51.   end Borg_Type;


Bon, en espérant que ça marche à tous les coup, pas comme le précédent.


Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  Algo

  Recherche de chaîne.

 

Sujets relatifs
comment faire un moteur de recherche[resolu] recherche et insertion structure liste chaine: la V2
Pattern Java | Probleme ecriture dans fichier texte.Recherche chaine de caractères
Commencer la recherche au rang 'n' de la chaine[VBS] recherche d'une chaine de caractere dans different fichiers
Recherche d'un caractere dans une chainerecherche d'un mot dans une chaine
Faire une seule recherche de 2 types de chaine de caractère[resolu] [batch] recherche chaine avec findstr
Plus de sujets relatifs à : Recherche de chaîne.


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR