Devoir de contrôle n°1 : sous-programmes, tri à bulles, matrices

Exercice 1 : nombres premiers (6 pts)

Un entier n est premier s'il est supérieur ou égal à 2 et n'a pas d'autre diviseur que 1 et lui-même.

• 1) Écrire la fonction EstPremier(n) qui renvoie vrai si n est premier et faux sinon (3 pts).
• 2) Expliquer pourquoi il suffit de tester les diviseurs d de 2 jusqu'à la racine carrée de n (1 pt).
• 3) Écrire un programme qui lit un entier N ≥ 2 et affiche tous les nombres premiers inférieurs ou égaux à N, puis leur nombre (2 pts).

Exemple : pour N = 11, le programme affiche :

Premiers : 2 3 5 7 11
Nombre : 5

Exercice 2 : tri à bulles (7 pts)

Le tri à bulles parcourt le tableau en comparant chaque élément à son voisin de droite et les échange s'ils ne sont pas dans l'ordre croissant. On recommence tant qu'au moins un échange a eu lieu pendant le dernier passage.

• 1) Appliquer cette méthode à T = [5, 1, 4, 2, 8] : donner le contenu de T après chaque passage et le nombre total d'échanges (2 pts).
• 2) Écrire l'algorithme de la procédure TriBulles(T, n, echanges, passages) qui trie T et renvoie le nombre d'échanges et le nombre de passages effectués, le dernier passage (sans échange) compris (3 pts).
• 3) Écrire un programme qui lit n puis les n éléments de T, appelle la procédure et affiche le tableau trié, le nombre d'échanges et le nombre de passages (2 pts).

Pour T = [5, 1, 4, 2, 8], le programme affiche :

Trié : 1 2 4 5 8
Échanges : 4
Passages : 3

Exercice 3 : matrice carrée (7 pts)

Soit M une matrice carrée de n lignes et n colonnes d'entiers (2 ≤ n ≤ 5). Écrire un programme qui lit n puis les éléments de M ligne par ligne, et affiche :

• la somme de la diagonale principale (M[i][i]) ;
• la somme de la diagonale secondaire (M[i][n-1-i]) ;
• le plus grand élément et sa position (première occurrence, lignes et colonnes comptées à partir de 1) ;
• si la matrice est symétrique (M[i][j] = M[j][i] pour tous i et j).

Exemple avec n = 3 et M = [[2, 7, 6], [9, 5, 1], [4, 3, 8]] :

Diagonale principale : 15
Diagonale secondaire : 15
Maximum : 9 en ligne 2 et colonne 1
Symétrique : non

• 1) Donner l'analyse et l'algorithme (4 pts).
• 2) Traduire en Python (3 pts).