Les tableaux deux dimensions.
Présentation
Un tableau (en python une liste) peut contenir des tableaux (en python une liste peut tout contenir c'est moins vrai des tableaux en C qui doivent contenir des éléments de même type) si chaque tableaux contenus à la même taille alors on parle de tableau deux dimensions . En mathématiques on utilise un objet pouvant naturellement être représenté par un tableau deux dimensions : les matrices . A tort peut être, je vais par la suite appelé matrice un tableau deux dimensions.
Les tableaux en deux dimensions sont utilisées pour modéliser des objets "plats", par exemple des images, une carte, un jeu en "2D" (tetris, puissance4 , sudoku, echecs ...). En mathématiques une matrice est utilisé par exemple pour modéliser des transformations géométriques, pour résoudre des systèmes d'équations à plusieurs inconnues, comme "nombre dérivé" pour des fonctions de plusieurs paramètres et d'image dans un espace en plusieurs dimensions. On peut aussi représenter un réseau social, une planification,.. l'usage est énorme et donc ce genre de tableau est très courant.
Exemple
Considérons l = [ [1,2],[3,4],[5,6],[7,8]], généralement la matrice se présente de la façon suivante :
Une matrice 4×2 :
1 2
3 4
5 6
7 8
Considérons l = [ [1,2,3] , [4,5,6] , [7,8,9] , [10,11,12] ] généralement la matrice se présente de la façon suivante :
Une matrice 4×3 :
1 2 3
4 5 6
7 8 9
10 11 12
Pour avoir un élément on utilise l[ligne][colonne].
Considérons l = [ [1,2,3] , [4,5,6] , [7,8,9] ] le nombre de lignes est égal au nombre des colonnes, on dit qu'on a une matrice carré :
Une matrice carré de taille 3 :
1 2 3
4 5 6
7 8 9
Pour avoir un élément on utilise l[ligne][colonne].
Q.C.M.
Si m = [[0,1,2,3],[4,5,6,7],[8,9,10,11]], alors :
Le nombre de ligne est 4. Le nombre de ligne est 3. le nombre de colonnes est 3. le nombre de colonnes est 4. Q.C.M.
Si m = [[0,1,2,3],[4,5,6,7],[8,9,10,11]], alors quelles expressions sont égales à 3 ? :
m[1][4] m[0][3] m[3] m[-3][-1] Q.C.M.
Si m est un tableau deux dimensions.
len(m) est le nombre de ligne. len(m) est le nombre de colonnes. len(m[0]) est le nombre de colonnes. len(m[0]) est le nombre de lignes. Q.C.M.
On reprèsente un tableau deux dimensions suivant la représentation matricielle (la ligne 0 est en haut), on reprèsente ci-dessous un petite partie du tableau :
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Si la case rouge est à la ligne i et à la colonne j alors la colonne bleu est :
à la ligne i + 3 et à la colonne j + 2 à la ligne i + 2 et à la colonne j + 3 à la ligne i -3 et à la colonne j - 2 à la ligne i - 3 et à la colonne j + 2 Exercices
Entrer en Python les matrices suivantes :
0 5 10 15 1 6 11 16 2 7 12 17 3 8 13 18 4 9 14 19
Pour les matrice au dessus, donner le nombre de lignes et le nombre de colonnes.
Algorithme
Souvent résoudre informatiquement des problèmes portant sur des matrices vont conduire à avoir des boucles imbriquées. Comme nous le verrons plus tard cela va entraîner que doubler la taille des lignes et des colonnes va entraîner un quadruplement des temps de calculs.
L'idée est dans un premier temps de parcourir la tableau ligne par ligne, et pour une ligne donnée de parcourir les colonnes une par une.
Exemple
De nombreux problèmes vont aboutir à un programme proche de celui ci dessous :
Comme vous le voyez le résultat est assez proche du problème d'un tableau classique il faut juste ajouter une boucle en plus une case est définie par deux paramètres.
Parfois une boucle unique suffit cependant, par exemple si on veut compter la somme d'une colonne donnée :
Exercices
Dans toutes les questions ci dessous, faire une fonction de tests.
Faire une fonction remplir(mat,nombre) qui va placer nombre dans toutes les cases du tableau en deux dimensions ( = matrice).
Faire une fonction absolue_matrice(mat) qui va appliquer la valeur absolue (en simplifiant : rendre positif) tous les nombres de la matrice.
Faire une fonction somme_totale(mat) qui va additionner toutes les cases de la matrice.
Faire une fonction qui vérifie qu'un tableau donné est bien en deux dimensions (il faut vérifier que toutes les lignes ont la même taille), la fonction retourne True ou False.
Faire une fonction qui vérifie qu'un tableau donné est carré (Le nombre de lignes est égal au nombre de colonnes).
Faire une fonction qui pour une matrice carré va retourner la somme des cases de la diagonale.
0 5 10 15 1 6 11 16 2 7 12 17 3 8 13 18
Faire une fonction qui pour une matrice donnée retourne le plus grand nombre de ses cases.
Faire une fonction qui va retourner l'indice de la ligne qui est la plus grande (c'est à dire où la somme des éléments est la plus grande), donner la première ligne si il existe des ex aequo.
Projet
Nous allons réaliser un puissance 4 basique (mode console à deux joueurs). On modélise la grille par une matrice 6×7 où une case vaut 0, 1 ou 2. O signifie case vide, 1 la case est au joueur 1 et 2 la case est au joueur 2. Par exemple la grille suivante :
sera modélisée par la grille (vous remarquez que par rapport à la représentation mathématique l'ordre des lignes est inversé).
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 0 0 0 0 0 0 0 Ligne 4 0 0 0 0 0 0 0 Ligne 3 0 0 2 0 0 0 0 Ligne 2 0 0 1 2 1 0 0 Ligne 1 0 2 1 1 2 0 0 Ligne 0 1 2 2 2 1 1 0
Pour cela il faut compléter les fonctions du fichier suivants :
Fichier à compléter verifie_ligne(matrice,ligne_debut,colonne_debut)
verifie_ligne(matrice,ligne_debut,colonne_debut) doit vérifier si la suite des 4 cases en ligne qui commence à la colonne donnée comportent des jetons identiques et de valeurs 1 ou 2. Si c'est le cas elle doit retourner la valeur en question, sinon elle doit retourner 0.
Exemple
verifie_ligne(matrice,0,0) doit retourner 1.
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 0 0 0 0 0 0 0 Ligne 4 0 0 0 0 0 0 0 Ligne 3 0 0 2 0 0 0 0 Ligne 2 0 0 1 2 1 0 0 Ligne 1 0 2 2 1 2 0 0 Ligne 0 1 1 1 1 2 1 0
verifie_ligne(matrice,0,1) doit retourner 0.
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 0 0 0 0 0 0 0 Ligne 4 0 0 0 0 0 0 0 Ligne 3 0 0 2 0 0 0 0 Ligne 2 0 0 1 2 1 0 0 Ligne 1 0 2 2 1 2 0 0 Ligne 0 1 1 1 1 2 1 0
verifie_ligne(matrice,1,1) doit retourner 0.
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 0 0 0 0 0 0 0 Ligne 4 0 0 0 0 0 0 0 Ligne 3 0 0 2 0 0 0 0 Ligne 2 0 0 1 2 1 0 0 Ligne 1 0 2 2 1 2 0 0 Ligne 0 1 1 1 1 2 1 0
verifie_colonne(matrice,ligne_debut,colonne_debut)
verifie_colonne(matrice,ligne_debut,colonne_debut) doit vérifier si la suite des 4 cases en colonne qui commence à la ligne donnée comportent des jetons identiques et de valeurs 1 ou 2. Si c'est le cas elle doit retourner la valeur en question, sinon elle doit retourner 0.
Exemple
verifie_colonne(matrice,1,2) doit retourner 2.
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 0 0 0 0 0 0 0 Ligne 4 0 0 2 0 0 0 0 Ligne 3 0 0 2 0 0 0 0 Ligne 2 0 0 2 2 1 0 0 Ligne 1 0 0 2 1 2 0 0 Ligne 0 1 2 1 1 1 1 0
verifie_colonne(matrice,0,3) doit retourner 0.
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 0 0 0 0 0 0 0 Ligne 4 0 0 0 1 0 0 0 Ligne 3 0 0 0 1 0 0 0 Ligne 2 0 0 2 2 1 0 0 Ligne 1 0 2 1 1 2 0 0 Ligne 0 0 1 2 2 1 0 0
verifie_diagonale_monte(matrice,ligne_debut,colonne_debut)
verifie_diagonale_monte(matrice,ligne_debut,colonne_debut) doit vérifier si la suite des 4 cases en diagonale montante qui commence à la ligne donnée et colonne donnée comportent des jetons identiques et de valeurs 1 ou 2. Si c'est le cas elle doit retourner la valeur en question, sinon elle doit retourner 0.
Exemple
verifie_diagonale_monte(matrice,1,2) doit retourner 2.
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 0 0 0 0 0 0 0 Ligne 4 0 0 0 0 0 2 0 Ligne 3 0 0 0 0 2 1 0 Ligne 2 0 0 2 2 1 2 0 Ligne 1 0 0 2 1 2 1 0 Ligne 0 1 2 1 1 1 1 0
verifie_diagonale_tombe(matrice,ligne_debut,colonne_debut)
verifie_diagonale_tombe(matrice,ligne_debut,colonne_debut) doit vérifier si la suite des 4 cases en diagonale montante qui commence à la ligne donnée et colonne donnée comportent des jetons identiques et de valeurs 1 ou 2. Si c'est le cas elle doit retourner la valeur en question, sinon elle doit retourner 0.
Exemple
verifie_diagonale_tombe(matrice,5,0) doit retourner 1.
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 1 0 0 0 0 0 0 Ligne 4 2 1 0 0 0 0 0 Ligne 3 1 1 1 0 0 0 0 Ligne 2 1 2 2 1 0 0 0 Ligne 1 2 1 1 2 0 0 0 Ligne 0 1 2 1 1 1 1 0
verifie_victoire_lignes(matrice)
verifie_victoire_lignes(matrice) doit vérifier si une série de 4 cases en ligne comporte des numéros tous identiques et égaux à 1 ou 2 si c'est le cas elle retourne le numéro en question sinon elle retourne 0.
Indication : il faut utiliser vérifie ligne avec tous les débuts représentés en rouge ci dessous :
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 0 0 0 0 0 0 0 Ligne 4 0 0 0 0 0 0 0 Ligne 3 0 0 0 0 0 0 0 Ligne 2 0 0 0 0 0 0 0 Ligne 1 0 0 0 0 0 0 0 Ligne 0 0 0 0 0 0 0 0
Indication 2 : il faut faire une double boucle for, une pour les lignes et une pour les colonnes.
verifie_victoire_colonnes(matrice)
La fonction est similaire à la précédente mais doit vérifier les victoires par colonne.
verifie_victoire_diagonales_montent(matrice)
La fonction est similaire à la précédente mais doit vérifier les victoires par diagonales qui montent.
verifie_victoire_diagonale_tombent(matrice)
La fonction est similaire à la précédente mais doit vérifier les victoires par diagonales qui tombent.
verifie_victoire(matrice)
La fonction teste si un joueur est victorieux elle doit donc synthétiser tous les tests précédents, retourne 1 si le joueur 1 est victorieux 2 si c'est le joueur 2 et 0 sinon.
hauteur(matrice,colonne)
La fonction doit donner la première case libre de la colonne donnée, si aucune case n'est libre vous devez retourner -1
Exemple
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 0 0 0 1 0 0 0 Ligne 4 0 0 0 2 0 0 0 Ligne 3 0 0 2 1 0 0 0 Ligne 2 0 0 1 2 1 0 0 Ligne 1 0 2 1 1 2 0 0 Ligne 0 1 1 2 2 1 1 0
Avec la matrice ci-dessus :
hauteur(matrice,0) = 1
hauteur(matrice,1) = 2
hauteur(matrice,2) = 4
hauteur(matrice,3) = -1
hauteur(matrice,4) = 3
hauteur(matrice,5) = 1
hauteur(matrice,6) = 0
place(matrice,joueur,colonne)
La fonction va faire deux choses, si le joueur (1 ou 2) peut placer son pion dans la colonne donnée alors elle doit modifier la matrice pour le placer et retourner True, sinon si le joueur ne peut pas jouer dans la colonne la fonction doit retourner False et ne pas modifier la matrice.
Exemple
Considérons la matrice suivante :
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 0 0 0 1 0 0 0 Ligne 4 0 0 0 2 0 0 0 Ligne 3 0 0 2 1 0 0 0 Ligne 2 0 0 1 2 1 0 0 Ligne 1 0 2 1 1 2 0 0 Ligne 0 1 1 2 2 1 1 0
alors :
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 0 0 0 1 0 0 0 Ligne 4 0 0 0 2 0 0 0 Ligne 3 0 0 2 1 0 0 0 Ligne 2 0 2 1 2 1 0 0 Ligne 1 0 2 1 1 2 0 0 Ligne 0 1 1 2 2 1 1 0
place(matrice,1,3) retourne False car la colonne est déjà remplie.
verifie_remplie(matrice)
verifie_remplie(matrice) doit vérifier s'il y a encore de la place dans la matrice. True si vrai, False sinon.
Exemple
Considérons la matrice suivante :
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 0 0 0 1 0 0 0 Ligne 4 0 0 0 2 0 0 0 Ligne 3 0 0 2 1 0 0 0 Ligne 2 0 0 1 2 1 0 0 Ligne 1 0 2 1 1 2 0 0 Ligne 0 1 1 2 2 1 1 0
alors :
Considérons la matrice suivante :
Colonne 0 Colonne 1 Colonne 2 Colonne 3 Colonne 4 Colonne 5 Colonne 6 Ligne 5 1 2 1 1 2 1 1 Ligne 4 2 1 2 2 1 1 1 Ligne 3 1 2 2 1 2 1 1 Ligne 2 2 1 1 2 1 2 2 Ligne 1 2 2 1 1 2 1 1 Ligne 0 1 1 2 2 1 1 2
alors :
phpMyVisites | Open source web analytics
