Chemins Matrice – Bac théorique – Section informatique – 2009
Sujet (Algo et programmation - Bac 2008)
Soit p et q deux entiers naturels tels que 5 :5_ p < q < 32. On se propose de remplir une matrice M à p lignes et q colonnes par des zéros (0) et des uns (1) de la façon suivante : On mettra 1 dans toute cellule M[i , j] si les représentations de i et de j dans la base 2 ont au moins une fois le chiffre 1 à la même position sinon on y mettra 0. On commencera à lire les positions à partir de la droite. Exemples M[5 , 3] aura la valeur 1 car les deux représentations binaires ont le chiffre 1 à la première position. En effet : 5 = (101)2 et 3 (11)2 M[9 , 4] aura la valeur 0 car les deux représentations binaires n'ont pas de 1 à la même place. En effet : 9 = (1001)2 et 4 = (100)2 On se propose ensuite de chercher tous les chemins rectilignes menant de la première ligne à la dernière ligne en n'empruntant que des cellules contenant des 1 et en sautant au maximum une seule cellule contenant 0. Par conséquent, un chemin rectiligne est une colonne ne comportant pas deux cellules consécutives contenant 0. Pour tout chemin trouvé, on affichera son numéro (l'indice j). En plus, les données relatives à ce problème seront enregistrées dans un fichier texte intitulé chemins.txt et placé sur la racine du disque D. Ce fichier comportera dans sa première ligne le naturel p suivi d'une espace, suivie du naturel q et comportera dans chacune des lignes qui suivent le numéro du chemin trouvé. La dernière ligne contiendra le nombre de chemins trouvés.
Solution Algorithmique
Dans cet algorithme, On va utiliser sept procédures :
- la fonction saisie()
- la fonction convertir_binaire()
- la fonction test_position1()
- la fonction test_cellule()
- la procédure remplir_matrice()
- la procédure afficher_matrice()
- la procédure remplir_fichier_chemin()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
Algorithme chemins_matrice Debut # Saisie des dimensions p et q p = saisie(5, 32) q = saisie(p, 32) # Remplir la matrice selon la règle définie remplir_matrice(m, p, q) # Afficher la matrice afficher_matrice(m, p, q) # Générer le fichier chemins.txt contenant les chemins remplir_fichier_chemin(m, p, q) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| p | entier |
| q | entier |
| m (matrice) | tableau T de 32 lignes x 32 colonnes d’entiers. |
La fonction saisir
La fonction saisie(inf, sup) sert à obliger l’utilisateur à entrer un nombre entier compris entre deux bornes :
inf : la borne inférieure (minimum autorisé)
sup : la borne supérieure (maximum autorisé)
Elle garantit que la valeur saisie est correcte.
La fonction demande d’abord à l’utilisateur d’entrer un entier dans l’intervalle [inf, sup].
Tant que l’utilisateur entre une valeur en dehors de l’intervalle, la fonction répète la saisie.
Dès qu’un nombre valide est fourni (inf ≤ n ≤ sup), la fonction le renvoie.
|
1 2 3 4 5 6 7 8 9 10 |
Fonction saisie(inf:entier, sup:entier): entier Ecrire('donner n tel que ' + inf + '<=n<=' + sup + ': ') lire (n) # Tant que la valeur n'est pas dans l’intervalle demandé, on redemande Tant que (n < inf) ou (n > sup) faire Ecrire('donner n tel que ' + inf + '<=n<=' + sup + ': ') lire (n) Fin tant que retourner n fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction convertir_binaire
La fonction convertir_binaire(n) sert à transformer un nombre entier positif en une chaîne représentant son écriture en binaire.
1- On initialise une chaîne vide qui contiendra le résultat binaire.
2- Tant que n > 0 :
- On calcule le reste de la division par 2 → c’est le prochain bit (0 ou 1).
- On ajoute ce bit au début de la chaîne binaire.
- On divise n par 2 (division entière).
3- Quand n atteint 0, la chaîne contient le nombre en binaire → on la retourne.
|
1 2 3 4 5 6 7 8 9 10 |
Fonction convertir_binaire(n:entier):entier binaire <- '' # Construction de la chaîne en binaire Tant que n > 0 faire reste <- n mod 2 # Bit extrait (0 ou 1) binaire <- str(reste) + binaire # Ajout au début de la chaîne n = n div 2 # Division entière Fin tant que retourner binaire Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| binaire | chaîne |
| reste | chaîne |
La fonction test_position1
Cette fonction sert à vérifier si deux nombres binaires (sous forme de chaînes) possèdent un bit ‘1’ aligné sur la même position en partant de la droite.
On commence à comparer les deux chaînes au dernier caractère (bit de poids faible).
1- Tant que : (ch1[pos1] == '0' ou ch2[pos2] == '0') et que l’on n’est pas encore au début des chaînes
on recule d’un pas (pos1 −= 1, pos2 −= 1).
2- Quand la boucle s’arrête, on vérifie : le bit actuel de ch1 est ‘1’ et le bit actuel de ch2 est ‘1’
3- Si les deux sont ‘1’, la fonction renvoie Vrai, sinon Faux.
|
1 2 3 4 5 6 7 8 9 10 11 |
Fonction test_position1(ch1:chaine, ch2:chaine):booleen pos1 <- long(ch1) - 1 # Dernier indice de ch1 pos2 <- long(ch2) - 1 # Dernier indice de ch2 # On recule tant que les deux bits sont 0 Tant que (ch1[pos1] = '0' ou ch2[pos2] == '0') et pos1 > 0 et pos2 > 0 faire pos1 <- pos1 - 1 pos2 <- pos2 - 1 Fin tant que # Retourne vrai si les deux bits rencontrés sont '1' retourner ch1[pos1] = '1' et ch2[pos2] = '1' Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| pos1 | entier |
| pos2 | entier |
La procédure remplir_fichier_resultat
Ce procédure sert à enregistrer dans un fichier binaire (resultat.dat) les n premiers éléments du tableau t.
Elle :
1- ouvre un fichier binaire nommé resultat.dat en écriture ("wb").
2- parcourt les n premiers éléments du tableau t.
3- écrit chaque élément dans le fichier.
4- ferme le fichier à la fin pour sauvegarder les données.
|
1 2 3 4 5 6 7 |
Procédure remplir_fichier_resultat(t:tableau;n:entier) Ouvrir("resultat.dat", f_resultats , "wb") # Fichier binaire pour résultats triés Pour i de 0 à n-1 faire Ecrire(f_resultats,t[i]) # Sauvegarde de chaque candidat trié Fin pour Fermer(f_resultats) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f_resultats | fichier du resultat.dat |
| i | entier |
La fonction recherche_nbr_admis
Cette fonction sert à compter le nombre d’admis dans un tableau t contenant des enregistrements (dictionnaires).
Un candidat est considéré "admis" lorsque la valeur du champ indiqué par champs est supérieure ou égale à 10.
|
1 2 3 4 5 6 7 8 |
Fonction recherche_nbr_admis(t:tableau,n:entier,champs:chaine) : entier nbr_admis<-0 Pour i de 0 à n-1 faire Si t[i][champs]>=10 alors nbr_admis<-nbr_admis+1 Fin si Fin pour retourner nbr_admis |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| nbr_admis | entier |
La fonction recherche_max_note
Cette fonction sert à chercher la note maximale dans un tableau t contenant des enregistrements (dictionnaires), en se basant sur un champ précis (exemple : "note1", "note2", …).
Elle :
1- suppose d’abord que le maximum est la valeur du champ champ du 1er élément → t[0][champ].
2- parcourt le tableau du 2ᵉ élément jusqu’au n-ième.
3- chaque fois qu’il trouve une valeur plus grande, il met à jour max_nombre.
4- à la fin, il retourne la plus grande valeur trouvée.
|
1 2 3 4 5 6 7 |
Procédure recherche_max_note(t:tableau, n:entier, champ:chaine):entier max_nombre <- t[0][champ] # On suppose que le premier est le maximum Pour i de 1 à n-1 faire Si max_nombre < t[i][champ] alors max_nombre <- t[i][champ] Fin si retourner max_nombre |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| max_nombre | entier |
| i | entier |
La procédure remplir_fichier_details
Le programme sert à créer un fichier texte (details.txt) contenant des statistiques calculées à partir des données des candidats.
Il extrait plusieurs informations importantes à partir du tableau t :
- max_moyenne → le nombre de candidats ayant une moyenne ≥ 10
- max_note1 → la note maximale obtenue dans la matière 1.
- nbr_note1 → le nombre de candidats ayant une note1 ≥ 10.
- max_note2 → la note maximale de la matière 2.
- nbr_note2 → le nombre de candidats ayant une note2 ≥ 10.
- max_note3 → la note maximale de la matière 3.
- nbr_note3 → le nombre de candidats ayant une note3 ≥ 10.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
Procédure remplir_fichier_details(t:tableau;n:entier) Ouvrir("resultat.dat", f_details , "w") # Fichier texte pour les statistiques # Calcul des différentes statistiques max_moyenne <- recherche_nbr_admis(t, n, "moyenne") max_note1 <- recherche_max_note(t, n, "note1") nbr_note1 <- recherche_nbr_admis(t, n, "note1") max_note2 <- recherche_max_note(t, n, "note2") nbr_note2 <- recherche_nbr_admis(t, n, "note2") max_note3 <- recherche_max_note(t, n, "note3") nbr_note3 <- recherche_nbr_admis(t, n, "note3") # Écriture des résultats dans le fichier texte Ecrire(f_details , Convch(max_moyenne) + '\n') Ecrire(f_details , Convch(max_note1) + ' ' + Conch(nbr_note1) +'\n') Ecrire(f_details , Convch(max_note2) + ' ' + Conch(nbr_note2) +'\n') Ecrire(f_details , Convch(max_note3) + ' ' + Conch(nbr_note3) +'\n') Fermer(f_details) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f_details | fichier du details.txt |
| max_moyenne | entier |
| max_note1 | entier |
| nbr_note1 | entier |
| max_note2 | entier |
| nbr_note2 | entier |
| max_note3 | entier |
| nbr_note3 | 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 |
import pickle from pickle import load, dump from numpy import * # Définition d'un dictionnaire modèle pour un candidat candidat = dict ( numero = int(), nom = str(), prenon = str(), matiere1 = str(), note1 = float, matiere2 = str(), note2 = float, matiere3 = str(), note3 = float ) # Tableau pouvant contenir jusqu'à 50 dictionnaires de candidats t = array([{}]*50) # Fonction pour saisir un nombre n strictement positif def saisie(): n = int(input('donner n > 0: ')) # Vérification que n est correct while (n <= 0): n = int(input('donner n > 0: ')) return n # Procedure pour remplir le fichier concours.dat avec les informations des candidats def remplir_fichier_concours(n): f_candidats = open("concours.dat", "wb") # Ouverture du fichier en mode binaire écriture for i in range(n): # Création d'un dictionnaire vide pour un candidat candidat = dict ( numero = int(), nom = str(), prenon = str(), matiere1 = str(), note1 = float, matiere2 = str(), note2 = float, matiere3 = str(), note3 = float ) # Saisie des informations du candidat candidat["numero"] = int(input('donner le numero du candidat: ')) candidat["nom"] = input('donner le nom du candidat: ') candidat["prenom"] = input('donner le prenom du candidat: ') candidat["matiere1"] = input('donner le nom de matiere1: ') candidat["note1"] = float(input('donner note1: ')) candidat["matiere2"] = input('donner le nom de matiere2: ') candidat["note2"] = float(input('donner note2: ')) candidat["matiere3"] = input('donner le nom de matiere3: ') candidat["note3"] = float(input('donner note3: ')) # Enregistrement du candidat dans le tableau local t t[i] = candidat # Calcul de la moyenne pondérée t[i]["moyenne"] = ((candidat["note1"] + 2*candidat["note2"] + 2*candidat["note1"]) / 5) # Attribution d’un rang provisoire (sera modifié après tri) t[i]["rang"] = i + 1 # Écriture du candidat dans le fichier concours.dat dump(candidat, f_candidats) f_candidats.close() # Fermeture du fichier # Procedure pour trier le tableau t selon la moyenne (ordre décroissant) def tri_decroissant_tableau(t, n): for i in range(n-1): indice_max = i # Recherche de la plus grande moyenne dans la partie restante du tableau for j in range(i+1, n): if t[indice_max]["moyenne"] < t[j]["moyenne"]: indice_max = j # Échange si un meilleur candidat est trouvé if indice_max != i: temp = t[i] t[i] = t[indice_max] t[indice_max] = temp # Procedure pour créer le fichier resultat.dat contenant les candidats triés def remplir_fichier_resultat(t, n): f_resultats = open("resultat.dat", "wb") # Fichier binaire pour résultats triés for i in range(n): dump(t[i], f_resultats) # Sauvegarde de chaque candidat trié f_resultats.close() # Fonction pour compter combien de candidats ont une note >= 10 dans un champ donné def recherche_nbr_admis(t, n, champs): nbr_admis = 0 for i in range(n): if t[i][champs] >= 10: nbr_admis += 1 return nbr_admis # Fonction pour trouver la note maximale dans un champ donné def recherche_max_note(t, n, champ): max_nombre = t[0][champ] # On suppose que le premier est le maximum for i in range(1, n): if max_nombre < t[i][champ]: max_nombre = t[i][champ] return max_nombre # Procedure qui crée un fichier texte contenant les statistiques finales def remplir_fichier_details(t, n): f_details = open("details.txt", "w") # Fichier texte pour les statistiques # Calcul des différentes statistiques max_moyenne = recherche_nbr_admis(t, n, "moyenne") max_note1 = recherche_max_note(t, n, "note1") nbr_note1 = recherche_nbr_admis(t, n, "note1") max_note2 = recherche_max_note(t, n, "note2") nbr_note2 = recherche_nbr_admis(t, n, "note2") max_note3 = recherche_max_note(t, n, "note3") nbr_note3 = recherche_nbr_admis(t, n, "note3") # Écriture des résultats dans le fichier texte f_details.write(str(max_moyenne) + '\n') f_details.write(str(max_note1) + ' ' + str(nbr_note1) + '\n') f_details.write(str(max_note2) + ' ' + str(nbr_note2) + '\n') f_details.write(str(max_note3) + ' ' + str(nbr_note3) + '\n') f_details.close() # ======================= # Programme principal # ======================= n = saisie() # Saisie du nombre de candidats remplir_fichier_concours(n) # Enregistrement des candidats dans concours.dat tri_decroissant_tableau(t, n) # Tri du tableau t par moyenne décroissante remplir_fichier_resultat(t, n) # Sauvegarde des candidats triés dans resultat.dat remplir_fichier_details(t, n) # Génération du fichier de statistiques |
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
