Exercices challenge
- Former 3 groupes.
- Pour résoudre ces challenges il faudra produire des fonctions récursives.
- Chaque challenge peut rapporter 4 points.
- Une aide est disponible pour chaque challenge mais coûte 2 points.
Challenges
Challenge 1
Le paradoxe de Zénon: Zénon (environ 490–430 av. J-C.) se tient à huit mètres d’un arbre, tenant une pierre. Il lance sa pierre dans la direction de l’arbre. Avant que le caillou puisse atteindre l’arbre, il doit traverser la première moitié des huit mètres. Il faut un certain temps, non nul, à cette pierre pour se déplacer sur cette distance. Ensuite, il lui reste encore quatre mètres à parcourir, dont elle accomplit d’abord la moitié, deux mètres, ce qui lui prend un certain temps. Puis la pierre avance d’un mètre de plus, progresse après d’un demi-mètre et encore d’un quart, et ainsi de suite, jusqu’à l’infini, et à chaque fois avec un temps non nul. Zénon en conclut que la pierre ne pourra pas frapper l’arbre, puisqu’il faudrait pour cela que soit franchie effectivement une série infinie d’étapes, ce qui est impossible. Pourtant, l’expérience le prouve aisément : il n’y a guère de difficulté à faire en sorte qu’une pierre heurte un arbre situé à 8 m de distance ! D’où le paradoxe…
Cette situation peut se modéliser à l’aide d’une suite définie par récurrence: $$d_1=4 ~et~ d_{n+1}=d_n + \frac{4}{2^n}$$
En implémentant cette suite en Python, on obtient les valeurs:
- 6.0 pour n = 2,
- 7.999992370605469 pour n = 20.
Challenge 2
La méthode de Heron (ou méthode babylonienne) est une méthode efficace d’extraction de racine carrée, c’est-à-dire de résolution de l’équation $x^2 = a$, avec a positif. Pour déterminer la racine carrée du nombre (positif) a, il convient dès lors de considérer la suite définie par récurrence de la façon suivante : $$x_{n+1}=\frac{x_n+\frac{a}{x_n}}{2}$$ Le premier terme $x_0>0$ sera choisi assez proche de $\sqrt{a}$, en général la partie entière de $\sqrt{a}$.
Challenge 3
Un nombre descriptif décrit la quantité de chaque chiffre du nombre. Par exemple:
- nombre: 1124
- nombre descriptif: 0 2 1 0 1 0 0 0 0 0. Dans 1124, il y a 0 zéros, 2 uns, 1 deux …
Challenge 4
L’algorithme d’Euclide est l’un des plus anciens algorithmes (300 avant JC). Il permet de déterminer le Plus Grand Commun Diviseur (PGCD) de deux entiers.
Détermination du PGCD de 20 et 35:
- $35=20\times1+15$
- $20 = 15\times1 + 5$
- $15 = 5\times3 + 0$
- Le PGCD est 5.
Challenge 5
En mathématiques, les coefficients binomiaux, définis pour tout entier naturel n et tout entier naturel k inférieur ou égal à n, donnent le nombre de parties de k éléments dans un ensemble de n éléments. $$C_{n}^{k}=\frac{n!}{k!\times(n-k)!}$$ La formulation récursive ci-après permet de calculer les coefficients binomiaux: $$ C(n,k) = \left\lbrace \begin{array}{ll} 1 & si~ k=0 ~ou~ n=k \\\\ C(n-1,k-1)+C(n-1,k) & sinon \\\\ \end{array} \right. $$