Facteurs premiers – Bac pratique – Section informatique – 2012
Sujet (Algo et programmation - Bac 2012)
A partir d'un fichier nommé "Nombres.dat" contenant N entiers, formé chacun de P chiffres, on veut former un deuxième fichier nommé "Facteurs.txt" qui contiendra, des chaînes. Chaque chaîne représente la concaténation de la fréquence de chacun des facteurs premiers d'un nombre du fichier "Nombres.dat" suivi du facteur premier lui même.
Exemple :
Pour N = 3 et P = 4 :
En effet :
a) 1912 = 2 *2 *2 *239
La chaîne générée sera "321239" pour dire que 3 est la fréquence du facteur premier 2 et 1 est la fréquence du facteur premier 239.
b) 3525 = 3 * 5 * 5 * 47
La chaîne générée sera "1325147" pour dire que 1 est la fréquence du facteur premier 3, 2 est la fréquence du facteur premier 5 et 1 est la fréquence du facteur premier 47.
Travail à faire :
Ecrire un programme Pascal et l'enregistrer sous le nom FactPrem, permettant :
1- de remplir un fichier nommé "Nombres.dat" par N entiers, formés de P chiffres (avec 2 < N < 100 et 2 < P < 6),
2- de créer, pour chaque entier du fichier "Nombres.dat", une chaîne représentant la concaténation de la fréquence de chacun de ses facteurs premiers suivi du facteur premier lui-même et l'enregistrer dans une ligne d'un fichier texte nommé "Facteurs.txt",
3- d'afficher le contenu du fichier "Facteurs.txt".
Solution Algorithmique
Dans cet algorithme, On va utiliser trois fonctions et deux procédures:
- la fonction saisie()
- la fonction saisie_nombre()
- la procédure remplir_fichier_nombres()
- la fonction facteur_premiers()
- la procédure remplir_fichier_facteurs()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 9 |
Algorithme facteurs Debut # Saisie du nombre de valeurs à traiter n <- saisie(2, 100) # Remplissage du fichier des nombres remplir_fichier_nombres(n) # Calcul et enregistrement des facteurs premiers remplir_fichier_facteurs(n) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction saisie
Cette fonction permet de saisir un entier n compris strictement entre deux bornes inf et sup.
Plus précisément :
Elle demande à l’utilisateur de saisir une valeur entière n.
Elle vérifie que n appartient à l’intervalle ]inf , sup[.
Tant que la valeur saisie est inférieure ou égale à inf ou supérieure ou égale à sup, la saisie est redemandée.
Lorsque la valeur est correcte, la fonction la retourne.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Fonction saisie(inf:entier ; sup:entier):entier # Première saisie de l'entier Ecrire('donner n tel que ' , inf , '< n < ' , sup , ': ') Lire(n) # Tant que n n'est pas dans l'intervalle demandé, # 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 | chaîne |
La fonction saisie_nombre
Cette fonction définit une fonction saisie_nombre() dont le rôle est de demander à l’utilisateur de saisir un nombre sous forme de chaîne de caractères, en veillant à ce que cette saisie respecte une contrainte de longueur.
Plus précisément, la fonction :
- demande à l’utilisateur de saisir un nombre ;
- vérifie que la saisie contient au minimum 2 chiffres et au maximum 6 chiffres ;
- redemande la saisie tant que cette condition n’est pas respectée ;
- retourne finalement le nombre valide sous forme de chaîne de caractères.
|
1 2 3 4 5 6 7 8 9 10 |
Fonction saisie_nombre(): chaine Ecrire('donner un nombre forme au maximum de 6 chiffres: ') Lire(nombre) # Vérification de la longueur de la chaîne Tant que (long(nombre) < 2) ou (long(nombre) > 6) faire Ecrire('donner un nombre forme au maximum de 6 chiffres: ') Lire(nombre) Fin tant que retourner nombre Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| nombre | chaine |
La procédure remplir_fichier_nombres
Cette procédure définit la fonction remplir_fichier_nombres(n) dont le rôle est de créer et remplir le fichier texte Nombres.dat avec des nombres saisis par l’utilisateur.
Plus précisément, cette procédure :
- affiche un message indiquant le début du remplissage du fichier
- ouvre le fichier Nombres.dat en mode écriture (le contenu précédent est effacé s’il existe)
- demande à l’utilisateur de saisir n nombres, chacun étant validé par la fonction saisie_nombre() (nombre sous forme de chaîne de 2 à 6 chiffres)
- écrit chaque nombre saisi dans le fichier, un nombre par ligne
- ferme le fichier après la fin de l’écriture
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Procedure remplir_fichier_nombres(n:entier) Ecrire ('*** Remplir le fichier Nombres.dat ***') # Ouverture du fichier en mode écriture Ouvrir( f , "Nombres.dat", "w") # Saisie et écriture de n nombres dans le fichier Pour i de 0 à n-1 faire nombre <- saisie_nombre() Ecrire(f, nombre + '\n') Fin pour # Fermeture du fichier Fermer(f) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | fichier |
| i | entier |
| nombre | chaîne |
La fonction facteur_premiers
Ce programme définit la fonction facteur_premiers(n) dont le rôle est de décomposer un entier n en facteurs premiers et de retourner cette décomposition sous forme d’une chaîne de caractères.
Plus précisément, la fonction :
- teste successivement les diviseurs entiers à partir de 2 ;
- décompose n en facteurs premiers en divisant n chaque fois qu’un diviseur est trouvé ;
- compte le nombre de répétitions (puissance) de chaque facteur premier ;
- construit une chaîne représentant la décomposition sous la forme : nombre_d’occurrences suivi du facteur (exemple : 2² × 3 devient "223" ou 12 = 2² × 3¹ devient "2231") ;
- retourne la chaîne finale contenant toute la décomposition.
|
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 |
Fonction facteur_premiers(n:entier): chaine i <- 2 # Premier diviseur possible ch <- '' # Stocke le facteur courant ch2 <- '' # Stocke la décomposition finale redondance_chiffre <- 0 # Compte le nombre de répétitions du facteur # Tant que n n’est pas totalement décomposé Tant que n > 1 faire # Si i est un diviseur de n Si n mod i = 0 alors # Éviter la répétition du même facteur dans ch Si long(ch) != 0 alors Si ch[long(ch) - 1] != Conch(i) alors ch <- ch + Convch(i) Finsi Sinon ch <- ch + Convch(i) Finsi redondance_chiffre <- redondance_chiffre + 1 n <- n / i # Division de n par i Sinon # Si on change de facteur, on ajoute # le facteur et son nombre d’occurrences Si redondance_chiffre > 0: ch2 <- ch2 + Conch(redondance_chiffre) + ch ch <- '' redondance_chiffre = 0 i <- i + 1 # Passage au diviseur suivant Fin si Fin tant que # Ajout du dernier facteur traité Si redondance_chiffre > 0 alors ch2 <- ch2 + Convch(redondance_chiffre) + ch Fin si retourner ch2 Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| ch | chaîne |
| ch2 | chaîne |
| redondance_chiffre | entier |
La procédure remplir_fichier_facteurs
Le rôle de cette procédure est de lire les nombres stockés dans le fichier Nombres.dat, de calculer leur décomposition en facteurs premiers, puis de stocker le résultat dans le fichier Facteurs.txt.
Plus précisément, la procédure :
- ouvre le fichier Nombres.dat en mode lecture et le fichier Facteurs.txt en mode écriture
- lit tous les nombres contenus dans Nombres.dat (un nombre par ligne)
- pour chaque nombre lu :
supprime le caractère de fin de ligne ;
convertit le nombre en entier ;
calcule sa décomposition en facteurs premiers à l’aide de la fonction facteur_premiers() ;
affiche cette décomposition à l’écran ;
écrit la décomposition correspondante dans le fichier Facteurs.txt ;
- ferme les deux fichiers après la fin du traitement.
|
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 |
Procédure remplir_fichier_facteurs(n:entier) Ouvrir(f_chaine , "chaines.txt" , "w") # Fichier des chaînes Ouvrir(f_nombre , "nombres.dat", "w") # Fichier des résultats Pour i de 0 à n-1 faire ch <- saisie_ch() # Saisie d'une chaîne valide Ecrire(f_chaine, ch + '\n') # Écriture de la chaîne dans le fichier # Extraction des chiffres de la chaîne Si long(extraire_chiffres(ch)) > 0 alors nombre <- extraire_chiffres(ch) # Test de divisibilité par 11 Si test_divisible11(nombre) alors Ecrire(nombre + ' est divisible par 11') Ecrire(f_nombre,nombre + ' est divisible par 11\n') Sinon Ecrire(nombre + ' n est pas divisible par 11') Ecrire(f_nombre, nombre + ' n est pas divisible par 11\n') Sinon # Cas où la chaîne ne contient aucun chiffre Ecrire('1999999999 n est pas un nombre decimal') Ecrire(f_nombre,'1999999999 n est pas un nombre decimal\n') Fin si Fin pour # Fermeture des fichiers Fermer(f_chaine) Fermer(f_nombre) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f_chaine | fichier |
| f_nombre | fichier |
| ch | chaîne |
| nombre | 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 |
# -------------------------------------------------- # Fonction qui permet de saisir un entier n # compris strictement entre inf et sup # -------------------------------------------------- def saisie(inf, sup): # Première saisie de 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 return n # -------------------------------------------------- # Fonction qui permet de saisir un nombre # sous forme de chaîne contenant au maximum 6 chiffres # -------------------------------------------------- def saisie_nombre(): nombre = input('donner un nombre forme au maximum de 6 chiffres: ') # Vérification de la longueur de la chaîne while len(nombre) < 2 or len(nombre) > 6: nombre = input('donner un nombre forme au maximum de 6 chiffres: ') return nombre # -------------------------------------------------- # Fonction qui remplit le fichier "Nombres.dat" # par n nombres saisis par l'utilisateur # -------------------------------------------------- def remplir_fichier_nombres(n): print('*** Remplir le fichier Nombres.dat ***') # Ouverture du fichier en mode écriture f = open("Nombres.dat", "w") # Saisie et écriture de n nombres dans le fichier for i in range(n): nombre = saisie_nombre() f.write(nombre + '\n') # Fermeture du fichier f.close() # -------------------------------------------------- # Fonction qui retourne la décomposition en facteurs # premiers d’un entier n sous forme d’une chaîne # -------------------------------------------------- def facteur_premiers(n): i = 2 # Premier diviseur possible ch = '' # Stocke le facteur courant ch2 = '' # Stocke la décomposition finale redondance_chiffre = 0 # Compte le nombre de répétitions du facteur # Tant que n n’est pas totalement décomposé while n > 1: # Si i est un diviseur de n if n % i == 0: # Éviter la répétition du même facteur dans ch if len(ch) != 0: if ch[len(ch) - 1] != str(i): ch = ch + str(i) else: ch = ch + str(i) redondance_chiffre = redondance_chiffre + 1 n = n / i # Division de n par i else: # Si on change de facteur, on ajoute # le facteur et son nombre d’occurrences if redondance_chiffre > 0: ch2 = ch2 + str(redondance_chiffre) + ch ch = '' redondance_chiffre = 0 i = i + 1 # Passage au diviseur suivant # Ajout du dernier facteur traité if redondance_chiffre > 0: ch2 = ch2 + str(redondance_chiffre) + ch return ch2 # -------------------------------------------------- # Fonction qui lit le fichier "Nombres.dat" # et écrit la décomposition en facteurs premiers # dans le fichier "Facteurs.txt" # -------------------------------------------------- def remplir_fichier_facteurs(n): # Ouverture des fichiers f_nombres = open("Nombres.dat", "r") f_facteurs = open("Facteurs.txt", "w") # Lecture de tous les nombres du fichier nombres = f_nombres.readlines() print('*** Contenu du fichier Facteurs.txt ***') # Traitement de chaque nombre for nombre in nombres: ch = nombre.strip('\n') # Suppression du retour à la ligne facteurs = facteur_premiers(int(ch)) print(facteurs) f_facteurs.write(facteurs + '\n') # Fermeture des fichiers f_nombres.close() f_facteurs.close() # -------------------------------------------------- # Programme principal # -------------------------------------------------- # Saisie du nombre de valeurs à traiter n = saisie(2, 100) # Remplissage du fichier des nombres remplir_fichier_nombres(n) # Calcul et enregistrement des facteurs premiers remplir_fichier_facteurs(n) |
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
