Crypter un message – Bac théorique – Section informatique – 2019
Sujet (Algo et programmation - Bac 2019)
Parmi les méthodes de chiffrement utilisant un mot-clé, on cite celle décrite ci-après qui permet de crypter un message msg ne dépassant pas 18 caractères et formé uniquement de lettres minuscules, de chiffres et d'espaces :
Etape1 : Remplir aléatoirement une matrice carrée Ml de dimension 6x6 par toutes les lettres alphabétiques minuscules ainsi que tous les chiffres.
NB :Les indices des lignes et des colonnes de la matrice M1 sont les lettres A, B, C, D, E et F.
Etape2 : Générer un message intermédiaire msgi, en concaténant les résultats du chiffrement de chaque caractère du message msg. Le résultat du chiffrement d'un caractère est la concaténation de l'indice de la ligne avec J'indice de la colonne de la case contenant le caractère à chiffrer.
Le caractère espace ne sera pas chiffré.
Etape3 :Remplir une deuxième matrice M2 de taille 7x6 caractères en mettant dans :
la première ligne, les lettres d'un mot-clé formé de 6 lettres majuscules,
le reste des lignes, Je message msgi caractère par caractère en commençant par la première case de la deuxième
NB :Chaque case vide de la matrice M2 sera rem pl ie par le caractère espace.
Etape4 : Trier les éléments de la première ligne de M2 scion un ordre alphabétique croissant, sachant que tout déplacement d'un élément entraîne le déplacement de tous les éléments de la colonne correspondante.
Etape5 : Concaténer les lettres de la matrice M2, colonne par colonne en commençant par la 1ère colonne et sans considérer les éléments de la lere ligne, pour obtenir le message, chiffré final.
Exemple :
Pour msg = "promotion bac 2019" et le mot-clé "CHAISE"
Etape 1 :La matrice M1 est remplie aléatoirement comme suit :
Etape 5 :
Le message chiffré final est "FAAECFDBC AACCEAC ABAB BBCCCDFABFCD "
Travail demandé
On se propose d'écrire un programme permettant :
- de saisir un message msg ne dépassant pas 18 caractères et formé uniquement de lettres minuscules, de chiffres et d'espaces.
- de saisir un mot-clé formé de 6 lettres
- de crypter le message msg selon la méthode de chiffrement décrite précédemment.
NB : On dispose d'un module Initialisation(Ml) qui permet de remplir aléatoirement la matrice carrée Ml comme décrit dans l'étape 1 et que le candidat peut appeler dans sa solution sans le développer.
1. Analyser le problème en le décomposant en modules.
2. Ecrire les algorithmes des modules envisagés.
Solution Algorithmique
Dans cet algorithme, On va utiliser deux fonctions et trois procédures:
- la procédure remplir_matrice_m1()
- la procédure factoriel_premiers()
- la fonction calcul_ppcm()
- la procédure remplir_fichier()
- la procédure afficher_fichier()
Algorithme du programme Principal
|
1 2 3 4 5 6 |
Algorithme CalcPPCM Debut n <- saisie(2, 100) # Nombre de calculs PPCM remplir_fichier(n) # Remplissage du fichier afficher_fichier() # Affichage du contenu Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction saisie
Cette fonction permet de saisir un entier valide compris entre deux bornes inf et sup.
1- Elle demande à l’utilisateur de saisir un entier n.
2- Elle vérifie que n appartient à l’intervalle [𝑖𝑛𝑓,𝑠𝑢𝑝]
3- Si la valeur saisie n’est pas valide, la fonction redemande la saisie jusqu’à obtenir un entier correct.
4- Elle retourne finalement la valeur valide saisie par l’utilisateur.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Fonction saisie():entier # Saisie initiale Ecrire('donner n tel que ' ,inf , '<= n <= ' , sup, ': ') Lire(n) # Répéter la saisie tant que n n'est pas valide Tant que Non(inf <= n <= sup) faire Ecrire('donner n tel que ' ,inf , '<= n <= ' , sup, ': ') Lire(n) Fin tant que # Retourner la valeur correcte retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La procédure factoriel_premiers
Cette procédure permet de décomposer un nombre entier n en facteurs premiers et de stocker ces facteurs dans le tableau t.
1- Le tableau t est d’abord initialisé à 0 pour effacer les anciennes valeurs.
2- On commence la recherche des diviseurs à partir de 2, le plus petit nombre premier.
3- Tant que n est différent de 1 :
Si i divise n, alors : i est un facteur premier de n. Alors on divise n par i et on stocke i dans le tableau t
Sinon, on passe au diviseur suivant.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Procedure factoriel_premiers(n:entier, t:tableau): index <- 0 # Indice du tableau t # Initialisation du tableau t à 0 Pour k de 0 à 49 faire t[k] <- 0 Fin pour i <- 2 # Premier diviseur possible # Décomposition en facteurs premiers Tant que n != 1 faire Si n mod i = 0 alors n <- n div i t[index] <- i index <- index + 1 Sinon i <- i + 1 Fin si Fin tant que Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| index | entier |
| k | entier |
| i | entier |
La fonction calcul_ppcm
Cette fonction permet de calculer le Plus Petit Commun Multiple (PPCM) de deux nombres à partir de leurs facteurs premiers stockés dans les tableaux t1 et t2.
Principe de fonctionnement
1- Initialisation
i = 0 : sert à parcourir les deux tableaux.
ppcm = 1 : variable qui contiendra le PPCM final.
2- Parcours simultané des deux tableaux
Tant qu’on a des facteurs dans les deux tableaux (t1[i] != 0 et t2[i] != 0) :
Si les facteurs sont identiques, on multiplie le PPCM par ce facteur. Sinon, on multiplie le PPCM par les deux facteurs différents.
L’indice i est incrémenté pour passer au facteur suivant.
3- Ajout des facteurs restants
Si un tableau a encore des facteurs après la fin du parcours commun, on les multiplie au PPCM :
Tant que t1[i] != 0 → multiplie le PPCM par les facteurs restants de t1.
Tant que t2[i] != 0 → multiplie le PPCM par les facteurs restants de t2.
4- Retour du résultat
La fonction retourne la valeur finale du PPCM.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
Fonction calcul_ppcm(t1:tableau;t2:tableau i <- 0 ppcm <- 1 # Parcours simultané des deux tableaux Tant que t1[i] != 0 et t2[i] != 0 faire Si t1[i] = t2[i] alors ppcm <- ppcm * t1[i] Sinon a <- t1[i] b <- t2[i] ppcm <- ppcm * a * b Fin si i <- i + 1 Fin tant que # Ajout des facteurs restants de t1 Tant que t1[i] != 0 faire ppcm <- ppcm * t1[i] i <- i + 1 Fin tant que # Ajout des facteurs restants de t2 Tant que t2[i] != 0 faire ppcm <- ppcm * t2[i] i <- i + 1 Fin tant que retourner ppcm Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| ppcm | entier |
La procédure remplir_fichier
Cette procédure sert à remplir un fichier nommé F_PPCM.dat avec le PPCM de plusieurs couples de nombres saisis par l’utilisateur.
1- Affichage d’un message d’information
Il indique à l’utilisateur que le fichier va être rempli.
2- Ouverture du fichier
Le fichier est ouvert en mode écriture ("w").
Si le fichier existe déjà, son contenu est effacé.
3- Saisie des couples de nombres :
La procédure demande à l’utilisateur de saisir n couples de nombres.
La fonction saisie garantit que les nombres sont compris entre 1 et 1000.
4- Décomposition en facteurs premiers
Chaque nombre est décomposé en facteurs premiers.
Les facteurs sont stockés dans les tableaux t1 et t2.
5- Calcul du PPCM
La procédure utilise la fonction calcul_ppcm pour obtenir le PPCM du couple.
6- Écriture dans le fichier
Chaque résultat est écrit dans le fichier sous la forme : PPCM(a, b) = résultat
7- Fermeture du fichier
La procédure libère le fichier et sauvegarde toutes les données.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Procedure remplir_fichier(n:entier) Ecrire('*** Remplir fichier F_PPCM.dat ***') # Ouverture du fichier en mode écriture Ouvri(f , "F_PPCM.dat", "w") # Saisie de n couples de nombres Pour i de 0 à n-1 faire a <- saisie(1, 1000) b <- saisie(1, 1000) # Décomposition en facteurs premiers factoriel_premiers(a, t1) factoriel_premiers(b, t2) # Calcul du PPCM ppcm <- calcul_ppcm(t1, t2) # Écriture du résultat dans le fichier Ecrire(f , 'PPCM(' + Convch(a) + ',' + Convch(b) + ') = ' + Convch(ppcm) + '\n') Fin pour # Fermeture du fichier Fermer(f) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| a | entier |
| b | entier |
| ppcm | entier |
| t1 | tableau |
| t2 | tableau |
| f | fichier |
La procédure afficher_fichier
Cette procédure sert à lire et afficher le contenu du fichier F_PPCM.dat créé précédemment, pour que l’utilisateur puisse voir les résultats des calculs de PPCM.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Procédure afficher_fichier() Ecrire('*** Contenu fichier F_PPCM.dat ***') # Ouverture du fichier en mode lecture Ouvri(f , "F_PPCM.dat", "r") lignes <- Lire_lignes(f) # Affichage de chaque ligne Pour ligne dans lignes faire Ecrire(ligne) Fin pour # Fermeture du fichier Fermer(f) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | fichier |
| lignes | chaîne |
| ligne | chaîne |
Solution en Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 |
from numpy import * # -------------------------------------------------- # Déclaration de deux tableaux de taille 50 # Ils serviront à stocker les facteurs premiers # -------------------------------------------------- t1 = array([int()] * 50) t2 = array([int()] * 50) # -------------------------------------------------- # Fonction de saisie sécurisée # Elle force l'utilisateur à saisir un entier # compris entre inf et sup # -------------------------------------------------- def saisie(inf, sup): # Saisie initiale n = int(input('donner un nombre entre ' + str(inf) + ' et ' + str(sup) + ' : ')) # Vérification de la validité de la saisie while not (inf <= n <= sup): n = int(input('donner un nombre entre ' + str(inf) + ' et ' + str(sup) + ' : ')) # Retour de la valeur valide return n # -------------------------------------------------- # Procédure qui décompose un nombre n # en facteurs premiers # Les facteurs sont stockés dans le tableau t # -------------------------------------------------- def factoriel_premiers(n, t): index = 0 # Indice du tableau t # Initialisation du tableau t à 0 for k in range(50): t[k] = 0 i = 2 # Premier diviseur possible # Décomposition en facteurs premiers while n != 1: if n % i == 0: n = n // i t[index] = i index = index + 1 else: i = i + 1 # -------------------------------------------------- # Fonction qui calcule le PPCM de deux nombres # à partir de leurs facteurs premiers stockés # dans t1 et t2 # -------------------------------------------------- def calcul_ppcm(t1, t2): i = 0 ppcm = 1 # Parcours simultané des deux tableaux while t1[i] != 0 and t2[i] != 0: if t1[i] == t2[i]: ppcm = ppcm * t1[i] else: a = t1[i] b = t2[i] ppcm = ppcm * a * b i = i + 1 # Ajout des facteurs restants de t1 while t1[i] != 0: ppcm = ppcm * t1[i] i = i + 1 # Ajout des facteurs restants de t2 while t2[i] != 0: ppcm = ppcm * t2[i] i = i + 1 return ppcm # -------------------------------------------------- # Procédure qui remplit le fichier F_PPCM.dat # avec les PPCM de couples de nombres saisis # -------------------------------------------------- def remplir_fichier(n): print('*** Remplir fichier F_PPCM.dat ***') # Ouverture du fichier en mode écriture f = open("F_PPCM.dat", "w") # Saisie de n couples de nombres for i in range(n): a = saisie(1, 1000) b = saisie(1, 1000) # Décomposition en facteurs premiers factoriel_premiers(a, t1) factoriel_premiers(b, t2) # Calcul du PPCM ppcm = calcul_ppcm(t1, t2) # Écriture du résultat dans le fichier f.write('PPCM(' + str(a) + ',' + str(b) + ') = ' + str(ppcm) + '\n') # Fermeture du fichier f.close() # -------------------------------------------------- # Procédure qui affiche le contenu du fichier # F_PPCM.dat # -------------------------------------------------- def afficher_fichier(): print('*** Contenu fichier F_PPCM.dat ***') # Ouverture du fichier en mode lecture f = open("F_PPCM.dat", "r") lignes = f.readlines() # Affichage de chaque ligne for ligne in lignes: print(ligne.strip('\n')) # Fermeture du fichiera f.close() # -------------------------------------------------- # Programme principal # -------------------------------------------------- n = saisie(2, 100) # Nombre de calculs PPCM remplir_fichier(n) # Remplissage du fichier afficher_fichier() # Affichage du contenu |
Exécution du programme
0 commentaire
laisser un commentaire
Passion de robotique
Tutoriels récents
Atelier robotique
Tutoriels populaires
Construction des robots
Tutoriels plus commentés
Bras robotique
Categories
Maison intelligente
