Matrice – Bac pratique – Section informatique – 2013
Sujet (Algo et programmation - Bac 2013)
On se propose de chercher dans une matrice M, les plus longues séquences d'éléments juxtaposés dont la somme est égale à zéro, en procédant comme suit :
Exemple:
Pour la matrice M de dimension 5x6 suivante :
Dans la lère ligne, il y a 2 séquences d'éléments juxtaposés dont la somme est égale à 0 :
- La séquence ayant comme ICD la valeur 1 et comme ICF la valeur 5.
- La séquence ayant comme ICD la valeur 3 et comme ICF la valeur 6.
Dans la 2ème ligne, il y a une seule séquence d'éléments juxtaposés dont la somme est égale à 0, la séquence ayant comme ICD la valeur 1 et comme ICF la valeur 4.
Dans la 3eme ligne, il y a une seule séquence d'éléments juxtaposés dont la somme est égale à 0, la séquence ayant comme ICD la valeur 2 et comme ICF la valeur 6.
Dans la 4eme ligne, il n'y a aucune séquence d'éléments juxtaposés dont la somme est égale à O.
Dans la Sème ligne, il y a une seule séquence d'éléments juxtaposés dont la somme est égale à 0, la séquence ayant comme ICD la valeur 1 et comme ICF la valeur.
Travail demandé
Ecrire un programme en Python intitulé Sequence qui permet, à partir d'une matrice M de dimension LxC, de remplir un tableau T et de créer un fichier "Long_Seq.txt", comme décrit précédemment.
Solution Algorithmique
Dans cet algorithme, On va utiliser trois fonctions et cinq procédures:
- la fonction saisie()
- la fonction saisie_element()
- la procédure remplir_matrice()
- la procédure afficher_matrice()
- la fonction verif_juxtapose()
- la procédure remplir_tableau()
- la procédure afficher_tableau()
- la procédure remplir_fichier_long_seq()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Algorithme Sequence Debut Ecrire('*** Saisie du nombre des lignes et de colonnes ***') # Saisie du nombre de lignes et de colonnes l <- saisie(0, 23) c <- saisie(2, 23) # Initialisation des variables globales longueur_tableau <- 0 max_sequence <- 0 # Appels des différentes fonctions remplir_matrice(m, l, c) afficher_matrice(m, l, c) remplir_tableau(t, m, l, c) afficher_tableau(t, longueur_tableau) remplir_fichier_long_seq(t, longueur_tableau, max_sequence) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| l | entier |
| c | entier |
| m | matrice |
| t | tableau |
La fonction saisie
La fonction saisie(inf, sup) permet de demander à l’utilisateur de saisir un entier strictement compris entre deux bornes inf et sup.
Plus précisément :
- La fonction affiche un message demandant un entier n tel que inf < n < sup. - Si la valeur saisie n’est pas dans l’intervalle ouvert ]inf, sup[, la saisie est redemandée. - La saisie est répétée tant que la condition n’est pas respectée. - Lorsque l’utilisateur entre enfin une valeur correcte, la fonction retourne cet entier.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Fonction saisie():entier # Demande à l'utilisateur de saisir un entier n Ecrire('donner n tel que ' + inf + '< n < ' + sup + ': ') Lire(n) # Tant que n n'appartient pas à l'intervalle ]inf , sup[ # on redemande la saisie Tant que (n <= inf) ou (n >= sup) faire Ecrire('donner n tel que ' + inf + '< n < ' + sup + ': ') Lire(n) Fin tant que # Retourne la valeur correcte saisie retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction supprimer_espaces
La fonction supprimer_espaces(ch) a pour rôle est de nettoyer une chaîne de caractères en supprimant les espaces inutiles.
Plus précisément, la fonction :
- Supprime les espaces au début de la chaîne.
- Supprime les espaces à la fin de la chaîne.
- Remplace les espaces doubles (ou multiples) à l’intérieur de la chaîne par un seul espace.
- Retourne la chaîne corrigée après nettoyage.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Fonction supprimer_espaces(ch:chaine):booleen # Supprimer les espaces au début de la chaîne Tant que ch[0] = ' ' faire ch <- Sous_chaine(ch ,1 , long(ch)] Fin tant que # Supprimer les espaces à la fin de la chaîne Tant que ch[long(ch)-1] = ' ' faire ch <- Sous_chaine(ch , 0, long(ch)-1] Fin tant que # Remplacer les doubles espaces par un seul espace Tant que Pos(ch,' ') > 0 faire ch <- ch.replace(" ", " ") Fin tant que # Retourner la chaîne nettoyée retourner ch Fin |
La fonction verif_phrase
La fonction verif_phrase(ch) a pour le rôle est de vérifier qu’une phrase ne contient que des lettres alphabétiques et des espaces.
Plus précisément :
1- La fonction parcourt la chaîne de caractères ch caractère par caractère.
2- Pour chaque caractère, elle vérifie s’il s’agit : d’une lettre alphabétique (majuscule ou minuscule) ou d’un espace.
3- Si tous les caractères respectent cette condition, la fonction retourne Vrai.
4- Si au moins un caractère non autorisé est rencontré, la fonction retourne Faux.
|
1 2 3 4 5 6 7 8 9 |
Fonction verif_phrase(ch:chaine):booleen i <- 0 # Parcourir la chaîne tant que les caractères sont valides Tant que (i < long(ch)-1) et (('A' <= Majus(ch[i])<= 'Z') ou ch[i] = ' ') faire i <- i + 1 Fin tant que # Retourne Vrai si le dernier caractère est valide retourner (('A' <= Majus(ch[i]) <= 'Z') ou ch[i] = ' ') Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
La fonction saisie_phrase()
La fonction saisie_phrase() a pour rôle est de permettre à l’utilisateur de saisir une phrase valide, après nettoyage.
Plus précisément :
1- La fonction demande à l’utilisateur de saisir une phrase.
2- Elle supprime les espaces inutiles (au début, à la fin et les espaces doubles) grâce à la fonction supprimer_espaces.
3- Elle vérifie ensuite que la phrase est valide (ne contient que des lettres et des espaces) à l’aide de la fonction verif_phrase.
4- Tant que la phrase contient des caractères non autorisés, la saisie est redemandée et nettoyée à nouveau.
5- Lorsque la phrase est valide, la fonction retourne la phrase correcte.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Fonction saisie_phrase(): chaine # Saisie d'une phrase par l'utilisateur Ecrire('donner une phrase: ') Lire(phrase) # Suppression des espaces inutiles phrase <- supprimer_espaces(phrase) # Tant que la phrase contient des caractères invalides # on redemande la saisie Tant que verif_phrase(phrase) = Faux faire # Saisie d'une phrase par l'utilisateur Ecrire('donner une phrase: ') Lire(phrase) # Suppression des espaces inutiles phrase <- supprimer_espaces(phrase) Fin tant que # Retourner la phrase valide retourner phrase Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| phrase | chaîne |
La procédure remplir_fichier_phrases
La procédure remplir_fichier_phrases(n) a pour rôle est de créer et remplir le fichier phrases.txt avec n phrases saisies par l’utilisateur.
Plus précisément :
1- La procédure affiche un message indiquant le début du remplissage du fichier.
2- Elle ouvre le fichier phrases.txt en mode écriture.
3- Elle répète n fois :
- la saisie d’une phrase valide à l’aide de la fonction saisie_phrase,
- l’écriture de cette phrase dans le fichier, une phrase par ligne.
4- Enfin, elle ferme le fichier.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Procédure remplir_fichier_phrases(n:entier) Ecrire('****** Remplissage fichier phrases.txt ******') # Ouvrir le fichier en mode écriture Ouvrir(f , "phrases.txt", "w") Pour i de 0 à n-1 faire phrase <- saisie_phrase() # Écriture de la phrase dans le fichier Ecrire(f , phrase + '\n') Fin pour # Fermer le fichier Fermer(f) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | fichier |
| phrase | chaîne |
La fonction crypter_caractere()
La fonction crypter_caractere(c, p) a pour rôle est de chiffrer un caractère alphabétique en utilisant le chiffrement de César, par décalage de p positions dans l’alphabet.
Plus précisément :
1- Si le caractère c est une lettre majuscule (A à Z), la fonction décale sa position de p lettres vers l’avant dans l’alphabet, en revenant au début si nécessaire.
2- Si le caractère c est une lettre minuscule (a à z), le même principe de décalage est appliqué.
3- Le décalage est circulaire : après Z on revient à A, et après z on revient à a.
4- La fonction retourne le caractère chiffré correspondant.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Fonction crypter_caractere(c:caractere,p:entier): caractere # Cas d'une lettre majuscule Si 'A' <= c <= 'Z' alors Si ord(c) + p <= 90 alors retourner chr(ord(c) + p) Sinon retourner chr(ord(c) + p - 26) Fin si # Cas d'une lettre minuscule Sinon Si ord(c) + p <= 122 alors retourner chr(ord(c) + p) Sinon retourner chr(ord(c) + p - 26) Fin si Fin si Fin |
La procédure remplir_fichier_ph_crypt
La procédure remplir_fichier_phrases(n) a pour rôle est de créer et remplir le fichier phrases.txt avec n phrases saisies par l’utilisateur.
Plus précisément :
1- La procédure affiche un message indiquant le début du remplissage du fichier.
2- Elle ouvre le fichier phrases.txt en mode écriture.
3- Elle répète n fois :
- la saisie d’une phrase valide à l’aide de la fonction saisie_phrase,
- l’écriture de cette phrase dans le fichier, une phrase par ligne.
4- Enfin, elle ferme le fichier.
|
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 |
Procédure remplir_fichier_ph_crypt() Ecrire('****** Fichier ph_crypt.txt ******') # Ouvrir le fichier source en lecture Ouvrir( f_phrases , "phrases.txt", "r") # Ouvrir le fichier destination en écriture Ouvrir( f_phr_crypt , "ph_crypt.txt", "w") # Lire toutes les phrases du fichier phrases <-Lire_lignes(f_phrases) Pour phrase dans phrases faire # Supprimer le retour à la ligne phrase <- phrase.rstrip('\n') p <- 1 # pas de décalage # Parcourir chaque caractère de la phrase Pour i de 0 à long(phrase)-1 fiare Si phrase[i] != ' ': caractere <- crypter_caractere(phrase[i], p) Sinon # Incrémenter le décalage après chaque espace p <- p + 1 caractere <- ' ' Fin si # Affichage à l'écran Ecrire(caractere) # Écriture dans le fichier crypté Ecrire(f_phr_crypt , caractere) Fin pour Ecrire() Ecrire(f_phr_crypt,'\n') Fin pour # Fermer les fichiers Fermer(f_phrases) Fermer(f_phr_crypt) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f_phrases | fichier |
| f_phr_crypt | fichier |
| phrases | chaîne |
| phrase | chaîne |
| i | entier |
| p | entier |
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 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 |
# -------------------------------------------------- # Fonction qui permet de saisir un entier n # compris strictement entre inf et sup # -------------------------------------------------- def saisie(inf, sup): # Demande à l'utilisateur de saisir un entier n n = int(input('donner n tel que ' + str(inf) + '< n < ' + str(sup) + ': ')) # Tant que n n'appartient pas à l'intervalle ]inf , sup[ # on redemande la saisie while (n <= inf) or (n >= sup): n = int(input('donner n tel que ' + str(inf) + '< n < ' + str(sup) + ': ')) # Retourne la valeur correcte saisie return n # -------------------------------------------------- # Fonction qui supprime les espaces inutiles # au début, à la fin et les espaces doubles # dans une chaîne de caractères # -------------------------------------------------- def supprimer_espaces(ch): # Supprimer les espaces au début de la chaîne while ch[0] == ' ': ch = ch[1:len(ch)] # Supprimer les espaces à la fin de la chaîne while ch[len(ch)-1] == ' ': ch = ch[0:len(ch)-1] # Remplacer les doubles espaces par un seul espace while ch.find(' ') > 0: ch = ch.replace(" ", " ") # Retourner la chaîne nettoyée return ch # -------------------------------------------------- # Fonction qui vérifie qu'une phrase ne contient # que des lettres alphabétiques et des espaces # -------------------------------------------------- def verif_phrase(ch): i = 0 # Parcourir la chaîne tant que les caractères sont valides while (i < len(ch)-1) and (('A' <= ch[i].upper() <= 'Z') or ch[i] == ' '): i = i + 1 # Retourne True si le dernier caractère est valide return (('A' <= ch[i].upper() <= 'Z') or ch[i] == ' ') # -------------------------------------------------- # Fonction qui permet de saisir une phrase valide # (lettres et espaces uniquement) après nettoyage # -------------------------------------------------- def saisie_phrase(): # Saisie d'une phrase par l'utilisateur phrase = input('donner une phrase: ') # Suppression des espaces inutiles phrase = supprimer_espaces(phrase) # Tant que la phrase contient des caractères invalides # on redemande la saisie while verif_phrase(phrase) == False: phrase = input('donner une phrase: ') phrase = supprimer_espaces(phrase) # Retourner la phrase valide return phrase # -------------------------------------------------- # Procedure qui remplit le fichier phrases.txt # avec n phrases saisies par l'utilisateur # -------------------------------------------------- def remplir_fichier_phrases(n): print('****** Remplissage fichier phrases.txt ******') # Ouvrir le fichier en mode écriture f = open("phrases.txt", "w") for i in range(n): phrase=saisie_phrase() # Écriture de la phrase dans le fichier f.write(phrase + '\n') # Fermer le fichier f.close() # -------------------------------------------------- # Fonction qui crypte un caractère par décalage # alphabétique (chiffrement de César) # -------------------------------------------------- def crypter_caractere(c, p): # Cas d'une lettre majuscule if 'A' <= c <= 'Z': if ord(c) + p <= 90: return chr(ord(c) + p) else: return chr(ord(c) + p - 26) # Cas d'une lettre minuscule else: if ord(c) + p <= 122: return chr(ord(c) + p) else: return chr(ord(c) + p - 26) # -------------------------------------------------- # Procedure qui lit les phrases du fichier phrases.txt # et crée le fichier ph_crypt.txt contenant # les phrases cryptées # -------------------------------------------------- def remplir_fichier_ph_crypt(): print('****** Fichier ph_crypt.txt ******') # Ouvrir le fichier source en lecture f_phrases = open("phrases.txt", "r") # Ouvrir le fichier destination en écriture f_phr_crypt = open("ph_crypt.txt", "w") # Lire toutes les phrases du fichier phrases = f_phrases.readlines() for phrase in phrases: # Supprimer le retour à la ligne phrase = phrase.rstrip('\n') p = 1 # pas de décalage # Parcourir chaque caractère de la phrase for i in range(len(phrase)): if phrase[i] != ' ': caractere = crypter_caractere(phrase[i], p) else: # Incrémenter le décalage après chaque espace p = p + 1 caractere = ' ' # Affichage à l'écran print(caractere, end='') # Écriture dans le fichier crypté f_phr_crypt.write(caractere) print() f_phr_crypt.write('\n') # Fermer les fichiers f_phrases.close() f_phr_crypt.close() # -------------------------------------------------- # Programme principal # -------------------------------------------------- n = saisie(0, 51) # Saisie du nombre de phrases remplir_fichier_phrases(n) # Remplissage du fichier phrases.txt remplir_fichier_ph_crypt() # Création du fichier crypté |
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
