Lycée Marceau MPSI 2015/2016 Le lundi 29 février 2016

Devoir d'informatique no 3 (2 heures)

Ce devoir est constitué de plusieurs petits exercices. L'ordre des exercices ne correspond à aucun critère de diculté ou de
longueur : vous pouvez les traiter dans l'ordre que vous voulez. Veillez à soigner la copie tant pour l'écriture, la propreté que
pour la rédaction, la rigueur et l'argumentation. De plus, on prètera une attention particuliére au respect des alignements
et des indentations des séquences d'instructions Python. La calculatrice est interdite.
Vous numéroterez vos copies et ferez apparaître clairement sur la première page le nombre de copies.
Exercice 1
1. Ecrire une fonction factorielle prenant comme argument un entier naturel n et qui renvoie n! ( On

n'acceptera pas bien sûr de réponse utilisant la propre fonction factorielle du module math ou numpy de Python. ).
2. Ecrire une fonction seuil prenant comme argument un entier M et qui renvoie le plus petit entier
n tel que n! > M.
3. Ecrire une fonction booléenne nommée est_divisible prenant comme argument un entier naturel
n et qui renvoie True si n! est divisible par n+1 et False sinon.
4. On considère la fonction suivante nommée mystere
1 def mystere (n):
2 s = 0
3 for k in range (1 , n +1) :
4 s = s + factorielle ( k)
5 return (s )

(a) Quelle valeur renvoie mystere(4) ?

(b) Expliquer ce que fait cette fonction mystere en faisant intervenir un invariant de boucle
(c) Déterminer le nombre de multiplications qu'eectue mystere(n) ( fac-
On supposera que l'appel à

torielle(k) nécessite k multiplications ).

(d) Proposer une amélioration du script de la fonction mystere an d'obtenir une complexité
linéaire i.e en (n)

Exercice 2
La fonction mystere suivante prend comme arguments deux tableaux (à une dimension) t et s.

1 def mystere (t , s):

2 lt , ls = len (t ) , len (s)
3 if lt != ls :
4 return ( False )
5 i = 0
6 while i < lt and t[ i] == s[ ls - i - 1] :
7 i = i + 1
8 return (i == lt )

1. Que retournent les appels suivants ?

(a) mystere( [ ], [ ] )
(b) mystere([1,2,3,4], [4,3,2,1])
(c) mystere([1,2,5,4], [4,3,2,1])
(d) En général, quel est le résultat d'un appel de la fonction mystere ? Justier brievement.

2. Evaluer la complexité en temps (dans le meilleur des cas et dans le pire des cas)de la fonction mystere
1
Lycée Marceau MPSI 2015/2016 Le lundi 29 février 2016

Exercice 3
1. Soit la fonction syr suivante qui prend comme argument un entier naturel n :
1 def syr ( n):
2 k = n
3 while k >1 :
4 k = k // 2
5 return (k )

(a) Donner les suites des valeurs successives prises par la variable k lors des deux appels syr(32)
et syr(20)
(b) Quelles sont les complexités en temps dans les meilleurs et pires des cas de la fonction syr
2. Soit la fonction syrac suivante qui prend comme argument un entier naturel n :
1 def syrac (n ):
2 k = n
3 while k >1 :
4 if k % 2 == 0:
5 k = k //2
6 else :
7 k = 1
8 return (k )

(a) Donner les suites des valeurs successives prises par la variable k lors des deux appels syrac(32)
et syrac(20)
(b) Quelles sont les complexités en temps dans les meilleurs et pires des cas de la fonction syrac
3. Soit la fonction syracuse suivante qui prend comme argument un entier naturel n :
1 def syracuse (n) :
2 k = n
3 while k >1 :
4 if k % 2 == 0:
5 k = k //2
6 else :
7 k = 3* k + 1
8 return (k )

On rappelle que le probleme de savoir si en partant d'un entier naturel quelconque, on arrive
nécessairement à 1 est un probleme ouvert i.e. on ne connait pas encore de réponse à cette question.

(a) Donner les suites des valeurs successives prises par la variable k lors des deux appels syra-
cuse(32) et syracuse(20)
(b) Quelles sont les complexités en temps dans les meilleurs et pires des cas de la fonction syracuse
4. Soit la fonction syrFor suivante qui prend comme argument un entier naturel n :
1 def syrFor ( n):
2 s = 0
3 for i in range (n +1) :
4 s = s + syr (i)
5 return (s )

Quelles sont les complexités en temps dans les meilleurs et pires des cas de la fonction syrFor ?
2
Lycée Marceau MPSI 2015/2016 Le lundi 29 février 2016

Exercice 4
1. Ecrire une fonction sommeChires prenant comme argument un entier naturel n et qui renvoie
la somme des chires du nombre n (en base 10)
On veut écrire une fonction qui teste si un nombre est multiple de 9 en utilisant la propriété suivante
Un entier est multiple de 9 si et seulement si la somme de ses chires est multiple de 9.
Le principe est de répéter le calcul de la somme des chires jusqu'à obtenir un nombre d'un seul
chire.
Exemple : si on teste avec n = 9565938. On calcule la somme de chires : on trouve 45. On réitère
le processus avec 45 : on trouve 9. On s'arrête et on conclut que 9565938 est bien un multiple de 9.

estMultiplede9 prenant comme argument un entier naturel n et qui renvoie

2. Ecrire une fonction
True si c'est un multiple de 9 et False sinon, en utilisant la propriété indiquée. On n'aura pas le
droit d'utiliser les opérateurs % et / ou // dans cette question

3. Ecrire une fonctionindiceDernierMultiplede9 prenant comme argument un tableau unidimen-

sionnel t d'entiers et qui retourne le plus grand indice de t où se trouve un multiple de 9, et
retourne None si aucun multiple de p n'est présent dans le tableau t . On demande un algorithme
qui minimise le temps d'exécution dans le cas le plus favorable.

supprimerPremierMultiplede9 prenant comme argument un tableau unidi-

4. Ecrire une fonction
mensionnel t et qui renvoie le tableau obtenu à partir de t en supprimant le premier élément qui
est un multiple de 9.

Exercice 5
On veut représenter un tableau t de nombres par un autre tableau c appelé codage de t. Les suites
consécutives de valeurs identiques de t sont représentées dans c par deux nombres r,v où r est le nombre
de répétitions de la valeur v dans une telle suite. Une valeur v de t qui ne se répète pas est donc
représentée par 1, v. Une valeur v qui se répète deux fois consécutivement est représentée par 2, v, et
ainsi de suite.
Par exemple, le codage de t= [0, 0, 0, 0, 5, -2, -2, -2, 0, 0, 0, 0, 0] est c= [4, 0, 1, 5, 3, -2, 5, 0].
Un entier à un indice pair dans c représente donc un nombre de répétitions consécutives d'une valeur de
t.
1. Ecrire une fonction decoder qui prend comme argument un tableau c de longueur paire et qui
renvoie le tableau t dont c est le codage.
2. Quelle est la complexité de votre fonction decoder ? Justier la réponse
On veut écrire la fonction de codage qui prend en entrée un tableau t et renvoie son codage c.
(a) Ecrire une fonction longueurBloc prenant comme argument un tableau t et un entier pos et
qui renvoie la longueur du plus long bloc de positions consécutives du tableau t commençant à
la position pos, et composé de cases consécutives qui contiennent toutes la valeur t[pos]. Par
exemple avec t = [0, 0, 0, 0, 5, -2, -2, -2, 0, 0, 0, 0, 0], les appels longueurBloc(t, 0),
longueurBloc(t, 1), longueurBloc(t, 4), longueurBloc(t, 8) doivent retourner respec-
tivement 4, 3, 1 et 5.

(b) En utilisant la fonction longueurBloc, écrire une fonction codage prenant comme argument
un tableau t et qui renvoie le codage du tableau t.

3
Lycée Marceau MPSI 2015/2016 Le lundi 29 février 2016

CORRECTION

Exercice 1
1 def factorielle (n) : 1 def seuil (M) :
2 p = 1 2 p , n = 1, 1
3 for k in range (1 , n +1) : 3 while p <= M :
1.
4 p = p * k 2.4 n = n + 1
5 return (p ) 5 p = p * n
6 return (n )

1 def est_divisible ( n): 4. On considère la fonction suivante

2 p = factorielle ( n) 1 def mystere ( n):
3 if p %( n +1) == 0: 2 s = 0
3.4 return ( True ) 3 for k in range (1 , n +1) :
5 else : 4 s = s + factorielle ( k)
6 return ( False ) 5 return (s )

(a) mystere(4) retourne 33

(b) On reprend les noms des variables locales de la fonction mystere
. On note (un )n∈N∗ la suite
Xn
∗
dénie par : ∀n ∈ N , un = k!. Montrons que l'expression  s − uk  est un invariant de
k=1
boucle.
A la première itération dans la boucle. s vaut 0 en entrée et on lui ajoute 1! soit s vaut 1 à la
n de la première itéeration ce qui est exactement la valeur de u1 .
Hérédité. A la k + 1-ième itération, k prend la valeur k + 1, s prend la valeur s + (k + 1)! et
uk+1 = uk + (k + 1)!. Donc s − uk a la même valeur au début de l'étape k + 1 qu'à la n de
cette étape.

Ainsi s − uk est bien un invariant de boucle . Or cette expression vaut 0 en entrée :

elle vaut donc toujours 0 en sortie, soit lorsque k vaut n.
n
mystere(n) retourne un =
X
Ainsi k!
k=1

(c) Lors de l'appel mystere(n), on eectue à l'étape k, 1 addition, 1 aectation et k multiplica-

tions (en calculant factorielle(k)).

n(n + 1)
Donc au total nous eectuons n additions et multiplications
2
(d) On améliore la complexité en temps, en calculant en parallèle le produit des premiers entiers
et la somme des premières factorielles.

1 def mystererapide ( n):

2 p , s = 1, 1
3 for k in range (2 , n +1) :
4 p = p * k
5 s = s + p
6 return (s )

Exercice 2
La fonction mystere suivante prend comme arguments deux tableaux (à une dimension) t et s.

4
 Lycée Marceau MPSI 2015/2016 Le lundi 29 février 2016

1 def mystere (t , s):

2 lt , ls = len (t ) , len (s)
3 if lt != ls :
4 return ( False )
5 i = 0
6 while i < lt and t[ i] == s[ ls - i - 1] :
7 i = i + 1
8 return (i == lt )

1. Que retournent les appels suivants ?

(a) mystere( [ ], [ ] ) retourne True (b) mystere([1,2,3,4], [4,3,2,1])retourne True

(c) mystere([1,2,5,4], [4,3,2,1])retourne False

(d) La fonction prend en paramètres deux tableaux t et s, et vérie si la suite des éléments dans
t, lue du plus petit indice au plus grand indice, est la même que la suite dans des éléments
dans s lue en sens inverse
2. Dans la meilleur des cas, les tableaux ne sont pas de la même longueur et au bout d'un test, on

retourne le résultat : complexité dans le meilleur des cas : (1)

Dans le pire des cas, les tableaux sont à l'envers l'un de l'autre ou quasiment (ils diérent de leur
miroir par le dernier élément à tester). Dans ce cas, on a eectué 2 len(t) tests de len(t) additions

: complexité dans le pire des cas : (len(t))

Exercice 3
1. Soit la fonction syr suivante qui prend comme argument un entier naturel n :
1 def syr ( n):
2 k = n
3 while k >1 :
4 k = k // 2
5 return (k )

(a) Lors de l'appel syr(32), la variable k prend successivement les valeurs :

32, 16, 8, 4, 2, 1 et le retour est 1
Lors de l'appel syr(20), la variable k prend successivement les valeurs :

20, 10, 5, 2, 1 et le retour est 1

(b) Les complexités dans les pires et les meilleurs des cas pour l'appel de syr(n) sont identiques :

il s'agit de (log2 (n))

2. Soit la fonction syrac suivante qui prend comme argument un entier naturel n :
1 def syrac (n ):
2 k = n
3 while k >1 :
4 if k % 2 == 0:
5 k = k //2
6 else :
7 k = 1
8 return (k )

5
Lycée Marceau MPSI 2015/2016 Le lundi 29 février 2016

(a) Lors de l'appel syrac(32), la variable k prend successivement les valeurs :

32, 16, 8, 4, 2, 1 et le retour est 1
Lors de l'appel syrac(20), la variable k prend successivement les valeurs :

20, 10, 5, 1 et le retour est 1

(b) Dans le meilleur des cas, à savoir lorsque n est impair, la complexité est (1) .

Dans le pire des cas, à savoir lorsque n est une puissance de 2, la complexité est (log2 (n)) .

3. Soit la fonction syracuse suivante qui prend comme argument un entier naturel n :
1 def syracuse (n) :
2 k = n
3 while k >1 :
4 if k % 2 == 0:
5 k = k //2
6 else :
7 k = 3* k + 1
8 return (k )

On rappelle que le probleme de savoir si en partant d'un entier naturel quelconque, on arrive
nécessairement à 1 est un probleme ouvert i.e. on ne connait pas encore de réponse à cette question.

(a) Lors de l'appel syracuse(32), la variable k prend successivement les valeurs :

32, 16, 8, 4, 2, 1 et le retour est 1
Lors de l'appel syracuse(20), la variable k prend successivement les valeurs :

20, 10, 5, 16, 8, 4, 2, 1 et le retour est 1

(b) Dans le meilleur des cas, à savoir lorsque n est une puissance de 2, la complexité est (log2 (n))
Dans le pire des cas, la complexité est inconnue, au moins tant que le problème de savoir si la
suite nit par arriver à 1 si on part d'un entier n quelconque reste ouvert.

4. Soit la fonction syrFor suivante qui prend comme argument un entier naturel n :
1 def syrFor ( n):
2 s = 0
3 for i in range (n +1) :
4 s = s + syr (i)
5 return (s )

n
syrFor(n) nécessite
X
Dans les pires et les meilleurs des cas, l'appel à log2 (k) additions, divisions
k=1
et tests, soit une complexité de (n log2 (n))

Exercice 4
1 def sommeChiffres ( n): 1 def estMultiplede9 (n) :
2 k, s = n, 0 2 k = n
3 while k > 0: 3 while k > 9:
1.4 s = s + k % 10 4 k = sommeChiffres9 ( k)
2.
5 k = k // 10 5 if k ==9 or k == 0 :
6 return (s ) 6 return ( True )
7 else : return ( False )

6
Lycée Marceau MPSI 2015/2016 Le lundi 29 février 2016

1 def indiceDernierMultiplede9 (t ):
2 for k in range ( len ( t) -1, -1, -1) :
3 if estMultiplede9 (t [k ]) :
3.
4 return (k )
5 return ( None )

1 def supprimerPremierMultiplede9 (t ):
2 tab , c = [] , 0
3 for k in range ( len ( t)) :
4 if not estMultiplede9 (t [k ]) or c > 0 :
4.5 tab . append ( t[k ])
6 if estMultiplede9 (t [k ]) :
7 c = 1
8 return ( tab )

Exercice 5
On veut représenter un tableau t de nombres par un autre tableau c appelé codage de t. Les suites
consécutives de valeurs identiques de t sont représentées dans c par deux nombres r,v où r est le nombre
de répétitions de la valeur v dans une telle suite. Une valeur v de t qui ne se répète pas est donc
représentée par 1, v. Une valeur v qui se répète deux fois consécutivement est représentée par 2, v, et
ainsi de suite.
Par exemple, le codage de t= [0, 0, 0, 0, 5, -2, -2, -2, 0, 0, 0, 0, 0] est c= [4, 0, 1, 5, 3, -2, 5, 0].
Un entier à un indice pair dans c représente donc un nombre de répétitionsconsécutives d'une valeur de
t.
1 def decoder (c):
2 tab = []
3 for k in range ( len ( c) //2) :
4 n , val = c [2* k] , c [2* k +1]
1.
5 for k in range (n ) :
6 tab . append ( val )
7 return ( tab )

2. La complexitéde la fonction decoder est la somme des valeurs aux positions paires de c.
1 def longueurBloc (t , pos ): 1 def codage (t ):
2 c , k , n = 0, pos , len (t) 2 tab , pos , n = [] , 0 , len (t )
3 while k < n and t[k ] == t[ 3 while pos < n :
(a) pos ]: 4 p = longueurBloc (t , pos )
4 c , k = c + 1, k + 1 (b)5 tab . append ( p)
5 return (c ) 6 tab . append ( t[ pos ])
7 pos = pos + p
8 return ( tab )