Skip to content

TD4. Tableaux et boucles

Ce TD a trois objectifs :

  • Définir les notions suivantes :
    • séquence de taille fixe
    • tableau
    • séquence de taille variable
    • tableau dynamique aussi appelé vecteur
    • list sans e
    • liste chaînée
  • Prendre en main la structure de contrôle for
  • Introduire la notion de complexité de calcul de façon intuitive

Préambule : éléments de langage

Question 1

Donner une définition du terme séquence de taille fixe.

Question 2

Donner une définition du terme tableau ainsi qu'une ligne de code, dans n'importe quel langage, permettant de créer un tableau.

Question 3

Donner une définition du terme séquence de taille variable.

Question 4

Donner une définition du terme tableau dynamique ainsi qu'une ligne de code, dans n'importe quel langage, permettant de créer un tableau dynamique.

Question 5

Donner une définition du terme list ainsi qu'une ligne de code python permettant de créer une list.

Question 6

Donner une définition du terme liste chaînée et réfléchir à la façon de créer une telle liste.

Exercice 1 : parcours de tableaux

Dans cet exercice nous allons parcourir un tableau. Comme les tableaux n'existent pas en python, quand nous disons tableau, cela signifie une list python sur laquelle on effectue uniquement des accès indexés.

Question 1

Écrire une fonction qui renvoie la somme des éléments d'un tableau à l'aide du boucle for. Combien d'additions sont nécessaires ?

Question 2

Écrire une fonction qui réalise la somme des éléments pairs d'un tableau à l'aide du boucle for. Combien d'additions sont nécessaires ?

Question 3

Écrire une fonction qui réalise la somme des éléments d'indices pairs d'un tableau à l'aide du boucle for. Combien d'additions sont nécessaires ?

Question 4

Écrire une fonction qui réalise le produit scalaire de deux vecteurs (au sens mathématique et non informatique tel que décrit dans le préambule) stockés dans deux tableaux. Combien d'additions sont nécessaires ?

Exercice 2 : polygones

On stocke un polygone comme un tableau de Point. On souhaite afficher tous les segments composant le polygone. On dispose pour ce faire d’une fonction affiche_segment(point1, point2).

Question 1

Écrire une fonction qui réalise l'affichage du polygone. Combien d'appels à la fonction affiche_segment sont nécessaires ?

Exercice 3 : somme de chiffres

Question 1

Écrire une fonction qui réalise la somme de tous les chiffres dans la représentation en base 10 d'un entier. Quel est le nombre de tours de boucle nécessaires ?

Exercice 4 : multiplication binaire (pour aller plus loin)

On s’intéresse à la réalisation manuelle de la multiplication de deux entiers. Il s’agit de réimplémenter l’algorithme vu à l'école primaire, mais en base 2. On écrira deux versions de cet algorithme :

  • une première utilisant l'opérateur modulo % pour tester la parité, et l'opérateur de division // ;
  • une deuxième utilisant les opérateurs bit-à-bit & et << en lieu et place de % et //.

L'opérateur & applique un AND bit-à-bit à ses deux opérandes. On peut s'en servir pour tester rapidement la parité d'un nombre, en l'appliquant sur des opérandes bien choisies. L'opérateur x >> k décale les bits du nombre x de k positions vers la droite. Autrement dit, la valeur de x est divisée par 2^k.

Dans les deux versions à écrire, on s’interdit bien sûr d'utiliser la multiplication sur les entiers sauf sur 0 et 1.

Question 1

Écrire une fonction qui renvoie un tableau dynamique contenant tous les bits d'un entier.

Question 2

Écrire une fonction qui réalise la multiplication en base 2 comme apprise à l'école primaire, de deux nombres. Combien de tours de boucles sont nécessaires ?