Python

Exercices corrigés utilisant le langage Python, pour Mpsi, Mpii, Pcsi, et Spé Mp, Pc, Mpsi (concours Polytechnique, Ens, Mines-Monts, Centrale, etc.)

Recherche de rep-units

On admet que tout {n\in\mathbb{N}} impair non multiple de {5} a un multiple {N} ne s’écrivant (en base {10}) qu’avec des {1}. L’objet de cet exercice est de programmer la recherche de N, et d’étudier pour quelles valeurs de n l’entier N a une longueur record

Des milliers de décimales de π

Soit x=\displaystyle\sum_{k=0}^{+\infty}p_k\,u_k, où {u_k=\dfrac{(k!)^2\,2^{k}}{(2k+1)!}}.
Ce développement est dit régulier si {\begin{cases}\forall k\ge1,\; 0\le p_k\le 2k\\\forall n\ge1,\;\exists m\ge n, p_m\lt 2k\end{cases}}On étudie la convergence de ces développements, et un algorithme réduisant (par reports de retenues) à sa forme régulière le développement de 10^nx, avec n\in\mathbb{N}. On en déduit une fonction Python donnant des milliers de décimales de \pi.

Des milliers de décimales de e

On utilise les notations de l’article précédent (« Base de numération factorielle »).
Connaissant la représentation factorielle d’un réel x, et pour tout entier n, on étudie un algorithme donnant la décomposition factorielle de 10^n x.
Application: on programme le calcul de milliers de décimales de e.

Base de numération factorielle

On montre que tout réel x s’écrit de façon unique x=\displaystyle\sum_{n=1}^{+\infty}\dfrac{b_n}{n!}{b_1\in\mathbb{Z}}, {b_n\in[\![0,n-1]\!]} pour {n\ge2}, et où pour tout {n\ge1}, il existe {m\ge n} tel que {b_m\lt n-1}.
Avec Python, et des schémas de Horner, on programme les conversions entre cette représentation « factorielle » et la représentation décimale.

Le théorème chinois

Soit {n_1,n_2,\ldots,n_r} dans {\mathbb{N}^*}, premiers entre eux deux à deux. Soit {N=\displaystyle\prod\limits_{k=1}^{r}n_k}.
Il existe un unique x\in[\![0,N-1]\!] tel que x\equiv n_j\mod n_j pour tout j.
Ce résultat est communément appelé théorème chinois. L’objet de cet article est de programmer le calcul de x en Python (deux méthodes).

Coefficients de Bézout

Soient {m,n} dans {\mathbb{N}^*}, avec {m\wedge n=1}.
Il existe une infinité de {(u,v)\in\mathbb{Z}^2} tel que {um+vn=1}.
Il existe en particulier un couple {(u,v)} unique tel que {\left|u\right|\le n/2} et {\left|v\right|\le m/2}.
L’objet de cet article est de programmer deux méthodes (l’une itérative, l’autre récursive) de calcul des deux entiers u et v.

Le problème des n reines

Le problème des huit reines est bien connu.
On se propose ici de programmer avec Python (et de visualiser avec le package turtle) la recherche des solutions au problème plus général des n reines (placées sur un échiquier n×n de telle sorte qu’aucune d’elle ne soit en prise avec une autre).

Le parcours du cavalier

On demande de programmer et visualiser (en Python, avec le package turtle) le parcours d’un cavalier sur un échiquier. À partir d’une position initiale du cavalier, on s’attachera à décrire des trajectoires explorant la totalité de l’échiquier en passant une fois et une seule sur chaque case (voir l’article de Wikipedia). On pourra généraliser à des échiquiers de tailles différentes et/ou modifiés pour rendre certaines de leurs cases inaccessibles.

Le collectionneur, épisode 1

Pour doper ses ventes, une marque de chocolat cache dans chaque tablette (et de façon équiprobable) l’une des N figurines d’une collection. On considère ici l’expérience (aléatoire!) vécue par un client cherchant compulsivement à compléter sa collection.
On note {X} le nombre de tablettes à acheter pour compléter l’album. Dans cet épisode, on calcule la loi de X, son espérance, sa variance.

L’urne d’Ehrenfest, épisode 2

On reprend les notations et résultats de l’épisode 1.
On forme ici la matrice de transition associée à ce processus de Markov, et on l’interprète comme celle d’un endomorphisme \varphi de {\mathbb{R}_{N}[X]} dans la base canonique.
Si {t\mapsto G_{n}(t)} est la fonction génératrice de {X_{n}}, on voit que {G_{n+1}=\varphi(G_{n})}.
On retrouve alors la relation {\text{E}(X_{n+1})=1+\Bigl(1-\dfrac{2}{N}\Bigr)\text{E}(X_{n})}.