Tableaux

Énoncé

Pendant cette séance, on va manipuler la structure de donnée tableau statique (qu'on appelle souvent simplement tableau) qui met en œuvre le type abstrait séquence de taille fixe.

Pour rappel, voici la terminologie utilisée en BPI ainsi que le lien vers le document résumant tout ça :

• type abstrait (abstract data type, ADT en anglais) : ensemble d'opérations et ensemble de propriétés ;
• structure de données : mise en œuvre concrète d'un type abstrait ;
• séquence de taille fixe : type abstrait avec 2 opérations : get(i) et set(i, v) ;
• tableau statique : mise en œuvre du type abstrait séquence de taille fixe à l'aide d'un segment de mémoire contiguë. Les deux opérations get(i) et set(i) s'effectuent en temps constant : la ième case se trouve en partant du début du tableau et en ajoutant i fois la taille d'une case. Autrement dit, la taille du tableau n'intervient pas quand on cherche à savoir où se trouve la ième case.

Python est un des rares langages à ne pas fournir la structure de données "tableau statique", mais propose par contre les tableaux dynamiques (appelés list dans la spécification en anglais du langage, mais on évitera ce terme pour ne pas confondre avec les listes chaînées que l'on verra bientôt en cours). Dans certains languages, on trouve aussi le terme vecteur (quand le tableau n'a qu'une dimension, ce qui sera très souvent le cas).

La différence entre un tableau statique et un dynamique est qu'un tableau statique a une taille fixe alors qu'un dynamique peut grandir ou rétrécir pendant l'exécution du programme. Pour simuler des tableaux statiques en Python, on s'interdira donc d'utiliser les fonctions permettant de modifier la taille d'un tableau dynamique (notamment append, insert, remove et del).

Fonction principale

Vous implanterez les fonctions 4 fonctions manquantes du fichier tableaux.py dont on donne la fonction principale (pour tester au fur et à mesure les fonctions implantées) :

#!/usr/bin/env python3
"""
  Tableaux d'entiers
"""

from random import randint

# TODO : implantez les fonctions :
#  - cree
#  - indice_prem_occ
#  - echange
#  - inverse
#  - min_et_max




def main():
    """
    Fonction principale
    """
    for taille in range(6):
        print("-- Taille =", taille, "--")
        tab = cree(taille)
        print("Tableau initial :", tab)
        for idx in range(taille):
            print("Indice de", tab[idx], ":", indice_prem_occ(tab, tab[idx]))
        print("Indice de 10 :", indice_prem_occ(tab, 10))
        inverse(tab)
        print("Tableau inverse :", tab)
        idx_min, idx_max = min_et_max(tab)
        if idx_min == idx_max == -1:
            print("Pas de valeur min ni max dans un tableau vide !")
        else:
            print(f"Valeur minimale {tab[idx_min]} à l'indice {idx_min}")
            print(f"Valeur maximale {tab[idx_max]} à l'indice {idx_max}")
        print()


main()

Initialisation du tableau

Implantez une fonction cree(taille) qui renvoie un tableau de taille entiers tirés aléatoirement entre 1 et 9. Afin de ne pas utiliser la fonction append, vous utiliserez la syntaxe des « compréhensions de listes » Python pour initialiser un tableau d'entier : par exemple [x*x for x in range(10)] crée et remplit un tableau avec les carrés de 0, 1, 2, ... 9 (à adapter bien sûr pour répondre à la question posée).

Pour générer des nombres aléatoires, on utilisera la fonction randint(inf, sup) qui renvoie un entier aléatoire dans l'intervalle [inf .. sup]. On ajoutera la ligne from random import randint en haut de notre programme pour importer cette fonction.

Recherche d'un élément dans le tableau

Implantez une fonction indice_prem_occ(tab, val) qui renvoie l'indice de la première occurrence de val dans le tableau tab, ou -1 si le tableau ne contient pas val.

Échange de deux éléments

Implantez une fonction echange(tab, idx1, idx2) qui échange les éléments d'indices idx1 et idx2 dans le tableau.

Inversion du tableau

Implantez une fonction inverse(tab) qui inverse les éléments du tableau en utilisant la fonction echange précédente. Par exemple, inverser([1,2,3,4,5]) modifie le tableau pour qu'il devienne [5,4,3,2,1].

Indices du min et du max

Implantez une fonction min_et_max(tab) qui renvoie sous la forme d'un tuple les indices de la valeur minimale et de la valeur maximale contenues dans le tableau. Si le tableau contient plusieurs fois la même valeur minimale (ou maximale), on renverra l'indice de la première occurrence. On renvoie (-1, -1) par convention si le tableau est vide.

Correction

Cliquez ici pour révéler la correction.

tableaux.py :

#!/usr/bin/env python3
"""
  Tableaux d'entiers
"""

from random import randint

# TODO : implantez les fonctions :
#  - cree
#  - indice_prem_occ
#  - echange
#  - inverse
#  - min_et_max


def cree(taille):
    """
    Cree un tableau rempli de chiffres aléatoires
    """
    return [randint(1, 9) for _ in range(taille)]


def indice_prem_occ(tab, val):
    """
    Renvoie l'indice de la premiere occurrence d'un valeur dans un tableau
      ou -1 si l'element est absent du tableau
    """
    idx = 0
    while (idx < len(tab)) and (tab[idx] != val):
        idx += 1
    if idx < len(tab):
        return idx
    return -1


def echange(tab, idx1, idx2):
    """
    Echange les cases d'indice idx1 et idx2 d'un tableau
    """
    tmp = tab[idx1]
    tab[idx1] = tab[idx2]
    tab[idx2] = tmp


def inverse(tab):
    """
    Inverse le contenu d'un tableau
    """
    deb = 0
    fin = len(tab) - 1
    while deb < fin:
        echange(tab, deb, fin)
        deb += 1
        fin -= 1


def min_et_max(tab):
    """
    Renvoie sous la forme d'un tuple les indices de la valeur minimale et de la valeur
      maximale contenues dans le tableau (-1, -1 si le tableau est vide)
    """
    if len(tab) == 0:
        return (-1, -1)
    idx_min = idx_max = 0
    idx = 1
    while idx < len(tab):
        if tab[idx] < tab[idx_min]:
            idx_min = idx
        if tab[idx] > tab[idx_max]:
            idx_max = idx
        idx += 1
    return idx_min, idx_max




def main():
    """
    Fonction principale
    """
    for taille in range(6):
        print("-- Taille =", taille, "--")
        tab = cree(taille)
        print("Tableau initial :", tab)
        for idx in range(taille):
            print("Indice de", tab[idx], ":", indice_prem_occ(tab, tab[idx]))
        print("Indice de 10 :", indice_prem_occ(tab, 10))
        inverse(tab)
        print("Tableau inverse :", tab)
        idx_min, idx_max = min_et_max(tab)
        if idx_min == idx_max == -1:
            print("Pas de valeur min ni max dans un tableau vide !")
        else:
            print(f"Valeur minimale {tab[idx_min]} à l'indice {idx_min}")
            print(f"Valeur maximale {tab[idx_max]} à l'indice {idx_max}")
        print()


main()