Lycée Qualifiant Mohamed Reda Slaoui TSI/PCSI
Centre de CPGE Devoir surveillé Informatique
Année2013/2014 Duré 2 heures Algorithmique et programmation
N. B. : La qualité de la rédaction et la rigueur des raisonnements seront pris en compte dans la
notation.
Exercice 1
Écrire des fonctions voyelles et consonnes, prenant en argument une chaîne de caractères et
renvoyant respectivement le nombre de voyelles et le nombre de consonnes présentes dans cette
chaîne.
Exercice 2 : Calcul de la racine carré
On peut approximer une racine carré du nombre nb avec l’algorithme, écrit en pseudo-code, suivant
fonction racine_carre(nb :reel) :reel
variable r0,r1 :reel
r0 nb/2
r1(r0 +nb/r0)/2
tant que abs((r1-r0)/r0) > faire
r0 r1
r1 (r0 +nb/r0)/2
fin tant que
return r1
fin fonction
Où est un seuil de tolérance. Normalement, c’est un nombre petit, comme par exemple 0,00001.
Traduire cet algorithme en Python (fonction racine_carre(nb) qui prend en paramètre un nombre
réel positif et retourne sa racine carré).
Exercice 3
Faites le programme DevineNombre, qui génère un nombre aléatoire entre 1 et 200, et qui demande
à l’usager de deviner le nombre en moins de 8 coups.
À chaque fois que le joueur tente un nombre, vous devez dire s’il est plus petit ou plus grand que le
nombre à deviner. Le programme refera jouer l’usager tant que ce dernier ne dis pas qu’il veut
arrêter.
Remarque : pour générer un nombre aléatoire en Python on utilise le module random
import random
r=[Link](n,p) #retourne un nombre entier aléatoire entre n et p
Exemple d’exécution
Devinez le nombre! Devinez le nombre! Trop petit! 85
5 100 Devinez le nombre! Trop grand!
Trop grand! Trop grand! 60 Meilleure chance la
Devinez le nombre! Devinez le nombre! Trop petit! prochaine fois, le nombre
1 10 Devinez le nombre! était: 83
Trop petit! Trop petit! 80 Encore?
Devinez le nombre! Devinez le nombre! Trop petit! n
4 20 Devinez le nombre!
Bravo! Bien devine! Trop petit! 90
Encore? Devinez le nombre! Trop grand!
o 50 Devinez le nombre!
1
Exercice 4
● Question 1 : Écrire une procédure, appelé Escalier, qui dessine un "escalier de nombres" de taille
n (avec 1<=n<=9), où n est le nombre de marches de cet escalier sera lu au clavier.
Exemple de sortie pour n=6 :
1
12
123
1234
12345
123456
● Question 2 : Faites un programme, DessineTriangle, qui imprime des triangles isocèles de
nombres de hauteurs différentes. La hauteur sera entrée au clavier et doit être entre 1 et 9. Voici un
exemple d’exécution dans le cas où la hauteur égale à 5.
1
121
12321
1234321
123454321
Exercice 5
● Question 1 : On définit la fonction suivante :
def test(L) :
for k in range(len(L)):
if int(L[k]) % 2 != 0:
return False
return True
Indiquer la réponse que fournira Python aux lignes de commande suivantes :
a. test([2, 0, 1, 4])
b. test(2014)
c. test([2, 0, 0, 4])
d. test(“2004”)
● Question 2 : Expliquer ce que réalise la fonction « test ».
● Question 3 : Par erreur, la fonction « test » a été implémentée comme ci-dessous :
def test(L) :
for k in range(len(L)):
if L[k] % 2 != 0:
return False
return True
Indiquer la réponse que fournira Python à la ligne de commande suivante : test([2, 0, 1, 4]). Justifier
cette réponse.
● Question 4 : Expliquer ce que réalise la fonction « test » ainsi implémentée.
2
Exercice 6 : Cryptologie
La légende raconte que Jules César transmettait ses messages en décalant chaque lettre de 3
positions : A devient D, B devient E,... W devient Z, X devient A, Y devient B et Z devient C.
Les chiffres sont décalés de la même façon, les autres caractères (espaces, virgules, points...) ne sont
pas modifiés.
● Question 1 : Donner la fonction Dict_Cesar( ) qui retourne un dictionnaire dont les clés sont des
lettres de l’alphabet et dont les valeurs sont leurs codes de César.
● Question 2 : Donner la fonction Dict_Cesar_inv( ) qui retourne un dictionnaire dont les clés sont
les codes de César et dont les valeurs sont les lettres de l’alphabet.
● Question 3 : Écrire deux fonctions Chiffre_Cesar(m) et Dechiffre_Cesar(m) réalisant le
chiffrement et le déchiffrement d’un message représenté par une chaîne.
Le code de César et ses dérivés sont très simples à craquer. Il suffit de trouver la valeur du décalage
pour décoder le message.
L’idée du code de Vigénére est d’utiliser une clé de codage qui encode le décalage de chaque lettre.
Par exemple, voici comment on code le message ’RENDEZ VOUS DEMAIN’ avec la clé
’BTSSIO’. Chaque lettre de la clé indique le décalage de la lettre correspondante : A décale de 1, B
de 2... De manière générale une lettre lettre décale de ord(lettre)-ord(‘A’)+1 (voir indication ci-
dessous).
Message R E N D E Z V O U S D E M A I N
Clé B T S S I O B T S S I O B T S S I O
Code T Y G W N O P H N B F Y F T R C
● Question 4 : Donner la fonction codage(lettre, cle) qui permet de retourner le code d’un caractère
passé en paramètre par rapport à un autre représentant la clé.
Exemple codage(‘R’,’B’) ‘T’ codage(‘U’,’S’) ‘N’
● Question 5 : Donner la fonction decodage(code, cle) qui permet de retourner la lettre
correspondante à u code donné.
Exemple decodage(‘T’,’B’) R decodage (‘N’,’S’) ‘U’
● Question 6 : Écrire une fonction chiffrement_vigenere(m, k) et une fonction
dechiffrement_vigenere(c, k) qui respectivement chiffre un message m et déchiffre un chiffré c par
le procédé de Vigenère avec la clé k.
Indication : la fonction ord (et chr) permet d’obtenir le code ASCII d’un caractère (et
réciproquement). On s’assurera que les messages et clés sont en majuscules, le type chaîne de
caractère disposant des méthodes upper et lower pour changer la casse d’une chaîne.
Exemple : Pour décaler le caractère ‘A’ par 2 on écrit : chr(ord(‘A’)+2)