# I- Présentation du problème ##A) Les entrées On nous fournit: - Un entier `N` (`2 ≤ N ≤ 5`), qui représente le nombre de mots à additionner; - `N` chaînes de caractères `mots`, chacune représentant un mot à additionner; - Une dernière chaîne de caractères `totalStr` représentant le total de l’addition des mots précédents. ##B) But du jeu Pour résoudre ce problème, il faut écrire un programme en C qui résout un cryptarithme, c'est-à-dire une équation dans laquelle les chiffres ont été remplacés par des lettres. Dans ce problème, chaque cryptarithme est une addition entre plusieurs mots. Le programme devra trouver et afficher l’unique correspondance entre chaque lettre et un chiffre (de 0 à 9). Il faut donc analyser et attribuer un chiffre à chaque lettre, en respectant les règles suivantes : - Une même lettre représente toujours le même chiffre; - Deux lettres distinctes ne peuvent pas correspondre au même chiffre; - Aucune lettre placée en tête d’un mot ne peut être associée au chiffre 0. Ce programme devra donc trouver la correspondance correcte entre les lettres et les chiffres afin de satisfaire l’équation du cryptarithme. ##C) La sortie On doit retourner toutes les lettres ainsi que leur valeur respective. L'affichage se fait ligne après ligne avec une lettre et son chiffre correspondant par ligne. # II- Ma méthode de résolution ##A) Approche synoptique J'analyse d'abord les données en identifiant les éléments clés du problème : les mots à additionner, ainsi que le mot total. Ensuite, j'extrais toutes les lettres distinctes présentes dans ces mots et les as organisées pour faciliter leur traitement. Ensuite, pour attribuer un chiffre à chaque lettre, j'explore différentes combinaisons possibles en générant des affectations de chiffres aux lettres tout en respectant les contraintes du problème. Cette exploration s’est faite de manière systématique afin de tester chaque possibilité. À chaque étape, je vérifie si l’association des lettres aux chiffres donnait une addition correcte. Dès qu’une configuration valide a été trouvée, j'affiche le résultat en respectant l’ordre alphabétique des lettres. ##B) Approche algorithmique et explication de mon programme Tout d'abord, mon programme commence par récupérer le nombre de mots à additionner ainsi que les mots eux-mêmes, suivis du mot représentant le total attendu. Il parcourt tous les mots et identifie quelles lettres sont présentes dans l’équation, ensuite, il trie ces lettres par ordre alphabétique afin de garantir un affichage structuré. Il faut ensuite que le programme génére les différentes permutations, pour cela le programme cherche toutes les façons possibles d’attribuer un chiffre (de 0 à 9) à chaque lettre unique. Il utilise une approche récursive qui explore toutes les combinaisons valides tout en respectant les contraintes du problème (par exemple, une lettre en début de mot ne peut pas être associée à 0). Une fois une possibilité déterminé, il faut vérifier si cette solution fonctionne, donc, pour chaque permutation générée, il convertit les mots en nombres en remplaçant les lettres par leurs chiffres associés. Une fois les mots convertient, le programme effectue l’addition des `N` mots et vérifie si la somme obtenue correspond bien au total donné dans l’entrée. Pour finir, lorsqu’une permutation valide est trouvée, il affiche chaque lettre suivie du chiffre qui lui est associé, en respectant l’ordre alphabétique. ```c /** * @file code.c * @author Eliott * @author ESBELIN * @version finale * @date 20 avril 2025 * @brief Mon code pour cryptarithm */ #include #include #include /** * @def #define MAX_LETTRES 10 * @brief défini une variable MAX_LETTRES à 10 */ #define MAX_LETTRES 10 /** * @def #define MAX_MOTS 5 * @brief défini une variable MAX_MOTS à 5 */ #define MAX_MOTS 5 /** * @def #define MAX_LONGUEUR 100 * @brief défini une variable MAX_LONGUEUR à 100 */ #define MAX_LONGUEUR 100 /** * @fn int verifier_solution(char mots[MAX_MOTS][MAX_LONGUEUR], int N, char totalStr[MAX_LONGUEUR], int chiffres[], char lettres[], int nb_lettres) * @brief vérifie si la combinaison satisfait l'addition * @param mots un tableau de chaines de caractères * @param N un entier naturel * @param totalStr une chaine de caractères * @param chiffres un entier naturel * @param lettres une chaine de caractère * @param nb_lettres un entier naturel * @return 1 si l'addition est correcte * @return 0 si l'addition n'est pas correcte */ int verifier_solution(char mots[MAX_MOTS][MAX_LONGUEUR], int N, char totalStr[MAX_LONGUEUR], int chiffres[], char lettres[], int nb_lettres) { int valeurs[N + 1]; for (int i = 0; i < N + 1; i++) { valeurs[i] = 0; char *mot = (i < N) ? mots[i] : totalStr; for (int j = 0; j < strlen(mot); j++) { int index = strchr(lettres, mot[j]) - lettres; valeurs[i] = valeurs[i] * 10 + chiffres[index]; } } int somme = 0; for (int i = 0; i < N; i++) { somme += valeurs[i]; } return (somme == valeurs[N]); } /** * @fn void permuter(int chiffres[], int index, int utilisé[], char mots[MAX_MOTS][MAX_LONGUEUR], int N, char totalStr[MAX_LONGUEUR], char lettres[], int nb_lettres) * @brief génère les permutations des chiffres * @param chiffres un tableau d'entier naturel * @param index un entier naturel * @param utilisé un tableau d'entier naturel * @param mots un tableau de chaines de caractères * @param N un entier naturel * @param totalStr une chaine de caractère * @param lettres une chaine de caractère * @param nb_lettres un entier naturel */ void permuter(int chiffres[], int index, int utilisé[], char mots[MAX_MOTS][MAX_LONGUEUR], int N, char totalStr[MAX_LONGUEUR], char lettres[], int nb_lettres) { if (index == nb_lettres) { if (verifier_solution(mots, N, totalStr, chiffres, lettres, nb_lettres)) { for (int i = 0; i < nb_lettres; i++) { printf("%c %d\n", lettres[i], chiffres[i]); } } return; } for (int i = 0; i < 10; i++) { if (!utilisé[i]) { int est_premiere_lettre = 0; for (int j = 0; j < N + 1; j++) { char *mot = (j < N) ? mots[j] : totalStr; if (lettres[index] == mot[0]) { est_premiere_lettre = 1; break; } } if (est_premiere_lettre && i == 0) continue; chiffres[index] = i; utilisé[i] = 1; permuter(chiffres, index + 1, utilisé, mots, N, totalStr, lettres, nb_lettres); utilisé[i] = 0; } } } int main() { int N; scanf("%d", &N); char mots[MAX_MOTS][MAX_LONGUEUR]; for (int i = 0; i < N; i++) { scanf("%s", mots[i]); } char totalStr[MAX_LONGUEUR]; scanf("%s", totalStr); char lettres[MAX_LETTRES] = ""; for (int i = 0; i < N + 1; i++) { char *mot = (i < N) ? mots[i] : totalStr; for (int j = 0; j < strlen(mot); j++) { if (!strchr(lettres, mot[j])) { int len = strlen(lettres); lettres[len] = mot[j]; lettres[len + 1] = '\0'; } } } // Trier les lettres par ordre alphabétique int nb_lettres = strlen(lettres); qsort(lettres, nb_lettres, sizeof(char), (int (*)(const void *, const void *)) strcmp); int chiffres[MAX_LETTRES], utilisé[10] = {0}; permuter(chiffres, 0, utilisé, mots, N, totalStr, lettres, nb_lettres); return 0; } ``` # III- Un autre programme ```c #include #include #include int N, letters, digit_used[10], letter_to_digit[10]; char word[6][11], letter[11], *p, line[6][11]; /** * @fn int cmp(const void *a, const void *b) * @brief trie les lettres alphabétiquement * @param a de type const void * * @param b de type const void * * @return la différence entre les deux caractères (suivant le code ASCII) */ int cmp(const void *a, const void *b){ return *(char*)a - *(char*)b; } /** * @fn int is_initial(char c) * @brief trie les lettres alphabétiquement * @param c un caractère * @return 1 si la lettre est en début de mot * @return 0 si la lettre n'est pas en début de mot */ int is_initial(char c){ for(int i = 0; i <= N; i++) if(word[i][0] == c) return 1; return 0; } /** * @fn void test() * @brief vérifie si l'addition est correcte * @return retour de fonction sans rien faire si la somme n'est pas correcte */ void test(){ for(int i = 0; i <= N; i++) for(int j = 0; word[i][j]; j++) for(int k = 0;; k++) if(word[i][j] == letter[k]){ line[i][j] = letter_to_digit[k] + '0'; break; } int sum = 0; for(int i = 0; i <= N; i++) sum += atoi(line[i]) * (i == N ? -1 : 1); if(sum) return; for(int i = 0; i < letters; i++) printf("%c %i\n", letter[i], letter_to_digit[i]); exit(0); } /** * @fn void assign(int i) * @brief teste chaque combinaison avant de trouver la bonne * @param i un entier naturel */ void assign(int i){ letter_to_digit[i] = is_initial(letter[i]); for(; letter_to_digit[i] <= 9; letter_to_digit[i]++) if(digit_used[letter_to_digit[i]] == 0){ if(i == letters - 1) test(); else digit_used[letter_to_digit[i]] = 1, assign(i + 1), digit_used[letter_to_digit[i]] = 0; } } int main(){ scanf("%d", &N); for(int i = 0; i <= N; i++) for(scanf("%s", p = word[i]); *p; p++) if(strchr(letter, *p) == 0) letter[letters++] = *p; qsort(letter, letters, sizeof(char), cmp); assign(0); } ``` Ce programme extrait directement les lettres uniques lors de la lecture des mots, alors que ton programme les rassemble après coup. Il trie ces lettres avec `qsort`, tout comme toi. Pour attribuer des chiffres, il utilise une affectation récursive qui évite 0 pour les lettres initiales dès le départ, tandis que toi, tu vérifies cela pendant les permutations. Il reconstruit les valeurs numériques des mots avec `atoi`, ce qui est plus direct que ton approche basée sur la multiplication progressive. Enfin, il s’arrête immédiatement (`exit(0)`) dès qu’une solution valide est trouvée, alors que ton programme teste toutes les permutations avant d'afficher la solution. Cela le rend potentiellement plus rapide dans certaines configurations. Vous trouverez [ici](../../../../telechargement.html) la page de téléchargement des fichiers concernant le rapport cryptarithm.