Algorithmique & Programmation Orientée Objet Semestre 2 ST Matrices de variables
Cours | TD - Corrections | TP
Exercice n°1 On considère une matrice d'entiers composée de 20 lignes de 8 colonnes. On souhaite effectuer diverses recherches au sein de ce tableau. a) Développer un sous-algorithme permettant de calculer la plus petite valeur contenue dans un tel tableau. b) Développer un sous-algorithme permettant de calculer la position de la plus petite valeur contenue dans un tel tableau. c) Développer un sous-algorithme permettant de calculer l'indice de la ligne dont la somme des valeurs est la plus grande.
ManipulationsMatriceEntier.lda { Type agrege de stockage d'une position 2D } { a coordonnees entières } structure position entier l <- 0 entier c <- 0 fin structure { Fonction de recherche et retour } { de la plus petite valeur contenue } { dans une matrice d'entiers } { t : Le tableau d'entiers où faire } { la recherche } entier fonction min(-> entier[][] t) entier n <- longueur(1,t) entier m <- longueur(2,t) entier i entier j entier min <- t[0][0] pour i de 0 à n-1 faire pour j de 0 à m-1 faire si t[i][j] < min alors min <- t[i][j] fsi fait fait retourner min fin fonction { Fonction de recherche et retour } { des coordonnees de la plus petite valeur } { contenue dans une matrice d'entiers } { t : La matrice d'entiers où faire } { la recherche } position fonction positionMin(-> entier [][] t) entier n <- longueur(1,t) entier m <- longueur(2,t) entier i entier j position pMin pour i de 0 à n-1 faire pour j de 0 à m-1 faire si t[i][j] < t[pMin.l][pMin.c] alors pMin.l <- i pMin.c <- j fsi fait fait retourner pMin fin fonction { Fonction de calcul et retour } { de la somme des valeurs contenues } { dans un tableau d'entiers } { ligne : Le tableau d'entiers traité } entier fonction sommeLigne(-> entier [] ligne) entier m <- longueur(ligne) entier i entier somme <- 0 pour i de 0 à m-1 faire somme <- somme+ligne[i] fait retourner somme fin fonction { Fonction de calcul et retour } { de l'indice de la ligne de somme maximum } { des lignes contenues } { dans une matrice d'entiers } { t : Le tableau d'entiers traité } entier fonction ligneMax(-> entier [][] t) entier n <- longueur(1,t) entier i entier iMax <- 0 entier somme <- sommeLigne(t[0]) entier max <- somme pour i de 1 à n-1 faire somme <- sommeLigne(t[i]) si somme > max alors iMax <- i max <- somme fsi fait retourner iMax fin fonction Clavier.class - Ecran.class - Exemple d'exécution
Exercice n°2 On manipule des matrices de réels. a) Développer un sous-algorithme permettant de copier une matrice dans une matrice. Leurs tailles sont supposées identiques. b) Développer un sous-algorithme permettant de copier la matrice transposée d'une matrice dans une matrice. Leurs tailles sont supposées compatibles. Transposer une matrice est l'opération consistant à permuter ses valeurs autour de la diagonale. c) Développer un sous-algorithme permettant de réaliser la transposition d'une matrice. La transposition se fait "en place", sans utilisation d'une matrice auxiliaire.
ManipulationsMatriceReel.lda { Action de copie d'une matrice de reel } { dans une matrice de reel supposee } { de tailles identiques } { src : La matrice de reel source } { dst : La matrice de reel cible } action copie(-> réel [][] src, réel [][] dst ->) entier n <- longueur(1,src); entier m <- longueur(2,src); entier i entier j pour i de 0 à n-1 faire pour j de 0 à m-1 faire dst[i][j] <- src[i][j] fait fait fin action { Action de transposition d'une matrice } { de reel dans une matrice de reel } { supposee de tailles compatibles } { src : La matrice de reel source } { dst : La matrice de reel cible } action transposition(-> réel [][] src, réel [][] dst ->) entier n <- longueur(1,src); entier m <- longueur(2,src); entier i entier j pour i de 0 à n-1 faire pour j de 0 à m-1 faire dst[j][i] <- src[i][j] fait fait fin action { Action de transposition d'une matrice } { carree de reel } { m : La matrice de reel à transposer } action transposition(-> réel [][] m ->) entier n <- longueur(m); entier i entier j réel aux pour i de 0 à n-2 faire pour j de i+1 à n-1 faire aux <- m[i][j] m[i][j] <- m[j][i] m[j][i] <- aux fait fait fin action Clavier.class - Ecran.class - Exemple d'exécution
Exercice n°3 On manipule des tableaux et des matrices de caractères. a) Développer un sous-algorithme permettant de générer un tableau à partir d'une matrice. Le tableau généré sera de taille nl*nc où nl et nc sont les nombres de lignes et de colonnes de la matrice. Les valeurs de la matrice seront reportées les unes à la suite des autres dans le tableau ligne de la matrice après ligne de la matrice (de gauche à droite et de bas en haut). b) Développer un sous-algorithme permettant de générer une matrice à partir d'un tableau. Outre le tableau, le sous-algorithme aura comme paramètre le nombre de lignes et le nombre de colonnes de la matrice à générer. Le report des valeurs dans la matrice est effectué séquentiellement de gauche à droite et de bas en haut. S'il n'y a pas assez de place, le report sera arrêté une fois la matrice pleine. S'il y a plus de place que nécessaire, les emplacements non remplis seront affectés avec le caractère espace.
ManipulationsMatriceCaractere.lda /* Fonction de calcul et retour du tableau */ /* de caracteres obtenu par linéarisation */ /* d'une matrice de carateres */ /* t : La matrice à linéariser */ caractere [] fonction transformationEnTableau(-> caractere [][] t) caractere [longueur(1,t)*longueur(2,t)] res entier i <- 0 entier l entier c pour l de 0 à longueur(1,t)-1 faire pour c de 0 à longueur(2,t)-1 faire res[i] <- t[l][c] i <- i+1 fait fait retourner res fin fonction /* Fonction de calcul et retour de la matrice */ /* de caracteres obtenue par transformation */ /* en matrice d'un tableau de carateres */ /* t : Le tableau à transformer */ /* lignes : Le nombre de lignes */ /* de la matrice créée */ /* colonnes : Le nombre de colonnes */ /* de la matrice créée */ caractere [][] fonction transformationEnMatrice(-> caractere [][] t, -> entier lignes, -> entier colonnes) caractere [lignes][colonnes] res entier i entier l entier c si lignes*colonnes <= longueur(1,t) alors i <- 0 pour l de 0 à lignes-1 faire pour c de 0 à colonnes-1 faire res[l][c] <- t[i] i <- i+1 fait fait sinon l <- 0 c <- 0 pour i de 0 à lignes*colonnes-1 faire si i < longueur(t) alors res[l][c] <- t[i] sinon res[l][c] <- ' ' fsi c <- c+1 si c == colonnes alors c <- 0 l <- l+1 fsi fait fsi retourner res fin fonction Clavier.class - Ecran.class - Exemple d'exécution
Exercice supplémentaire On considère une matrice de NxM "cellules". Chaque cellule possède 4 cellules voisines (à droite, à gauche, en haut et en bas). Un déplacement élémentaire entre cellules ne peut être réalisé qu'entre deux cellules voisines. La "distance" existant entre deux cellules est le nombre minimum de déplacements élémentaires permettant de passer de la première cellule à la seconde. a) Développer un sous-algorithme permettant de calculer la matrice des distances existant entre chaque cellule d'une matrice NxM et une cellule de position arbitraire. Pour une matrice de 14 lignes de 20 colonnes et la position départ (8,5) On considère que la matrice de taille NxM est une matrice de booléens. Cette matrice représente un plateau de jeu définissant 2 territoires (vrai pour le joueur n°1, faux pour le joueur n°2). Exemple de plateau de jeu b) Développer un sous-algorithme permettant de calculer la matrice des distances existant entre chaque cellule d'une matrice NxM et une cellule de position arbitraire. Dans cette version, le passage par une cellule du territoire du joueur opposé au joueur auquel appartient la cellule de départ est interdit. Une distance égale à -1 signifie une cellule non atteignable. Distances à partir de la position initiale (8,5) Distances à partir de la position initiale (1,8)
ParcoursMatrice.lda entier [][] fonction matriceDesDistances(-> entier px, -> entier py, -> entier nl, -> entier nc) entier [nl][nc] md entier i entier j pour i de 0 à nl-1 faire pour j de 0 à nc-1 faire md[i][j] <- abs(i-py)+abs(j-px) fait fait retourner md fin fonction booleen fonction voisin(-> entier x, -> entier y, -> entier [][] md, -> entier distance) booleen res <- faux si ( x >= 0 ) et ( x < longueur(2,md) ) et ( y >= 0 ) et ( y < longueur(1,md) ) alors si md[y][x] == distance alors res <- vrai fsi fsi retourner res fin fonction booleen fonction voisinage(-> entier c, -> entier l, -> entier [][] md, -> entier distance, -> booleen [][] t, -> booleen v) booleen res <- faux si ( md[l][c] == -1 ) et ( t[l][c] == v ) alors si voisin(c+1,l,md,distance) alors res <- vrai sinon si voisin(c-1,l,md,distance) alors res <- vrai sinon si voisin(c,l+1,md,distance) alors res <- vrai sinon si voisin(c,l-1,md,distance) alors res <- vrai fsi fsi fsi fsi fsi retourner res fin fonction entier [][] fonction distances(-> entier px, -> entier py, -> booleen [][] t) entier i entier j entier l entier c booleen change entier distance <- 0 entier nl -> longueur(1,t) entier nc -> longueur(2,t) entier [nl][nc] md pour i de 0 à nl-1 faire pour j de 0 à nc-1 faire md[i][j] <- -1 fait fait md[py][px] <- 0 faire change <- faux pour l de 0 à nl-1 faire pour c de 0 à nc-1 faire si voisinage(c,l,md,distance,t,t[py][px]) alors change <- vrai md[l][c] <- distance+1 fsi fait fait distance <- distance+1 tant que (change) retourner md fin fonction Clavier.class - Ecran.class - Exemple d'exécution