Devoir de synthèse n°1 : tri par insertion, gestion d'un stock, chiffre de César

Exercice 1 : tri par insertion (6 pts)

Le tri par insertion fait grandir une partie triée au début du tableau : à chaque tour, on prend l'élément suivant et on le glisse à sa place parmi les éléments déjà triés, en décalant vers la droite ceux qui sont plus grands.

On considère la procédure suivante et son appel.

def inserer(T, n):
    for i in range(1, n):
        x = T[i]
        j = i - 1
        while j >= 0 and T[j] > x:
            T[j + 1] = T[j]
            j = j - 1
        T[j + 1] = x
        print(T[:n])

T = [7, 3, 5, 1]
inserer(T, 4)

• 1) Donner l'affichage obtenu (2 pts).
• 2) Combien de décalages (exécutions de T[j + 1] = T[j]) sont faits au total pour ce tableau ? Que vaut ce nombre pour un tableau trié à l'envers de n éléments ? (2 pts)
• 3) Pourquoi la condition est-elle écrite j >= 0 and T[j] > x et pas T[j] > x and j >= 0 ? Que se passe-t-il si on inverse ? (2 pts)

Exercice 2 : gestion d'un stock (8 pts)

Un magasin garde son stock dans deux tableaux de même taille : noms (les noms des produits) et qtes (leurs quantités). On utilise n cases.

• 1) Écrire la procédure Saisir(noms, qtes, n) qui lit les n produits : pour chacun, d'abord le nom puis la quantité (1,5 pt).
• 2) Écrire la procédure Afficher(noms, qtes, n) qui affiche une ligne « nom quantité » par produit (1 pt).
• 3) Écrire la fonction IndiceMax(qtes, n) qui renvoie l'indice de la plus grande quantité (1,5 pt).
• 4) Écrire la fonction Supprimer(noms, qtes, n, nom) qui supprime le produit de ce nom en décalant les suivants, et renvoie le nouveau nombre de produits (le même n si le nom n'existe pas) (2 pts).
• 5) Écrire le programme principal (2 pts) : il lit n, saisit les produits, affiche le stock, affiche le produit le plus fourni, lit un nom à supprimer, puis affiche le stock mis à jour ou « Produit introuvable ».

Exemple : pour 3 produits Huile 12, Sucre 40, Farine 25 et le nom à supprimer Huile, le programme affiche :

Stock :
Huile 12
Sucre 40
Farine 25
Plus grand stock : Sucre (40)
Après suppression de Huile :
Sucre 40
Farine 25

Exercice 3 : le chiffre de César (6 pts)

Le chiffre de César remplace chaque lettre par celle qui se trouve k places plus loin dans l'alphabet (en revenant au début après z). Les majuscules restent des majuscules, les minuscules des minuscules, et tous les autres caractères (espaces, chiffres, ponctuation) ne changent pas. Exemple avec k = 3 : « Bizerte » devient « Elchuwh ».

• 1) Écrire la fonction Decaler(ch, k) qui renvoie ch dont chaque lettre est décalée de k places (2,5 pts). On rappelle que ord(c) donne le code d'un caractère et chr(code) le caractère de ce code.
• 2) Comment déchiffrer un message ? En déduire la fonction Dechiffrer (1 pt).
• 3) Écrire un programme qui lit un message puis une clé k (1 ≤ k ≤ 25), affiche le message chiffré puis le message déchiffré (2,5 pts).

Pour « Bizerte » et k = 3, le programme affiche :

Elchuwh
Bizerte