{
"cells": [
{
"cell_type": "markdown",
"id": "55bf8f76",
"metadata": {},
"source": [
"# Neuvième exercice JavaScript"
]
},
{
"cell_type": "markdown",
"id": "74595666",
"metadata": {},
"source": [
"![](\"https://blog.univ-angers.fr/mathsinfo/files/2022/06/image-8.png\")
"
]
},
{
"cell_type": "markdown",
"id": "30847ac2",
"metadata": {},
"source": [
"![](\"https://blog.univ-angers.fr/mathsinfo/files/2022/06/image-9.png\")
"
]
},
{
"cell_type": "markdown",
"id": "0638a4c2",
"metadata": {},
"source": [
"*Résumé en français* : Des lapins naissent et deviennent matures au bout de 1 mois, âge auquel ils pourront se reproduire.\n",
"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 :\n",
"\n",
">> lapins(0, 4)\n",
"0 # Après 0 mois, il n'y a pas de paire adultes\n",
">> lapins(1, 4)\n",
"1 # Après 1 mois, une seule paire d'adultes\n",
">>lapins(4, 0)\n",
"1 # Lapins stériles (taux = 0), on reste à 1\n",
">> lapins(6, 3) \n",
"40 \n",
">> lapins(8, 12)\n",
"8425\n",
">> lapins(7, 4)\n",
"181 \n",
"\n",
"# (1 0) > (0 1) > (4 1) > (4 5) > (20 9) > (36 29) > (116 65) > 181"
]
},
{
"cell_type": "markdown",
"id": "7a1ada45",
"metadata": {},
"source": [
"Cet exercice étant assez facile, proposons **différentes versions** :"
]
},
{
"cell_type": "markdown",
"id": "bab884f1",
"metadata": {},
"source": [
"## Une simple boucle"
]
},
{
"cell_type": "markdown",
"id": "b4d90e1f",
"metadata": {},
"source": [
"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.\n",
"\n",
"Il faut faire attention à l'écriture du processus, voici une version **INCORRECTE** :"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "9f140906",
"metadata": {},
"outputs": [],
"source": [
" var lapins = (n, b) => {\n",
" let [immatures, adultes] = [1, 0];\n",
" for (let i = 0; i < n; i++) {\n",
" immatures = adultes * b; // on écrase immatures trop tôt\n",
" adultes += immatures;\n",
" }\n",
" return adultes;\n",
"}"
]
},
{
"cell_type": "markdown",
"id": "f2080430",
"metadata": {},
"source": [
"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** :"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "8bc05d80",
"metadata": {},
"outputs": [],
"source": [
" var lapins = (n, b) => {\n",
" let [immatures, adultes] = [1, 0];\n",
" for (let i = 0; i < n; i++) {\n",
" temp = immatures // On mémorise valeur précédente\n",
" immatures = b * adultes\n",
" adultes += temp; // que l'on utilise ici\n",
" }\n",
" return adultes;\n",
"}"
]
},
{
"cell_type": "markdown",
"id": "8b742a73",
"metadata": {},
"source": [
"On peut également utiliser cette écriture **CORRECTE** :"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "d807277a",
"metadata": {},
"outputs": [],
"source": [
" var lapins = (n, b) => {\n",
" let [immatures, adultes] = [1, 0];\n",
" for (let i = 0; i < n; i++) {\n",
" [immatures, adultes] = [adultes * b, immatures + adultes];\n",
" }\n",
" return adultes;\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "63136c34",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"8425"
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lapins(8,12)"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "d6284822",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"0"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lapins(0,4)"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "e3b8f30f",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"1"
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lapins(4,0)"
]
},
{
"cell_type": "markdown",
"id": "1e99f44c",
"metadata": {},
"source": [
"## Version récursive"
]
},
{
"cell_type": "markdown",
"id": "4eef2ea6",
"metadata": {},
"source": [
"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"
]
},
{
"cell_type": "markdown",
"id": "d9d50440",
"metadata": {},
"source": [
"Si on note u la suite donnant le nombre d'adultes au fil des mois, on a u(0) = 0, u(1) = 1 etc."
]
},
{
"cell_type": "markdown",
"id": "16ccdde1",
"metadata": {},
"source": [
"Cette suite peut être définie par une **relation de récurrence** :\n",
"\n",
"$$\\left\\{\\begin{matrix}\n",
"u(0)=0 \\mbox{ et } u(1) = 1\\\\\n",
"u(n+1) = 3 \\times u(n-1) + u(n)\\\\\n",
"\\end{matrix}\\right.$$"
]
},
{
"cell_type": "markdown",
"id": "77483e7a",
"metadata": {},
"source": [
"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."
]
},
{
"cell_type": "markdown",
"id": "87db5892",
"metadata": {},
"source": [
"Essayez en effet de vous convaincre que 0 → 1 → 1 → 4 → 7 → 19 correspond à :\n",
"\n",
"u(2) = 1 = 3 * 0 + 1, u(3) = 4 = 3 * 1 + 1, u(4) = 7 = 3 * 1 + 4, u(5) = 19 = 3 * 4 + 7 🤔"
]
},
{
"cell_type": "markdown",
"id": "d1a878c7",
"metadata": {},
"source": [
"Traduction en Python :"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "c69dfaaa",
"metadata": {},
"outputs": [],
"source": [
"var lapins = (n, b) => n <= 1 ? \n",
" n : \n",
" b * lapins(n - 2, b) + lapins(n - 1, b)"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "0256da90",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"19"
]
},
"execution_count": 8,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lapins(5,3)"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "94e028d3",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"8425"
]
},
"execution_count": 9,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lapins(8,12)"
]
},
{
"cell_type": "markdown",
"id": "545c307c",
"metadata": {},
"source": [
"## Version matricielle"
]
},
{
"cell_type": "markdown",
"id": "7e5ec90d",
"metadata": {},
"source": [
"Autre vision en utilisant cette fois-ci un **calcul matriciel**. En effet, observons que :\n",
"\n",
"$$\\begin{pmatrix}\n",
"u_{n+1} \\\\\n",
"u_n\n",
"\\end{pmatrix} = \\begin{pmatrix}\n",
"u_n + 3\\times u_{n-1} \\\\\n",
"u_n\n",
"\\end{pmatrix}=\n",
"\\begin{pmatrix}\n",
"1 & 3\\\\\n",
"1 & 0 \\\\\n",
"\\end{pmatrix} \\begin{pmatrix}\n",
"u_{n} \\\\\n",
"u_{n-1}\n",
"\\end{pmatrix}$$"
]
},
{
"cell_type": "markdown",
"id": "4d1d1adf",
"metadata": {},
"source": [
"On peut donc calculer **u(n+1)** et **u(n)** à l'aide des **puissances** d'une unique matrice 2 x 2 :\n",
"\n",
"$$\\begin{pmatrix}\n",
"u_{n+1} \\\\\n",
"u_n\n",
"\\end{pmatrix} =\n",
"\\begin{pmatrix}\n",
"1 & 3\\\\\n",
"1 & 0 \\\\\n",
"\\end{pmatrix}^n \\begin{pmatrix}\n",
"1 \\\\\n",
"0\n",
"\\end{pmatrix}$$"
]
},
{
"cell_type": "markdown",
"id": "ddd3110d",
"metadata": {},
"source": [
"De façon **plus générale**, le nombre de paires d'adultes pour un taux de reproduction `b` peut être calculé par :\n",
"\n",
"$$\\begin{pmatrix}\n",
"u_{n+1} \\\\\n",
"u_n\n",
"\\end{pmatrix} =\n",
"\\begin{pmatrix}\n",
"1 & b\\\\\n",
"1 & 0 \\\\\n",
"\\end{pmatrix}^n \\begin{pmatrix}\n",
"1 \\\\\n",
"0\n",
"\\end{pmatrix}$$"
]
},
{
"cell_type": "markdown",
"id": "9b46de78",
"metadata": {},
"source": [
"Il existe des bibliothèques JavaScript pour faire du calcul matriciel, par exemple math.js :\n",
"\n",
">> m = [[1, 3], [1, 0]]\n",
"\n",
">> math.pow(m,4)\n",
"0: [19, 21]\n",
"1: [7, 12]\n",
"\n",
">> math.pow(m,70)\n",
"0: [1.455103155612549e+25, 1.8956729415189765e+25]\n",
"1: [6.318909805063255e+24, 8.232121751062236e+24]"
]
},
{
"cell_type": "markdown",
"id": "77148790",
"metadata": {},
"source": [
"Sinon, vous pouvez vous créer une petite fonction permettant de mettre une matrice 2 x 2 à une puissance quelconque, par exemple :"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "4662e4ca",
"metadata": {},
"outputs": [],
"source": [
"var power = (m, n) => // Matrice m à la puissance n\n",
"{\n",
" [[a, b], [c, d]] = m; // On récupère les coefficients\n",
" r = [[1, 0], [0, 1]] // Matrice unité\n",
" for (i = 0; i < n; i++) // n multiplications matricielles\n",
" {\n",
" [e, f] = [a * r[0][0] + c * r[0][1], b * r[0][0] + d * r[0][1]];\n",
" [g, h] = [a * r[1][0] + c * r[1][1], b * r[1][0] + d * r[1][1]];\n",
" r = [[e, f], [g, h]];\n",
" };\n",
" return r\n",
"}"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "ee75f2d4",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[ [ 19, 21 ], [ 7, 12 ] ]"
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"power([[1, 3],[1, 0]], 4)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "e0055b83",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"[\n",
" [ 1.455103155612549e+25, 1.8956729415189765e+25 ],\n",
" [ 6.318909805063255e+24, 8.232121751062236e+24 ]\n",
"]"
]
},
"execution_count": 12,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"power([[1, 3],[1, 0]], 70)"
]
},
{
"cell_type": "markdown",
"id": "0fe3836c",
"metadata": {},
"source": [
"Programme final en JavaScript qui utilise la fonction `power` ci-dessus :"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "d3422456",
"metadata": {},
"outputs": [],
"source": [
"var lapins = (n, b) => power([[1, b],[1, 0]], n)[1][0]"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "08fb276e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"8425"
]
},
"execution_count": 14,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"lapins(8, 12)"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "JavaScript (Node.js)",
"language": "javascript",
"name": "javascript"
},
"language_info": {
"file_extension": ".js",
"mimetype": "application/javascript",
"name": "javascript",
"version": "18.3.0"
}
},
"nbformat": 4,
"nbformat_minor": 5
}