Recherche de chaîne.

Recherche de chaîne. - Algo - Programmation

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.

Reply

Marsh Posté le 29-11-2011 à 18:17:30   

Reply

Marsh Posté le 30-11-2011 à 10:35:57    

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
Reply

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.

Reply

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


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

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.

Reply

Marsh Posté le 30-11-2011 à 16:32:53    

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

Reply

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


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

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 ?


Message édité par Profil supprimé le 30-11-2011 à 16:54:33
Reply

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.

Reply

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.

Reply

Marsh Posté le 30-11-2011 à 19:45:51   

Reply

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 :
  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é!  --
Reply

Marsh Posté le 30-11-2011 à 20:33:30    

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.
 
 

Reply

Marsh Posté le 30-11-2011 à 20:56:47    

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é!  --
Reply

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.

Reply

Marsh Posté le 30-11-2011 à 23:16:35    

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é!  --
Reply

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 :
  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
Reply

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

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed