|
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
constante N : entier <- 20
constante M : entier <- 8
{ Type agrege de stockage d'une position }
structure position
l : entier <- 0
c : entier <- 0
fin structure
{ Methode de recherche la plus petite valeur }
{ contenue dans une matrice de entier }
entier fonction min(t)
Données
t : Tableau [N][M] de entier
Locales
min : 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
{ Methode de recherche des coordonnees }
{ de la plus petite valeur }
{ contenue dans une matrice de entier }
position fonction positionMin(t)
Données
t : Tableau [N][M] de entier
Locales
min : entier
i : entier
j : entier
pMin : position
min <- t[0][0]
pour i de 0 à N-1 faire
pour j de 0 à M-1 faire
si t[i][j] < min alors
pMin.l <- i
pMin.c <- j
min <- t[i][j]
fsi
fait
fait
retourner pMin
fin fonction
{ Methode de calcul de la somme des valeurs }
{ contenues dans un tableau de entier }
entier fonction sommeLigne(ligne)
Données
ligne : Tableau [M] de entier
Locales
somme : entier
i : entier
somme <- 0
pour i de 0 à M-1 faire
somme <- somme+ligne[i]
fait
retourner somme
fin fonction
{ Methode de calcul de l'indice de la ligne }
{ de somme maximum des lignes }
{ contenues dans une matrice de entier }
entier fonction ligneMax(t)
Données
t : Tableau [N][M] de entier
Locales
max : entier
i : entier
iMax : entier
somme : entier
max <- sommeLigne(t[0])
iMax <- 0
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 NxM dans une matrice NxM.
b) Développer un sous-algorithme permettant de copier la matrice transposée d'une matrice NxM dans une matrice MxN. 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 NxN. La transposition est à réaliser en "en place",
sans utilisation d'une matrice auxiliaire.
|
ManipulationsMatriceReel.lda
constante N : entier <- ...
constante M : entier <- ...
{ Methode de copie d'une matrice de reel }
{ dans une matrice de reel supposee }
{ de taille identique }
action copie(src,dst)
Données
src : Tableau [N][M] de réel
Résultat
dst : Tableau [N][M] de réel
locales
i : entier
j : entier
pour i de 0 à N-1 faire
pour j de 0 à M-1 faire
dst[i][j] <- src[i][j]
fait
fait
fin action
{ Methode de transposition d'une matrice }
{ de reel dans une matrice de reel }
{ supposee de taille compatible }
action transposition(src,dst)
Données
src : Tableau [N][M] de réel
Résultat
dst : Tableau [M][N] de réel
locales
i : entier
j : entier
pour i de 0 à N-1 faire
pour j de 0 à M-1 faire
dst[j][i] <- src[i][j]
fait
fait
fin action
{ Methode de transposition d'une matrice }
{ carree de reel }
action transposition(m)
Données / Résultats
m : Tableau [N][N] de réel
locales
i : entier
j : entier
aux : réel
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 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
constante N : entier <- ...
constante M : entier <- ...
Tableau [N][M] de entier fonction matriceDesDistances(px,py)
Données
px : entier
py : entier
Locales
i : entier
j : entier
md : Tableau [N][M] de entier
pour i de 0 à N-1 faire
pour j de 0 à M-1 faire
md[i][j] <- abs(i-py)+abs(j-px)
fait
fait
retourner md
fin fonction
booleen fonction voisin(x,y,md,distance)
Données
x : entier
y : entier
md : Tableau [N][M] de entier
distance : entier
Locales
res : booleen
res <- faux
si ( x >= 0 ) et ( x < M ) et ( y >= 0 ) et ( y < N ) alors
si md[y][x] = distance alors
res <- vrai
fsi
fsi
retourner res
fin fonction
booleen fonction voisinage(c,l,md,distance,t,v)
Données
c : entier
l : entier
md : Tableau [N][M] de entier
distance : entier
t : Tableau [N][M] de booleen
v : booleen
Locales
res : 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
Tableau [N][M] de entier fonction distances(px,py,t)
Données
px : entier
py : entier
t : Tableau [N][M] de booleen
Locales
i : entier
j : entier
l : entier
c : entier
change : booleen
distance : entier
md : Tableau [N][M] de entier
distance <- 0
pour i de 0 à N-1 faire
pour j de 0 à M-1 faire
md[i][j] <- -1
fait
fait
md[py][px] <- 0
faire
change <- faux
pour l de 0 à N-1 faire
pour c de 0 à M-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
|
|
