Problème des suites – Bac pratique – Section informatique – 2015
Sujet (Algo et programmation - Bac 2015)
Soit la suite U définie par :
La suite U converge toujours vers 1 quelque soit la valeur de départ (Uo).
Travail demandé
Ecrire un programme en Python intitulé "Suit_Min" qui permet de
1- Remplir un fichier nommé "Departdat" par P entiers compris entre 2 et 1000 représentant différentes valeurs de U0 (avec 2 < P < 30).
2- A partir du fichier "Depart.dat", générer un nouveau fichier d'enregistrements nommé "Suite.dat" où chaque enregistrement contient les champs suivants :
Dep : valeur du terme de départ Uo provenant du fichier "liepart.dat".
Nb nombre de termes calculés de la suite U pour atteindre la valeur 1.
3- A partir du fichier "Suite.dat", afficher les valeurs des termes de départ (Dep) correspondant au nombre de termes (Nb) minimal.
Solution Algorithmique
Dans cet algorithme, On va utiliser trois fonctions et trois procédures:
- la fonction saisie()
- la procédure remplir_fichier_depart()
- la fonction nbr_termes_suite()
- la procédure remplir_fichier_suite()
- la fonction recherche_terme_min()
- la procédure afficher_termes_min()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 |
Algorithme Suit_Min Debut p = saisie(1, 31) # Saisie du nombre de valeurs à générer remplir_fichier_depart(p) # Remplissage du fichier de départ remplir_fichier_suite() # Calcul et sauvegarde des suites terme_min <- recherche_terme_min() # Recherche du nombre minimal de termes afficher_termes_min(terme_min) # Affichage des résultats Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| p | entier |
| terme_min | entier |
La fonction saisie
Le rôle de cette fonction est de permettre à l’utilisateur de saisir un entier n compris strictement entre deux bornes inf et sup.
1- La fonction saisie(inf, sup) demande à l’utilisateur d’entrer un entier n.
2- Elle vérifie que n appartient à l’intervalle ouvert ] inf , sup [ (c’est-à-dire inf < n < sup). 3- Tant que la valeur saisie n’est pas valide (n ≤ inf ou n ≥ sup), la fonction redemande la saisie. 4- Une fois une valeur correcte entrée, la fonction retourne n.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
Fonction saisie(inf:entier, sup:entier):entier # Première saisie de 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 valide retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La procédure remplir_fichier_depart
Le rôle de cette procédure remplir_fichier_depart est de permettre à l’utilisateur de saisir p nombres entiers compris entre 2 et 2000 et de les enregistrer dans le fichier Depart.dat, un nombre par ligne.
1- Affichage d’un message
La procédure informe l’utilisateur que le remplissage du fichier va commencer.
2- Ouverture du fichier Depart.dat en mode écriture
Le fichier est créé ou écrasé s’il existe déjà.
Les données qui y seront écrites remplaceront le contenu précédent.
3- Boucle de saisie des nombres
La procédure demande p nombres à l’utilisateur de saisir un entier valide.
Elle appelle la fonction saisie pour récupérer un entier compris strictement entre 2 et 2000.
Cette fonction vérifie que l’utilisateur entre une valeur correcte.
4- Écriture du nombre dans le fichier
La procédure convertit le nombre en chaîne de caractères.
La procédure écrit chaque nombre sur une nouvelle ligne du fichier.
5- Fermeture du fichier
La procédure sauvegarde définitivement les données et libère la ressource.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Procedure remplir_fichier_depart(p:entier): Ecrire('*** Remplir le fichier Depart.dat ***') # Ouverture du fichier en mode écriture texte Ouvrir(f , "Depart.dat", "w") Pour i de 0 à p-1 faire # Saisie d'une valeur valide entre 2 et 2000 u0 <- saisie(2, 2000) # Écriture de la valeur dans le fichier, une par ligne Ecrire(f, Convch(u0) + '\n') Fin pour Fermer(f) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | fichier |
| i | entier |
| u0 | entier |
La fonction nbr_termes_suite
Le rôle de cette fonction nbr_termes_suite est de calculer et retourner le nombre de termes de la suite de Collatz (ou suite 3n+1) à partir d’un entier u0 jusqu’à atteindre 1.
Étapes détaillées du fonctionnement
1- Initialisation du compteur
Un compteur nbr_termes est créé pour compter le nombre d’étapes de la suite. Initialement, il vaut 0.
2- Boucle principale
Tant que la valeur actuelle u0 n’est pas égale à 1, la boucle continue.
L’objectif est d’appliquer les règles de Collatz jusqu’à ce que la suite atteigne 1.
Si u0 est pair, on le divise par 2.
Si u0 est impair, on le transforme en 3*u0 + 1.
Mise à jour de la valeur courante : u0 = u1
La nouvelle valeur calculée devient la valeur courante pour l’itération suivante.
Incrémentation du compteur : nbr_termes = nbr_termes + 1
À chaque étape, on ajoute 1 au compteur pour suivre le nombre de transformations effectuées.
3- Retour de la valeur
Une fois que u0 atteint 1, la fonction retourne le nombre total d’étapes nécessaires pour arriver à 1.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
Fonction nbr_termes_suite(u0:entier):entier nbr_termes <- 0 Tant que (u0 != 1) faire Si u0 div 2 = 0 alors u1 <- u0 div 2 # Si pair, diviser par 2 Sinon u1 <- 3 * u0 + 1 # Si impair, multiplier par 3 et ajouter 1 Fin si u0 <- u1 nbr_termes <- nbr_termes + 1 # Incrémenter le compteur Fin tant que retourner nbr_termes Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| u1 | entier |
| nbr_termes | entier |
La procédure remplir_fichier_suite
La procédure remplir_fichier_suite parcourt toutes les valeurs de départ dans Depart.dat, calcule pour chacune le nombre de termes de la suite U, et enregistre ces informations dans un fichier binaire Suite.dat sous forme de dictionnaires.
Étapes détaillées du fonctionnement
1- Affichage d’un message
La procédure informe l’utilisateur que le calcul et l’enregistrement des suites vont commencer.
2- Ouverture des fichiers
Depart.dat : fichier texte contenant les valeurs de départ.
Suite.dat : fichier binaire où seront enregistrées les informations pour chaque suite.
3- Lecture des lignes du fichier de départ
Chaque ligne contient un nombre saisi par l’utilisateur.
La procédure supprime le caractère \n à la fin de chaque ligne pour ne garder que le nombre.
Elle calcule le nombre de termes de la suite et prépare un enregistrement contenant la valeur de départ et le nombre de termes.
Elle écrit l'enregistrement dans le fichier binaire et enregistre le dictionnaire dans Suite.dat au format binaire avec pickle.
4- Fermeture des fichiers
La procédure sauvegarde les données et libère les ressources.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Procedure remplir_fichier_suite() Ecrire('*** Contenu du fichier Suite.dat ***') Ouvrir(f_depart , "Depart.dat", "r") # Lecture des valeurs de départ Ouvrir(f_suite , open("Suite.dat", "wb") # Création du fichier binaire pour les suites termes_u0 <- f_depart.readlines() # Lecture de toutes les lignes Pour u0 dans termes_u0 faire u0 <- u0.strip('\n') # Suppression du retour à la ligne nbr_termes <- nbr_termes_suite(Valeur(u0)) # Calcul du nombre de termes # Remplissage du dictionnaire suite_enregistrement['dep'] <- u0 suite_enregistrement['nb'] <- nbr_termes # Affichage du résultat pour l'utilisateur print('u0= ', u0, 'nbr_termes= ', nbr_termes) # Écriture du dictionnaire dans le fichier binaire Ecrire(f_suite,suite_enregistrement) Fin pour Fermer(f_depart) Fermer(f_suite) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f_depart | fichier |
| f_suite | fichier |
| termes_u0 | chaîne |
| u0 | chaîne |
| suite_enregistrement | Enregistrement |
| nbr_termes | entier |
La fonction recherche_terme_min
La fonction lit toutes les valeurs de départ dans Depart.dat, calcule le nombre de termes de chaque suite de Collatz, et retourne le plus petit nombre de termes trouvé.
Étapes détaillées du fonctionnement
1- Ouverture du fichier de départ
La fonction ouvre le fichier texte contenant les valeurs de départ des suites.
2- Lecture de la première valeur
La fonction lit la première ligne et supprime le retour à la ligne.
3- Initialisation du minimum
La fonction calcule le nombre de termes de la suite pour la première valeur u0.
Ce nombre sert d’initialisation du minimum.
4- Lecture de la deuxième valeur et boucle sur toutes les autres
La fonction parcourt toutes les lignes suivantes jusqu’à la fin du fichier.
5- Mise à jour du minimum
Pour chaque valeur de départ, la fonction calcule le nombre de termes de sa suite.
Si ce nombre est inférieur au minimum courant, on met à jour le minimum.
6- Lecture de la ligne suivante
La fonction passe à la valeur suivante.
7- Fermeture du fichier
La fonction libère la ressource après avoir terminé la lecture.
8- Retour du résultat
La fonction renvoie le nombre minimal de termes parmi toutes les suites.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Fonction recherche_terme_min():entier Ouvrir(f_depart , "Depart.dat", "r") u0 <- Lire_ligne(f_depart) u0 <- u0.strip('\n') terme_min <- nbr_termes_suite(int(u0)) # Initialisation avec le premier élément u0 <- Lire_ligne(f_depart) # Parcours de tous les autres éléments Tant que u0 != "" faire u0 <- u0.strip('\n') # Si le nombre de termes de cette suite est inférieur au minimum, on le remplace Si terme_min > nbr_termes_suite(int(u0)) alors terme_min <- nbr_termes_suite(int(u0)) Fin si u0 <- Lire_ligne(f_depart) Fin tant que Ouvrir(f_depart) retourner terme_min # Retourne le nombre minimal de termes Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f_depart | fichier |
| u0 | chaîne |
| terme_min | entier |
La procédure afficher_termes_min
Cette procédure permet de remplir le tableau t avec les 9 pixels voisins du pixel situé à la position (i, j) dans la matrice m, y compris le pixel central.
La matrice m représente une image (ou une matrice de pixels).
Le pixel central est m[i][j].
Les pixels voisins correspondent au voisinage 3×3 autour de ce pixel.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
Procedure afficher_termes_min(terme_min:entier) Ecrire('*** Les valeurs Dep ayant le Nb minimal ***') Ouvrir(f_suite , "Suite.dat", "rb") Tant que Vrai: Essayer: suites <- Lire_enregistrement(f_suite) # Lecture d'un enregistrement # Si le nombre de termes correspond au minimum, on affiche Si int(suites["nb"]) == terme_min: print("Dep :", suites["dep"], " Nb :", suites["nb"]) en Cas de fin de fichier : # Fin du fichier atteinte sortir Fin tant que Ouvrir(f_suite) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f_suite | fichier |
| suites | enregistrement |
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 |
import pickle from pickle import load, dump # -------------------------------------------------- # Dictionnaire qui contiendra : # - 'dep' : la valeur de départ de la suite # - 'nb' : le nombre de termes de la suite avant d'atteindre 1 # -------------------------------------------------- suite_enregistrement = dict( dep=int(), nb=int() ) # -------------------------------------------------- # Fonction qui permet de saisir un entier n # strictement compris entre inf et sup # -------------------------------------------------- def saisie(inf, sup): # Saisie initiale d'un entier par l'utilisateur n = int(input('donner n tel que ' + str(inf) + '< n < ' + str(sup) + ': ')) # Tant que l'entier n n'est pas dans l'intervalle ]inf, sup[, on redemande while (n <= inf) or (n >= sup): n = int(input('donner n tel que ' + str(inf) + '< n < ' + str(sup) + ': ')) # Retourne la valeur valide saisie return n # -------------------------------------------------- # Procedure pour remplir le fichier "Depart.dat" # avec p nombres saisis par l'utilisateur # -------------------------------------------------- def remplir_fichier_depart(p): print('*** Remplir le fichier Depart.dat ***') # Ouverture du fichier en mode écriture texte f = open("Depart.dat", "w") for i in range(p): # Saisie d'une valeur valide entre 2 et 2000 u0 = saisie(2, 2000) # Écriture de la valeur dans le fichier, une par ligne f.write(str(u0) + '\n') f.close() # -------------------------------------------------- # Fonction qui calcule le nombre de termes # de la suite de Collatz à partir de u0 # -------------------------------------------------- def nbr_termes_suite(u0): nbr_termes = 0 while (u0 != 1): if u0 % 2 == 0: u1 = u0 // 2 # Si pair, diviser par 2 else: u1 = 3 * u0 + 1 # Si impair, multiplier par 3 et ajouter 1 u0 = u1 nbr_termes = nbr_termes + 1 # Incrémenter le compteur return nbr_termes # -------------------------------------------------- # Procedure qui remplit le fichier "Suite.dat" # contenant les dictionnaires avec : # - valeur de départ # - nombre de termes de la suite # Le fichier est en mode binaire grâce à pickle # -------------------------------------------------- def remplir_fichier_suite(): print('*** Contenu du fichier Suite.dat ***') f_depart = open("Depart.dat", "r") # Lecture des valeurs de départ f_suite = open("Suite.dat", "wb") # Création du fichier binaire pour les suites termes_u0 = f_depart.readlines() # Lecture de toutes les lignes for u0 in termes_u0: u0 = u0.strip('\n') # Suppression du retour à la ligne nbr_termes = nbr_termes_suite(int(u0)) # Calcul du nombre de termes # Remplissage du dictionnaire suite_enregistrement['dep'] = u0 suite_enregistrement['nb'] = nbr_termes # Affichage du résultat pour l'utilisateur print('u0= ', u0, 'nbr_termes= ', nbr_termes) # Écriture du dictionnaire dans le fichier binaire dump(suite_enregistrement, f_suite) f_depart.close() f_suite.close() # -------------------------------------------------- # Fonction qui recherche le nombre minimal de termes # parmi toutes les suites # -------------------------------------------------- def recherche_terme_min(): f_depart = open("Depart.dat", "r") u0 = f_depart.readline() u0 = u0.strip('\n') terme_min = nbr_termes_suite(int(u0)) # Initialisation avec le premier élément u0 = f_depart.readline() # Parcours de tous les autres éléments while u0 != "": u0 = u0.strip('\n') # Si le nombre de termes de cette suite est inférieur au minimum, on le remplace if terme_min > nbr_termes_suite(int(u0)): terme_min = nbr_termes_suite(int(u0)) u0 = f_depart.readline() f_depart.close() return terme_min # Retourne le nombre minimal de termes # -------------------------------------------------- # Procedure qui affiche les valeurs de départ # dont la suite a le nombre minimal de termes # -------------------------------------------------- def afficher_termes_min(terme_min): print('*** Les valeurs Dep ayant le Nb minimal ***') f_suite = open("Suite.dat", "rb") while True: try: suites = pickle.load(f_suite) # Lecture d'un dictionnaire # Si le nombre de termes correspond au minimum, on affiche if int(suites["nb"]) == terme_min: print("Dep :", suites["dep"], " Nb :", suites["nb"]) except EOFError: # Fin du fichier atteinte break f_suite.close() # -------------------------------------------------- # Programme principal # -------------------------------------------------- p = saisie(1, 31) # Saisie du nombre de valeurs à générer remplir_fichier_depart(p) # Remplissage du fichier de départ remplir_fichier_suite() # Calcul et sauvegarde des suites terme_min = recherche_terme_min() # Recherche du nombre minimal de termes afficher_termes_min(terme_min) # Affichage des résultats |
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
