Les matrices

Objectifs

Ce chapitre rappelle les acquis de 3ᵉ année sur les tableaux à deux dimensions, appelés couramment matrices.

À la fin de ce chapitre, l’élève doit être capable de :

• déclarer une matrice, en algorithmique et en Python ;
• choisir le parcours adapté au traitement demandé : toutes les cases, certaines cases, une zone, ou jusqu’à ce qu’une condition soit remplie ;
• délimiter une zone de la matrice, par une condition ou par les bornes des boucles ;
• remplir une matrice suivant un motif donné ;
• reconnaître, à la lecture d’un énoncé, le parcours qui convient.

Plan du chapitre

1. Structure
2. Parcours
3. Remplissages
4. Méthode
5. Retenons

1. Structure

1.1 Définition

Définition. Un tableau à deux dimensions, ou matrice, est un tableau dont les éléments, tous de même type, sont rangés en NL lignes et NC colonnes. Chaque élément est repéré par deux indices, le numéro de sa ligne i et le numéro de sa colonne j. On le note M[i, j].

Une matrice de NL lignes et NC colonnes contient NL × NC éléments.

Exemple. La matrice M suivante compte 5 lignes et 5 colonnes, soit 25 éléments. Elle sert d’exemple dans tout le chapitre.

La case colorée en orange est M[1, 2], qui vaut 7 : ligne 1, colonne 2. La case colorée en bleu est M[3, 1], qui vaut 11.

Remarque importante. Le premier indice est toujours celui de la ligne, le second celui de la colonne. Les indices commencent à 0 : la dernière ligne porte l’indice NL − 1, la dernière colonne l’indice NC − 1.

1.2 La matrice carrée

Définition. Une matrice est carrée lorsqu’elle a autant de lignes que de colonnes. Ce nombre commun, noté N, est appelé l’ordre de la matrice.

Une matrice carrée possède deux diagonales :

• la diagonale principale, du coin supérieur gauche au coin inférieur droit, formée des cases pour lesquelles i = j ;
• la diagonale secondaire, du coin supérieur droit au coin inférieur gauche, formée des cases pour lesquelles i + j = N − 1, c’est-à-dire j = N − 1 − i.

Les deux écritures de la diagonale secondaire servent à deux usages. La condition i + j = N - 1 permet de reconnaître une case de la diagonale au cours d’un parcours ; la formule j = N - 1 - i permet d’atteindre directement la case de la ligne i, M[i, N - 1 - i], sans parcourir la ligne.

Exemple. Sur la matrice M d’ordre 5, la diagonale principale est colorée en orange, la diagonale secondaire en bleu.

La diagonale principale contient 3, 2, 9, 6 et 7 ; la diagonale secondaire contient 4, 5, 9, 11 et 4. La case centrale, commune aux deux diagonales, est colorée en vert.

Remarque importante. Lorsque N est impair, les deux diagonales se croisent sur la case centrale M[N Div 2, N Div 2]. Ici, la case M[2, 2], qui vaut 9, appartient aux deux diagonales.

Les deux diagonales partagent la matrice en plusieurs zones : au-dessus, au-dessous, à gauche, à droite. Le paragraphe 2.3 montre comment ne parcourir que l’une d’elles.

1.3 Déclaration

En algorithmique

Une matrice se déclare de deux façons.

Première forme : directement dans le tableau de déclaration des objets :

Deuxième forme : on déclare d’abord un nouveau type, puis l’objet de ce type :

TDNT

TDO

Dès qu’une matrice est transmise à un module, la deuxième forme s’impose : l’en-tête du module doit nommer le type de son paramètre, par exemple Procédure Remplir (@M : Mat, NL, NC : Entier).

Remarque importante. La matrice est déclarée avec sa taille maximale, ici 20 lignes et 20 colonnes. Le nombre de lignes et de colonnes réellement utilisées, NL et NC, est saisi à l’exécution : tous les traitements portent sur les indices 0 à NL − 1 et 0 à NC − 1, jamais sur la taille déclarée.

En Python

Une matrice se représente par un tableau de la bibliothèque numpy, créé une fois NL et NC connus. On l’écrit array([[valeur] * NC] * NL) : une ligne de NC valeurs, répétée NL fois.

**Première forme : une valeur initiale, et la taille des chaînes précisée par dtype**

from numpy import array

M = array([[0] * NC] * NL)                    # entiers
R = array([[0.0] * NC] * NL)                  # réels
B = array([[False] * NC] * NL)                # booléens
C = array([[''] * NC] * NL, dtype='U1')       # caractères
S = array([[''] * NC] * NL, dtype='U20')      # chaînes de 20 caractères au plus

Deuxième forme : le nom du type

from numpy import array

M = array([[int()] * NC] * NL)                # entiers, initialisés à 0
R = array([[float()] * NC] * NL)              # réels, initialisés à 0.0
B = array([[bool()] * NC] * NL)               # booléens, initialisés à False
C = array([[str()] * NC] * NL)                # caractères, initialisés à ''
S = array([[str] * NC] * NL)                  # chaînes de longueur quelconque

Les deux formes sont correctes et figurent dans le document officiel d’implémentation en Python des conventions algorithmiques. L’élément de la ligne i et de la colonne j s’écrit M[i, j], comme en algorithmique.

Remarque importante. Pour une matrice de chaînes, il ne faut pas écrire array([[''] * NC] * NL) sans dtype : numpy réserve alors un seul caractère par case, et après S[0, 0] = "Tunis", la case contient "T". On précise dtype='U20', ou l’on utilise la forme array([[str] * NC] * NL).

2. Parcours

Une fois la matrice déclarée, tout traitement doit répondre à deux questions : quelles cases parcourir, et dans quel ordre. Cette partie traite la première question, la partie 3 la seconde.

2.1 Le parcours complet

Pour visiter toutes les cases, on imbrique deux boucles Pour : la boucle extérieure fait varier le numéro de ligne i, la boucle intérieure le numéro de colonne j. Pour chaque valeur de i, la boucle intérieure parcourt toute la ligne i : la matrice est parcourue ligne par ligne.

Ordre de visite d’une matrice de 3 lignes et 4 colonnes, parcourue ligne par ligne : chaque case porte son rang de visite.

Remplir une matrice

Procédure Remplir (@M : Mat, NL, NC : Entier)
DEBUT
    Pour i de 0 à NL - 1 Faire
        Pour j de 0 à NC - 1 Faire
            Écrire("M[", i, ", ", j, "] = ")
            Lire(M[i, j])
        Fin Pour
    Fin Pour
FIN

TDOL

Lorsque les valeurs saisies doivent respecter une condition, la lecture de chaque case devient une saisie contrôlée : Lire(M[i, j]) est placé dans une boucle Répéter … Jusqu'à condition.

Afficher une matrice

Procédure Afficher (M : Mat, NL, NC : Entier)
DEBUT
    Pour i de 0 à NL - 1 Faire
        Pour j de 0 à NC - 1 Faire
            Écrire(M[i, j], " ")
        Fin Pour
        Écrire_nl()
    Fin Pour
FIN

TDOL

Le passage à la ligne se place après la boucle intérieure : il sépare deux lignes de la matrice, et non deux éléments.

En Python

def Remplir(M, NL, NC):
    for i in range(NL):
        for j in range(NC):
            M[i, j] = int(input("M[" + str(i) + ", " + str(j) + "] = "))

def Afficher(M, NL, NC):
    for i in range(NL):
        for j in range(NC):
            print(M[i, j], end=" ")
        print()

Le parcours colonne par colonne

En échangeant les deux boucles, la boucle extérieure fait varier j et la boucle intérieure i : la matrice est parcourue colonne par colonne.

Pour j de 0 à NC - 1 Faire
    Pour i de 0 à NL - 1 Faire
        Traitement(M[i, j])
    Fin Pour
Fin Pour

Remarque importante. Échanger les boucles change l’ordre de visite, jamais l’écriture de la case : on écrit toujours M[i, j], la ligne en premier. Pour une somme ou un maximum, l’ordre est indifférent ; il ne compte que lorsque l’énoncé l’impose, par exemple pour remplir une matrice colonne après colonne.

2.2 Le parcours avec condition

Toutes les cases sont visitées, mais un Si placé dans la double boucle ne laisse passer que certaines d’entre elles. La condition peut porter sur la valeur de la case, ou sur sa position.

Condition sur la valeur : compter les éléments pairs

Fonction NbPairs (M : Mat, NL, NC : Entier) : Entier
DEBUT
    nb ← 0
    Pour i de 0 à NL - 1 Faire
        Pour j de 0 à NC - 1 Faire
            Si M[i, j] Mod 2 = 0 Alors
                nb ← nb + 1
            FinSi
        Fin Pour
    Fin Pour
    Retourner nb
FIN

TDOL

Sur la matrice M du paragraphe 1.1, cette fonction retourne 10.

Condition sur la position : les éléments au-dessus de la diagonale principale

Méthode 1 : par une condition.

Une case est située au-dessus de la diagonale principale lorsque son numéro de colonne dépasse son numéro de ligne : j > i.

Fonction SommeHaut (M : Mat, N : Entier) : Entier
DEBUT
    s ← 0
    Pour i de 0 à N - 1 Faire
        Pour j de 0 à N - 1 Faire
            Si j > i Alors
                s ← s + M[i, j]
            FinSi
        Fin Pour
    Fin Pour
    Retourner s
FIN

TDOL

Sur la matrice M, cette fonction retourne 60. Une seconde méthode, par les bornes des boucles, est présentée au paragraphe 2.3.

def NbPairs(M, NL, NC):
    nb = 0
    for i in range(NL):
        for j in range(NC):
            if M[i, j] % 2 == 0:
                nb = nb + 1
    return nb

def SommeHaut(M, N):
    s = 0
    for i in range(N):
        for j in range(N):
            if j > i:
                s = s + M[i, j]
    return s

Une condition sur la position délimite une partie de la matrice : une zone.

2.3 Le parcours d’une zone

Définition. Une zone est une partie de la matrice à laquelle un traitement s’intéresse. Elle se décrit de deux manières : par une condition portant sur les indices i et j de la case, testée à l’intérieur d’un parcours complet ; ou par les bornes des boucles, qui ne visitent alors que les cases utiles.

Le paragraphe 2.2 a utilisé la première manière. Celle-ci utilise la seconde.

Une ligne ou une colonne

Lorsque la ligne L est fixée, seul j varie : une seule boucle suffit. De même pour la colonne C, où seul i varie.

Pour j de 0 à NC - 1 Faire          Pour i de 0 à NL - 1 Faire
    Traitement(M[L, j])                 Traitement(M[i, C])
Fin Pour                            Fin Pour

Les diagonales

Sur une diagonale, la colonne se déduit de la ligne : j = i pour la diagonale principale, j = N - 1 - i pour la diagonale secondaire. Une seule boucle suffit, et l’on atteint directement la case utile.

Fonction Trace (M : Mat, N : Entier) : Entier
DEBUT
    s ← 0
    Pour i de 0 à N - 1 Faire
        s ← s + M[i, i]
    Fin Pour
    Retourner s
FIN

TDOL

Sur la matrice M, cette fonction retourne 27, la somme de la diagonale principale. Un parcours complet avec la condition j = i donnerait le même résultat, mais en visitant 25 cases au lieu de 5.

Les triangles

Les triangles sont délimités par une diagonale. Pour chaque ligne i, les bornes de la boucle sur j s’arrêtent sur cette diagonale.

Pour exclure la diagonale, on décale la borne d’une case : au-dessus de la diagonale principale, sans elle, s’écrit Pour j de i + 1 à N - 1.

Méthode 2 : par les bornes. La fonction SommeHaut du paragraphe 2.2 s’écrit :

Fonction SommeHaut (M : Mat, N : Entier) : Entier
DEBUT
    s ← 0
    Pour i de 0 à N - 1 Faire
        Pour j de i + 1 à N - 1 Faire
            s ← s + M[i, j]
        Fin Pour
    Fin Pour
    Retourner s
FIN

TDOL

Elle retourne le même résultat, 60, sans aucun test : les cases hors de la zone ne sont jamais visitées.

Remarque importante. Les deux manières sont correctes. La condition est plus facile à trouver, puisqu’elle se lit sur le schéma ; les bornes évitent de visiter les cases inutiles. Pour trouver les bornes, on regarde une ligne i quelconque et l’on se demande : sur quelle colonne la zone commence-t-elle, sur quelle colonne finit-elle ?

La pyramide : une zone délimitée par deux diagonales

On veut remplir par 1, 2, 3, … une pyramide de N lignes, dans une matrice de N lignes et 2N − 1 colonnes. Pour N = 4 :

La matrice de 2N − 1 colonnes est formée de deux matrices carrées d’ordre N, qui partagent la colonne du milieu, d’indice N − 1.

• Le bord gauche de la pyramide est la diagonale secondaire du premier carré (colonnes 0 à N − 1) : j = N - 1 - i, en orange.
• Le bord droit est la diagonale principale du second carré (colonnes N − 1 à 2N − 2), décalée de N − 1 colonnes : j = N - 1 + i, en bleu.

La ligne i de la pyramide va donc de la colonne N - 1 - i à la colonne N - 1 + i.

Procédure Pyramide (@M : Mat, N : Entier)
DEBUT
    x ← 1
    Pour i de 0 à N - 1 Faire
        Pour j de N - 1 - i à N - 1 + i Faire
            M[i, j] ← x
            x ← x + 1
        Fin Pour
    Fin Pour
FIN

TDOL

def Pyramide(M, N):
    x = 1
    for i in range(N):
        for j in range(N - 1 - i, N + i):
            M[i, j] = x
            x = x + 1

2.4 Le parcours avec arrêt

Certains traitements n’ont pas besoin de visiter toutes les cases : ils s’arrêtent dès que la réponse est connue. Deux questions reviennent sans cesse :

Le nombre de cases à visiter n’est pas connu à l’avance : le traitement peut s’arrêter à n’importe quelle case. C’est pourquoi on utilise Tant que, et non Pour. Le drapeau mémorise ce que l’on a découvert ; il figure dans la condition de la boucle.

Sur une ligne : une seule boucle

Fonction RechercheLigne (M : Mat, NC, L, X : Entier) : Booléen
DEBUT
    Trouve ← Faux
    j ← 0
    Tant que (j < NC) Et Non(Trouve) Faire
        Si M[L, j] = X Alors
            Trouve ← Vrai
        Sinon
            j ← j + 1
        FinSi
    Fin Tant que
    Retourner Trouve
FIN

TDOL

La vérification a la même charpente ; seuls le drapeau et le test s’inversent. La ligne L est croissante si chaque élément est inférieur ou égal au suivant :

Fonction LigneCroissante (M : Mat, NC, L : Entier) : Booléen
DEBUT
    ok ← Vrai
    j ← 0
    Tant que (j < NC - 1) Et ok Faire
        Si M[L, j] > M[L, j + 1] Alors
            ok ← Faux
        Sinon
            j ← j + 1
        FinSi
    Fin Tant que
    Retourner ok
FIN

TDOL

Sur la matrice M, la ligne 2 (1, 4, 9, 3, 8) n’est pas croissante : la boucle s’arrête dès la comparaison de 9 et de 3.

Sur toute la matrice : deux boucles

Sur la matrice entière, les deux boucles deviennent des Tant que, et le drapeau figure dans les deux conditions : dès qu’il change, la boucle intérieure s’arrête, puis la boucle extérieure.

Fonction Recherche (M : Mat, NL, NC, X : Entier) : Booléen
DEBUT
    Trouve ← Faux
    i ← 0
    Tant que (i < NL) Et Non(Trouve) Faire
        j ← 0
        Tant que (j < NC) Et Non(Trouve) Faire
            Si M[i, j] = X Alors
                Trouve ← Vrai
            Sinon
                j ← j + 1
            FinSi
        Fin Tant que
        i ← i + 1
    Fin Tant que
    Retourner Trouve
FIN

TDOL

Remarque importante. L’instruction j ← 0 se place à l’intérieur de la boucle extérieure, juste avant la boucle intérieure. Placée avant la boucle extérieure, elle ne serait exécutée qu’une fois : dès la deuxième ligne, j vaudrait déjà NC, et seule la première ligne serait parcourue.

Application : la matrice symétrique. Une matrice carrée est symétrique lorsque M[i, j] = M[j, i] pour toutes ses cases. Il suffit de vérifier les cases situées au-dessus de la diagonale principale : chacune est comparée à sa symétrique, et la diagonale est toujours égale à elle-même. La vérification combine donc une zone, par les bornes, et un arrêt.

Fonction Symetrique (M : Mat, N : Entier) : Booléen
DEBUT
    ok ← Vrai
    i ← 0
    Tant que (i < N - 1) Et ok Faire
        j ← i + 1
        Tant que (j < N) Et ok Faire
            Si M[i, j] ≠ M[j, i] Alors
                ok ← Faux
            Sinon
                j ← j + 1
            FinSi
        Fin Tant que
        i ← i + 1
    Fin Tant que
    Retourner ok
FIN

TDOL

La matrice S est symétrique : chaque case orange est égale à la case bleue qui lui correspond de l’autre côté de la diagonale. La matrice M du paragraphe 1.1 ne l’est pas, et la fonction s’arrête dès la première comparaison : M[0, 1] = 8 alors que M[1, 0] = 6.

def Recherche(M, NL, NC, X):
    Trouve = False
    i = 0
    while (i < NL) and not (Trouve):
        j = 0
        while (j < NC) and not (Trouve):
            if M[i, j] == X:
                Trouve = True
            else:
                j = j + 1
        i = i + 1
    return Trouve

def Symetrique(M, N):
    ok = True
    i = 0
    while (i < N - 1) and ok:
        j = i + 1
        while (j < N) and ok:
            if M[i, j] != M[j, i]:
                ok = False
            else:
                j = j + 1
        i = i + 1
    return ok

2.5 Le parcours par indice linéaire

Parcourue ligne par ligne, une matrice de NL lignes et NC colonnes se lit comme une suite de NL × NC éléments. Chaque case reçoit alors un rang k, de 0 à NL × NC − 1.

Transférer une matrice dans un tableau : le compteur k

La méthode la plus directe fait avancer un compteur k à chaque case visitée.

Procédure Transferer (M : Mat, NL, NC : Entier, @T : Tab)
DEBUT
    k ← 0
    Pour i de 0 à NL - 1 Faire
        Pour j de 0 à NC - 1 Faire
            T[k] ← M[i, j]
            k ← k + 1
        Fin Pour
    Fin Pour
FIN

TDOL

La formule de l’indice linéaire

Le rang d’une case se calcule sans compteur. Avant la ligne i, on a parcouru i lignes complètes, soit i * NC cases ; dans la ligne i, la case est la j-ième. D’où, dans les deux sens :

Indice linéaire. k = i * NC + j, et réciproquement i = k Div NC et j = k Mod NC.

Exemple. Dans la matrice M, où NC = 5, la case M[3, 1], qui vaut 11, a pour rang k = 3 * 5 + 1 = 16. Réciproquement, pour k = 16 : 16 Div 5 = 3 et 16 Mod 5 = 1.

Le transfert s’écrit alors avec une seule instruction dans la double boucle : T[i * NC + j] ← M[i, j].

Application : trier toute une matrice

On veut trier une matrice dans l’ordre croissant, de sorte qu’une lecture ligne par ligne donne une suite croissante. Trier chaque ligne séparément ne suffit pas : le dernier élément d’une ligne pourrait dépasser le premier de la suivante. Deux méthodes existent.

Méthode 1 : par un tableau. On procède en trois temps :

1. transférer la matrice dans un tableau T ;
2. trier le tableau T, avec l’un des tris déjà étudiés ;
3. replacer le tableau dans la matrice, dans le même ordre.

TDNT

Procédure TrierMatrice (@M : Mat, NL, NC : Entier)
DEBUT
    Transferer(M, NL, NC, T)
    Tri_Bulles(T, NL * NC)
    Replacer(T, NL, NC, M)
FIN

TDOL

Procédure Replacer (T : Tab, NL, NC : Entier, @M : Mat)
DEBUT
    k ← 0
    Pour i de 0 à NL - 1 Faire
        Pour j de 0 à NC - 1 Faire
            M[i, j] ← T[k]
            k ← k + 1
        Fin Pour
    Fin Pour
FIN

TDOL

Le tableau T compte 400 éléments : c’est le nombre maximal de cases d’une matrice de 20 lignes et 20 colonnes. La procédure Tri_Bulles est le tri à bulles déjà étudié ; tout autre tri convient.

def Transferer(M, NL, NC, T):
    k = 0
    for i in range(NL):
        for j in range(NC):
            T[k] = M[i, j]
            k = k + 1

def Replacer(T, NL, NC, M):
    k = 0
    for i in range(NL):
        for j in range(NC):
            M[i, j] = T[k]
            k = k + 1

def TrierMatrice(M, NL, NC):
    T = array([0] * (NL * NC))
    Transferer(M, NL, NC, T)
    Tri_Bulles(T, NL * NC)
    Replacer(T, NL, NC, M)

Sur la matrice M, la matrice triée commence par 1, 1, 1, 2, 2 sur la première ligne et se termine par 9, 9, 9, 10, 11 sur la dernière.

Cette méthode en trois temps est la plus longue, mais chaque étape réemploie un module connu : c’est elle qu’il faut maîtriser d’abord.

Méthode 2 : le tri sur place. La formule de l’indice linéaire permet de trier la matrice directement, sans tableau intermédiaire. On reprend le tri à bulles d’un tableau de NL × NC éléments, et l’on remplace chaque élément de rang k par la case correspondante de la matrice. Pour alléger l’écriture, on calcule d’abord les coordonnées des deux cases comparées : (l1, c1) pour le rang k, (l2, c2) pour le rang k + 1.

Procédure TrierMatrice (@M : Mat, NL, NC : Entier)
DEBUT
    nb ← NL * NC
    Répéter
        Permut ← Faux
        Pour k de 0 à nb - 2 Faire
            l1 ← k Div NC
            c1 ← k Mod NC
            l2 ← (k + 1) Div NC
            c2 ← (k + 1) Mod NC
            Si M[l1, c1] > M[l2, c2] Alors
                aux ← M[l1, c1]
                M[l1, c1] ← M[l2, c2]
                M[l2, c2] ← aux
                Permut ← Vrai
            FinSi
        Fin Pour
        nb ← nb - 1
    Jusqu'à Non(Permut) Ou (nb = 1)
FIN

TDOL

def TrierMatrice(M, NL, NC):
    nb = NL * NC
    Permut = True
    while Permut and nb > 1:
        Permut = False
        for k in range(nb - 1):
            l1 = k // NC
            c1 = k % NC
            l2 = (k + 1) // NC
            c2 = (k + 1) % NC
            if M[l1, c1] > M[l2, c2]:
                aux = M[l1, c1]
                M[l1, c1] = M[l2, c2]
                M[l2, c2] = aux
                Permut = True
        nb = nb - 1

Les deux méthodes donnent la même matrice triée.

Remarque importante. Dans le tri à bulles de référence, la variable qui compte les éléments restant à trier s’appelle NC. Ici, ce nom est déjà pris par le nombre de colonnes : on l’appelle nb. Confondre les deux fausserait toutes les divisions k Div NC dès la deuxième passe.

3. Remplissages

Dans la partie 2, l’ordre de visite était toujours l’ordre naturel, ligne par ligne, et seul changeait l’ensemble des cases visitées. Ici, toutes les cases sont remplies, mais dans un ordre imposé par un motif. La difficulté n’est plus de délimiter une zone : elle est de faire varier les indices dans le bon sens.

Deux principes suffisent :

• une boucle peut parcourir ses indices dans le sens décroissant : Pour j de N - 1 à 0 [Pas = -1] Faire ;
• une valeur qui augmente d’une case à la suivante se range dans un compteur x, initialisé une fois pour toutes avant les boucles.

Serpentin

On veut remplir une matrice carrée M d’ordre N par les entiers de 1 à N × N, ligne par ligne, en changeant de sens à chaque ligne : les lignes de numéro pair se remplissent de gauche à droite, les lignes de numéro impair de droite à gauche.

Exemple. Pour N = 5 :

En effet, la ligne 0 reçoit 1 à 5 de gauche à droite ; la ligne 1, colorée, reçoit 6 à 10 de droite à gauche, si bien que 6 se trouve dans la colonne 4 et 10 dans la colonne 0.

Travail demandé

1. Écrire l’algorithme de la procédure Serpentin(M, N) qui remplit la matrice M d’ordre N selon ce motif.

N.B. N est un entier déjà saisi dans le programme appelant, tel que 2 ≤ N ≤ 20.

Procédure Serpentin (@M : Mat, N : Entier)
DEBUT
    x ← 1
    Pour i de 0 à N - 1 Faire
        Si i Mod 2 = 0 Alors
            Pour j de 0 à N - 1 Faire
                M[i, j] ← x
                x ← x + 1
            Fin Pour
        Sinon
            Pour j de N - 1 à 0 [Pas = -1] Faire
                M[i, j] ← x
                x ← x + 1
            Fin Pour
        FinSi
    Fin Pour
FIN

def Serpentin(M, N):
    x = 1
    for i in range(N):
        if i % 2 == 0:
            for j in range(N):
                M[i, j] = x
                x = x + 1
        else:
            for j in range(N - 1, -1, -1):
                M[i, j] = x
                x = x + 1

Spirale

On veut remplir une matrice carrée M d’ordre N par les entiers de 1 à N × N, en spirale : on part de la case M[0, 0], on tourne dans le sens des aiguilles d’une montre le long des bords, puis on recommence un tour plus à l’intérieur, jusqu’au centre.

Exemple. Pour N = 5 :

En effet, le premier tour, coloré en orange, parcourt les bords de 1 à 16 ; le deuxième tour parcourt les cases de 17 à 24 ; le troisième se réduit à la case centrale, en bleu, qui reçoit 25.

Travail demandé

1. Combien de tours faut-il pour remplir une matrice d’ordre N ? Vérifier la réponse pour N = 4 et pour N = 5.
2. Écrire l’algorithme de la procédure Spirale(M, N) qui remplit la matrice M d’ordre N selon ce motif.

N.B. N est un entier déjà saisi dans le programme appelant, tel que 2 ≤ N ≤ 20.

Procédure Spirale (@M : Mat, N : Entier)
DEBUT
    x ← 1
    Pour c de 0 à (N + 1) Div 2 - 1 Faire
        f ← N - 1 - c
        Pour j de c à f Faire
            M[c, j] ← x
            x ← x + 1
        Fin Pour
        Pour i de c + 1 à f - 1 Faire
            M[i, f] ← x
            x ← x + 1
        Fin Pour
        Si c < f Alors
            Pour j de f à c [Pas = -1] Faire
                M[f, j] ← x
                x ← x + 1
            Fin Pour
            Pour i de f - 1 à c + 1 [Pas = -1] Faire
                M[i, c] ← x
                x ← x + 1
            Fin Pour
        FinSi
    Fin Pour
FIN

def Spirale(M, N):
    x = 1
    for c in range((N + 1) // 2):
        f = N - 1 - c
        for j in range(c, f + 1):
            M[c, j] = x
            x = x + 1
        for i in range(c + 1, f):
            M[i, f] = x
            x = x + 1
        if c < f:
            for j in range(f, c - 1, -1):
                M[f, j] = x
                x = x + 1
            for i in range(f - 1, c, -1):
                M[i, c] = x
                x = x + 1

Procédure Spirale (@M : Mat, N : Entier)
DEBUT
    x ← 1
    deb ← 0
    fin ← N - 1
    Tant que deb ≤ fin Faire
        Pour j de deb à fin Faire
            M[deb, j] ← x
            x ← x + 1
        Fin Pour
        Pour i de deb + 1 à fin - 1 Faire
            M[i, fin] ← x
            x ← x + 1
        Fin Pour
        Si deb < fin Alors
            Pour j de fin à deb [Pas = -1] Faire
                M[fin, j] ← x
                x ← x + 1
            Fin Pour
            Pour i de fin - 1 à deb + 1 [Pas = -1] Faire
                M[i, deb] ← x
                x ← x + 1
            Fin Pour
        FinSi
        deb ← deb + 1
        fin ← fin - 1
    Fin Tant que
FIN

def Spirale(M, N):
    x = 1
    deb = 0
    fin = N - 1
    while deb <= fin:
        for j in range(deb, fin + 1):
            M[deb, j] = x
            x = x + 1
        for i in range(deb + 1, fin):
            M[i, fin] = x
            x = x + 1
        if deb < fin:
            for j in range(fin, deb - 1, -1):
                M[fin, j] = x
                x = x + 1
            for i in range(fin - 1, deb, -1):
                M[i, deb] = x
                x = x + 1
        deb = deb + 1
        fin = fin - 1

4. Méthode

Devant un énoncé, la première question n’est pas « quel algorithme écrire ? », mais « quelles cases faut-il parcourir ? ». Certains mots de l’énoncé désignent presque toujours le même schéma.

Remarque importante. Ce tableau ne donne aucun algorithme : il indique la charpente. Le traitement placé à l’intérieur — une somme, un comptage, une comparaison — reste à écrire à chaque fois.

Relevé de notes

Un professeur range les notes de sa classe dans une matrice M de NL lignes et NC colonnes : la ligne i correspond à l’élève i, la colonne j à la matière j. Toutes les matières ont le même coefficient.

• NL est un entier tel que 2 ≤ NL ≤ 40, nombre maximal d’élèves d’une classe.
• NC est un entier tel que 2 ≤ NC ≤ 10.
• Une note est un réel de l’intervalle [0, 20].

Exemple. Pour NL = 6 et NC = 4 :

En effet :

• six notes sont strictement inférieures à 10 : 6.5, 6.5, 9.5, 8, 9.5 et 7 ;
• les moyennes des six élèves sont 11.5, 16.5, 10, 13, 11 et 13 ; par exemple, pour l’élève 1 : (17 + 14 + 20 + 15) / 4 = 16.5 ;
• la meilleure note de chaque matière est 17, 18, 20 et 16 ;
• la plus petite note, 6.5, apparaît en M[0, 1] et en M[2, 0] ; la première rencontrée dans un parcours ligne par ligne est M[0, 1] ;
• les élèves 1 et 3 ont obtenu au moins 10 dans toutes les matières ;
• la note 20 a été attribuée, la note 19 ne l’a pas été.

Travail demandé

1. Écrire l’algorithme de la procédure Remplir(M, NL, NC) qui remplit la matrice M par les notes de la classe.
2. Écrire l’algorithme de la fonction NbInferieures(M, NL, NC) qui retourne le nombre de notes strictement inférieures à 10.
3. Écrire l’algorithme de la fonction MoyenneEleve(M, NC, i) qui retourne la moyenne de l’élève i.
4. En faisant appel à la fonction MoyenneEleve, écrire l’algorithme de la procédure RemplirMoy(M, NL, NC, Moy) qui remplit un tableau Moy de NL réels par les moyennes des élèves.
5. Écrire l’algorithme de la fonction MeilleureNote(M, NL, j) qui retourne la meilleure note de la matière j.
6. Écrire l’algorithme de la procédure PlusPetite(M, NL, NC, L, C) qui détermine la ligne L et la colonne C de la plus petite note de la matrice. Si cette note apparaît plusieurs fois, on retient la première rencontrée dans un parcours ligne par ligne.
7. Écrire l’algorithme de la fonction ToutesValidees(M, NC, i) qui vérifie si l’élève i a obtenu au moins 10 dans toutes les matières.
8. Écrire l’algorithme de la fonction Existe(M, NL, NC, x) qui vérifie si la note x a été attribuée à au moins un élève.

N.B. NL et NC sont déjà saisis dans le programme appelant. Le candidat n’est pas appelé à déclarer les nouveaux types.

Procédure Remplir (@M : Mat, NL, NC : Entier)
DEBUT
    Pour i de 0 à NL - 1 Faire
        Pour j de 0 à NC - 1 Faire
            Répéter
                Écrire("Note de l'élève ", i, ", matière ", j, " : ")
                Lire(M[i, j])
            Jusqu'à (M[i, j] ≥ 0) Et (M[i, j] ≤ 20)
        Fin Pour
    Fin Pour
FIN

def Remplir(M, NL, NC):
    for i in range(NL):
        for j in range(NC):
            M[i, j] = float(input("Note " + str(i) + ", " + str(j) + " : "))
            while not (0 <= M[i, j] <= 20):
                M[i, j] = float(input("Note " + str(i) + ", " + str(j) + " : "))

Fonction NbInferieures (M : Mat, NL, NC : Entier) : Entier
DEBUT
    nb ← 0
    Pour i de 0 à NL - 1 Faire
        Pour j de 0 à NC - 1 Faire
            Si M[i, j] < 10 Alors
                nb ← nb + 1
            FinSi
        Fin Pour
    Fin Pour
    Retourner nb
FIN

def NbInferieures(M, NL, NC):
    nb = 0
    for i in range(NL):
        for j in range(NC):
            if M[i, j] < 10:
                nb = nb + 1
    return nb

Fonction MoyenneEleve (M : Mat, NC, i : Entier) : Réel
DEBUT
    s ← 0
    Pour j de 0 à NC - 1 Faire
        s ← s + M[i, j]
    Fin Pour
    Retourner s / NC
FIN

def MoyenneEleve(M, NC, i):
    s = 0
    for j in range(NC):
        s = s + M[i, j]
    return s / NC

Procédure RemplirMoy (M : Mat, NL, NC : Entier, @Moy : Tab)
DEBUT
    Pour i de 0 à NL - 1 Faire
        Moy[i] ← MoyenneEleve(M, NC, i)
    Fin Pour
FIN

def RemplirMoy(M, NL, NC, Moy):
    for i in range(NL):
        Moy[i] = MoyenneEleve(M, NC, i)

Fonction MeilleureNote (M : Mat, NL, j : Entier) : Réel
DEBUT
    max ← M[0, j]
    Pour i de 1 à NL - 1 Faire
        Si M[i, j] > max Alors
            max ← M[i, j]
        FinSi
    Fin Pour
    Retourner max
FIN

def MeilleureNote(M, NL, j):
    Max = M[0, j]
    for i in range(1, NL):
        if M[i, j] > Max:
            Max = M[i, j]
    return Max

Procédure PlusPetite (M : Mat, NL, NC : Entier, @L, @C : Entier)
DEBUT
    L ← 0
    C ← 0
    Pour i de 0 à NL - 1 Faire
        Pour j de 0 à NC - 1 Faire
            Si M[i, j] < M[L, C] Alors
                L ← i
                C ← j
            FinSi
        Fin Pour
    Fin Pour
FIN

def PlusPetite(M, NL, NC):
    global L, C
    L = 0
    C = 0
    for i in range(NL):
        for j in range(NC):
            if M[i, j] < M[L, C]:
                L = i
                C = j

Fonction ToutesValidees (M : Mat, NC, i : Entier) : Booléen
DEBUT
    ok ← Vrai
    j ← 0
    Tant que (j < NC) Et ok Faire
        Si M[i, j] < 10 Alors
            ok ← Faux
        Sinon
            j ← j + 1
        FinSi
    Fin Tant que
    Retourner ok
FIN

def ToutesValidees(M, NC, i):
    ok = True
    j = 0
    while (j < NC) and ok:
        if M[i, j] < 10:
            ok = False
        else:
            j = j + 1
    return ok

Fonction Existe (M : Mat, NL, NC : Entier, x : Réel) : Booléen
DEBUT
    Trouve ← Faux
    i ← 0
    Tant que (i < NL) Et Non(Trouve) Faire
        j ← 0
        Tant que (j < NC) Et Non(Trouve) Faire
            Si M[i, j] = x Alors
                Trouve ← Vrai
            Sinon
                j ← j + 1
            FinSi
        Fin Tant que
        i ← i + 1
    Fin Tant que
    Retourner Trouve
FIN

def Existe(M, NL, NC, x):
    Trouve = False
    i = 0
    while (i < NL) and not (Trouve):
        j = 0
        while (j < NC) and not (Trouve):
            if M[i, j] == x:
                Trouve = True
            else:
                j = j + 1
        i = i + 1
    return Trouve

5. Retenons

Matrice. Un tableau à deux dimensions, ou matrice, range des éléments de même type en NL lignes et NC colonnes. La case de la ligne i et de la colonne j se note M[i, j] ; les indices commencent à 0.

Matrice carrée. La diagonale principale est formée des cases où i = j, la diagonale secondaire des cases où i + j = N - 1, c’est-à-dire j = N - 1 - i.

Déclaration. En algorithmique, Tableau de NL lignes * NC colonnes Type_élément, avec un nouveau type dès que la matrice est transmise à un module. En Python, array([[valeur] * NC] * NL), avec dtype pour les chaînes.

Quelles cases ? Toutes : deux Pour. Certaines : un Si dans les deux Pour, ou des bornes qui délimitent la zone. Jusqu’à la réponse : Tant que et un drapeau.

Dans quel ordre ? Ligne par ligne par défaut. Un motif impose un autre ordre : bornes décroissantes, compteur initialisé une seule fois.

Indice linéaire. k = i * NC + j, et réciproquement i = k Div NC, j = k Mod NC.

Teste tes connaissances

Un quiz corrigé question par question, puis des flashcards pour mémoriser les notions du chapitre.