Livre_silo 30 août 2013 16:32 Page 169
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
169
6 – Notions de complexité et algorithmique sur les tableaux
Exercice 6.28 En s’inspirant de la fonction creer_matrice, écrire les trois fonctions suivantes :
1 une fonction qui prend un entier n > 0 en argument et renvoie la matrice identité de dimension n ;
2 une fonction qui prend un entier n > 1 en argument et renvoie la matrice tridiagonale de dimension n
suivante :
1
1
(0)
1
. . .
. . .
. . .
. . .
. . .
. . .
. . .
1
(0)
1
1
3 une fonction qui prend un entier n > 0 en argument et renvoie la matrice de dimension n formée sur
le modèle suivant, ici pour n = 4 :
1 2 3 4
2 1 2 3
3 2 1 2
4 3 2 1
Exercice 6.29 * Écrire une fonction qui décide si une matrice donnée est symétrique et une autre qui
décide si elle est antisymétrique. Quelle est la complexité de ces fonctions ?
Exercice 6.30
1 Définir en Python deux matrices a et b représentant respectivement :
A =
(
1 2
3 4
)
et
B =
(
5 6
7 8
)
2 Quelle est la valeur de l’expression a + b ? Pourquoi ?
3 Écrire une fonction somme_matrices qui calcule la somme de deux matrices de mêmes dimensions.
4 Quelle est la valeur d’une expression comme 3 * a ? Pourquoi ?
5 Écrire une fonction scal_matrice qui prend en argument une matrice (de dimensions quelconques) et
un flottant, et calcule le produit de cette matrice par ce flottant.
Exercice 6.31 ** Dans cet exercice, on programme différents jeux d’alignements dans une grille.
1 Écrire un programme qui permet à deux joueurs humains de jouer au Tic-tac-toe. Le programme vérifiera
que les coups joués sont valides et détectera la victoire d’un joueur ou la partie nulle.
2 Modifier ce programme pour qu’il joue de façon aléatoire contre un joueur humain.
3 Modifier ce programme pour qu’il joue de façon suffisamment stratégique pour ne jamais perdre, qu’il
soit premier ou second à jouer.
4 Écrire un programme qui permet à deux joueurs humains de jouer au Morpion : la grille de jeu est
cette fois-ci rectangulaire, de dimensions choisies en début de partie et il faut réaliser un alignement
de 5 pions pour gagner.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
169
6 – Notions de complexité et algorithmique sur les tableaux
Exercice 6.28 En s’inspirant de la fonction creer_matrice, écrire les trois fonctions suivantes :
1 une fonction qui prend un entier n > 0 en argument et renvoie la matrice identité de dimension n ;
2 une fonction qui prend un entier n > 1 en argument et renvoie la matrice tridiagonale de dimension n
suivante :
1
1
(0)
1
. . .
. . .
. . .
. . .
. . .
. . .
. . .
1
(0)
1
1
3 une fonction qui prend un entier n > 0 en argument et renvoie la matrice de dimension n formée sur
le modèle suivant, ici pour n = 4 :
1 2 3 4
2 1 2 3
3 2 1 2
4 3 2 1
Exercice 6.29 * Écrire une fonction qui décide si une matrice donnée est symétrique et une autre qui
décide si elle est antisymétrique. Quelle est la complexité de ces fonctions ?
Exercice 6.30
1 Définir en Python deux matrices a et b représentant respectivement :
A =
(
1 2
3 4
)
et
B =
(
5 6
7 8
)
2 Quelle est la valeur de l’expression a + b ? Pourquoi ?
3 Écrire une fonction somme_matrices qui calcule la somme de deux matrices de mêmes dimensions.
4 Quelle est la valeur d’une expression comme 3 * a ? Pourquoi ?
5 Écrire une fonction scal_matrice qui prend en argument une matrice (de dimensions quelconques) et
un flottant, et calcule le produit de cette matrice par ce flottant.
Exercice 6.31 ** Dans cet exercice, on programme différents jeux d’alignements dans une grille.
1 Écrire un programme qui permet à deux joueurs humains de jouer au Tic-tac-toe. Le programme vérifiera
que les coups joués sont valides et détectera la victoire d’un joueur ou la partie nulle.
2 Modifier ce programme pour qu’il joue de façon aléatoire contre un joueur humain.
3 Modifier ce programme pour qu’il joue de façon suffisamment stratégique pour ne jamais perdre, qu’il
soit premier ou second à jouer.
4 Écrire un programme qui permet à deux joueurs humains de jouer au Morpion : la grille de jeu est
cette fois-ci rectangulaire, de dimensions choisies en début de partie et il faut réaliser un alignement
de 5 pions pour gagner.