--- title: "Introduction aux algorithmes" date: "2022-10-05" patat: eval: tai: command: fish fragment: false replace: true ccc: command: fish fragment: false replace: true images: backend: auto --- # Rappel (1/2) ## Quels algos avons-nous vu la semaine passée? . . . * L'algorithme de la factorielle. * L'algorithme du PPCM. * Le début de l'algorithme du PGCD. # Rappel (2/2) ## Algorithme du PPCM? . . . ```C int main() { int m = 15, n = 12; int mult_m = m, mult_n = n; while (mult_m != mult_n) { if (mult_m > mult_n) { mult_n += n; } else { mult_m += m; } } printf("Le ppcm de %d et %d est %d\n", n, m, mult_m); } ``` # Le calcul du PGCD (1/5) ## Définition Le plus grand commun diviseur (PGCD) de deux nombres entiers non nuls est le plus grand entier qui les divise en même temps. ## Exemples: ```C PGCD(3, 4) = 1, PGCD(4, 6) = 2, PGCD(5, 15) = 5. ``` . . . ## Mathématiquement Décomposition en nombres premiers: $$ 36 = 2^2\cdot 3^2,\quad 90=2\cdot 5\cdot 3^2, $$ On garde tous les premiers à la puissance la plus basse $$ PGCD(36, 90)=2^{\min{1,2}}\cdot 3^{\min{2,2}}\cdot 5^{\min{0,1}}=18. $$ # Le calcul du PGCD (2/5) ## Algorithme Par groupe de 3 (5-10min): * réfléchissez à un algorithme alternatif donnant le PGCD de deux nombres; * écrivez l'algorithme en pseudo-code. . . . ## Exemple d'algorithme ```C PGCD(36, 90): 90 % 36 != 0 // otherwise 36 would be PGCD 90 % 35 != 0 // otherwise 35 would be PGCD 90 % 34 != 0 // otherwise 34 would be PGCD ... 90 % 19 != 0 // otherwise 19 would be PGCD 90 % 18 == 0 // The end! ``` * 18 modulos, 18 assignations, et 18 comparaisons. # Le calcul du PGCD (3/5) ## Transcrivez cet exemple en algorithme (groupe de 3) et codez-le (5-10min)! . . . ## Optimisation * Combien d'additions / comparaisons au pire? * Un moyen de le rendre plus efficace? . . . ## Tentative de correction ```C void main() { int n = 90, m = 78; int gcd = 1; for (int div = n; div >= 2; div--) { // div = m, sqrt(n) if (n % div == 0 && m % div == 0) { gcd = div; break; } } printf("Le pgcd de %d et %d est %d\n", n, m, gcd); } ``` # Le calcul du PGCD (4/5) ## Réusinage: l'algorithme d'Euclide `Dividende = Diviseur * Quotient + Reste` ```C PGCD(35, 60): 35 = 60 * 0 + 35 // 60 -> 35, 35 -> 60 60 = 35 * 1 + 25 // 35 -> 60, 25 -> 35 35 = 25 * 1 + 10 // 25 -> 35, 20 -> 25 25 = 10 * 2 + 5 // 10 -> 25, 5 -> 10 10 = 5 * 2 + 0 // PGCD = 5! ``` . . . ## Algorithme Par groupe de 3 (5-10min): * analysez l'exemple ci-dessus; * transcrivez le en pseudo-code. # Le calcul du PGCD (5/5) ## Pseudo-code ```C entier pgcd(m, n) { tmp_n = n tmp_m = m tant que (tmp_m ne divise pas tmp_n) { tmp = tmp_n tmp_n = tmp_m tmp_m = tmp modulo tmp_m } retourne tmp_m } ``` # Le code du PGCD de 2 nombres ## Implémentez le pseudo-code et postez le code sur matrix (5min). . . . ## Un corrigé possible ```C #include <stdio.h> void main() { int n = 90; int m = 78; printf("n = %d et m = %d\n", n, m); int tmp_n = n; int tmp_m = m; while (tmp_n%tmp_m > 0) { int tmp = tmp_n; tmp_n = tmp_m; tmp_m = tmp % tmp_m; } printf("Le pgcd de %d et %d est %d\n", n, m, tmp_m); } ``` # Quelques algorithmes simples * Remplissage d'un tableau et recherche de la valeur minimal * Anagrammes * Palindromes * Crible d'ératosthène . . . * Ces algorithme nécessitent d'utiliser des **tableaux**. # Collections: tableaux statiques * Objets de même type: leur nombre est **connu à la compilation**; * Stockés contigüement en mémoire (très efficace); ```C #define SIZE 10 int entiers[] = {2, 1, 4, 5, 7}; // taille 5, initialisé int tab[3]; // taille 3, non initialisé float many_floats[SIZE]; // taille 10, non initialisé ``` * Les indices sont numérotés de `0` à `taille-1`; ```C int premier = entier[0]; // premier = 2 int dernier = entier[4]; // dernier = 7 ``` * Les tableaux sont **non-initialisés** par défaut; * Les bornes ne sont **jamais** vérifiées. ```C int indetermine_1 = tab[1]; // undefined behavior int indetermine_2 = entiers[5]; // UB ``` # Remarques * Depuis `C99` possibilité d'avoir des tableaux dont la taille est *inconnue à la compilation*; ```C int size; scanf("%d", &size); char string[size]; ``` . . . * Considéré comme une mauvaise pratique: que se passe-t-il si `size == 1e9`? * On préfère utiliser l'allocation **dynamique** de mémoire pour ce genre de cas-là (spoiler du futur du cours). # Initialisation * Les variables ne sont **jamais** initialisées en `C` par défaut. * Question: Que contient le tableau suivant? ```C double tab[4]; ``` . . . * Réponse: On en sait absolument rien! * Comment initialiser un tableau? . . . ```C #define SIZE 10 double tab[SIZE]; for (int i = 0; i < SIZE; ++i) { tab[i] = rand() / (double)RAND_MAX * 10.0 - 5.0; // tab[i] contient un double dans [-5;5] } ``` # Recherche du minimum dans un tableau (1/2) ## Problématique Trouver la valeur minimale contenue dans un tableau et l'indice de l'élément le plus petit. ## Écrire un pseudo-code résolvant ce problème (groupe de 3), 2min . . . ```C index = 0 min = tab[0] for i in [1; SIZE] { if min > tab[i] { min = tab[i] index = i } } ``` # Recherche du minimum dans un tableau (2/2) ## Implémenter ce bout de code en C (groupe de 3), 4min . . . ```C int index = 0; float min = tab[0]; for (int i = 1; i < SIZE; ++i) { if min > tab[i] { min = tab[i]; index = i; } } ``` # Tri par sélection (1/2) ## Problématique Trier un tableau par ordre croissant. ## Idée d'algorithme ```C ind = 0 tant que (ind < SIZE-1) Trouver le minimum du tableau, tab_min[ind:SIZE]. Échanger tab_min avec tab[ind] ind += 1 ``` # Tri par sélection (2/2) ## Implémentation par groupe de 3 * Initialiser aléatoirement un tableau de `double` de taille 10; * Afficher le tableau; * Trier par sélection le tableau; * Afficher le résultat trié; * Vérifier algorithmiquement que le résultat est bien trié. # Un type de tableau particulier ## Les chaînes de caractères ```C string = tableau + char + magie noire ``` # Le type `char`{.C} - Le type `char`{.C} est utilisé pour représenter un caractère. - C'est un entier 8 bits signé. - En particulier: - Écrire ```C char c = 'A'; ``` - Est équivalent à: ```C char c = 65; ``` - Les fonctions d'affichage interprètent le nombre comme sa valeur ASCII. # Chaînes de caractères (strings) - Chaîne de caractère `==` tableau de caractères **terminé par la valeur** `'\0'`{.C} ou `0`{.C}. ## Exemple ```C char *str = "HELLO !"; char str[] = "HELLO !"; ``` Est représenté par | `char` | `H` | `E` | `L` | `L` | `O` | | `!` | `\0`| |---------|------|------|------|------|------|------|------|-----| | `ASCII` | `72` | `69` | `76` | `76` | `79` | `32` | `33` | `0` | . . . ## A quoi sert le `\0`? . . . Permet de connaître la fin de la chaîne de caractères (pas le cas des autres sortes de tableaux). # Syntaxe ```C char name[5]; name[0] = 'P'; // = 70; name[1] = 'a'; // = 97; name[2] = 'u'; // = 117; name[3] = 'l'; // = 108; name[4] = '\0'; // = 0; char name[] = {'P', 'a', 'u', 'l', '\0'}; char name[5] = "Paul"; char name[] = "Paul"; char name[100] = "Paul is not 100 characters long."; ``` # Fonctions - Il existe une grande quantités de fonction pour la manipulation de chaînes de caractères dans `string.h`. - Fonctions principales: ```C // longueur de la chaîne (sans le \0) size_t strlen(char *str); // copie jusqu'à un \0 char *strcpy(char *dest, const char *src); // copie len char char *strncpy(char *dest, const char *src, size_t len); // compare len chars int strncmp(char *str1, char *str2, size_t len); // compare jusqu'à un \0 int strcmp(char *str1, char *str2); ``` - Pour avoir la liste complète: `man string`. . . . ## Quels problèmes peuvent se produire avec `strlen`, `strcpy`, `strcmp`? # Les anagrammes ## Définition Deux mots sont des anagrammes l'un de l'autre quand ils contiennent les mêmes lettres mais dans un ordre différent. ## Exemple | `t` | `u` | `t` | `u` | `t` | `\0` | ` ` | ` ` | |------|------|------|------|------|------|------|-----| | `t` | `u` | `t` | `t` | `u` | `\0` | ` ` | ` ` | ## Problème: Trouvez un algorithme pour déterminer si deux mots sont des anagrammes. # Les anagrammes ## Il suffit de: 1. Trier les deux mots. 2. Vérifier s'ils contiennent les mêmes lettres. ## Implémentation en live (offerte par HepiaVPN) ```C int main() { // pseudo C tri(mot1); tri(mot2); if egalite(mot1, mot2) { // anagrammes } else { // pas anagrammes } } ``` <!-- TODO: Live implémentation hors des cours? --> # Les palindromes Mot qui se lit pareil de droite à gauche que de gauche à droite: . . . * rotor, kayak, ressasser, ... ## Problème: proposer un algorithme pour détecter un palindrome . . . ## Solution 1 ```C while (first_index < last_index { if (mot[first_index] != mot [last_index]) { return false; } first_index += 1; last_index -= 1; } return true; ``` . . . ## Solution 2 ```C mot_tmp = revert(mot); return mot == mot_tmp; ``` # Crible d'Ératosthène Algorithme de génération de nombres premiers. ## Exercice * À l'aide d'un tableau de booléens, * Générer les nombres premiers plus petits qu'un nombre $N$ ## Pseudo-code * Par groupe de trois, réfléchir à un algorithme. ## Programme en C * Implémenter l'algorithme et le poster sur le salon `Element`.