Aller au contenu

12. TP 8 : Exercices sur les tableaux et les fonctions⚓︎

12.1 Exercice 1 ✪⚓︎

Écrire une fonction mesurer qui prend en paramètre :

  • un tableau de taille quelconque.

Cette fonction renvoie la taille du tableau.

b1 = ("mesurer([1,2,5]) == 3", "mesurer([10]py-str100) == 100", "mesurer([]) == 0",)bksl-nlbenchmark = [b1, ]bksl-nl 5/5

bksl-nldef mesurer(tableau):bksl-nl taille = len(tableau)bksl-nl return taillebksl-nlbksl-nl# oubksl-nlbksl-nldef mesurer(tableau):bksl-nl return len(tableau)bksl-nl

A

Z

12.2 Exercice 2 ✪⚓︎

  • Compléter la fonction générer_tableau_0 qui prend en paramètre :

    • un entier nombre_éléments.

    Cette fonction renvoie un tableau de taille nombre_éléments contenant uniquement des 0.

  • Modifier la fonction générer_tableau_aléatoire qui prend en paramètres :

    • un entier nombre_éléments ;
    • deux entiers a et b;

    Cette fonction renvoie un tableau de taille nombre_éléments contenant des nombres entiers aléatoires entre a et b.

    Rappel : pour générer des nombres aléatoires entre a et b, on utilisera random.randint(a, b).

def validerpy-undvaleur(T, a, b):bksl-nl return all(map(lambda x: a<=x<=b, T))bksl-nlbksl-nlb1 = ("générerpy-undtableaupy-und0(3) == [0]py-str3", "générerpy-undtableaupy-und0(100) == [0]py-str100", "générerpy-undtableaupy-und0(0) == []",)bksl-nlb2 = ("validerpy-undvaleur(générerpy-undtableaupy-undaléatoire(3, 1, 6), 1, 6) == True", \bksl-nl "validerpy-undvaleur(générerpy-undtableaupy-undaléatoire(3, 1, 1), 1, 1) == True", \bksl-nl "validerpy-undvaleur(générerpy-undtableaupy-undaléatoire(100, 1, 100), 1, 100) == True",)bksl-nlbksl-nlbenchmark = [b1, b2 ]bksl-nl 5/5

import randombksl-nlbksl-nldef générerpy-undtableaupy-und0(nombrepy-undéléments):bksl-nl tableaupy-unddepy-und0 = []bksl-nl return bksl-nlbksl-nldef générerpy-undtableaupy-undaléatoire(nombrepy-undéléments, a, b):bksl-nl tableaupy-undaléatoire = [i for i in range(nombrepy-undéléments)]bksl-nl returnbksl-nlbksl-nlTpy-undzéro = générerpy-undtableaupy-und0(3)bksl-nlprint(Tpy-undzéro)bksl-nlTpy-undaléa = générerpy-undtableaupy-undaléatoire(5, 1, 6)bksl-nlprint(Tpy-undaléa)bksl-nlimport randombksl-nlbksl-nldef générerpy-undtableaupy-und0(nombrepy-undéléments):bksl-nl tableaupy-unddepy-und0 = nombrepy-undéléments py-str [0]bksl-nl return tableaupy-unddepy-und0bksl-nlbksl-nldef générerpy-undtableaupy-undaléatoire(nombrepy-undéléments, a, b):bksl-nl tableaupy-undaléatoire = [random.randint(a,b) for i in range(nombrepy-undéléments)]bksl-nl return tableaupy-undaléatoirebksl-nlbksl-nlTpy-undzéro = générerpy-undtableaupy-und0(3)bksl-nlprint(Tpy-undzéro)bksl-nlTpy-undaléa = générerpy-undtableaupy-undaléatoire(5, 1, 6)bksl-nlprint(Tpy-undaléa)bksl-nl

A

Z

12.3 Exercice 3 ✪⚓︎

Compléter la fonction vérifier_appartenance qui prend en paramètres :

  • un tableau d'entiers T ;
  • un entier x.

Cette fonction renvoie True si la valeur appartient au tableau et False sinon.

def validerpy-undvaleur(T, a, b):bksl-nl return all(map(lambda x: a<=x<=b, T))bksl-nlbksl-nlb1 = ("compterpy-undrépétition([1,3,6], 6) == 1", "compterpy-undrépétition([8,8,8], 8) == 3", "compterpy-undrépétition([1, 8, 1, 8], 8) == 2", "compterpy-undrépétition([1,3,99], 100) == 0")bksl-nlbksl-nlbenchmark = [b1, ]bksl-nl 5/5

bksl-nldef vérifierpy-undappartenance(T, x):bksl-nl if x in T:bksl-nl return Truebksl-nl else:bksl-nl return Falsebksl-nlbksl-nl# oubksl-nlbksl-nldef vérifierpy-undappartenance(T, x):bksl-nl return x in Tbksl-nl

A

Z

12.4 Exercice 4 ✪⚓︎

Écrire une fonction compter_répétition qui prend en paramètres :

  • un tableau d'entiers T ;
  • un entier élément.

Cette fonction compte le nombre de fois où l'élément élément figure dans le tableau T.

Aide

On aura sans doute besoin d'un accumulateur comptant le nombre de répétitions...

def validerpy-undvaleur(T, a, b):bksl-nl return all(map(lambda x: a<=x<=b, T))bksl-nlbksl-nlb1 = ("compterpy-undrépétition([1,3,6], 6) == 1", "compterpy-undrépétition([8,8,8], 8) == 3", "compterpy-undrépétition([1, 8, 1, 8], 8) == 2", "compterpy-undrépétition([1,3,99], 100) == 0")bksl-nlbksl-nlbenchmark = [b1, ]bksl-nl 5/5

bksl-nldef compterpy-undrépétition(T, élément):bksl-nl compteur = 0bksl-nl for entier in T:bksl-nl if entier == élément:bksl-nl compteur = compteur + 1bksl-nl # une fois le parcours complet du bksl-nl # tableau, on renvoie le compteurbksl-nl return compteurbksl-nl

A

Z

12.5 Exercice 5 ✪⚓︎

Écrire une fonction spiraler qui prend en paramètres :

  • un tableau d'entiers T.

Cette fonction dessine une spirale carrée (angle à 90°) dont la longueur est donnée par les valeurs du tableau T.

benchmark = []bksl-nl 5/5

import turtlebksl-nlbksl-nldef spiraler(T):bksl-nl return Nonebksl-nlbksl-nlT = [ipy-str5 for i in range(40)]bksl-nlspiraler(T)bksl-nlimport turtlebksl-nlbksl-nldef spiraler(T):bksl-nl for longueur in T:bksl-nl turtle.forward(longueur)bksl-nl turtle.right(90)bksl-nl return Nonebksl-nlbksl-nlT = [ipy-str5 for i in range(40)]bksl-nlspiraler(T)bksl-nl

A

Z

Aide

On utilisera turtle.forward(L) pour avancer d'une longueur L et turtle.right(A) pour tourner à droite d'un angle A.

12.6 Exercice 6 ✪✪⚓︎

Écrire la fonction trouver_indice qui prend en paramètres :

  • un tableau d'entiers T ;
  • un entier x.

Cette fonction renvoie :

  • l'indice i de la position du premier entier du tableau égal à x ;
  • None sinon.
b1 = ("trouverpy-undindice([1,3,6], 1) == 0", "trouverpy-undindice([i for i in range(100), 99) == 99")bksl-nlbksl-nlbenchmark = [b1, ]bksl-nl 5/5

bksl-nlbksl-nlT = [2, 4, 5, 7, 12, 7, 5]bksl-nlindice = trouverpy-undindice(T, 5)bksl-nlprint(indice)bksl-nldef trouverpy-undindice(T, x):bksl-nl for indice in range(len(T)):bksl-nl # si x est trouvé dans le tableaubksl-nl if T[indice] == x: bksl-nl # on renvoie l'indicebksl-nl return indicebksl-nl # on a fini de parcourir T etbksl-nl # x n'est pas trouvébksl-nl return Nonebksl-nlbksl-nlT = [2, 4, 5, 7, 12, 7, 5]bksl-nlindice = trouverpy-undindice(T, 5)bksl-nlprint(indice)bksl-nl

A

Z

12.7 Point cours !⚓︎

Cours

Il est également possible de modifier les valeurs d'un tableaux en accédant à ses éléments par indice.

Ainsi : 

T = [1, 2, 3]
for i in range(len(T)):
    T[i] = T[i] * 2
print(T)

permet de multiplier par 2 tous les éléments du tableau T.

Essayez cet exemple dans le terminal ci-dessous :

12.8 Exercice 7 ✪⚓︎

En vous aidant des commentaires, écrire la fonction ajouter_lettre qui prend en paramètres :

  • un tableau de lettres T de taille len(T);
  • une lettre lettre.

Cette fonction renvoie un tableau de lettres T de taille len(T) + 1.

Par exemple :

ajouter_lettre(['c', 'a', 't'], 's')
renvoie 
['c', 'a', 't', 's']

b1 = ("ajouterpy-undlettre(['a','b'], 'c') == ['a','b','c']", "ajouterpy-undlettre([], 'a') == ['a']", "ajouterpy-undlettre(['a']py-str3, 'b') == ['a', 'a', 'a', 'b']")bksl-nlbksl-nlbenchmark = [b1, ]bksl-nl 5/5

def ajouterpy-undlettre(T, lettre):bksl-nl taille = len(T)bksl-nl # créer un nouveau tableau de taille len(T) + 1bksl-nl # rempli de 0bksl-nlbksl-nl # remplir ce tableau grâce à un parcours de Tbksl-nl # sur les indicesbksl-nlbksl-nl # rajouter la lettre à la dernière position bksl-nl # dans le nouveau tableau (len(T))bksl-nlbksl-nl # renvoyer le nouveaupy-undtableaubksl-nl passbksl-nlbksl-nlT1 = ['c', 'a', 't']bksl-nllettre = 's'bksl-nlT2 = ajouterpy-undlettre(T1, lettre)bksl-nlprint(T2)bksl-nldef ajouterpy-undlettre(T, lettre):bksl-nl taille = len(T)bksl-nl nouveaupy-undtableau = [0] py-str (taille+1)bksl-nl bksl-nl for i in range(taille):bksl-nl nouveaupy-undtableau[i] = T[i]bksl-nl nouveaupy-undtableau[len(T)] = lettrebksl-nl bksl-nl return nouveaupy-undtableaubksl-nlbksl-nlT1 = ['c', 'a', 't']bksl-nllettre = 's'bksl-nlT2 = ajouterpy-undlettre(T1, lettre)bksl-nlprint(T2)bksl-nl

A

Z

12.9 Exercice 8 ✪⚓︎

Compléter la fonction concaténer qui prend en paramètres :

  • un tableau de nombres entiers T1 de taille len(T1);
  • un tableau de nombres entiers T2 de taille len(T2);

Cette fonction renvoie un tableau d'entiers T de taille len(T1) + len(T2).

Par exemple :

concaténer([8, 6, 4], [1, 2])
renvoie 
[8, 6, 4, 1, 2]

b1 = ("concaténer([1,3,6], [6]) == [1,3,6,6]", "concaténer([6], [6,1,4]) == [6,6,1,4]", "concaténer([], [6]) == [6]")bksl-nlbksl-nlbenchmark = [b1, ]bksl-nl 5/5

def concaténer(T1, T2):bksl-nl passbksl-nlbksl-nltableau1 = [3, 4, 5]bksl-nltableau2 = [6, 7]bksl-nltableaupy-undcomplet = concaténer(tableau1, tableau2)bksl-nlprint(tableaupy-undcomplet)bksl-nldef concaténer(T1, T2):bksl-nl taille1 = len(T1)bksl-nl taille2 = len(T2)bksl-nl bksl-nl nouveaupy-undtableau = [0] py-str (taille1 + taille2)bksl-nl bksl-nl for i in range(taille1):bksl-nl nouveaupy-undtableau[i] = T1[i]bksl-nl for i in range(taille2):bksl-nl # On ne veut pas réécrire sur les indices 0, 1 ,2...bksl-nl nouveaupy-undtableau[i + taille1] = T2[i]bksl-nl bksl-nl return nouveaupy-undtableaubksl-nlbksl-nltableau1 = [3, 4, 5]bksl-nltableau2 = [6, 7]bksl-nltableaupy-undcomplet = concaténer(tableau1, tableau2)bksl-nlprint(tableaupy-undcomplet)bksl-nl

A

Z

12.10 Exercice 9 ✪⚓︎

Écrire la fonction prefixe qui prend en paramètres :

  • un tableau de nombres entiers T1 de taille len(T1);
  • un tableau de nombres entiers T2 de taille len(T2);

Cette fonction renvoie True si le tableau T2 commence par tous les éléments du tableau T1 dans le même ordre et False sinon.

b1 = ("prefixe([5], [5, 3, 1, 8, 8]) == True", \bksl-nl "prefixe([3], [1, 8, 8]) == False", \bksl-nl "prefixe([8,8,8], [8]) == False", \bksl-nl "prefixe([], [5, 3, 1, 8, 8]) == True")bksl-nlbksl-nlbenchmark = [b1, ]bksl-nl 5/5

def prefixe(T1, T2):bksl-nl taillepy-undT1 = len(T1)bksl-nl taillepy-undT2 = len(T2)bksl-nl passbksl-nlbksl-nlT1 = [5, 6, 3, 1]bksl-nlT2 = [5, 6, 3, 1, 8, 8]bksl-nlprint(prefixe(T1, T2))bksl-nlprint(prefixe(T2, T1))bksl-nldef prefixe(T1, T2):bksl-nl taillepy-undT1 = len(T1)bksl-nl taillepy-undT2 = len(T2)bksl-nl # cas où T2 est plus petit que T1bksl-nl # T1 ne peut pas être un préfixe...bksl-nl if taillepy-undT2 < taillepy-undT1:bksl-nl return Falsebksl-nlbksl-nl for indice in range(taillepy-undT1):bksl-nl if T1[indice] != T2[indice]:bksl-nl return Falsebksl-nl else:bksl-nl print("Jusque-là, tout va bien...")bksl-nl # on a parcouru tout T1 et tous les éléments bksl-nl # sont les mêmesbksl-nl return Truebksl-nlbksl-nlT1 = [5, 6, 3, 1]bksl-nlT2 = [5, 6, 3, 1, 8, 8]bksl-nlprint(prefixe(T1, T2))bksl-nlprint(prefixe(T2, T1))bksl-nlbksl-nlbksl-nl

A

Z

12.11 Exercice 10 ✪✪⚓︎

Écrire la fonction suffixe qui prend en paramètres :

  • un tableau de nombres entiers T1 de taille len(T1);
  • un tableau de nombres entiers T2 de taille len(T2);

Cette fonction renvoie True si le tableau T2 termine par tous les éléments du tableau T1 dans le même ordre et False sinon.

b1 = ("suffixe([8, 5], [1, 8, 5]) == True", \bksl-nl "suffixe([3], [1, 8, 8]) == False",\bksl-nl "suffixe([8,8,8], [8]) == False",\bksl-nl "suffixe([], [5, 3, 1, 8]) == True")bksl-nlbksl-nlbenchmark = [b1, ]bksl-nl 5/5

def suffixe(T1, T2):bksl-nl taillepy-undT1 = len(T1)bksl-nl taillepy-undT2 = len(T2)bksl-nl bksl-nlbksl-nlT1 = [1, 8, 8]bksl-nlT2 = [5, 6, 3, 1, 8, 8]bksl-nlprint(suffixe(T1, T2))bksl-nlprint(suffixe(T2, T1))bksl-nlbksl-nlbksl-nldef suffixe(T1, T2):bksl-nl taillepy-undT1 = len(T1)bksl-nl taillepy-undT2 = len(T2)bksl-nl # cas où T2 est plus petit que T1bksl-nl # T1 ne peut pas être un préfixe...bksl-nl if taillepy-undT2 < taillepy-undT1:bksl-nl return Falsebksl-nlbksl-nl for indice in range(taillepy-undT1):bksl-nl if T1[taillepy-undT1 - indice - 1] != T2[taillepy-undT2 - indice - 1]:bksl-nl return Falsebksl-nl else:bksl-nl print("Jusque-là, tout va bien...")bksl-nl # on a parcouru tout T1 dans l'ordre inversebksl-nl # et tous les éléments sont les mêmesbksl-nl return Truebksl-nlbksl-nlT1 = [1, 8, 8]bksl-nlT2 = [5, 6, 3, 1, 8, 8]bksl-nlprint(suffixe(T1, T2))bksl-nlprint(suffixe(T2, T1))bksl-nl

A

Z

Aide

Pour lire un tableau dans le sens inverse, il faut trouver une formule à appliquer sur les indices du tableau.

Par exemple, un tableau de taille 4 va se parcourir ainsi sur l'indice i par ordre croissant :

i 0 1 2 3
??? 3 2 1 0

Quelle sera la formule à écrire à la place des ??? pour obtenir 3 quand i vaut 0; 2 quand i vaut 1 etc.

12.12 Exercice 11 ✪✪⚓︎

  • Écrire la fonction déterminer_minimum qui prend en paramètres :

    • un entier taille_T1 ;
    • un entier taille_T2 ;

    Cette fonction renvoie le maximum des deux tailles.

  • Écrire la fonction distance_hamming qui prend en paramètres :

    • un tableau de chaîne de caractères T1 de taille len(T1);
    • un tableau de chaîne de caractères T2 de taille len(T2);

    Cette fonction renvoie le nombre de lettres qui diffère d'un tableau à l'autre. Si les tableaux sont de taille différente, les caractères en trop seront comptés comme des différences : on utilisera la fonction déterminer_minimum pour comparer la taille des tableaux.

    Par exemple :

    distance_hamming(['t', 'o', 't', 'o'], ['t', 'a', 't', 'a'])
    renvoie 
    [8, 6, 4, 1, 2]

b1 = ("déterminerpy-undminimum(8, 2) == 2", "déterminerpy-undminimum(1, 8) == 1", "déterminerpy-undminimum(-1, -2) == -2")bksl-nlb2 = ("distancepy-undhamming(['c', 'h', 'a', 't'], ['c', 'h', 'a', 't']) == 0", \bksl-nl "distancepy-undhamming(['c', 'h', 'i', 'e', 'n'], ['c', 'h', 'i', 'o', 't']) == 2", \bksl-nl "distancepy-undhamming(['c', 'h', 'a', 't'], ['c', 'h', 'a', 't', 'o', 'n']) == 2",bksl-nl "distancepy-undhamming(['v', 'i', 'd', 'e'], []) == 4")bksl-nlbksl-nlbenchmark = [b1, b2 ]bksl-nl 5/5

def déterminerpy-undminimum(taillepy-undT1, taillepy-undT2):bksl-nl passbksl-nlbksl-nldef distancepy-undhamming(T1, T2):bksl-nl passbksl-nlbksl-nlT1 = ['a', 'c', 'b', 'a']bksl-nlT2 = ['a', 'b', 'b', 'a', 'c', 'd', 'd']bksl-nlbksl-nlprint(distancepy-undhamming(T1, T2)) # doit renvoyer 4bksl-nldef déterminerpy-undminimum(taillepy-undT1, taillepy-undT2):bksl-nl if taillepy-undT2 > taillepy-undT1: return taillepy-undT1bksl-nl else: return taillepy-undT2bksl-nlbksl-nldef distancepy-undhamming(T1, T2):bksl-nl taillepy-undT1 = len(T1)bksl-nl taillepy-undT2 = len(T2)bksl-nl taillepy-undminimum = déterminerpy-undminimum(taillepy-undT1, taillepy-undT2)bksl-nlbksl-nl différence = 0bksl-nl for indice in range(taillepy-undminimum):bksl-nl if T1[indice] != T2[indice]:bksl-nl différence = différence + 1bksl-nlbksl-nl if taillepy-undT1 > taillepy-undminimum:bksl-nl manquant = taillepy-undT1 - taillepy-undminimumbksl-nl else:bksl-nl manquant = taillepy-undT2 - taillepy-undminimumbksl-nlbksl-nl différence = différence + manquantbksl-nl return différencebksl-nlbksl-nlT1 = ['a', 'c', 'b', 'a']bksl-nlT2 = ['a', 'b', 'b', 'a', 'c', 'd', 'd']bksl-nlbksl-nlprint(distancepy-undhamming(T1, T2))bksl-nl

A

Z

12.13 Exercice 12 ✪✪✪⚓︎

Comme nous le verrons par la suite, les algorithmes de tri de tableaux sont un cas fondamental en théorie informatique. Ils permettent d'aborder la notion d'efficacité au travers de la complexité (~ le coût) d'un algorithme.

Nous proposons ici d'implémenter une méthode de tri très simple.

Prenons le tableau suivant : [5, 3, 2, 7]

Premier passage dans la boucle externe

Étape i = 0 : plaçons le plus petit élément à l'indice 0 du tableau.

Passage j = 0 5 3 2 7 5 == 5 → On ne fait rien.
Passage j = 1 5 3 2 7 3 <= 5 → On échange T[1] avec T[0]
Passage j = 2 3 5 2 7 2 <= 3 → On échange T[2] avec T[0]
Passage j = 3 2 5 3 7 7 >= 2 → On ne fait rien.

i = 0 contient l'élément le plus petit.

Deuxième passage dans la boucle externe

Étape i = 1 : plaçons le second plus petit élément à l'indice 1 du tableau.

Passage j = 0 2 5 3 7 2 <= 5 → On ne fait rien.
Passage j = 1 2 5 3 7 5 == 5 → On ne fait rien
Passage j = 2 2 5 3 7 3 <= 5 → On échange T[2] avec T[1]
Passage j = 3 2 3 5 7 7 >= 3 → On ne fait rien.

i = 1 contient le deuxième élément le plus petit. Les deux premiers éléments du tableau sont triés dans l'ordre croissant.

L'algorithme comporte donc deux boucles imbriquées l'une dans l'autre. À chaque fois qu'on trouve un nouvel entier plus petit qu' l'entier situé à la position i, on l'inverse avec celui situé à la position j.

Écrire une fonction trier qui prend pour paramètre un tableau T et réalise le tri de ce tableau selon l'algorithme ci-dessus. La fonction renvoie un tableau trié dans l'ordre croissant.

def validerpy-undvaleur(T, a, b):bksl-nl return all(map(lambda x: a<=x<=b, T))bksl-nlbksl-nlb1 = ("compterpy-undrépétition([1,3,6], 6) == 1", "compterpy-undrépétition([8,8,8], 8) == 3", "compterpy-undrépétition([1, 8, 1, 8], 8) == 2", "compterpy-undrépétition([1,3,99], 100) == 0")bksl-nlbksl-nlbenchmark = [b1, ]bksl-nl 5/5

def trier(T):bksl-nl for i in range(len(T)):bksl-nl for j in range(len(T)):bksl-nl if T[i] < T[j]:bksl-nl T[i], T[j] = T[j], T[i]bksl-nl return Tbksl-nlbksl-nlT = [5, 3, 9, 1, 8, 3, -1, 9, 1]bksl-nlprint(T)bksl-nlT = trier(T)bksl-nlprint(T)bksl-nldef trier(T):bksl-nl for i in range(len(T)):bksl-nl for j in range(len(T)):bksl-nl if T[i] < T[j]:bksl-nl T[i], T[j] = T[j], T[i]bksl-nl return Tbksl-nlbksl-nlT = [5, 3, 9, 1, 8, 3, -1, 9, 1]bksl-nlprint(T)bksl-nlT = trier(T)bksl-nlprint(T)bksl-nl

A

Z

Retour en haut de la page