Nombre Mersenne – Bac pratique – Section informatique – 2011
Sujet (Algo et programmation - Bac 2011)
Un nombre M est dit "nombre de Mersenne", s'il est défini par M = 2N-1 avec N un nombre premier.
Exemples :
Si M = 31, alors M est un nombre de Mersenne. En effet, il peut s'écrire sous la forme 2^N-1 où N = 5 qui est un nombre premier.
Si M = 255, alors M n'est pas un nombre de Mersenne. En effet, il peut s'écrire sous la forme 2^N-1 où N 8 qui est un nombre premier.
Travail demandé :
Ecrire un programme en Python qui permet de :
1) Déterminer tous les nombres de Mersenne compris dans l'intervalle [A B] avec A et B, 2 entiers saisis tels que 2 < A < B < 50000.
2) Stocker chaque nombre M de Mersenne trouvé, dans une ligne d'un fichier texte intitulé « mersenne.txt » sous la forme M = (2^N) - 1, avec :
Solution Algorithmique
Dans cet algorithme, On va utiliser trois fonctions et une procédure:
- la fonction saisie()
- la fonction test_premier()
- la fonction test_mersenne()
- la procédure remplir_fichier_mersenne()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 9 |
Algorithme nombres_mersennes Debut # Saisie de la borne inférieure a a <- saisie(2, 50000) # Saisie de la borne supérieure b (avec b > a) b <- saisie(a, 50000) # Recherche et écriture des nombres de Mersenne remplir_fichier_mersenne(a, b) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| a | entier |
| b | entier |
La fonction saisie
Cette procédure permet de saisir un entier compris strictement entre deux bornes inf et sup, en contrôlant la validité de la saisie.
Plus précisément :
il demande à l’utilisateur d’entrer un entier n tel que inf < n < sup ; si la valeur saisie n’appartient pas à cet intervalle, le programme redemande la saisie jusqu’à obtenir une valeur correcte ; une fois la saisie valide, la fonction retourne l’entier n.
|
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 un entier 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 un entier 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 test_premier
Ce programme permet de tester si un entier n est un nombre premier.
Fonctionnement :
Il cherche un diviseur de n à partir de 2.
Tant que n n’est pas divisible par i et que i ne dépasse pas n // 2, il incrémente i
Si aucun diviseur n’est trouvé, alors n est premier.
|
1 2 3 4 5 6 7 8 9 10 |
Fonction test_premier(n:entier): booleen i <- 2 # Recherche d’un diviseur de n # On s’arrête si i divise n ou si i dépasse n//2 Tant que (n mod i != 0) ou (i <= n div 2): i <- i + 1 Fin tant que # Si aucun diviseur n’a été trouvé, n est premier retourner n mod i != 0 Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
La fonction test_mersenne
Ce programme permet de vérifier si un entier m est un nombre de Mersenne.
Fonctionnement :
Il calcule m − 1 et vérifie s’il s’agit d’une puissance de 2.
Il détermine l’exposant i correspondant à cette puissance.
Il teste ensuite si i est un nombre premier en utilisant la fonction test_premier.
Valeur retournée :
- l’exposant i si m est un nombre de Mersenne
- 0 si m n’est pas un nombre de Mersenne.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
Fonction test_mersenne(m:entier): entier m1 <- m - 1 # Valeur à tester comme puissance de 2 m2 <- 2 # Sert à reconstruire 2^i i <- 1 # Compteur de puissance # On divise m1 par 2 tant que c’est possible Tant que m1 > 1 faire m1 <- m1 div 2 m2 <- m2 * 2 i <- i + 1 Fin tant que # Vérifie si m = 2^i - 1 et si i est premier Si (m = m2 - 1) et test_premier(i) alors retourner i # m est un nombre de Mersenne Sinon retourner 0 # m n’est pas un nombre de Mersenne Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| m1 | entier |
| m2 | entier |
| i | entier |
La procédure remplir_fichier_mersenne
Cette procédure permet de créer et remplir un fichier texte nommé sms.dat contenant une liste de SMS associés à des numéros de téléphone.
Plus précisément, la procédure remplir_fichier_sms(n) :
1- ouvre (ou crée) le fichier texte sms.dat en mode écriture
2- répète n fois les opérations suivantes
3- saisit un message SMS à l’aide de la fonction saisie_sms()
4- demande à l’utilisateur de saisir un numéro de téléphone
5- écrit dans le fichier une ligne contenant le SMS suivi du numéro de téléphone
6- ferme le fichier après la fin de l’enregistrement
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
Procédure remplir_fichier_mersenne(a:entier,b:entier) # Ouverture du fichier en mode écriture Ouvrir(f , "mersenne.txt", "w") test_vide <- Vrai # Indique s'il existe au moins un nombre de Mersenne # Parcours de tous les entiers entre a et b Pour i de a à b + 1 faire # Test si i est un nombre de Mersenne Si test_mersenne(i) != 0 alors test_vide <- Faux # Affichage à l’écran Ecrire(i + ' = 2^' + test_mersenne(i) + ' - 1') # Écriture dans le fichier Ecrire(f, i + ' = 2^' + test_mersenne(i) + ' - 1\n') Fin si Fin pour # Si aucun nombre de Mersenne n’a été trouvé Si test_vide alors Ecrire("Il n'y a aucun nombre de Mersenne.") Fin si # Fermeture du fichier Fermer(f) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | fichier |
| i | entier |
| test_vide | booléen |
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 |
# -------------------------------------------------- # Fonction pour saisir un entier n strictement compris # entre inf et sup # -------------------------------------------------- def saisie(inf, sup): # Première saisie de l'entier n = int(input('donner un entier tel que ' + str(inf) + '< n < ' + str(sup) + ' : ')) # Tant que n n'est pas dans l'intervalle demandé, # on redemande la saisie while (n <= inf) or (n >= sup): n = int(input('donner un entier tel que ' + str(inf) + '< n < ' + str(sup) + ' : ')) # Retourne la valeur correcte saisie return n # -------------------------------------------------- # Fonction qui teste si un nombre n est premier # Retourne True si n est premier, False sinon # -------------------------------------------------- def test_premier(n): i = 2 # Recherche d’un diviseur de n # On s’arrête si i divise n ou si i dépasse n//2 while (n % i != 0) and (i <= n // 2): i = i + 1 # Si aucun diviseur n’a été trouvé, n est premier return n % i != 0 # -------------------------------------------------- # Fonction qui teste si m est un nombre de Mersenne # Un nombre de Mersenne est de la forme : 2^i - 1 # avec i premier # -------------------------------------------------- def test_mersenne(m): m1 = m - 1 # Valeur à tester comme puissance de 2 m2 = 2 # Sert à reconstruire 2^i i = 1 # Compteur de puissance # On divise m1 par 2 tant que c’est possible while m1 > 1: m1 = m1 // 2 m2 = m2 * 2 i = i + 1 # Vérifie si m = 2^i - 1 et si i est premier if (m == m2 - 1) and test_premier(i): return i # m est un nombre de Mersenne else: return 0 # m n’est pas un nombre de Mersenne # -------------------------------------------------- # Procédure qui écrit dans un fichier texte # tous les nombres de Mersenne compris entre a et b # -------------------------------------------------- def remplir_fichier_mersenne(a, b): # Ouverture du fichier en mode écriture f = open("mersenne.txt", "w") test_vide = True # Indique s'il existe au moins un nombre de Mersenne # Parcours de tous les entiers entre a et b for i in range(a, b + 1): # Test si i est un nombre de Mersenne if test_mersenne(i) != 0: test_vide = False # Affichage à l’écran print(str(i) + ' = 2^' + str(test_mersenne(i)) + ' - 1') # Écriture dans le fichier f.write(str(i) + ' = 2^' + str(test_mersenne(i)) + ' - 1\n') # Si aucun nombre de Mersenne n’a été trouvé if test_vide: print("Il n'y a aucun nombre de Mersenne.") # Fermeture du fichier f.close() # -------------------------------------------------- # Programme principal # -------------------------------------------------- # Saisie de la borne inférieure a a = saisie(2, 50000) # Saisie de la borne supérieure b (avec b > a) b = saisie(a, 50000) # Recherche et écriture des nombres de Mersenne remplir_fichier_mersenne(a, b) |
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
