Discussion :

[enigman0001]

bonjour

j'ai crée un algorithme de chiffrement qui prend un mot en paramètres et mélange les lettres de façon aléatoire puis renvoie le mot chiffrée

mais le problème c'est que ça prend 15 secondes !!!

voila le code source, si quelqu'un a des idées pour l'optimiser, je suis preneur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
#include <string>
#include <ctime>
#include <cstdlib>
#include "MelangeMot.h"
 
using namespace std;
 
string melange_mot(string mot)
{
    string chaine(mot);
    int i(0), nombreAleatoire(0);
    int const MAX(mot.size());
    bool v;
 
    while(!v)// si il reste des caractéres non chiffrées
    {
      v = cherche_caractere(mot, '*'); // si toutes les cases de mot[] contiennent '*'
 
      // generation du nombre aleatoire
      srand(time(0));
      nombreAleatoire = rand() % MAX;
 
      // recuperation d'un caractere au hasard
      if(mot[nombreAleatoire] != '*') // pour eviter de chiffrer le meme caractere 2 fois
      {
        chaine[i] = mot[nombreAleatoire]; // on recupére le caractére dans chaine[]
        mot[nombreAleatoire] = '*'; //et on le remplace par '*', la prochaine fois il ne seras pas chiffré
        ++i;
      }
    }
 
    // renvoie du mot chiffré
    return chaine;
}
bool cherche_caractere(std::string mot, char c)
{
    int i(0);
    bool valeure(true);
 
    while(mot[i] != '\0' && valeure)
    {
      if(mot[i] != c)// si un caractere est differant de c
      {
        valeure = false;
      }
      ++i;
    }
 
    return valeure; // on revoi la valeur de verité
}

et merci pour votre aide.

[Bousk]

Salut,

Ton code est très mauvais et surtout n'a aucune logique
- variables non initialisées
- copies dans tous les sens
- multiple boucles inutiles
- réinitialisation du générateur au milieu
- pioche au hasard de la lettre à remplacer sans même s'assurer qu'elle est à processer

T'es chanceux que le code démarre et ne dure que 15s.
Ton algo n'est pas bon, pose-le sur une feuille et en théorie avant de le coder.

Et quand tu auras fait ça, pourquoi ne pas utiliser std::shuffle ?

[Pyramidev]

Bonjour,

Il ne s'agit pas de chiffrement. Quand on chiffre un mot, on se donne le moyen de récupérer le mot de départ. Or, avec ta méthode, tu n'as plus de moyen de le retrouver. Par exemple, si tu as "icenh", tu ne pourras pas savoir si le mot de départ était, par exemple, "chien" ou "niche". Si tu veux faire un chiffrement en mélangeant les lettres, alors il faut sauvegarder quelque part l'ordre dans lequel remettre les lettres pour retrouver le mot de départ.

A part ça, pour mélanger les lettres de ton mot, voici une idée d'algorithme décrite sous forme d'exemple :

A partir de ton mot, par exemple "chien", tu crées un tableau d'entiers consécutifs de 0 jusqu'au nombre de caractères de ta chaîne moins un :
0 1 2 3 4

Ensuite, tu génères un nombre aléatoire modulo 5. Par exemple, admettons que ce soit 1.
Dans ton tableau, tu copies ton élément numéro 1, c'est-à-dire 1, dans un nouveau tableau et, dans ton ancien tableau, tu remplaces 1 par -1 pour dire que tu l'as déjà pris :
0 -1 2 3 4
1

Ensuite, tu génères un nombre aléatoire modulo 4. Par exemple, admettons que ce soit 2.
Dans ton tableau, parmi les éléments non pris, tu copies ton élément numéro 2, c'est-à-dire 3, à la fin du nouveau tableau et, dans ton ancien tableau, tu remplaces 3 par -1 pour dire que tu l'as déjà pris :
0 -1 2 -1 4
1 3

Ensuite, tu génères un nombre aléatoire modulo 3. Par exemple, admettons que ce soit 2.
Dans ton tableau, parmi les éléments non pris, tu copies ton élément numéro 2, c'est-à-dire 4, à la fin du nouveau tableau et, dans ton ancien tableau, tu remplaces 4 par -1 pour dire que tu l'as déjà pris :
0 -1 2 -1 -1
1 3 4

Ensuite, tu génères un nombre aléatoire modulo 2. Par exemple, admettons que ce soit 1.
On a alors :
0 -1 -1 -1 -1
1 3 4 2

Enfin, tu prends l'élément qui reste :
-1 -1 -1 -1 -1
1 3 4 2 0

Tu obtiens ainsi une clé de chiffrement, 1 3 4 2 0, qui te permet de dire dans quel ordre mélanger les lettres de ton mot.
Par exemple, elle transformera "chien" en "henic".
La clé de déchiffrement qui remettra les lettres dans le bon ordre sera 4 0 3 1 2.

[Pyramidev]

Pour générer une permutation aléatoire avec une probabilité uniforme (c.-à-d. où chaque permutation a autant de chances d'être choisie que les autres), je viens de penser à un autre algo, plus simple à coder et aussi plus performant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Soit un ensemble à n éléments.
Pour i allant de 0 à n-1.
    Soit k un entier aléatoire entre i et n-1 inclus, choisi avec une probabilité uniforme.
    Si i est différent de k.
        Échanger l'élément numéro i avec l'élément numéro k.
    FinSi
FinPour

Tu peux appliquer cet algo à la suite d'entiers consécutifs (0 1 2 3 4 dans l'exemple de mon précédent message).
Par rapport à l'algo de mon précédent message, celui du message présent évite d'allouer un tableau supplémentaire et de compter à chaque fois le nombre d'éléments différents de -1 de gauche à droite.

[enigman0001]

Salut,

Ton code est très mauvais et surtout n'a aucune logique
- variables non initialisées
- copies dans tous les sens
- multiple boucles inutiles
- réinitialisation du générateur au milieu
- pioche au hasard de la lettre à remplacer sans même s'assurer qu'elle est à processer

T'es chanceux que le code démarre et ne dure que 15s.
Ton algo n'est pas bon, pose-le sur une feuille et en théorie avant de le coder.

Et quand tu auras fait ça, pourquoi ne pas utiliser std::shuffle ?

merci pour ton aide

[enigman0001]

Pour générer une permutation aléatoire avec une probabilité uniforme (c.-à-d. où chaque permutation a autant de chances d'être choisie que les autres), je viens de penser à un autre algo, plus simple à coder et aussi plus performant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Soit un ensemble à n éléments.
Pour i allant de 0 à n-1.
    Soit k un entier aléatoire entre i et n-1 inclus, choisi avec une probabilité uniforme.
    Si i est différent de k.
        Échanger l'élément numéro i avec l'élément numéro k.
    FinSi
FinPour

Tu peux appliquer cet algo à la suite d'entiers consécutifs (0 1 2 3 4 dans l'exemple de mon précédent message).
Par rapport à l'algo de mon précédent message, celui du message présent évite d'allouer un tableau supplémentaire et de compter à chaque fois le nombre d'éléments différents de -1 de gauche à droite.

salut et merci pour tes réponses rapide
en effet c'est un code très simple, je vais l'essayer