AP1 CPU - TP7

Tableaux

  • Créez un fichier tableau.py. Dans ce fichier déclarer un tableau tab de 20 entiers.

  • Complétez le fichier pour qu’il mette des entiers aléatoires entre -50 et 50 dans le tableau. On rappelle que randrange(-50,51) renvoie un entier aléatoire entre -50 et 50 et qu’il faut utiliser la commande from random import randrange pour pouvoir utiliser cette fonction.

  • Affichez le tableau (print(tab) suffit)

Tri 1

  • Ecrivez une fonction indice_max(T,i,j) qui parcourt toutes les cases du tableau entre \(i\) et \(j\) et renvoie la position de la case qui contient le plus grand entier.

  • Testez votre fonction plusieurs fois, pour \(i = 0, j = 19\), pour \(i = 0, j = 10\), et pour \(i = 10, j = 19\) pour vous assurer qu’elle fonctionne correctement.

Dans ce premier exercice, on va essayer de trier le tableau tab. Un algo possible est le suivant:

  • Trouver le maximum du tableau. Le mettre dans la dernière case (la case 19)

  • Trouver la case la plus grande entre les cases de 0 à 18. Mettre cette valeur dans l’avant dernière case (la case 18)

  • ainsi de suite

Pour trouver les différents maximums, on utilisera la fonction indice_max.

  • Ecrivez l’algorithme de tri. Allez-y progressivement (d’abord mettre la plus grande valeur dans la dernière case)

Recherche

Dans un tableau trié, on peut chercher si un élément est présent plus rapidement que dans un tableau non trié.

Plus précisément, on peut trouver si un élément \(x\) est compris entre les cases \(i\) et \(j\) du tableau de la façon suivante:

  • Si \(i = j\), il faut que x soit dans la case \(T[i]\)

  • Sinon, prenons la case \(m = (i+j)//2\). C’est une case pile au milieu entre \(i\) et \(j\).

    • On regarde si \(x\) est dans la case \(m\) (si oui c’est gagné)
    • Si ce n’est pas le cas, on regarde si \(x\) est plus petit que la valeur de la case. Dans ce cas, on sait qu’il suffit de chercher entre les cases \(i\) et \(m-1\) (il faut donc changer la valeur de \(j\))
    • Si ce n’est pas le cas (donc si \(x\) est plus grand que la valeur de la case), on sait qu’il suffit de chercher entre les cases \(m+1\) et \(j\) (il faut donc changer la valeur de \(i\))

Par exemple, cherchons 11 dans le tableau suivant:

\[\begin{array}{|c||c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline k &0&1&2&3&4&5&6&7&8&9\\ \hline T[k]& 1&2&4&5&8&10&11&13&15&16\\ \hline \end{array} \]

  • On commence avec \(i = 0\), \(j = 9\). La case au milieu est la case \((i+j)//2 = 4\). La valeur en T[4] est de 8, qui est plus petit que 11. On cherche donc dans les cases entre 5 et 9.

  • On continue donc avec \(i = 5, j = 9\). La case au milieu est la case \((i+j)//2 = 7\). La valeur en T[7] est de 13 qui est plus grand que 11. On cherche donc dans les cases entre 5 et 6.

  • On continue donc avec \(i = 5, j = 6\). La case au milieu est la case \((i+j)//2 = 5\). La valeur en T[5] est de 10 qui est plus petit que 11. On cherche donc dans les cases entre 6 et 6.

  • On a \(i = j\). On regarde la case, il y a 11 à l’intérieur, c’est gagné !

Pour implémenter cet algorithme, notez bien qu’il y a deux cas pour arrêter l’algorithme: soit on a trouvé la valeur, soit on a \(i = j\) et la case qu’on regarde ne contient pas l’élément qu’on cherche

  • Ecrire une fonction cherchequi cherche un élément \(x\) dans un tableau \(T\) trié de taille \(n\), et renvoie Vrai s’il est présent et faux sinon.

  • Tester votre fonction

  • Ecrire une fonction ou_inserer qui prend en entrée un élément \(x\) dont on suppose qu’il n’est pas forcément dans le tableau et qui renvoie à quelle position il faudrait l’insérer. (Aide: c’est le même algorithme. Quand on s’arrête avec \(i = j\), la case où il faut insérer \(x\) est soit \(i\), soit \(i+1\))

Tri 2

  • Recopiez votre fonction ou_inserer dans un autre fichier.

Un autre algorithme de tri fonctionne ainsi.

  • On ne touche pas à la première case

  • On regarde la valeur de la deuxième case, et on regarde s’il faut l’insérer avant ou après la valeur de la première case

  • On regarde la valeur de la troisième case, et on regarde s’il faut l’insérer avant la première case, entre les deux cases, ou après les deux cases.

  • etc.

Pour programmer cet algorithme, il faut utiliser la fonction ou_inserer.

  • Ecrivez l’algorithme de tri.