---
title: "Introduction aux algorithmes"
date: "2021-09-29"
---

# Exercice: test si un nombre est premier

## Avec tout ce que vous avez appris la dernière fois:

* Écrivez le code testant si un nombre est premier.
* Quels sont les ajouts possibles par rapport au code de la semaine passée?
* Rencontrez-vous des problèmes éventuels de compilation?
* Voyez-vous une façon de générer des nombres premiers avec votre programme?

. . .

## Implémentez-la et postez votre code sur le salon matrix (10 min).

# Corrigé: enfin pas vraiment mais juste un possible

\footnotesize 

```C
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>
int main() {
   int nb = 1;
   printf("Entrez un nombre: ");
   scanf("%d", &nb);
   bool premier = true;
   for (int div = 2; div <= sqrt(nb); div++) {
      if (nb % div == 0) {
         premier = false;
         break;
      }
   }
   if (premier) {
      printf("Le nombre %d est premier\n", nb);
   } else {
      printf("Le nombre %d n'est pas premier\n", nb);
   }
   return 0;
}
```

# Quelques algorithmes simples

## Voyons quelques algorithmes supplémentaires

- Plus petit commun multiple (PPCM) de deux nombres
- Autre algorithme de calcul du PPCM de deux nombres
- Plus grand commun diviseur (PGCD) de deux nombres

# Le calcul du PPCM (1/5)

## Définition

Le plus petit commun multiple (PPCM), `p`, de deux entiers non nuls, `a` et `b`,
est le plus petit entier strictement positif qui soit multiple de ces deux
nombres.

Exemples:

```C
PPCM(3, 4) = 12,
PPCM(4, 6) = 12,
PPCM(5, 15) = 15.
```

. . .

## 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 élevée
$$
PPCM(36, 90)=2^2\cdot 3^2\cdot 5=180.
$$

# Le calcul du PPCM (2/5)

## Exemple d'algorithme

```C
PPCM(36, 90):
36  < 90  // 36  + 36
72  < 90  // 72  + 36
108 > 90  // 90  + 90
108 < 180 // 108 + 36
144 < 180 // 144 + 36
180 = 180 // The End!
```

* 5 additions, 5 assignations, et 6 comparaisons.

. . .

## Transcrivez cet exemple en algorithme (groupe de 3), 5min

. . .

## et codez-le!


# Le calcul du PPCM (3/5)

## Tentative de correction

```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);
}
```

. . .

* Combien d'additions / comparaisons au pire?

# Le calcul du PPCM (4/5)

## Réusinage: Comment décrire une fonction qui ferait ce calcul (arguments, sorties)?

. . .

En `C` on pourrait la décrire comme

```C
int ppcm(int a, int b); // La **signature** de cette fonction
```

. . .

## Algorithme

Par groupe de 3 (5-10min):

* réfléchissez à un algorithme alternatif donnant le PPCM de deux nombres;
* écrivez l'algorithme en pseudo-code.

# Le calcul du PPCM (5/5)

## Indication

Si un nombre, `p`, est multiple de `a` et de `b` alors il peut s'écrire `p = a
* i = b * j`  ou encore `p / a = i` et `p / b = j`.

<!-- Si un nombre, $p$, est multiple de $a$ et de $b$ alors il peut s'écrire -->
<!-- $$ -->
<!-- p = a \cdot i = b \cdot j, -->
<!-- $$ -->
<!-- ou encore $p / a = i$ et $p / b = j$. -->

. . .

## Pseudo-code

```C
int ppcm(int a, int b) {
    for (i in [1, b]) {
        if a * i is divisible by b {
            return a * i
        }
    }
}
```

# Le code du PPCM de 2 nombres (1/2)

## Implémentez le pseudo-code et postez le code sur matrix (5min).

. . .

## Un corrigé possible


```C
#include <stdio.h>
#include <stdlib.h> 

int main() { 
   int n = 15, m = 12;
   int i = 1;
   while (n * i % m != 0) {
      i++;
   }
   printf("Le ppcm de %d et %d est %d\n", n, m, n*i);
}
```

# Le code du PPCM de 2 nombres (2/2)

## Corrigé alternatif

```C
#include <stdio.h>
#include <stdlib.h> 

int main() { 
   int res = n*m;
   for (int i = 2; i <= m; i++) {
     if (n * i % m == 0) {
        res = n * i;
        break;
     }
   }
   printf("Le ppcm de %d et %d est %d\n", n, m, res);
}
```

# 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
int pgcd(int a, int b) {
    tmp_n = n
    tmp_m = m
    while (tmp_m does not divide tmp_n) {
        tmp   = tmp_n
        tmp_n = tmp_m
        tmp_m = tmp modulo tmp_m
    }
    return 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);
}
```


