Mot clef : Python

Des milliers de décimales de π

On considère un développement x=\displaystyle\sum_{k=0}^{+\infty}p_k\,u_k, où {u_k=\dfrac{(k!)^2\,2^{k}}{(2k+1)!}}.
Il 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 ici les notations et les 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})}.

Le dernier non effacé

On écrit à la suite tous les entiers de {1} jusqu’à {2017}. On les efface de {3} en {3} : d’abord {1}, puis {4}, puis {7}, etc. On recommence sur la liste restante 2,3,5,6,8,9,11,\ldots et ainsi de suite. Quel est le dernier nombre affiché, et au bout de combien d’itérations? Illustrer tout cela avec Python.

La dernière moyenne

On écrit une liste de n nombres réels. On en efface deux, pris au hasard, pour les remplacer par leur demi-somme. On répète cette opération jusqu’à ce qu’il reste un seul réel X. Quelle est la valeur minimum possible pour X? Illustrer avec Python.

Pavage par des dominos

On s’intéresse au nombre u_n de façons de remplir un rectangle 4\times n par des dominos (horizontaux ou verticaux). On trouve une relation de récurrence vérifiée par les {u_{n}}. On écrit une fonction Python calculant {u_n}. On donne une expression des u_n et on étudie leur série génératrice.

Répétitions de 0

Soit A une matrice à coefficients égaux à 0 ou 1.
On demande d’écrire une fonction Python (utilisant Numpy), prenant en argument une telle matrice, et renvoyant le plus grand nombre de zéros consécutifs dans A (horizontalement, verticalement, ou en diagonale montante ou descendante).

Matrices bistochastiques, épisode 9

Soit {B_{n}\in\mathcal{M}_n(\mathbb{R})} la matrice de terme général {(b_{i,j})_{1\le i,j\le n}} définie par:
{\begin{cases}b_{i,i+1}=b_{i+1,i}=\dfrac{1}{2}\text{\ si }1\le i\lt n\\b_{1,1}=b_{n,n}=\dfrac{1}{2},\text{\ et\ }b_{i,j}=0\text{\ dans les autres cas}\end{cases}}On diagonalise B_n, on étudie la limite de ses puissances, et on illustre les résultats avec l’aide du langage Python.