---
title: "Introduction aux algorithmes III"
date: "2024-09-30"
---
# Rappel (1/2)
## Quels algos avons-nous vu la semaine passée?
. . .
* L'algorithme de la factorielle.
* L'algorithme du PPCM.
# 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
\footnotesize
* Objets de même type: leur nombre est **connu à la compilation**;
* Stockés de façon contiguë 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` la taille peut être *inconnue à la compilation* (VLA);
```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]
}
int other_tab[4] = {0}; // pareil que {0, 0, 0, 0}
```
# 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]
pour i de 1 à SIZE - 1
si 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 = min([ind:SIZE]).
Échanger tab_min avec tab[ind]
ind += 1
```