--> Algorithmes Python pour le baccalauréat On trouvera ci-dessous les différents types d'algorithmes utilisés dans des sujets de baccalauréat. Dans chaque cas est donné un exemple concret ainsi que les explications associées. Algorithmes pour les suites Calcul d'un terme Soit $(u_n)$ la suite définie par $u_0=100$ et pour tout entier $n$, $u_{n+1}=1,03u_n-10$.
L'algorithme ci-dessous permet de calculer et d'afficher $u_{10}$ u = 100 for i in range(1,11): u = 1.03*u-10 print(u) L'instruction range(1,11) crée la liste de nombre [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].
À chaque étape de la boucle for la nouvelle valeur de u est calculée à partir de l'ancienne valeur de u, et ceci à dix reprises.
La valeur finale de la variable u est bien celle de $u_{10}$.

Si on veut afficher toutes les valeurs des termes de $u_1$ à $u_{10}$, on doit écrire print(u) à l'intérieur de la boucle for. u = 100 for i in range(1,11): u = 1.03*u-10 print(u) Si on veut afficher tous les termes de $u_0$ jusqu'à $u_{10}$, il y a deux façons de procéder.
Soit on affiche $u_0$ en écrivant print(u) juste après la première affection, et ensuite on procède comme précédemment : u = 100 print(u) for i in range(1,11): u = 1.03*u-10 print(u) Soit on affiche les valeurs successives de u à l'intérieur de la boucle avant de faire le calcul de u. Il manquera alors l'affichage du résultat du dernier calcul. On ajoute donc print(u) à la sortie de la boucle u = 100 for i in range(1,11): print(u) u = 1.03*u-10 print(u)

Pour pouvoir calculer n'importe quel terme (et pas seulement $u_{10}$) on utilise généralement une fonction à l'aide de l'instruction def. def u(n): u = 100 for i in range(1,n+1): u = 1.03*u-10 return u Si on exécute ce programme rien ne s'affiche, et c'est normal, on a juste définit une fonction qui se charge dans la mémoire de l'ordinateur (dans la RAM) mais qui n'est pas encore utilisée.
On voit que la fonction u est construite sur le même principe que les programmes précédents mais avec une valeur générique n plutôt que $10$.
Lorsque la fonction est appelée la valeur finale de la variable u est retournée (return u). def u(n): u = 100 for i in range(1,n+1): u = 1.03*u-10 return u print(u(10)) Il faut bien-sûr utiliser l'instruction print pour afficher le résultat de u(10) sinon nous n'aurions pas pu connaître la valeur retournée par la fonction u.
On peut effectuer d'autres calculs en appelant la fonction u : def u(n): u = 100 for i in range(1,n+1): u = 1.03*u-10 return u print(u(100)) Ou encore : def u(n): u = 100 for i in range(1,n+1): u = 1.03*u-10 return u s = u(0)+u(1)+u(2)+u(3) print(s) Ce type d'algorithme peut être utilisé dans les sujets de baccalauréat pour demander au candidat d'émettre une conjecture sur la suite considérée. Les conjectures doivent porter sur le sens de variation de la suite ainsi que sur son éventuelle limite. Calcul de la somme des termes d'une suite Dans le dernier exemple, on peut voir qu'il serait très long d'ajouter un à un tous les termes de la suite $(u_n)$ de $u_0$ jusqu'à $u_{100}$ par exemple.
La méthode est de calculer la somme à l'intérieur de la boucle for.
On considère maintenant la suite géométrique $(v_n)$ de premier terme $v_0=1$ et de raison $\dfrac{1}{2}$.
Le programme suivant permet de calculer $v_0+v_1+\cdots+v_{20}$ $=$ $\displaystyle{\sum_{k=0}^{20}v_k}$. La somme est obtenue à l'aide de la variable s. v = 1 s = 1 for i in range(1,21): v = 0.5*v s = s+v print(s) Pour pouvoir calculer la somme jusqu'à un terme choisi, on définit une fonction : def somme(n): v = 1 s = 1 for i in range(1,n+1): v = 0.5*v s = s+v return s print(somme(30)) Recherche de seuil Lorsqu'on sait qu'une suite est convergente, ou divergente vers $\pm\infty$, des algorithmes de recherche de seuil permettent de déterminer le premier rang où les termes de la suite sont à une certaine distance de la limite, ou dépasse une certaine valeur.
On admet que la suite $(u_n)$ définie par $u_0=500$ et pour tout entier $n$, $u_{n+1}=0,8u_n+10$, est décroissante et converge vers $50$.
L'algorithme ci-dessous permet de déterminer le premier terme $n_0$ à partir duquel, pour tout $n\geq n_0$, $u_n<51$. u = 500 n = 0 while u >= 51: n = n+1 u = 0.8*u+10 print(n) La boucle while permet d'effectuer les calculs des termes u et de leur rang n tant que le résultat de u est supérieur ou égale à $51$.
Lorsqu'on sort de la boucle while la condition n'est plus vérifiée et donc pour la valeur de n affichée on a u<51.
Pour cette suite on a donc, pour tout $n\geq28$, que $u_n <51$ (puisque $(u_n)$ est décroissante).

On peut utiliser une fonction pour généraliser cette méthode.
Dans l'algorithme ci-dessous la fonction seuil utilise un paramètre p pour retourner la valeur du premier entier $n$ tel que $u_n<50+10^{-p}$.
C'est-à-dire le rang du premier terme qui soit une valeur approchée à $10^{-p}$ de la limite. def seuil(p): u = 500 n = 0 while u>= 50+10**(-p): n = n+1 u = 0.8*u+10 return n L'utilisation ci-dessous permet d'afficher le premier rang à partir du quel les termes sont à $10^{-6}$ de la limite de la suite : def seuil(p): u = 500 n = 0 while u>= 50+10**(-p): n = n+1 u = 0.8*u+10 return n print(seuil(6)) Pour les suites divergeant vers $+\infty$ le principe est quasiment le même.
On admet que la suite $(v_n)$ définie par $v_0=50$ et pour tout entier $n$, $v_{n+1}=1.01v_n$ est croissante et diverge vers $+\infty$.
L'algorithme suivant permet de définir une fonction qui retourne le rang du premier terme où la suite dépasse $10^p$. def seuil(p): v = 50 n = 0 while v < 10**p: n = n+1 v = 1.01*v return n Un exemple d'utilisation pour déterminer le rang du premier terme qui dépasse le milliard : def seuil(p): v = 50 n = 0 while v < 10**p: n = n+1 v = 1.01*v return n print(seuil(9)) Les suites doubles On peut définir des suites « interdépendantes » comme dans l'exemple ci-dessous:

$(u_n)$ et $(v_n)$ sont deux suites définies par $u_0=20$, $v_0=60$ et pour tout entier naturel $n$ :

$u_{n+1}=\dfrac{2u_n+v_n}{4}$ et $v_{n+1}=\dfrac{u_n+2v_n}{4}$. L'algorithme ci-dessous définit une fonction qui retourne les valeurs de $u_n$ et $v_n$ pour $n$ donné. def suites(n): u = 20.0 v = 60.0 for i in range(1,n+1): w = u u = (2*u+v)/4 v = (u+2*v)/4 return u,v print(suites(10)) Les premiers termes de la suite sont donnés avec une « virgule » (u=20.0 et v=60.0) seulement pour cette version de Python. Dans un sujet de bac il n'y aura pas obligation de faire apparaître cette écriture.
La subtilité d'un tel algorithme réside ici dans l'utilisation de la variable w. En effet lorsqu'on effectue le calcul u = (2*u+v)/4 la valeur de u est modifiée et on ne peut plus utiliser son ancienne valeur pour le calcul suivant v = (u+2*v)/4.
On avait donc besoin de sauvegarder la précédente valeur de u pour le calcul de v, et nous avons utilisé pour cela ici une troisième variable w. Récurrence double Une suite définie par une double récurrence est une suite où pour calculer un terme on a besoin des deux précédents.
Observons cela dans l'exemple ci-dessous :

Soit $(u_n)$ la suite définie par $u_0=1$, $u_1=1$ et pour tout entier $n$ : $$u_{n+1}=u_{n+1}+u_n.$$ On a par exemple que $u_2=u_1+u_0$ $=$ $1+1$ $=$ $2$, ou encore $u_3=u_2+u_1$ $=$ $2+1$ $=$ $3$, etc.

L'algorithme ci-dessous définit une fonction qui permet de calculer un terme quelconque de la suite pour $n\geq1$. def u(n): u = 1 v = 1 for i in range(2,n+1): w = u+v u = v v = w return v print(u(2)) print(u(3)) print(u(4)) print(u(5)) La variable u joue ici le rôle de $u_n$, la variable v celui de $u_{n+1}$, et le résultat de $u_{n+1}+u_n$ est stocké dans la variable w.
À chaque itération il faut donc que l'ancienne valeur de v devienne la nouvelle valeur de u et que v prenne la valeur de w. Algorithmes pour les fonctions Définir une fonction Python permet de définir des fonctions à l'aide de def.
Par exemple, l'algorithme ci-dessous permet de définir la fonction $f$ définie sur $\mathbb{R}$ par $f(x)=\sqrt{x^4+1}$ : from math import* def f(x): return sqrt(x**4+1) La première ligne from math import* est nécessaire car sinon la fonction sqrt n'est pas reconnue par Python.
Pour pouvoir utiliser la fonction f on peut afficher quelques images de la sorte : from math import* def f(x): return sqrt(x**4+1) print(f(0)) print(f(10)) print(f(-50)) On peut utiliser une liste définie par compréhension pour afficher un tableau de valeurs de la fonction $f$. from math import* def f(x): return sqrt(x**4+1) L = [f(i) for i in range(0,10)] print(L) La liste L contient les images f(i) pour i compris entre 0 et 9. Approximation des solutions d'une équation On considère la fonction $f$ définie sur $\mathbb{R}$ par $f(x)=x^5+x-1$.
On admet que $f$ est strictement croissante sur $\mathbb{R}$ et que l'équation $f(x)=0$ admet une unique solution $\alpha$ sur $[0\,;1]$.
L'algorithme ci-dessous permet d'obtenir un encadrement à $10^{-2}$ de $\alpha$. def f(x): return x**5+x-1 x = 0 while f(x) < 0: x = x+0.01 print(x) Le résultat affichée, 0,76, correspond à la première valeur de x pour laquelle f(x) est positif.
Ainsi, grâce à cette algorithme on peut affirmer que : $0,75 < \alpha < 0,76$. Cet algorithme peut être écrit sans définir la fonction $f$ : x = 0 while x**5+x-1 < 0: x = x+0.01 print(x)

Pour gagner en précision on peut définir une fonction avec le pas en paramètre. La fonction equation ci-dessous possède un paramètre p qui correspond à un pas de $10^{-p}$. def f(x): return x**5+x-1 def equation(p): x = 0 while f(x) < 0: x = x+10**(-p) return x Mais cette algorithme présente un problème. Si on donne un pas très petit (donc une valeur importante pour p) il sera très lent. En effet, x part de $0$ pour avancer de très peu à chaque itération. def f(x): return x**5+x-1 def equation(p): x = 0 while f(x) < 0: x = x+10**(-p) return x print(equation(6)) On peut résoudre cet écueil en donnant un autre paramètre à la fonction en plus de p pour la valeur initiale de $x$.
Ainsi, en donnant des valeurs successives à p de plus en plus grandes et en exploitant les résultats affichés on gagne du temps d'exécution. def f(x): return x**5+x-1 def equation(p,a): x = a while f(x) < 0: x = x+10**(-p) return x print(equation(1,0)) def f(x): return x**5+x-1 def equation(p,a): x = a while f(x) < 0: x = x+10**(-p) return x print(equation(2,0.7)) def f(x): return x**5+x-1 def equation(p,a): x = a while f(x) < 0: x = x+10**(-p) return x print(equation(3,0.75)) def f(x): return x**5+x-1 def equation(p,a): x = a while f(x) < 0: x = x+10**(-p) return x print(equation(4,0.754)) def f(x): return x**5+x-1 def equation(p,a): x = a while f(x) < 0: x = x+10**(-p) return x print(equation(5,0.7548)) def f(x): return x**5+x-1 def equation(p,a): x = a while f(x) < 0: x = x+10**(-p) return x print(equation(6,0.75487))
Cette dernière exécution nous donne : $0,754\,877 < \alpha < 0,754\,878$.

La méthode de dichotomie apparaît parfois dans des sujets de baccalauréat.
La méthode de la dichotomie se rapproche de celle à employer dans le jeu du « juste prix » où il faut deviner un prix et où le présentateur répond par « plus grand » ou « plus petit ».
Il faut alors choisir le centre de l'intervalle dans lequel se trouve le prix. Par exemple si on sait que le prix est compris entre $0$ et $10\,000$ €, il faut proposer au départ $5\,000$, puis si par exemple l'animateur dit « plus grand » on doit annoncer $7\,500$ etc.

Pour une fonction dont on sait qu'elle s'annule sur $[0\,;1]$ par exemple, on calcule $f(0,5)$ en fonction du signe trouvé et et du sens de variation de $f$, la solution de $f(x)=0$ sera soit dans $[0\,;0,5]$ soit dans $[0,5\,;1]$.
Dans l'animattion ci-dessous les points rouge sur l'axe des abscisses correspondent à l'intervalle initiale. Le point vert correspond au centre de l'intervalle délimité par les points rouge.
À l'étape suivante (en faisant augmenter k de $1$), le nouvel intervalle dépend du signe que l'on avait pour l'image du point vert. Xmin = -1 Xmax = 2 Ymin = -1.2 Ymax = 2.2 function base(){ couleur = noir peinture = blanc transparence = 1 rectangle([-5,5],20,20) traceX() traceY() couleur = bleu graphe(f,0,10) couleur = rouge } function f(x){ return Math.pow(x,5)+x-1 } function dicho(n){ base() a = 0 b = 1 for(i = 0; i < n-1; i++){ c = (a+b)/2 if( f(c) < 0){ a = c } else{ b = c } } point([a,0]) point([b,0]) segment([a,0],[a,f(a)],[5,2]) segment([0,f(a)],[a,f(a)],[5,2]) segment([b,0],[b,f(b)],[5,2]) segment([0,f(b)],[b,f(b)],[5,2]) c = (a+b)/2 if( f(c) < 0){ a = c } else{ b = c } couleur = vert point([c,0]) segment([c,0],[c,f(c)],[5,2]) segment([0,f(c)],[c,f(c)],[5,2]) couleur = noir texte(c,[-0.5,1]) } base() curseur("k",1,1,10,1) dicho({k}) Appliquons cette méthode à notre fonction $f$ précédente. def f(x): return x**5+x-1 def dicho(n): a = 0 b = 1 for i in range(0,n): c = (a+b)/2 if f(c) < 0: a = c else: b = c return [a,b] print(dicho(10)) Dans la fonction dicho on répète n fois le principe exposé précédemment.
Si l'image du centre de l'intervalle $[a\,;b]$ est négative l'intervalle $[a\,;b]$ devient $[c\,;b]$ (avec c le centre de l'intervalle).
Sinon, (si l'image du centre de l'intervalle $[a\,;b]$ est positive) l'intervalle $[a\,;b]$ devient $[a\,;c]$.
La fonction dicho retourne les bornes du dernier intervalle $[a\,;b]$ calculé.

Après exécution nous voyons ici que la solution $\alpha$ vérifie :
$$0,753\,906\,25 < \alpha < 0.754\,882\,812\,5$$ Approximation d'un extremum Lorsqu'on connaît les variations d'une fonction sur un intervalle on peut vouloir y déterminer une valeur approchée de l'extremum que présente la fonction sur celui-ci.
On admet que la fonction $f$ définie pour tout réel $x$ par $f(x)=-x^4-x^3+10x+1$ est croissante puis décroissante sur $[0\,;2]$.
On cherche à déterminer sa valeur maximale sur $[0\,;2]$.
Pour cela on va avancer d'un pas constant à partir de $0$ et regarder les images successives pour en retenir la plus grande. def f(x): return -x**4-x**3+10*x+1 x = 0 sup = f(x) while x < 2: x = x+0.01 if f(x)>sup: sup = f(x) print(sup) Si on veut connaître la valeur de x pour laquelle le maximum est atteint lors de ce balayage, on ajoute une variable xmax comme suit : def f(x): return -x**4-x**3+10*x+1 x = 0 xmax = 0 sup = f(x) while x < 2: x = x+0.01 if f(x)>sup: sup = f(x) xmax =x print(xmax, sup) Dans l'algorithme ci-dessous, on définit une fonction qui prend en paramètre une variable p correspondant à un pas de $10^{-p}$ et deux paramètres a et b correspond aux bornes de l'intervalle sur lequel on cherche une approximation de maximum de la fonction. def f(x): return -x**4-x**3+10*x+1 def maximum(p,a,b): x = a sup = f(a) xmax = a while x < b: x = x+10**(-p) if f(x)>sup: sup = f(x) xmax = x return xmax, sup print(maximum(6,1.14,1.15)) On a utilisé les valeurs 1,14 et 1,15 à l'aide de l'algorithme précédent (sinon l'exécution à partir de $0$ aurait été longue). Algorithmes pour les probabilités Pour les algorithmes probabilistes, le module random devra être chargé à chaque fois.
Les deux fonctions que l'on utilisera sont random() qui fournit un nombre aléatoire de $[0\,;1[$ et randint(a,b) qui fournit un entier aléatoire entre $a$ et $b$.
Dans les exemples ci-dessous on pourra appuyer plusieurs fois sur Exécuter pour voir l'effet de ces instructions. from random import* print(random()) from random import* print(randint(1,6)) Schéma de Bernoulli ∼ Loi binomiale On considère ici une variable aléatoire $X$ suivant la loi binomiale de paramètres $80$ et $0,12$.
Par exemple :
La valeur finale de $X$ après exécution de l'algorithme suivant, correspond aux nombres de succès parmi les $80$ éléments de l'échantillon. from random import* X = 0 for i in range(0,80): e = randint(1,100) if e <= 12: X = X+1 print(X) La variable e définie à la ligne 4 retourne un entier aléatoire entre $1$ et $100$. La probabilité qu'il soit inférieur à $12$ est bien de $0,12$. Ainsi, la probabilité que la ligne 6 s'exécute est de $0,12$.
Cette manière de faire est par contre peu pratique si on veut généraliser la méthode. On va plutôt générer un nombre aléatoire entre $0$ et $1$ à l'aide de random() puis de regarder si le résultat est inférieur à $0,12$. from random import* X = 0 for i in range(0,80): e = random() if e <= 0.12: X = X+1 print(X) De cette façon on peut généraliser cet algorithme à toutes variables aléatoires suivant une loi binomiale de paramètres quelconques $n$ et $p$. from random import* def vaBinom(n,p): X = 0 for i in range(0,n): e = random() if e <= p: X = X+1 return X print(vaBinom(1000,0.5)) Expériences aléatoires avec plus de deux issues possibles Il est possible qu'une expérience aléatoire possède au moins trois issues, comme par exemple dans un lancé de dé à $6$ faces.
L'algorithme ci-dessous simule $500$ lancés d'un dé à $6$ faces équilibré. Il affiche en retour le face « moyenne » obtenue. from random import* s = 0 for i in range(0,500): s = s+randint(1,6) print(s/500) On peut dans cette situation également définir une fonction permettant de choisir le nombre de lancés du dé : from random import* def de(n): s = 0 for i in range(0,n): s = s+randint(1,6) return s/n print(de(20))

Une autre situation que l'on peut rencontrer est celle de jeux à base de roue.
Par exemple, dans une fête foraine une roue est constituée de $6$ secteurs angulaires de même surface, chacun portant un numéro distinct entre $1$ à $6$. En fonction du secteur obtenu après avoir fait tourner la roue, le joueur possède les gains suivants :
Numéro du secteur $1$ $2$ $3$ $4$ $5$ $6$
Gain $0$ $0$ $1$ $1$ $2$ $10$
Le prix de la participation au jeu est de $5$ €.
L'algorithme suivant permet de simuler $1\,000$ parties de ce jeu et affiche le gain moyen. from random import* s = 0 for i in range(0,1000): j = randint(1,6) if j == 3 or j == 4: s = s+1 if j == 5: s = s+2 if j == 6: s = s+10 gainMoyen = s/1000-5 print(gainMoyen)

On peut utiliser les fonctions aléatoires de Python dans des situations de tirages aléatoires comme dans l'exemple ci-dessous.

Parmi les $23$ joueurs d'une équipe de football, trois sont tirés au hasard pour subir un contrôle antidopage à la fin d'un match.
On suppose que les joueurs sont numérotés de $1$ jusqu'à $23$. L'algorithme ci-dessous permet d'obtenir les numéros des trois joueurs devant subir le contrôle. from random import* a = 0 b = 0 c = 0 while a == b or a == c or b == c: a = randint(1,23) b = randint(1,23) c = randint(1,23) print(a,b,c) Cet algorithme effectue un tirage aléatoire de trois nombres entre $1$ et $23$ et tant qu'au moins deux résultats sont identiques on recommence le tirage. Ainsi lorsqu'on sort de la boucle while on est assuré que les trois valeurs de a, b et c sont distinctes. Algorithmes pour le dénombrement Coefficients binomiaux La factorielle d'un entier naturel peut-être utilisée pour calculer les coefficients binomiaux. Les deux algorithmes ci-dessous définissent chacun une fonction permettant de calculer la factorielle d'un entier donné.
Le premier plus classique le fait à l'aide d'une boucle for, alors que le deuxième le fait par récursivité. C'est-à-dire qu'au sein de la fonction on effectue un appel vers cette même fonction mais pour une autre valeur du paramètre. def facto(n): f = 1 for i in range(2,n+1): f = f*i return f print("1! = ",facto(1)) print("2! = ",facto(2)) print("3! = ",facto(3)) print("4! = ",facto(4)) print("10! = ",facto(10)) def facto(n): if n == 1: f = 1 else: f = n*facto(n-1) return f print("1! = ",facto(1)) print("2! = ",facto(2)) print("3! = ",facto(3)) print("4! = ",facto(4)) print("10! = ",facto(10))

Pour calculer les coefficients binomiaux on peut, maintenant que l'on a la fonction factorielle, utilisée la formule suivante :
pour tout entier naturel $n$ et $k\leq n$, $\displaystyle{ {n \choose k} }=\dfrac{n!}{k!(n-k)!}$. def facto(n): f = 1 for i in range(2,n+1): f = f*i return f def coefBinom(n,k): return facto(n)/(facto(k)*facto(n-k)) print("3 parmi 5 : ",coefBinom(5,3)) print("4 parmi 9 : ",coefBinom(9,4))

On peut également calculer les coefficients binomiaux à l'aide de la formule de Pascal :
pour tout entier $b\geq1$ et pour tout $k\leq n$ : ${n-1 \choose k-1}+{n-1 \choose k}={n \choose k}$. def coefBinom(n,k): if n == 1 and (k ==0 or k ==1): f = 1 else: f = 0 if n > 1: f = coefBinom(n-1,k-1)+coefBinom(n-1,k) return f print("3 parmi 5 : ",coefBinom(5,3)) print("4 parmi 9 : ",coefBinom(9,4))
En combinatoire on s'intéresse également aux arrangements des éléments d'un ensemble.
L'algorithme ci-dessous permet d'obtenir la liste des arrangements composés de deux éléments d'un ensemble qui est donné sous la forme d'une liste. def arr2(A): n = len(A) for i in range(0,n): for j in range(0,n): if j != i: print(A[i],A[j]) arr2([1,2,3,4]) La ligne 5 if j != i: est importante, puisque dans un arrangement il ne peut y avoir de répétitions.
L'algorithme suivant est basé sur le même principe, et affiche la liste des arrangements de trois éléments d'un ensemble donné. def arr3(A): n = len(A) for i in range(0,n): for j in range(0,n): for k in range(0,n): if k != j and k !=i and i != j: print(A[i],A[j],A[k]) arr3(['a','b','c','d'])