Algorithmique et Programmation 1

CC final – 7/01/2021

Algorithmique et Programmation 1

Contrôle Continu final

7 janvier 2021 – Durée 1h30
4 pages (recto-verso)
CORRECTION

• Aucun document n’est autorisé

• Aucun matériel électronique n’est autorisé - Les téléphones sont formellement interdits
• Le barême est donné à titre indicatif et peut être modifié
• Ce sujet comporte 4 exercices, qui sont tous indépendants
• Au sein d’un même exercice, il est possible d’utiliser les fonctions qui sont l’objet des questions
précédentes, même si vous n’avez pas répondu à ces questions.
• Il est nécessaire de donner la chaı̂ne de documentation, comprenant la signature, de toute
fonction écrite
• N’oubliez pas de bien indiquer l’indentation de vos fonctions !
• Prenez le temps de bien lire l’énoncé !
 Algorithmique et Programmation 1
CC final – 7/01/2021

Exercice 1 (2 points) - Suite d’instructions

Quelles sont les valeurs des variables x, y, z et t à la fin de l’exécution des instructions suivantes ?
1 x, y = 3, 1
2
3 for i in range(5):
4 y = 2*x
5
6 t, x = x+1, x+y
7
8 for j in range(1,7,2):
9 if j%3 == 0 :
10 x = x-1
11 else :
12 x = x+2
13
14 z = "AB"
15 if ((x > y) or (x < y)):
16 z = z*t
17 else :
18 z = z+z

2 points (0.5 point chaque) – x = 12, y = 6, z = ”ABABABAB”, t = 4

Exercice 2 (2 points) - Comprendre et analyser un code en Python On considère la fonction

foo dont la définition est donnée ci-dessous.
1 def foo(a):
2 """Mystere"""
3 s = 0
4 if a%2 == 0 :
5 for i in range(2, a+1, 2):
6 s = s + i
7 else :
8 for i in range(1, a+1, 2) :
9 s = s + i
10 return s

1. Que retournent foo(5) et foo(8) ?

1 point, 0.5 chaque appel

foo(5) retourne 9 ; foo(8) retourne 20

2. Expliquer ce que fait cette fonction, et donner sa signature

1 point, 0.5 l’explication et 0.5 la signature
Si a est pair, cette fonction aditionne les nombres pairs compris entre 2 et a inclus ; si a
est impair, elle aditionne les nombres impairs compris entre 1 et a inclus.
Signature : Int –> Int
Algorithmique et Programmation 1
CC final – 7/01/2021

Exercice 3 (11 points) - Ecrire des fonctions en Python

Dans cet exercice, nous allons utiliser des listes d’entiers pour représenter des ensembles d’entiers.
On rappelle que dans un ensemble, un élément n’appartient pas deux fois.
La liste de taille 0 représente l’ensemble vide.

Pour chaque question, il vous est possible d’utiliser les fonctions qui sont l’objet des questions
précédentes, même si vous n’avez pas répondu à ces questions.
La chaine de documentation (y compris la signature) de chaque fonction sera notée, n’oubliez
donc pas de la préciser pour chaque fonction !

Attention, il est interdit d’utiliser le type prédéfini set dans la totalité de cet exercice.

L’ensemble de ces questions peuvent être répondues avec des fonctions ou des procédures,
en utilisant le fait que les listes sont mutables. Les deux solutions sont acceptées, mais
il faudra faire attention que les appels sont cohérents avec les définitions précedemment
données.
Chaines de documentation et signatures des fonctions doivent être ajoutées pour chaque
fonction.

1. Définir la fonction est_ensemble(liste) qui vérifie si une liste d’entiers liste est un
ensemble (c’est à dire, si une liste d’entiers ne contient pas du doublon).
# Il y a plusieurs solutions possibles
# Le bareme est le suivant : 2.5 points au total
# 0.5 pour la chaine de documentation + signature
# 2 pour le reste de la fonction

def est_ensemble(l) :
"""List --> Bool
Retourne Vrai si la liste l est un ensemble, Faux sinon"""
n = len(l)
if n == 0:
return True
else :
i = 0
ens = True
while i < n and ens :
if l[i] in l[i+1:n] :
ens = False
i = i +1
return ens
Algorithmique et Programmation 1
CC final – 7/01/2021

2. Définir la fonction transforme_ens(liste) qui, étant donné une liste d’entiers, vérifie si
c’est un ensemble, et si non supprime les doublons pour retourner un ensemble.
# Il y a plusieurs solutions possibles (boucle while, compréhension de listes...)
# Le bareme est le suivant : 2 points au total
# 0.5 pour la chaine de documentation + signature
# 1.5 pour la fonction

def transforme_ens(liste) :
"""List --> List
Vérifie si la liste est un ensemble, et supprime les doublons si non"""
if est_ensemble(liste) :
return liste
else :
ens = []
for i in liste :
if i not in ens :
ens.append(i)
return ens

3. Définir la fonction ajoute_ens(ens, elem) qui, étant donné un liste d’entiers ens, re-
tourne un ensemble auquel est ajouté l’entier elem si il n’apparait pas déjà dans ens.
# Il y a plusieurs solutions possibles (tester d’abord si c’est un ensemble,
# ajouter l’élément puis transformer en ensemble, faire une procédure...)
# Le bareme est le suivant : 2 point au total
# 0.5 pour la chaine de documentation + signature
# 1.5 pour la fonction

def ajoute_ens(ens, elem) :

"""List x Int --> List
Ajoute l’élément elem à l’ensemble ens si et seulement si il n’apparait pas déjà"""
ens.append(elem)
return transforme_ens(ens)

4. Définir la fonction intersection(ens1, ens2) qui, étant deux listes d’entiers représen-
tant des ensembles, retourne un ensemble correspondant à l’intersection de ens1 et ens2 (et
donc les entiers communs aux deux ensembles).
# Le bareme est le suivant : 2 points au total
# 0.5 pour la chaine de documentation + signature
# 1.5 pour la fonction

def intersection(ens1, ens2) :

"""List x List --> List
Retourne l’intersection de deux ensembles’"""
inter = []
for i in ens1 :
if i in ens2 :
inter.append(i)
return transforme_ens(inter)
Algorithmique et Programmation 1
CC final – 7/01/2021

5. Définir la fonction egal_ensemble(ens1, ens2) qui vérifie si deux listes d’entiers repré-
sentent le même ensemble (quel que soit l’ordre des éléments dans les listes).
# Il y a plusieurs solutions possibles (encore et toujours)
# Le bareme est le suivant : 2.5 points au total
# 0.5 pour la chaine de documentation + signature
# 2 pour la fonction

def egal_ensemble(ens1, ens2) :

"""List x List --> Bool
Retourne True si les deux ensembles sont égaux, False sinon’"""
ens1 = transforme_ens(ens1)
ens2 = transforme_ens(ens2)
egal = True
if len(ens1) == len(ens2) :
i = 0
while i < len(ens1) and egal :
if ens1[i] not in ens2 :
egal = False
i = i+1
else :
egal = False
return egal
 Algorithmique et Programmation 1
CC final – 7/01/2021

Exercice 4 (5 points) - Algorithmique et complexité

Soit la fonction tous_pairs suivante :
1 def tous_pairs(liste):
2 """List --> Bool
3 Vérifie si tous les éléments de la liste sont pairs"""
4 pairs = True
5 i = 0
6 n = len(liste)
7 while i < n and pairs:
8 if liste[i] % 2 != 0 :
9 pairs = False
10 i = i + 1
11 return pairs

1. Pour chacun des appels suivant, dire (1) que retourne la fonction, et (2) combien de tours dans
la boucle while sont effectués (c’est à dire, combien de fois la condition de boucle est-elle
vraie ?)
(a) tous_pairs([2, 6, 12, 4])
(b) tous_pairs([2, 9, 12, 4])

2 points (0.5 point chaque réponse)

(a) True, 4 tours dans la boucle
(b) False, 2 tours dans la boucle

Pour les deux questions suivantes, vous utiliserez comme mesure de complexité le nombre de com-
paraisons effectuées sur les éléments de la liste, de longueur n (supposé grand), en ligne 8.
2. Calculez la complexité dans le meilleur cas de cet algorithme

1.5 points Meilleur cas : liste[0] % 2 == 0 ; 1 comparaison

3. Calculez la complexité dans le pire cas de cet algorithme

1.5 points Pire cas : tous les éléments de la liste sont pairs : n comparaisons