Coefficient binomial – Bac théorique – Section informatique – 2024
Sujet (Algo et programmation - Bac 2024)
Pour deux entiers naturels n et k, le coefficient binomial qu'on note Cb (n,k) est défini comme étant le nombre de sous-ensembles différents, à k éléments, que l'on peut former à partir d'un ensemble contenant n éléments
Le coefficient binomial Cb (n,k) est un entier naturel vérifiant l'un des trois cas suivants :
Travail demandé :
- Sachant que le fichier "Coeff.txt" contient au maximum 50 couples d'entiers, déclarer un type pour le tableau T ainsi que tout type nécessaire à sa déclaration.
- Ecrire un algorithme d'une procédure nommée Remplir (Ch , T) qui permet de remplir le tableau T comme décrit précédemment.
NB :
Le candidat n'est pas appelé à remplir le fichier "Coeff.txt". On rappelle que chaque ligne du fichier contient un couple d'entiers ayant le format (n,k).
Le paramètre Ch utilisé dans l'entête du module Remplir est une chaine de caractères contenant l'emplacement et le nom physique du fichier "Coeff.txt".
La procédure Remplir doit prendre en charge l'ouverture et la fermeture du fichier "Coeff.txt".
Solution Algorithmique
Dans cet algorithme, On va utiliser deux fonctions fonctions et trois procédures
- la fonction saisie()
- la procédure remplir_fichier_coeff()
- la fonction cb()
- la procédure remplir_tableau()
- la procédure afficher_tableau()
Algorithme du programme Principal
|
1 2 3 4 5 6 7 8 |
Algorithme coefficient_binomial Debut taille <- saisie() # Saisie de la taille remplir_fichier_coeff(taille) # Remplissage du fichier remplir_tableau(t) # Lecture du fichier et calcul afficher_tableau(t, taille) # Affichage du résultat Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| taille | entier |
| t | tableau des enregistrements |
La fonction saisie
Cette fonction permet de saisir et retourner un entier > 0 en contrôlant la validité de la saisie.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Fonction saisie():entier # Demande à l'utilisateur de saisir un entier n tq 0<n<=50 Ecrire('donner un entier n tq 0<n<=50') Lire(n) # Vérification de la validité de la saisie Tant que Non (0<n<=50) faire Ecrire('donner un entier n tq 0<n<=50 : ') Lire(n) Fin tant que # Retourne la valeur valide saisie par l'utilisateur retourner n Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La procédure remplir_fichier_coeff
Le rôle de cette procédure est de créer et remplir le fichier texte Coeff.txt en y enregistrant des couples de nombres entiers (n, k) saisis par l’utilisateur.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
Procedure remplir_fichier_coeff(taille:entier) Ecrire('*** Remplir fichier Coeff.txt ***') # Ouverture du fichier en mode écriture texte Ouvrir(f , "Invites.txt", "w") # Saisie de "taille" couples (n, k) Pour i de 0 à taille-1 faire Ecrire('donner n : ') Lire(n) ('donner k : ') Lire(k) # Écriture du couple sous la forme (n,k) Ecrire(f,'(' + Convch(n) + ',' + Convch(k) + ')' + '\n') Fin pour # Fermeture du fichier Fermer(f) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | fichier |
| i | entier |
| n | entier |
| k | entier |
La fonction cb
Le rôle de cette fonction est de calculer le coefficient binomial C(n,k) en utilisant une méthode récursive, basée sur la relation du triangle de Pascal.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
Fonction cb(n:entier, k:entier):entier # Cas où le coefficient est nul Si n < k alors retourner 0 # Cas de base Sinon Si k = 0 ou k = n alors retourner 1 # Cas récursif Sinon Si 1 <= k <= n - 1 alors retourner cb(n-1,k-1)+cb(n - 1, k) Fin si Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| n | entier |
La procédure remplir_tableau
Cette procédure lit les couples (n,k) à partir du fichier Coeff.txt, calcule pour chacun le coefficient binomial correspondant et remplit le tableau t par des enregistrements contenant n, k et C(n,k).
|
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 |
Procedure remplir_tableau(t:tableau) # Ouverture du fichier en mode lecture Ouvrir (f , "Coeff.txt", "r") # Lecture de toutes les lignes du fichier couples <- Lire_lignes(f) i <- 0 # Traitement de chaque couple (n,k) Pour couple dans couples faire # Création d’un enregistrement pour stocker les données binomial = Enregistrement( n=int(), k=int(), r=int() ) # Suppression du retour à la ligne couple <- couple.strip('\n') # Extraction de n et k depuis la chaîne binomial['n'] <- Valeur(Sous_chaine(couple , 1 , Pos(couple , ',')) binomial['k'] <- Valeur(Sous_chaine(couple , Pos(couple , ',')+1 , Pos(couple , ')')) # Calcul du coefficient binomial binomial['r'] <- cb(binomial['n'], binomial['k']) # Stockage dans le tableau t[i] <- binomial i <- i+1 Fin pour # Fermeture du fichier Fermer(f) Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| f | fichier |
| couples | chaîne |
| couple | chaîne |
| i | entier |
| binomial | enregistrement |
La procédure afficher_tableau
Cette Procédure affiche le contenu du tableau t.
|
1 2 3 4 5 6 |
Procédure afficher_tableau(t:tableau, taille:entier) Ecrire("*** Le contenu du tableau T ***") Pour i de 0 à taille-1 faire Ecrire(t[i]) Fin pour Fin |
Déclaration des objets
| Objet | Type / Nature |
|---|---|
| i | 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 |
from numpy import * # -------------------------------------------------- # Déclaration d’un tableau global de taille 50 # Chaque case contiendra un enregistrement représentant # un coefficient binomial (n, k, r) # -------------------------------------------------- t = array([{}] * 50) # -------------------------------------------------- # Fonction de saisie de la taille # Elle demande un entier n tel que 0 < n ≤ 50 # -------------------------------------------------- def saisie(): # Saisie initiale n = int(input('donner un nombre n tq 0<n<=50: ')) # Vérification de la validité de la saisie # Tant que n n’est pas compris entre 1 et 50 while not (0 < n <= 50): n = int(input('donner un nombre n tq 0<n<=50: ')) # Retour de la valeur valide return n # -------------------------------------------------- # Procédure qui remplit le fichier "Coeff.txt" # Chaque ligne contient un couple (n, k) # -------------------------------------------------- def remplir_fichier_coeff(taille): print('*** Remplir fichier Coeff.txt ***') # Ouverture du fichier en mode écriture f = open("Coeff.txt", "w") # Saisie de "taille" couples (n, k) for i in range(taille): n = int(input('donner n : ')) k = int(input('donner k : ')) # Écriture du couple sous la forme (n,k) f.write('(' + str(n) + ',' + str(k) + ')' + '\n') # Fermeture du fichier f.close() # -------------------------------------------------- # Fonction récursive qui calcule le coefficient binomial # C(n,k) selon la formule : # C(n,k) = C(n-1,k-1) + C(n-1,k) # -------------------------------------------------- def cb(n, k): # Cas où le coefficient est nul if n < k: return 0 # Cas de base elif k == 0 or k == n: return 1 # Cas récursif elif 1 <= k <= n - 1: return cb(n - 1, k - 1) + cb(n - 1, k) # -------------------------------------------------- # Procédure qui lit le fichier "Coeff.txt" # et remplit le tableau t par des dictionnaires # -------------------------------------------------- def remplir_tableau(t): # Ouverture du fichier en mode lecture f = open("Coeff.txt", "r") # Lecture de toutes les lignes du fichier couples = f.readlines() i = 0 # Traitement de chaque couple (n,k) for couple in couples: # Création d’un enregistrement pour stocker les données binomial = dict( n=int(), k=int(), r=int() ) # Suppression du retour à la ligne couple = couple.strip('\n') # Extraction de n et k depuis la chaîne binomial['n'] = int(couple[1:couple.find(',')]) binomial['k'] = int(couple[couple.find(',') + 1:couple.find(')')]) # Calcul du coefficient binomial binomial['r'] = cb(binomial['n'], binomial['k']) # Stockage dans le tableau t[i] = binomial i = i + 1 # Fermeture du fichier f.close() # -------------------------------------------------- # Procédure d’affichage du contenu du tableau t # -------------------------------------------------- def afficher_tableau(t, taille): print("*** Le contenu du tableau T ***") for i in range(taille): print(t[i]) # -------------------------------------------------- # Programme principal # -------------------------------------------------- taille = saisie() # Saisie de la taille remplir_fichier_coeff(taille) # Remplissage du fichier remplir_tableau(t) # Lecture du fichier et calcul afficher_tableau(t, taille) # Affichage du résultat |
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
