Tableaux¶
Comparaisons et tests de tableaux¶
➥ Déterminer si deux tableaux sont identiques :
def tableaux_egaux(a: [int], b: [int]) -> bool: """ :entrée a: tableau d'int :entrée b: tableau d'int :sortie te: bool :post-cond: te est True si et seulement si len(a) == len(b) et ∀ i ∈ [0;len(a)[, a[i] == b[i] >>> tableaux_egaux([1, 2, 4, 3], [1, 2, 4, 3]) True >>> tableaux_egaux([1, 2, 4, 3], [9, 2, 4, 3]) False >>> tableaux_egaux([1, 2, 4, 3], [1, 2, 4]) False >>> tableaux_egaux([1, 2, 4], [1, 2, 4, 3]) False """
➥ Déterminer si le tableau b est un préfixe du tableau a :
def tableau_prefixe(a: [int], b: [int]) -> bool: """ :entrée a: tableau d'int :entrée b: tableau d'int :sortie te: bool :post-cond: te est True si et seulement si len(a) >= len(b) et ∀ i ∈ [0;len(b)[, a[i] == b[i] >>> tableaux_prefixe([1, 2, 4, 3], [1, 2, 4, 3]) True >>> tableaux_prefixe([1, 2, 4, 3], [9, 2, 4, 3]) False >>> tableaux_prefixe([1, 2, 4, 3], [1, 2, 4]) True >>> tableaux_prefixe([1, 2, 4], [1, 2, 4, 3]) False """
➥ Retourner True si et seulement si le tableau a est un Palindrome :
def tableau_palindrome(a: [int]) -> bool: """ :entrée a: tableau d'int :sortie p: bool :post-cond: p est True si et seulement si ∀ i ∈ [0;len(a)[, a[i] == a[len(a)-1-i] >>> tableau_palindrome([1, 2, 4, 3]) False >>> tableau_palindrome([1, 2, 4, 2, 1]) True >>> tableau_palindrome([1, 2, 2, 1]) True >>> tableau_palindrome([4]) True """
Recherche de valeurs¶
➥ Trouver l’indice du plus petit élément d’un tableau :
def indice_min(a: [float]) -> int: """ :entrée a: tableau de float :pré-cond: len(a) > 0 :sortie imin: int :post-cond: ∀ i ∈ [0;len(a)[, a[imin] ≤ a[i] >>> indice_min([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0]) 2 >>> indice_min([2.0, 1.0, -3.0, 7.0, -3.0, 5.0, 1.0]) 2 >>> # mais 4 est aussi une réponse correcte """
NB : si le tableau contient plusieurs minima ex-æquo, cette spécification n’impose pas lequel doit être retourné.
➥ Trouver l’indice le plus à gauche du plus petit élément d’un tableau :
def indice_min_gauche(a: [float]) -> int: """ :entrée a: tableau de float :pré-cond: len(a) > 0 :sortie imin: int :post-cond: ∀ i ∈ [0;imin[, a[imin] < a[i], ∀ i ∈ ]imin;len(a)[, a[imin] ≤ a[i], >>> indice_min_gauche([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0]) 2 >>> indice_min_gauche([2.0, 1.0, -3.0, 7.0, -3.0, 5.0, 1.0]) 2 """
NB : La différence avec indice_min ci-dessus est que, si le tableau contient plusieurs minima ex-aequo, cette spécification impose de retourner l’indice du plus à gauche.
➥ Trouver l’indice le plus à droite du plus petit élément d’un tableau :
def indice_min_droite(a: [float]) -> int: """ :entrée a: tableau de float :pré-cond: len(a) > 0 :sortie imin: int :post-cond: ∀ i ∈ [0;imin[, a[imin] ≤ a[i], ∀ i ∈ ]imin;len(a)[, a[imin] < a[i], >>> indice_min_droite([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0]) 2 >>> indice_min_droite([2.0, 1.0, -3.0, 7.0, -3.0, 5.0, 1.0]) 4 """
➥ Trouver l’indice du plus grand élément d’un tableau :
def indice_max(a: [float]) -> int: """ :entrée a: tableau de float :sortie imax: int :pré-cond: len(a) > 0 :post-cond: ∀ i ∈ [0;len(a)[, a[imax] ≤ a[i] >>> indice_max([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0]) 3 >>> indice_max([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0]) 3 >>> # mais 5 est aussi une réponse correct """
NB : si le tableau contient plusieurs maxima ex-aequo, cette spécification n’impose pas lequel doit être retourné.
➥ Trouver l’indice le plus à gauche de la valeur v dans un tableau :
def indice_gauche(a: [float], v: float) -> int: """ :entrée a: tableau de float :entrée v: float :sortie ival: int :post-cond: si v ∈ a, a[ival] = v et ∀ i ∈ [0;ival[, a[i] ≠ v sinon ival = -1 >>> indice_gauche([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0], 2.0) 0 >>> indice_gauche([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0], 7.0) 3 >>> indice_gauche([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 7.0) 3 >>> indice_gauche([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0], 9.0) -1 """
➥ Trouver l’indice le plus à droite de la valeur v dans un tableau :
def indice_droite(a: [float], v: float) -> int: """ :entrée a: tableau de float :entrée v: float :sortie ival: int :post-cond: si v ∈ a, a[ival] = v et ∀ i ∈ ]ival, len(a)[, a[i] ≠ v sinon ival = -1 >>> indice_droite([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0], 2.0) 0 >>> indice_droite([2.0, 1.0, -3.0, 7.0, 3.0, 5.0, 1.0], 7.0) 3 >>> indice_droite([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 7.0) 5 >>> indice_droite([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 9.0) -1 """
➥ Trouver l’indice de la n-ème occurrence de v dans un tableau :
def indice_n(a: [float], v: float, n: int) -> int: """ :entrée a: tableau de float :entrée v: float :entrée n: int :sortie ival: int :pré-cond: n > 0 :post-cond: si v apparaît au moins n fois dans a, alors a[ival] = v, et a[0:ival] contient v exactement n-1 fois, sinon ival = -1 >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 2.0, 1) 0 >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 2.0, 2) -1 >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 7.0, 1) 3 >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 7.0, 2) 5 >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 7.0, 3) -1 >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 9.0, 1) -1 >>> indice_n([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 9.0, 2) -1 """
➥ Compter le nombre d’occurrences de v dans un tableau:
def nb_occurences(a: [float], v: float) -> int: """ :entrée a: tableau de float :entrée v: float :sortie n: int :post-conf: n = |{ i | i ∈ [0;len(a)[ et a[i] = n }| >>> nb_occurences([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 2.0) 1 >>> nb_occurences([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 7.0) 2 >>> nb_occurences([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0], 9.0) 0 """
Calculs sur les valeurs¶
➥ Calculer la somme des éléments d’un tableau :
def somme(a: [float]) -> float: """ :entrée a: tableau de float :pré-cond: len(a) > 0 :sortie s: float :post-cond: s = Σ a[i] pour i ∈ [0;len(a)[ >>> somme([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0]) 18.0 """
➥ Calculer la moyenne des éléments d’un tableau :
def moyenne(a: [float]) -> float: """ :entrée a: tableau de float :pré-cond: len(a) > 0 :sortie m: float :post-cond: s est la moyenne des éléments de a >>> moyenne([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0]) 2.5714285714285716 """
➥ ⭑ Calculer la moyenne pondérée des éléments d’un tableau :
def moyenne_ponderee(a: [float], poids: [float]) -> float: """ :entrée a: tableau de float :entrée poids: tableau de float :pré-cond: len(a) > 0, len(poids) == len(a), somme(poids) != 0 :sortie mp: float :post-cond: s est la moyenne pondérée des éléments de a telle que ∀ i ∈ [0;len(a)[, a[i] est pondérée par poids[i] >>> moyenne_ponderee([10.0, 12.0, 7.0], [1.0, 2.0, 1.0]) 10.25 """
Génération et modification de tableaux¶
➥ ⭑ Retourner un tableau contenant les \(n\) premiers nombres premier :
def premiers(n: int) -> [int]: """ :entrée n: int :pré-cond: n > 0 :sortie a: tableau d'int :post-cond: len(a) == n ∀ i ∈ [0;n[, a[i] est le (i+1)-ème nombre premier >>> premiers(3) array([2, 3, 5]) >>> premiers(10) array([2, 3, 5, 7, 11, 13, 17, 19, 23, 29]) """
On rappelle qu’un nombre premier admet exactement deux diviseurs : 1 et lui même.
Par exemple, premiers(10) retournera le tableau
[2,3,5,7,11,13,17,19,23,29]1.➥ ⭑ Retourner un tableau contenant les \(n\) premiers termes de la suite de Fibonacci :
def fibonacci(n: int) -> [int]: """ :entrée n: int :pré-cond: n > 0 :sortie a: tableau d'int :post-cond: len(a) == n ∀ i ∈ [0;n[, a[i] = Fi >>> fibonacci(4) array([1, 1, 2, 3]) >>> fibonacci(10) array([1, 1, 2, 3, 5, 8, 13, 21, 34, 55]) """
On rappelle que la suite de Fibonnaci2 est définie par :
\[\begin{split}& F_0 = 1 \\ & F_1 = 1 \\ & \forall n > 1, ~~ F_n = F_{n-1} + F_{n-2}\end{split}\]➥ ⭑ Retourner un tableau de \(n\) booléen indiquant, pour chaque nombre entre 0 et n-1, s’il est premier ou non :
def eratosthene(n: int) -> [bool]: """ :entrée n: int :pré-cond: n > 0 :sortie a: tableau de bool :post-cond: len(a) == n ∀ i ∈ [0;n[, a[i] est True si et seulement si i est premier >>> eratosthene(4) array([False, False, True, True]) >>> eratosthene(10) array([False, False, True, True, False, True, False, True, False, False]) """
La méthode proposée (le crible d’Ératosthène) consiste à :
initialiser tous les éléments du tableau à True (à part 0 et 1),
pour chaque élément à partir de 2, s’il vaut True, mettre tous ses multiples à False.
À la fin de ce processus, les nombres premiers et uniquement eux seront à True.
➥ Retournerr le tableau inverse de a :
def tableau_inverse(a: [float]) -> [float]: """ :entrée a: tableau de float :sortie b: tableau de float :post-cond: ∀ i ∈ [0;len(a)[, b[i] == a[len(a)-1-i] >>> tableau_inverse([]) array([]) >>> tableau_inverse([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0]) array([1.0, 7.0, 3.0, 7.0, -3.0, 1.0, 2.0]) """
➥ ⭑ Calculer les moyennes par groupe pour un tableau contenant toutes les notes d’une promotion d’étudiants :
def moyennes_par_groupe(notes: [float], nbEtu: [int]) -> [float]: """ :entrée notes: tableau de float :entrée nbEtu: tableau d'int :pré-cond: - la somme des éléments de nbEtu est égale à len(notes) - notes[0 : nbEtu[0]] contient les notes du premier groupe ; notes[nbEtu[0] : nbEtu[0] + nbEtu[1]] contient les notes du deuxième groupe, et ainsi de suite... :sortie moy: tableau de float :post-cond: - len(moy) = len(nbEtu) - ∀ i ∈ [0;len(moy)[, moy[i] contient la moyenne des étudiants du (i+1)ème groupe >>> moyennes_par_groupes([11.0, 9.0, 10.0, 15.0, 16.0, 2.0, 3.0, 4.0], [3, 2, 3]) array([10.0, 15.5, 3.0]) """
➥ ⭑⭑ Calculer les moyennes par groupe pour un tableau contenant toutes les notes d’une promotion d’étudiants :
def moyennes_par_groupe2(notes: [float], groupe: [int], nbGroupe, int) -> [float]: """ :entrée notes: tableau de float :entrée groupe: tableau d'int :entrée nbGroupes: int :pré-cond: - len(notes) = len(groupe) - ∀ i ∈ [0;len(notes)[, notes[i] est la note du (i+1)ème étudiant, et groupe[i] est le numéro de groupe (entre 0 et nbGroupes-1) de cet étudiant :sortie moy: tableau de float :post-cond: - len(moy) = nbGroupes - ∀ i ∈ [0;len(moy)[, moy[i] contient la moyenne des étudiants du groupe n° i >>> moyennes_par_groupes2([11.0, 15.0, 9.0, 3.0, 10.0, 16.0, 2.0, 4.0], [ 0, 1, 0, 2, 0, 1, 2, 2]) array([10.0, 15.5, 3.0]) """
➥ ⭑⭑ Générer toutes les chaînes de caractères de longueur \(n\) composées des caractères
'a'et'b':def mots_ab(n: int) -> [str]: """ :entrée n: int :pré-cond: n ≥ 0 :sortie mots: tableau de str :post-cond: mots contient toutes les chaînes de caractères de longueur n composées des caractères 'a' et 'b'. >>> # l'ordre peut être différent >>> mots_ab(0) array([""]) >>> mots_ab(1) array(["a", "b"]) >>> mots_ab(2) array(["aa", "ab", "ba", "bb"]) >>> mots_ab(3) array(["aaa", "aab", "aba", "abb", "baa", "bab", "bba", "bbb"]) >>> mots_ab(4) array(["aaaa", "aaab", "aaba", "aabb", "abaa", "abab", "abba", "abbb", "baaa", "baab", "baba", "babb", "bbaa", "bbab", "bbba", "bbbb", ]) """
NB: pour n = 0, la réponse est constituée de l’unique chaîne
""(qui a bien pour longueur 0, et qui ne contient aucun autre caractère que'a'ou'b').Bien que ce ne soit pas une obligation, cet algorithme est plus simple à écrire sous forme récursive qu’itérative.
➥ ⭑⭑ Générer toutes les chaînes de caractères de longueur \(n\) composées d’un ensemble de caractères donnés :
def mots(chars: str, n: int) -> [str]: """ :entrée chars: str :entrée n: int :sortie mots: tableau de str :pré-cond: n ≥ 0, len(chars) > 0, tous les caractères de chars sont différents :post-cond: mots contient toutes les chaînes de caractères de longueur n composées des caractères de chars. >>> mots("abc", 0) array([""]) >>> mots("abc", 1) array(["a", "b", "c"]) >>> mots("abc", 2) array(["aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc"]) >>> mots("XyZ", 2) array(["XX", "Xy", "XZ", "yX", "yy", "yZ", "ZX", "Zy", "ZZ"]) """
On pourra s’inspirer de la solution de mots_ab, dont cet algorithme est une généralisation.
Modification de tableau¶
➥ Modifier le tableau a de sorte à inverser l’ordre de ses éléments :
def inverse_tableau(a: [float]): """ :e/s a: tableau de float :post-cond: ∀ i ∈ [0;len(a)[, aₑ[i] == aₛ[len(a)-1-i] >>> a = array([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0]) >>> inverse_tableau(a) >>> a array([1.0, 7.0, 3.0, 7.0, -3.0, 1.0, 2.0]) """
➥ Insèrer une valeur dans un tableau, en décalant les autres valeurs vers la droite :
def insere_val(a: [float], v: float, i: int): """ :e/s a: tableau de float :entrée v: float :entrée i: int :pré-cond: 0 ≤ i < len(a) :post-cond: ∀ j ∈ [0;len(a)[, aₛ[j] == aₑ[j] si j < i aₛ[j] == v si j = i aₛ[j] == aₑ[j-1] si j > i >>> a = array([2.0, 1.0, -3.0, 7.0, 3.0, 7.0, 1.0]) >>> insere_val(a, 9.0, 2) >>> a array([1.0, 7.0, 9.0, 3.0, 7.0, -3.0, 1.0]) """
NB: le tableau ne change pas de taille, donc cette procédure perd la valeur initialement la plus à droite du tableau.
Tableaux triés¶
➥ ⭑ Trouver l’indice de la valeur v dans un tableau trié :
def indice_gauche(a: [float], v: float) -> int: """ :entrée a: tableau de float :entrée v: float :pré-cond: a est trié: ∀ i ∈ [1;len(a)[, a[i] ≥ a[i-1] :sortie ival: int :post-cond: si v ∈ a, a[ival] = v sinon ival = -1 """
Si \(v\) a plusieurs occurences dans le tableau, on ne spécifie pas l’indice de laquelle doit être retourné. En revanche, il faut tirer partie du fait que le tableau est trié pour trouver rapidement le résultat3.
➥ ⭑ Insèrer une valeur à sa place dans un tableau trié, en décalant les autres valeurs vers la droite :
def insere_val(a: [float], v: float) -> int: """ :e/s a: tableau de float :entrée v: float :pré-cond: a est trié: ∀ i ∈ [1;len(a)[, a[i] ≥ a[i-1] :sortie ival: int :post-cond: a est toujours trié ; ∀ i ∈ [0;len(a)[, aₛ[i] == aₑ[i] si i < ival aₛ[i] == v si i = ival aₛ[i] == aₑ[i-1] si i > ival """
NB: le tableau ne change pas de taille, donc cette procédure perd la valeur initialement la plus à droite du tableau.
➥ Supprimer tous les doublons d’un tableau trié :
def suppression_doublons(a: [float]) -> int: """ :e/s a: tableau de float :sortie newlen: int :pré-cond: a est trié: ∀ i ∈ [1;len(a)[, a[i] ≥ a[i-1] :post-cond: - 0 ≤ newlen ≤ len(a) - ∀ i ∈ [0;len(a)[, ∃ j ∈ [0;newlen[, aₛ[j] = aₑ[i] - ∀ i ∈ [1;newlen[, aₛ[i-1] < aₛ[i] """
NB: le tableau ne change pas de taille, mais \(newlen\) est la nouvelle longueur « utile » du tableau, c’est à dire l’indice à partir duquel les valeurs dans \(aₛ\) ne sont plus pertinentes.
➥ Copier les valeurs de deux tableaux triés dans un troisième tableau de sorte à ce que ce dernier soit trié lui aussi :
def interclassement(a1: [float], a2: [float]) -> [float]: """ :entrée a1: tableau de float :entrée a2: tableau de float :pré-cond: a1 est trié: ∀ i ∈ [1;len(a1)[, a1[i] ≥ a1[i-1] a2 est trié: ∀ i ∈ [1;len(a2)[, a2[i] ≥ a2[i-1] :sortie a3: tableau de float :post-cond: - len(a3) = len(a1) + len(a2) - a3 est trié: ∀ i ∈ [1;len(a3)[, a3[i] ≥ a3[i-1] - a3 contient toutes les valeurs de a1 et a2 """
Indices
- 1
Bien que cela soit possible, il n’est pas conseillé de réutiliser la fonction premier, car il existe une solution plus efficace qui ne l’utilise pas.
- 2
Bien que cela soit possible, il n’est pas conseillé de réutiliser la fonction fibo, car il existe une solution plus efficace qui ne l’utilise pas.
- 3
Pour cela on effectuera une recherche dichotomique : à chaque étape, on regarde au milieu de la plage d’indice considérée, et selon que la valeur trouvée est plus grande ou plus petite que \(v\), on n’en considère plus que la moitié gauche ou la moitié droite.