Résumé en français : Des lapins naissent et deviennent matures au bout de 1 mois, âge auquel ils pourront se reproduire.
Créez une fonction qui détermine le nombre de paires de lapins matures après n
mois en commençant par un unique couple de lapins immatures et qui se reproduisent à raison de b
paires à la fin de chaque mois. Voir le tableau ci-dessus dans le cas de n
= 5 mois avec un taux de reproduction de b
= 3 pour bien comprendre le déroulement. Quelques autres exemples :
>> lapins(0, 4) 0 # Après 0 mois, il n'y a pas de paire adultes >> lapins(1, 4) 1 # Après 1 mois, une seule paire d'adultes >>lapins(4, 0) 1 # Lapins stériles (taux = 0), on reste à 1 >> lapins(6, 3) 40 >> lapins(8, 12) 8425 >> lapins(7, 4) 181 # (1 0) > (0 1) > (4 1) > (4 5) > (20 9) > (36 29) > (116 65) > 181
Cet exercice étant assez facile, proposons différentes versions :
On part de 0 adulte et d'une paire de lapins immatures. Chaque mois, le nouveau nombre d'immatures est égal au nombre d'adultes qui se reproduisent avec un taux b
(c'est-à-dire la multiplication du nombre d'adultes par le coefficient b
). Et le nouveau nombre d'adultes est égal au nombre d'adultes précédents + les immatures précédents qui deviennent adultes.
Il faut faire attention à l'écriture du processus, voici une version INCORRECTE :
var lapins = (n, b) => {
let [immatures, adultes] = [1, 0];
for (let i = 0; i < n; i++) {
immatures = adultes * b; // on écrase immatures trop tôt
adultes += immatures;
}
return adultes;
}
En effet, on commence par mettre à jour la variable immatures
puis on utilise cette valeur à la ligne suivante, or nous avions besoin de la valeur précédente de immatures
et non pas de la valeur actualisée. Une technique classique est d'utiliser une variable temporaire :
var lapins = (n, b) => {
let [immatures, adultes] = [1, 0];
for (let i = 0; i < n; i++) {
temp = immatures // On mémorise valeur précédente
immatures = b * adultes
adultes += temp; // que l'on utilise ici
}
return adultes;
}
On peut également utiliser cette écriture CORRECTE :
var lapins = (n, b) => {
let [immatures, adultes] = [1, 0];
for (let i = 0; i < n; i++) {
[immatures, adultes] = [adultes * b, immatures + adultes];
}
return adultes;
}
lapins(8,12)
8425
lapins(0,4)
0
lapins(4,0)
1
Reprenons l'exemple proposé dans l'énoncé avec n = 5 et b = 3. Le nombre de paires d'adultes matures est successivement : 0 → 1 → 1 → 4 → 7 → 19
Si on note u la suite donnant le nombre d'adultes au fil des mois, on a u(0) = 0, u(1) = 1 etc.
Cette suite peut être définie par une relation de récurrence :
$$\left\{\begin{matrix} u(0)=0 \mbox{ et } u(1) = 1\\ u(n+1) = 3 \times u(n-1) + u(n)\\ \end{matrix}\right.$$Ce qui signifie que le nombre de paires d'adultes au mois n+1
est 3 fois le nombre de paires d'adultes 2 mois avant (reproduction) + les immatures du mois précédent qui deviennent adultes.
Essayez en effet de vous convaincre que 0 → 1 → 1 → 4 → 7 → 19 correspond à :
u(2) = 1 = 3 * 0 + 1, u(3) = 4 = 3 * 1 + 1, u(4) = 7 = 3 * 1 + 4, u(5) = 19 = 3 * 4 + 7 🤔
Traduction en Python :
var lapins = (n, b) => n <= 1 ?
n :
b * lapins(n - 2, b) + lapins(n - 1, b)
lapins(5,3)
19
lapins(8,12)
8425
Autre vision en utilisant cette fois-ci un calcul matriciel. En effet, observons que :
$$\begin{pmatrix} u_{n+1} \\ u_n \end{pmatrix} = \begin{pmatrix} u_n + 3\times u_{n-1} \\ u_n \end{pmatrix}= \begin{pmatrix} 1 & 3\\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} u_{n} \\ u_{n-1} \end{pmatrix}$$On peut donc calculer u(n+1) et u(n) à l'aide des puissances d'une unique matrice 2 x 2 :
$$\begin{pmatrix} u_{n+1} \\ u_n \end{pmatrix} = \begin{pmatrix} 1 & 3\\ 1 & 0 \\ \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix}$$De façon plus générale, le nombre de paires d'adultes pour un taux de reproduction b
peut être calculé par :
Il existe des bibliothèques JavaScript pour faire du calcul matriciel, par exemple math.js :
>> m = [[1, 3], [1, 0]] >> math.pow(m,4) 0: [19, 21] 1: [7, 12] >> math.pow(m,70) 0: [1.455103155612549e+25, 1.8956729415189765e+25] 1: [6.318909805063255e+24, 8.232121751062236e+24]
Sinon, vous pouvez vous créer une petite fonction permettant de mettre une matrice 2 x 2 à une puissance quelconque, par exemple :
var power = (m, n) => // Matrice m à la puissance n
{
[[a, b], [c, d]] = m; // On récupère les coefficients
r = [[1, 0], [0, 1]] // Matrice unité
for (i = 0; i < n; i++) // n multiplications matricielles
{
[e, f] = [a * r[0][0] + c * r[0][1], b * r[0][0] + d * r[0][1]];
[g, h] = [a * r[1][0] + c * r[1][1], b * r[1][0] + d * r[1][1]];
r = [[e, f], [g, h]];
};
return r
}
power([[1, 3],[1, 0]], 4)
[ [ 19, 21 ], [ 7, 12 ] ]
power([[1, 3],[1, 0]], 70)
[ [ 1.455103155612549e+25, 1.8956729415189765e+25 ], [ 6.318909805063255e+24, 8.232121751062236e+24 ] ]
Programme final en JavaScript qui utilise la fonction power
ci-dessus :
var lapins = (n, b) => power([[1, b],[1, 0]], n)[1][0]
lapins(8, 12)
8425