|
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
|
|
