Discussion :

[Crusy007]

Bonjour à tous,

J'aurais besoin de votre aide car je n'arrive pas à faire une incrémentation d'une chaine de caractères.

Voilà le problème :
On doit retrouver (obligatoirement avec 8 threads) un mot (de 5 caractères) contenu dans un fichier texte.
On donne au départ un alphabet de 10 lettres qui sont utilisées dans le mot et chaque thread doit tester une partie des combinaisons possibles.
Comme on a un alphabet de 10 lettres et que le mot en fait 5, il y a 10^5 possibilités.

Admettons que le mot recherché soit "clair".
Le programme doit tester toutes les combinaisons possibles et retrouver le mot.
Donc il commence par "aaaaa", puis "aaaab", etc.., jusqu'à "claiq", puis "clair".

Voilà le code auquel on a pensé :

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
            //Variables globales//
            int nb_lettres_alphabet;
            char combinaison[int nb_lettres_alphabet];
            int taille_mdp;
            int nb_threads;
 
                //Fonctions//
 
    char thread1 (char combinaison[])
    {
        mdp = fopen (mdp.txt, 'r');
        const char val_debut = "aaaaa";
        const char val_fin  = "ccccc";
        char i;
        for (i = val_debut ; i < val_fin ; i++) //Le problème est au niveau des conditions de la boucle "for" 
        {
            if (mdp == combinaison[i])
                {
                    pthread_cancel (thread2);
                    pthread_cancel (thread3);
                    pthread_cancel (thread4);
                    pthread_cancel (thread5);
                    pthread_cancel (thread6);
                    pthread_cancel (thread7);
                    pthread_cancel (thread8);
                    printf ("Le mot recherché est: ");
                    printf (combinaison[i]);
                }
        }
               return(combinaison[i]);
    }

Est-ce qu'on est sur la bonne voie?
Merci à tous pour votre aide

[foetus]

Dans la table ascii les lettres minuscules et majuscules sont dans l'ordre croissant

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
    char current_str[5]  = "aaaaa";
    char searched_str[5] = "clair";
 
    unsigned char limit = 'r', is_not_equal;
 
    do {
        is_not_equal = ((current_str[0] != searched_str[0]) || (current_str[1] != searched_str[1]) || (current_str[2] != searched_str[2]) || (current_str[3] != searched_str[3]) || (current_str[4] != searched_str[4]));
 
        printf("%s\n", current_str);
 
        ++current_str[4];
 
        if (current_str[4] > limit) {
            current_str[4] = 'a';
            ++current_str[3];
 
            if (current_str[3] > limit) {
                current_str[3] = 'a';
                ++current_str[2];
 
                if (current_str[2] > limit) {
                    current_str[2] = 'a';
                    ++current_str[1];
 
                    if (current_str[1] > limit) {
                        current_str[1] = 'a';
                        ++current_str[0];
 
                        if (current_str[0] > limit) {
                            current_str[0] = 'a';
 
                            is_not_equal = 0; // quit
                        }
                    }
                }
            }
        }
    } while (is_not_equal);

[stendhal666]

Avec un alphabet de 10 lettres tu es en fait en numérotation de base 10; tu peux donc utiliser simplement un int dans ta boucle for qui sera traduisible en chaîne de caractère (ex: 1234 = "bcde" si l'alphabet est constitué des 10 premières lettres de l'alphabet dans l'ordre). Cela simplifiera grandement ton programme.

[foetus]

tu peux donc utiliser simplement un int dans ta boucle for qui sera traduisible en chaîne de caractère (ex: 1234 = "bcde"

Le problème de ta solution , c'est de devoir séparer tous les chiffres pour pourvoir faire les conversions ton entier <-> ta chaîne réelle.

Alors que même si c'est assez pénible, simplement tu peux savoir la longueur de ta chaîne et via des while modifier ta chaîne (ou bien si tes chaînes sont petites de façon bourrin avec des if imbriqués comme je l'ai fait )

[Crusy007]

Bonjour,

Merci beaucoup pour vos réponses. J'avais également une question Foetus concernant ton code. Je comprends ce que tu as fait mais j'ai l'impression que tu fais les tests dans un seul thread. Le but pour nous est de répartir toutes les combinaisons possibles dans 8 threads. Dans ce cas-là, il suffirait juste pour moi de modifier les tableaux "current_str" et "searched_str"? Car si j'ai bien compris tu testes tout d'un coup à travers quatre boucles if.

[foetus]

Oui c'est mono-threadé parce que rendre l'algo multi-threadé c'est ton travail

Par exemple tu pourrais calculer le nombre de combinaisons et le diviser par le nombre de thread.

C'était juste pour te montrer que les caractères ASCII majuscules et minuscules sont triés dans l'ordre croissant et qu'on peut manipuler un caractère comme un nombre (avec +1 +2 +3 ... ou -1 -2 -3 ...)
Et ensuite, comme une chaîne de caractères ASCII, c'est un tableau de caractères (avec le fameux '\0' final) c'est relativement simple pour accéder à un caractère en particulier. Il faut juste faire attention à la longueur de ta chaîne.

[stendhal666]

Le problème de ta solution , c'est de devoir séparer tous les chiffres pour pourvoir faire les conversions ton entier <-> ta chaîne réelle.

Alors que même si c'est assez pénible, simplement tu peux savoir la longueur de ta chaîne et via des while modifier ta chaîne (ou bien si tes chaînes sont petites de façon bourrin avec des if imbriqués comme je l'ai fait )

Mais non, c'est beaucoup plus simple que ça! tu traduis une seule fois la chaîne recherchée en un int, tu recherches l'int en question avec tes threads en attribuant à chacun un intervalle de (10^TAILLE_DU_MOT-1)/NB_THREADS et tu retraduis une seule fois le résultat en chaîne de caractère.

sachant que les fonctions de conversion ne sont pas bien compliquées...

EDIT / PS: c'est un exercice de cours - en choisissant un alphabet de 10 lettres ça m'étonnerait que le prof ait pas en tête la ressemblance avec la numérotation décimale...

[Crusy007]

Ok je vais prendre en considération ce que vous m'avez dit. Merci pour vos réponses . Juste une dernière question, pour faire un multi-thread, il me suffira juste de modifier la limite de "searched_str"? Vu que par exemple le thread n°1 va tester toutes les combinaisons possibles de "aaaaa" à "ccccc". Puis le thread n°2 testera de "ccccc" à "ggggg" par exemple vu que le mot de passe fait 5 caractères. Après je suis d'accord pour le calcul des possibilités. Il y a une fonction qui va s'occuper de faire ce calcul. Mais ça sera (10^5)/8, ça va faire 12500, car l'alphabet nous sera fixé, il sera de 10 lettres (à nous de les choisir), le mdp fera forcément 5 caractères et on utilisera 8 threads.

P.S: Désolé si je demande peut-être plusieurs fois la même chose, vous avez sûrement remarqué que je rame un peu ^^'.