---
title: "Tableaux à deux dimensions et représentation des nombres"
date: "2023-10-17"
---

# Réusinage de code (refactoring)

## Exercice:

* Réusiner le code se trouvant sur
  [Cyberlearn](https://cyberlearn.hes-so.ch/pluginfile.php/703384/mod_resource/content/1/comprendre.c).

# Tableau à deux dimensions (1/4)

## Mais qu'est-ce donc?

. . .

* Un tableau où chaque cellule est un tableau.

## Quels cas d'utilisation?

. . .

* Tableau à double entrée;
* Image;
* Écran (pixels);
* Matrice (mathématique);
 
# Tableau à deux dimensions (2/4)

## Exemple: tableau à 3 lignes et 4 colonnes d'entiers

+-----------+-----+-----+-----+-----+
| `indices` | `0` | `1` | `2` | `3` |
+-----------+-----+-----+-----+-----+
| `0`       | `7` | `4` | `7` | `3` |
+-----------+-----+-----+-----+-----+
| `1`       | `2` | `2` | `9` | `2` |
+-----------+-----+-----+-----+-----+
| `2`       | `4` | `8` | `8` | `9` |
+-----------+-----+-----+-----+-----+

## Syntaxe

```C
int tab[3][4]; // déclaration d'un tableau 3 x 4
tab[2][1]; // accès case: ligne 2, colonne 1
tab[2][1] = 14; // assignation de 14 à la position 2, 1
```

# Tableau à deux dimensions (3/4)

\footnotesize

## Exercice: 

Déclarer et initialiser aléatoirement un tableau `50x100` avec des valeurs `0` à `255`

. . .

```C
#define NX 50
#define NY 100
int tab[NX][NY];
for (int i = 0; i < NX; ++i) {
    for (int j = 0; j < NY; ++j) {
        tab[i][j] = rand() % 256; // 256 niveaux de gris
    }
}
```
 
## Exercice: afficher le tableau

. . .

```C
for (int i = 0; i < NX; ++i) {
    for (int j = 0; j < NY; ++j) {
        printf("%d ", tab[i][j]);
    }
    printf("\n");
}
```

# Tableau à deux dimensions (4/4)

## Attention

* Les éléments ne sont **jamais** initialisés.
* Les bornes ne sont **jamais** vérifiées.

    ```C
    int tab[3][2] = { {1, 2}, {3, 4}, {5, 6} };
    printf("%d\n", tab[2][1]);  // affiche?
    printf("%d\n", tab[10][9]); // affiche?
    printf("%d\n", tab[3][1]);  // affiche?
    ```
    
# La couverture de la reine

* Aux échecs la reine peut se déplacer horizontalement et verticalement
* Pour un échiquier `5x6`, elle *couvre* les cases comme ci-dessous

+-----+-----+-----+-----+-----+-----+-----+
| ` ` | `0` | `1` | `2` | `3` | `4` | `5` |
+-----+-----+-----+-----+-----+-----+-----+
| `0` | `*` | ` ` | `*` | ` ` | `*` | ` ` |
+-----+-----+-----+-----+-----+-----+-----+
| `1` | ` ` | `*` | `*` | `*` | ` ` | ` ` |
+-----+-----+-----+-----+-----+-----+-----+
| `2` | `*` | `*` | `R` | `*` | `*` | `*` |
+-----+-----+-----+-----+-----+-----+-----+
| `3` | ` ` | `*` | `*` | `*` | ` ` | ` ` |
+-----+-----+-----+-----+-----+-----+-----+
| `4` | `*` | ` ` | `*` | ` ` | `*` | ` ` |
+-----+-----+-----+-----+-----+-----+-----+

## Exercice

* En utilisant les structures de contrôle, les tableaux à deux dimensions, et des
  `char` uniquement.
* Implémenter un programme qui, à partir des
  coordonnées de la reine, affiche un tableau comme ci-dessus pour un
  échiquier `8x8`.

## Poster le résultat sur `Element`

# Types énumérés (1/2)

* Un **type énuméré**: ensemble de *variantes* (valeurs constantes).
* En `C` les variantes sont des entiers numérotés à partir de 0.

    ```C
    enum days {
        monday, tuesday, wednesday,
        thursday, friday, saturday, sunday
    };
    ```
* On peut aussi donner des valeurs "custom"

    ```C
    enum days {
        monday = 2, tuesday = 8, wednesday = -2,
        thursday = 1, friday = 3, saturday = 12, sunday = 9
    };
    ```
* S'utilise comme un type standard et un entier

    ```C
    enum days d = monday;
    (d + 2) == monday + monday; // true
    ```

# Types énumérés (2/2)

* Très utile dans les `switch ... case`{.C}

    ```C
    enum days d = monday;
    switch (d) {
        case monday:
            // trucs
            break;
        case tuesday:
            printf("0 ou 1\n");
            break;
    }
    ```
* Le compilateur vous prévient qu'il en manque!

# Utilisation des types énumérés

## Réusiner votre couverture de la reine avec des `enum`

A faire à la maison comme exercice!

# Représentation des nombres (1/2)

* Le nombre `247`.

## Nombres décimaux: Les nombres en base 10 

+--------+--------+--------+
| $10^2$ | $10^1$ | $10^0$ |
+--------+--------+--------+
| `2`    | `4`    | `7`    |
+--------+--------+--------+

$$
247 = 2\cdot 10^2 + 4\cdot 10^1 + 7\cdot 10^0.
$$

# Représentation des nombres (2/2)

* Le nombre `11110111`.

## Nombres binaires: Les nombres en base 2

+-------+-------+-------+-------+-------+-------+-------+-------+
| $2^7$ | $2^6$ | $2^5$ | $2^4$ | $2^3$ | $2^2$ | $2^1$ | $2^0$ |
+-------+-------+-------+-------+-------+-------+-------+-------+
| `1`   | `1`   | `1`   | `1`   | `0`   | `1`   | `1`   | `1`   |
+-------+-------+-------+-------+-------+-------+-------+-------+
 
$$
1\cdot 2^7 + 1\cdot 2^6 +1\cdot 2^5 +1\cdot 2^4 +0\cdot 2^3 +1\cdot 2^2
+1\cdot 2^1 +1\cdot 2^0
$$

. . .

$$
= 247.
$$

# Conversion de décimal à binaire (1/2)

## Convertir 11 en binaire?

. . .

* On décompose en puissances de 2 en partant de la plus grande possible

    ```
    11 / 8 = 1, 11 % 8 = 3
    3  / 4 = 0,  3 % 4 = 3
    3  / 2 = 1,  3 % 2 = 1
    1  / 1 = 1,  1 % 1 = 0
    ```
* On a donc

    $$
    1011 \Rightarrow 1\cdot 2^3 + 0\cdot 2^2 + 1\cdot 2^1 + 1\cdot
    2^0=11.
    $$

# Conversion de décimal à binaire (2/2)

## Convertir un nombre arbitraire en binaire: 247?

* Par groupe établir un algorithme.

. . .

## Algorithme

1. Initialisation
    
    ```C
    num = 247
    N = 0

    tant que (2^(N+1) < num) {
        N += 1
    }
    ```

. . .

2. Boucle

    ```C
    tant que (N >= 0) {
        bit = num / 2^N
        num = num % 2^N
        N -= 1
    }
    ```

# Les additions en binaire

Que donne l'addition `1101` avec `0110`?

* L'addition est la même que dans le système décimal

    ```
       1101         8+4+0+1 = 13
    +  0110    +    0+4+2+0 =  6
    -------    -----------------
      10011      16+0+0+2+1 = 19
    ```
* Les entiers sur un ordinateur ont une précision **fixée** (ici 4 bits).
* Que se passe-t-il donc ici?

. . .

## Dépassement de capacité: le nombre est "tronqué"

* `10011 (19) -> 0011 (3)`.
* On fait "le tour"."

# Entier non-signés minimal/maximal

* Quel est l'entier non-signé maximal représentable avec 4 bit?

. . .

$$
(1111)_2 = 8+4+2+1 = 15
$$

* Quel est l'entier non-signé minimal représentable avec 4 bit?

. . .

$$
(0000)_2 = 0+0+0+0 = 0
$$

* Quel est l'entier non-signé min/max représentable avec N bit?

. . .

$$
0\mbox{ et  }2^N-1.
$$

* Donc `uint32_t?` maximal est?

. . .

$$
2^{32}-1=4'294'967'295
$$


# Les multiplications en binaire (1/2)

Que donne la multiplication de `1101` avec `0110`?

* La multiplication est la même que dans le système décimal

    ```
         1101                13
    *    0110    *            6
    ---------    --------------
         0000                78
        11010
       110100
    + 0000000
    ---------    --------------
      1001110    64+0+0+8+4+2+0
    ```

# Les multiplications en binaire (2/2)

## Que fait la multiplication par 2?

. . .

* Décalage de un bit vers la gauche!

    ```
         0110
    *    0010
    ---------
         0000
    +   01100
    ---------
        01100
    ```

. . .

## Que fait la multiplication par $2^N$?

. . .

* Décalage de $N$ bits vers la gauche!

# Entiers signés (1/2)

Pas de nombres négatifs encore...

## Comment faire?

. . .

## Solution naïve:

* On ajoute un bit de signe (le bit de poids fort):

    ```
    00000010: +2
    10000010: -2
    ```

## Problèmes?

. . .

* Il y a deux zéros (pas trop grave): `10000000` et `00000000`
* Les additions différentes que pour les non-signés (très grave)
    
    ```
      00000010              2    
    + 10000100           + -4
    ----------           ----
      10000110 = -6  !=    -2
    ```

# Entiers signés (2/2)

## Beaucoup mieux

* Complément à un:
    * on inverse tous les bits: `1001 => 0110`.

## Encore un peu mieux

* Complément à deux:
    * on inverse tous les bits,
    * on ajoute 1 (on ignore les dépassements).

. . .

* Comment écrit-on `-4` en 8 bits?

. . .

```
     4 =  00000100
            ________
    -4 =>   00000100
            
            11111011
          + 00000001 
          ----------
            11111100
```

# Le complément à 2 (1/2)

## Questions:

* Comment on écrit `+0` et `-0`?
* Comment calcule-t-on `2 + (-4)`?
* Quel est le complément à 2 de `1000 0000`?

. . .

## Réponses

* Comment on écrit `+0` et `-0`?

    ```
    +0 = 00000000
    -0 = 11111111 + 00000001 = 100000000 => 00000000 
    ```
* Comment calcule-t-on `2 + (-4)`?

    ```
      00000010            2
    + 11111100        +  -4
    ----------        -----
      11111110           -2
    ```
* En effet

    ```
    11111110 => 00000001 + 00000001 = 00000010 = 2.
    ```

# Le complément à 2 (2/2)

## Quels sont les entiers représentables en 8 bits?

. . .

```
01111111 =>  127
10000000 => -128 // par définition
```

## Quels sont les entiers représentables sur $N$ bits?

. . .

$$
-2^{N-1} ... 2^{N-1}-1.
$$

## Remarque: dépassement de capacité en `C`

* Comportement indéfini!

