Problème suite de Fibonacci – Bac théorique – Section informatique – 2026
Sujet (Algo et programmation - Bac 2026)
En se basant sur le triangle de Pascal, on peut calculer les termes de la suite de Fibonacci et les termes de la suite diatomique de Stern en appliquant le procédé suivant:
- Les termes de la suite de Fibonacci sont déterminés en calculant la somme des valeurs situées sur chaque diagonale ascendante du triangle de Pascal (diagonale partant du bord gauche et montant vers la droite comme illustré par la figure Fig1 ci-après).
- Les termes de la suite diatomique de Stern sont déterminés en comptant le nombre de valeurs impaires situées sur chaque diagonale ascendante du triangle de Pascal (diagonale partant du bord gauche et montant vers la droite comme illustré par la figure Fig2 ci-après).
Exemples:
- Les 9 termes de la suite de Fibonacci de F1 à F9 sont: 1, 1, 2, 3, 5, 8, 13, 21 et 34. Ces termes sont déterminés à partir du triangle de Pascal en utilisant le procédé décrit précédemment, comme l'illustre la figure Fig1 ci-après.
- Les 9 termes de la suite diatomique de Stern de S1 à S9 sont: 1, 1, 2, 1, 3, 2, 3, 1 et 4. Ces termes sont déterminés à partir du triangle de Pascal en utilisant le procédé décrit précédemment, comme l'illustre la figure Fig2 ci-après.
Travail demandé :
1) Ecrire un algorithme d'une procédure TrianglePascal(M, N) qui permet de remplir une matrice M par les N premières lignes du triangle de Pascal en utilisant le procédé suivant:
- Les lignes sont remplies jusqu'à la diagonale principale.
- Pour chaque ligne :
Le premier élément et le dernier élément sont égaux à 1,
Les autres éléments sont déterminés en appliquant la formule suivante : M[ligne, colonne] = M[ligne - 1, colonne] + M[ligne - 1, colonne - 1]
NB: M est de type Mat et N est un entier supérieur ou égal à 5 déjà saisi dans le programme appelant.
2) Ecrire un algorithme d'une procédure Remplir(M, N, TFS) qui permet de remplir un tableau TFS, de type Tab, par N enregistrements où chaque enregistrement est composé des deux champs suivants :
- Fib: le terme de rang i de la suite de Fibonacci (i = [1..N]).
- Ste le terme de rang i de la suite diatomique de Stern (i e [1..N]).
Le calcul des termes de la suite de Fibonacci et les termes de la suite diatomique de Stern se fait à partir de la matrice M, déjà remplie par les N premières lignes du triangle de Pascal et en utilisant le procédé décrit précédemment.
Exemple : Pour N = 9, le tableau TFS est:
3) Une société de télécommunication organise un jeu promotionnel destiné à ses abonnés fidèles.
Chaque abonné est identifié par un matricule, qui est une chaine de caractères composée de 4 chiffres. Les matricules sont stockés dans un fichier texte nommé "Fidele.txt", à raison d'un matricule par ligne.
Ecrire un algorithme d'un programme qui permet de:
- Saisir un entier N (avec 5 ≤ N ≤ 100).
- Remplir une matrice M par les N premières lignes du triangle de Pascal en faisant appel à la procédure TrianglePascal.
- Remplir un tableau TFS par N enregistrements en faisant appel à la procédure Remplir.. Créer et remplir un fichier texte nommé "Gagnants.txt" par les gagnants et les super gagnants, sachant qu':
- un abonné est déclaré "Gagnant" si la somme des chiffres de son matricule est un terme de la suite de Fibonacci figurant dans le tableau TFS ou un terme de la suite diatomique de Stern figurant dans le tableau TFS.
- un abonné est déclaré "Super gagnant" si la somme des chiffres de son matricule est à la fois un terme de la suite de Fibonacci et un terme de la suite diatomique de Stern figurants dans le tableau TFS, non obligatoirement dans la même case.
NB:
Chaque ligne du fichier "Gagnants.txt" doit contenir le matricule du gagnant, suivi d'un espace, puis du commentaire "Gagnant" ou "Super gagnant" selon le cas. Le fichier "Fidele.txt" est enregistré sur la racine du disque D.
Le fichier "Gagnants.txt" est à créer sur la racine du disque D.
Exemple: À partir du tableau TFS de la question 2) et du fichier texte "Fidele.txt", dont le contenu est présenté dans la première colonne du tableau suivant, on obtient le fichier texte "Gagnants.txt", dont le contenu figure dans la deuxième colonne du même tableau :
En effet :
Pour le matricule 2001, la somme de ses chiffres est égale à 3, qui est à la fois un terme de la suite de Fibonacci figurant dans le tableau TFS à la case d'indice 4 et un terme de la suite diatomique de Stern figurant dans le tableau TFS à la case d'indice 5. Par conséquent il est déclaré "Super gagnant".
Pour le matricule 0130, la somme de ses chiffres est égale à 4 qui est seulement un terme de la suite diatomique de Stern figurant dans le tableau TFS à la case d'indice 9, donc il est déclaré "Gagnant".
Pour le matricule 3110, la somme de ses chiffres est égale à 5. Le nombre 5 est un terme de la suite de Fibonacci figurant dans le tableau TFS à la case d'indice 5. Cependant, bien qu'il appartienne mathématiquement à la suite diatomique de Stern, il ne figure pas dans le tableau TFS pour cette suite. Par conséquent, ce matricule est déclaré "Gagnant", mais non "Super gagnant".
Solution Algorithmique
Dans cet algorithme, On va utiliser huit fonctions et deux procédures :
- la fonction saisie_n()
- la fonction sommefacteurs()
- la fonction somme_chiffres()
- la fonction test_nombre_fort()
- la procédure NbrFort()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 9 |
Algorithme nbr_fort Debut # Création du fichier des abonnés fidèles remplir_fidele() # Saisie du nombre de lignes du triangle de Pascal n = saisie_n() # Détermination des gagnants et création du fichier résultat remplir_gagnants() Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La fonction saisie_n
Cette fonction permet de saisir et retourner un entier entre 5 et 100 en contrôlant la validité de la saisie.
|
1 2 3 4 5 6 7 8 9 10 |
Fonction saisie_n():entier Ecrire('saisir 5<=n<=100: ') Lire(n) # Tant que la valeur saisie n’est pas valide, on redemande Tant que Non (5<=n<=100) faire Ecrire('saisir 5<=n<=100: ') Lire(n) Fin tant que retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La procédure trianglepascal
Cette procédure permet de construire et d'afficher le triangle de Pascal jusqu'à la nᵉ ligne en remplissant une matrice selon la règle où les éléments des bords valent 1 et chaque élément intérieur est égal à la somme des deux éléments situés au-dessus de lui.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
Procédure trianglepascal(m:matrice, n:entier) # Remplissage du triangle Pour i de 1 à n faire Pour j de 0 à i-1 faire # Premier et dernier élément de chaque ligne Si (j = 0) ou (j =i-1) alors m[i][j] <- 1 # Calcul des éléments internes Sinon m[i][j] <- m[i-1][j] + m[i-1][j-1] Fin si Fin pour Fin pour # Affichage du triangle Pour i de 1 à n faire Pour j de 0 à i-1: Ecrire(m[i][j]) Fin pour Ecrire() Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
La procédure remplir
Cette procédure parcourt les lignes du triangle de Pascal, calcule pour chacune une somme particulière et le nombre de valeurs impaires correspondantes, enregistre ces résultats dans le tableau tfs, puis affiche son contenu.
|
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 |
Procédure remplir(m:matrice,n:entier,tfs:tab) Pour i de 1 à n+1 faire somme <- 0 nbr_impaires <- 0 # Parcours de la moitié de la ligne Pour j de 0 à (i div 2 + 1) faire # Calcul de la somme somme <- somme + m[i-j][j] # Comptage des nombres impairs Si m[i-j][j] mod 2 != 0 alors nbr_impaires <- nbr_impaires + 1 Fin si # Création d'un nouvel enregistrement enregistrement = Enregistrement( Fib:entier, Ste=entier ) # Stockage des résultats enregistrement['Fib'] <- somme enregistrement['Ste'] <- nbr_impaires # Insertion dans le tableau tfs[i] <- enregistrement # Affichage du contenu du tableau Pour i de 1 à n+1 faire Ecrire(tfs[i]['Fib'], ',', tfs[i]['Ste']) Finpour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| j | entier |
| somme | entier |
| nbr_impaires | entier |
La procédure remplir_fidele
Cette procédure crée le fichier Fidele.txt, y enregistre les matricules des abonnés fidèles saisis par l'utilisateur, à raison d'un matricule par ligne, puis ferme le fichier.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
Procédure remplir_fidele() Ecrire("Remplir le fichier Fidèle") # Ouverture du fichier en écriture Ouvrir("Fidele.txt" , f , "w") # Saisie du nombre d'abonnés Ecrire("donner le nombre des abonnés fideles :") Lire(n) # Saisie des matricules Pour i de 0 à n-1 faire Ecrire("donner une matricule formée de 4 chiffres :") Lire(matricule) Ecrire(f, matricule + '\n') Fin pour # Fermeture du fichier Fermer(f) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | fichier texte |
| n | entier |
| i | entier |
| matricule | chaîne des caractères |
La fonction somme_chiffres
Cette fonction calcule et retourne la somme des chiffres d’un nombre donné sous forme de chaîne de caractères.
|
1 2 3 4 5 6 7 |
Fonction somme_chiffres(ch:chaine):entier s <- 0 Pour i de 0 à long(ch)-1 faire s <- s+Valeur(ch[i]) Fin pour retourner s Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | entier |
| s | entier |
La procédure recherche
Cette fonction calcule la somme des chiffres d’un matricule et vérifie si cette somme existe dans les champs Fib et Ste du tableau tfs, puis retourne le nombre de correspondances trouvées.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
Procédure recherche(matricule:chaîne, tfs:tab, n:entier) # Calcul de la somme des chiffres du matricule s <- somme_chiffres(matricule) resultat <- 0 # Recherche dans le champ Fib i <- 1 Tant que (i < n) et (tfs[i]['Fib'] != s) faire i <- i+1 Fin tant que Si tfs[i]['Fib'] = s alors resultat <- resultat + 1 Finsi # Recherche dans le champ Ste i <- 1 Tant que (i < n) et (tfs[i]['Ste'] != s) faire i <- i+1 Fin tant que Si tfs[i]['Ste'] = s alors resultat <- resultat + 1 Fin si retourner resultat Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| s | entier |
| resultat | entier |
| i | entier |
La procédure remplir_gagnants
Cette procédure lit les matricules des abonnés fidèles, construit les données nécessaires à partir du triangle de Pascal, détermine les gagnants et super gagnants selon une recherche dans un tableau de résultats, puis enregistre les résultats dans un fichier Gagnants.txt.
|
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 |
Procédure remplir_gagnants(n:entier) # Ouverture des fichiers Ouvrir("Fidele.txt",f_fidele, "r") Ouvrir"Gagnants.txt",f_gagnant ,"w") # Lecture du premier matricule Lire_ligne(f_fidele,matricule) # Construction du triangle de Pascal trianglepascal(m, n) # Remplissage du tableau tfs remplir(m, n ,tfs) Ecrire("Le contenu du fichier Gagnants.txt") # Parcours de tous les matricules Tant que (matricule != '') faire # Suppression du caractère de fin de ligne matricule <- matricule.strip('\n') # Recherche des correspondances Si recherche(matricule, tfs, n) = 1 alors Ecrire(matricule, ' Gagnant') Ecrire(f_gagnant,matricule + ' Gagnant\n') Sinon recherche(matricule, tfs, n) = 2 alors Ecrire(matricule, ' Super Gagnant') Ecrire(f_gagnant,matricule + ' Super gagnant\n') Fin si # Lecture du matricule suivant Lire_ligne(f_fidele,matricule) Fin tant que # Fermeture des fichiers Fermer(f_fidele) Fermer(f_gagnant) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f_fidele | fichier texte |
| f_gagnant | fichier texte |
| matricule | chaîne des caractères |
| m | matrice des entier |
| tfs | tableau des enregistrements |
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 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 |
from numpy import array # ========================================================== # Déclaration des constantes # ========================================================== lignes = 100 # Nombre maximal de lignes de la matrice colonnes = 100 # Nombre maximal de colonnes de la matrice # ========================================================== # Structure d'un enregistrement contenant : # Fib : somme calculée dans le triangle de Pascal # Ste : nombre de valeurs impaires correspondantes # ========================================================== enregistrement = dict( Fib=int(), Ste=int() ) # Tableau de 100 enregistrements tfs = array([{}] * 100) # ========================================================== # Création d'une matrice de taille maximale # Elle servira à stocker le triangle de Pascal # ========================================================== m = array([[int()] * colonnes] * lignes) # ========================================================== # Fonction permettant de saisir un entier entre 5 et 100 # ========================================================== def saisie_n(): n = int(input("donner 5<=n<=100 : ")) while not(5<=n<=100): n = int(input("donner 5<=n<=100 : ")) return n # ========================================================== # Construction et affichage du triangle de Pascal # Les bords du triangle valent 1 et les autres éléments # sont obtenus par la somme des deux éléments supérieurs # ========================================================== def trianglepascal(m, n): # Remplissage du triangle for i in range(1, n + 1): for j in range(i): # Premier et dernier élément de chaque ligne if (j == 0) or (j == i - 1): m[i][j] = 1 # Calcul des éléments internes else: m[i][j] = m[i - 1][j] + m[i - 1][j - 1] # Affichage du triangle for i in range(1, n + 1): for j in range(i): print(m[i][j], end=" ") print() # ========================================================== # Remplit le tableau tfs # Pour chaque ligne du triangle : # - calcule une somme particulière # - compte les valeurs impaires # ========================================================== def remplir(m, n , tfs): for i in range(1, n + 1): somme = 0 nbr_impaires = 0 # Parcours de la moitié de la ligne for j in range(i // 2 + 1): # Calcul de la somme somme = somme + m[i - j][j] # Comptage des nombres impairs if m[i - j][j] % 2 != 0: nbr_impaires = nbr_impaires + 1 # Création d'un nouvel enregistrement enregistrement = dict( Fib=int(), Ste=int() ) # Stockage des résultats enregistrement['Fib'] = somme enregistrement['Ste'] = nbr_impaires # Insertion dans le tableau tfs[i] = enregistrement # Affichage du contenu du tableau for i in range(1, n + 1): print(tfs[i]['Fib'], ',', tfs[i]['Ste']) # ========================================================== # Création du fichier "Fidele.txt" # contenant les matricules des abonnés fidèles # ========================================================== def remplir_fidele(): print("Remplir le fichier Fidèle") # Ouverture du fichier en écriture f = open("Fidele.txt", "w") # Saisie du nombre d'abonnés n = int(input("donner le nombre des abonnés fideles :")) # Saisie des matricules for i in range(n): matricule = input("donner une matricule formée de 4 chiffres :") f.write(matricule + '\n') # Fermeture du fichier f.close() # ========================================================== # Calcule la somme des chiffres d'une chaîne numérique # Exemple : "1234" --> 10 # ========================================================== def somme_chiffres(ch): s = 0 for i in range(len(ch)): s = s + int(ch[i]) return s # ========================================================== # Recherche si la somme des chiffres du matricule # apparaît dans le champ Fib et/ou Ste du tableau tfs # # Retour : # 0 : aucune correspondance # 1 : une seule correspondance # 2 : deux correspondances # ========================================================== def recherche(matricule, tfs, n): # Calcul de la somme des chiffres du matricule s = somme_chiffres(matricule) resultat = 0 # Recherche dans le champ Fib i = 1 while (i < n) and (tfs[i]['Fib'] != s): i = i + 1 if tfs[i]['Fib'] == s: resultat = resultat + 1 # Recherche dans le champ Ste i = 1 while (i < n) and (tfs[i]['Ste'] != s): i = i + 1 if tfs[i]['Ste'] == s: resultat = resultat + 1 return resultat # ========================================================== # Création du fichier "Gagnants.txt" # Un matricule est : # - Gagnant si une seule correspondance est trouvée # - Super Gagnant si deux correspondances sont trouvées # ========================================================== def remplir_gagnants(n): # Ouverture des fichiers f_fidele = open("Fidele.txt", "r") f_gagnant = open("Gagnants.txt", "w") # Lecture du premier matricule matricule = f_fidele.readline() # Construction du triangle de Pascal trianglepascal(m, n) print('***************************') # Remplissage du tableau tfs remplir(m, n ,tfs) print('***************************') print("Le contenu du fichier Gagnants.txt") # Parcours de tous les matricules while (matricule != ''): # Suppression du caractère de fin de ligne matricule = matricule.strip('\n') # Recherche des correspondances if recherche(matricule, tfs, n) == 1: print(matricule, ' Gagnant') f_gagnant.write(matricule + ' Gagnant\n') elif recherche(matricule, tfs, n) == 2: print(matricule, ' Super Gagnant') f_gagnant.write(matricule + ' Super gagnant\n') # Lecture du matricule suivant matricule = f_fidele.readline() # Fermeture des fichiers f_fidele.close() f_gagnant.close() # ========================================================== # Programme principal # ========================================================== # Création du fichier des abonnés fidèles remplir_fidele() # Saisie du nombre de lignes du triangle de Pascal n = saisie_n() # Détermination des gagnants et création du fichier résultat remplir_gagnants(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
