{"id":358,"date":"2022-06-10T07:02:28","date_gmt":"2022-06-10T06:02:28","guid":{"rendered":"https:\/\/blog.univ-angers.fr\/mathsinfo\/?p=358"},"modified":"2022-06-19T08:03:04","modified_gmt":"2022-06-19T07:03:04","slug":"kata9","status":"publish","type":"post","link":"https:\/\/blog.univ-angers.fr\/mathsinfo\/2022\/06\/10\/kata9\/","title":{"rendered":"Neuvi\u00e8me exercice en Python, JavaScript et APL"},"content":{"rendered":"\n
\"\"<\/a><\/figure>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n

R\u00e9sum\u00e9 en fran\u00e7ais<\/span> : Des lapins naissent et deviennent matures au bout de 1 mois, \u00e2ge auquel ils pourront se reproduire.
Cr\u00e9ez une fonction qui d\u00e9termine le nombre de paires de lapins matures<\/strong> apr\u00e8s n<\/strong> mois en commen\u00e7ant par un unique<\/strong> couple de lapins immatures et qui se reproduisent \u00e0 raison de b<\/strong> paires \u00e0 la fin de chaque mois. Voir le tableau ci-dessus dans le cas de n<\/strong> = 5 mois avec un taux de reproduction de b<\/strong> = 3 pour bien comprendre le d\u00e9roulement. Quelques autres exemples :<\/p>\n\n\n\n

>> lapins(0, 4)\n0                     # Apr\u00e8s 0 mois, il n'y a pas de paire adultes\n>> lapins(1, 4)\n1                     # Apr\u00e8s 1 mois, une seule paire d'adultes\n>>lapins(4, 0)\n1                     # Lapins st\u00e9riles (taux = 0), on reste \u00e0 1\n>> lapins(6, 3)       \n40 \n>> lapins(8, 12)\n8425\n>> lapins(7, 4)\n181 \n\n# (1 0) > (0 1) > (4 1) > (4 5) > (20 9) > (36 29) > (116 65) > 181<\/code><\/pre>\n\n\n\n
Cet exercice \u00e9tant assez facile, proposons diff\u00e9rentes versions<\/strong> :<\/p>\n\n\n\n
Une simple boucle<\/h2>\n\n\n\n
On part de 0<\/strong> adulte et d’une paire de lapins immatures<\/strong>. Chaque mois<\/strong>, le nouveau nombre d’immatures<\/strong> est \u00e9gal<\/strong> au nombre d’adultes qui se reproduisent avec un taux b<\/strong> (c’est-\u00e0-dire la multiplication du nombre d’adultes par le coefficient b<\/strong>). Et le nouveau nombre d’adultes<\/strong> est \u00e9gal au nombre d’adultes<\/strong> pr\u00e9c\u00e9dents<\/strong> + les immatures pr\u00e9c\u00e9dents<\/strong> qui deviennent adultes.<\/p>\n\n\n\n
Il faut faire attention \u00e0 l’\u00e9criture du processus, voici une version INCORRECTE<\/strong> :<\/p>\n\n\n\n
def lapins(n, b):\n    immatures, adultes = 1, 0\n    for i in range(n):\n        immatures = b * adultes         # on \u00e9crase immatures trop t\u00f4t\n        adultes =  adultes + immatures\n    return adultes<\/code><\/pre>\n\n\n\n
En effet, on commence par mettre \u00e0 jour la variable immatures<\/strong> puis on utilise cette valeur \u00e0 la ligne suivante, or nous avions besoin de la valeur pr\u00e9c\u00e9dente<\/strong> de immatures<\/strong> et non pas de la valeur actualis\u00e9e. Une technique classique est d’utiliser une variable temporaire<\/strong> :<\/p>\n\n\n\n
def lapins(n, b):\n    immatures, adultes = 1, 0\n    for i in range(n):\n        temp = immatures            # On m\u00e9morise valeur pr\u00e9c\u00e9dente\n        immatures = b * adultes\n        adultes =  adultes + temp   # que l'on utilise ici\n    return adultes<\/code><\/pre>\n\n\n\n
Mais en Python ou en JavaScript, on peut \u00e9galement utiliser cette \u00e9criture CORRECTE<\/strong> :<\/p>\n\n\n\n
python<\/h3>\n\n\n\n
def lapins(n, b):\n    immatures, adultes = 1, 0\n    for i in range(n):\n        immatures, adultes = b * adultes, adultes + immatures\n    return adultes\n\n>> lapins(8,12)\n8425\n>> lapins(0,4)\n0\n>> lapins(4,0)\n1<\/code><\/pre>\n\n\n\n
javascript<\/h3>\n\n\n\n
La traduction est quasi identique en JavaScript<\/strong> :<\/p>\n\n\n\n
 const 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}<\/code><\/pre>\n\n\n\n
Avec d’infinies variations, par exemple en utilisant un objet<\/strong> et une boucle Tant que<\/strong> :<\/p>\n\n\n\n
const lapins = (n, b) => {\n  const tous = {immatures: 1, adultes: 0};    \/\/ Tous les lapins\n  mois = 0;\n  while (mois < n) {\n    let temp = tous.adultes;\n    tous.adultes += tous.immatures;\n    tous.immatures = temp * b;\n    mois++;\n  }  \n  return tous.adultes;\n}<\/code><\/pre>\n\n\n\n
Version r\u00e9cursive<\/h2>\n\n\n\n
Reprenons l’exemple propos\u00e9 dans l’\u00e9nonc\u00e9 avec n = 5 et b = 3. Le nombre de paires d’adultes matures est successivement : 0 \u2192 1 \u2192 1 \u2192 4 \u2192 7 \u2192 19<\/p>\n\n\n\n
Si on note u<\/strong> la suite donnant le nombre d’adultes au fil des mois, on a u(0) = 0, u(1) = 1 etc.<\/p>\n\n\n\n
Cette suite peut \u00eatre d\u00e9finie par une relation de r\u00e9currence<\/strong> :<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
Ce qui signifie que le nombre de paires d’adultes au mois n+1<\/strong> est 3 fois<\/strong> le nombre de paires d’adultes<\/strong> 2 mois avant<\/strong> (reproduction) + les immatures<\/strong> du mois pr\u00e9c\u00e9dent<\/strong> qui deviennent adultes.<\/p>\n\n\n\n
Essayez en effet de vous convaincre que 0 \u2192 1 \u2192 1<\/span> \u2192 4<\/span> \u2192 7<\/span> \u2192 19<\/span> correspond \u00e0 :<\/p>\n\n\n\n
u(2) = 1<\/span> = 3 *<\/strong> 0 +<\/strong> 1, u(3) = 4<\/span> = 3 *<\/strong> 1 +<\/strong> 1, u(4) = 7<\/span> = 3 *<\/strong> 1 +<\/strong> 4, u(5) = 19<\/span> = 3 *<\/strong> 4 +<\/strong> 7 \ud83e\udd14<\/p>\n\n\n\n
Les traductions<\/strong> en Python et JavaScript sont imm\u00e9diates :<\/p>\n\n\n\n
Python<\/span>\n\ndef lapins(n, b):\n  if n <= 1: return n\n  return b * lapins(n - 2, b) + lapins(n - 1, b)\n\nJavaScript<\/span>\n\nconst lapins = (n, b) => n <= 1 ? \n                         n : \n                         b * lapins(n - 2, b) + lapins(n - 1, b)\n\n>> lapins(5,3)\n19\n>> lapins(8,12)\n8425<\/code><\/pre>\n\n\n\n
Version matricielle<\/h2>\n\n\n\n
Autre vision en utilisant cette fois-ci un calcul matriciel<\/strong>. En effet, observons que :<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
On peut donc calculer u(n+1)<\/strong> et u(n) <\/strong>\u00e0 l’aide des puissances<\/strong> d’une unique matrice 2 x 2 :<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
De fa\u00e7on plus g\u00e9n\u00e9rale<\/strong>, le nombre de paires d’adultes pour un taux de reproduction b<\/strong> peut \u00eatre calcul\u00e9 par :<\/p>\n\n\n\n
\"\"<\/a><\/figure>\n\n\n\n
Python<\/h3>\n\n\n\n
Pour calculer la puissance d’une matrice 2 x 2, nous pouvons cr\u00e9er une fonction de multiplication ou utiliser une biblioth\u00e8que comme numpy<\/strong> :<\/p>\n\n\n\n
import numpy as np                 # On importe numpy\n\nm = np.array([[1, 3], [1, 0]])     # Cr\u00e9ation de la matrice m\n\nfor k in range(5):                 # Calcul de m^0, m^1... m^4\n  print('m^{} = {}'.format(k, np.linalg.matrix_power(m, k)))\n\nR\u00e9sultats<\/span>\n\nm^0 = [[1 0], [0 1]]\nm^1 = [[1 3], [1 0]]\nm^2 = [[4 3], [1 3]]\nm^3 = [[ 7 12], [ 4  3]]\nm^4 = [[19 21], [ 7 12]]<\/code><\/pre>\n\n\n\n
Attention cependant, la biblioth\u00e8que numpy<\/strong> ne g\u00e8re pas (par d\u00e9faut) les entiers arbitrairement grands et peut donner des r\u00e9sultats FAUX<\/strong> :<\/p>\n\n\n\n
>> np.linalg.matrix_power(m, 50)      # m \u00e0 la puissance 50\n\n[[ 827677709047869124 1078278355240672323]\n [ 359426118413557441  468251590634311683]]    # R\u00e9sultat EXACT\n\n>> np.linalg.matrix_power(m, 70)      # m \u00e0 la puissance 70\n[[   23110438186405259  6654818438609454037]\n [-3930641878366699193<\/strong>  3953752316553104452]]  # R\u00e9sultat FAUX !<\/code><\/pre>\n\n\n\n
On peut malgr\u00e9 tout pr\u00e9ciser comment les donn\u00e9es doivent \u00eatre stock\u00e9es (entier, flottant, objet) :<\/p>\n\n\n\n
import numpy as np\n\nm = np.array([[1, 3], [1, 0]], dtype=object<\/span>)  # en tant qu'objet\n\n>> np.linalg.matrix_power(m, 70)\n[[14551031556125490725277067 18956729415189764489429973]\n [6318909805063254829809991 8232121751062235895467076]]   # EXACT !<\/code><\/pre>\n\n\n\n
Programme final<\/strong> en Python :<\/p>\n\n\n\n
import numpy as np\n\ndef lapins(n, b):\n    m = np.array([[1, b], [1, 0]], dtype=object)\n    return np.linalg.matrix_power(m, n)[1][0]    # on r\u00e9cup\u00e8re u(n)\n\n>> lapins(8, 12)\n8425\n>> lapins(0, 4)\n0\n>> lapins(4, 0)\n1<\/code><\/pre>\n\n\n\n
Javascript<\/h3>\n\n\n\n
Il existe des biblioth\u00e8ques JavaScript pour faire du calcul matriciel, par exemple math.js<\/a> :<\/p>\n\n\n\n
>> m = [[1, 3], [1, 0]]\n\n>> math.pow(m,4)\n0: [19, 21]\n1: [7, 12]\n\n>> math.pow(m,70)\n0: [1.455103155612549e+25, 1.8956729415189765e+25]\n1: [6.318909805063255e+24, 8.232121751062236e+24]<\/code><\/pre>\n\n\n\n
Sinon, vous pouvez vous cr\u00e9er une petite fonction permettant de mettre une matrice 2 x 2 \u00e0 une puissance quelconque, par exemple :<\/p>\n\n\n\n
const power = (m, n) =>      \/\/ Matrice m \u00e0 la puissance n\n{\n    [[a, b], [c, d]] = m;    \/\/ On r\u00e9cup\u00e8re les coefficients\n    r = [[1, 0], [0, 1]]     \/\/ Matrice unit\u00e9\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}\n\n>> power([[1, 3],[1, 0]], 4)\n0: [19, 21]\n1: [7, 12]\n\n>> power([[1, 3],[1, 0]], 70)\n0: [1.455103155612549e+25, 1.8956729415189765e+25]\n1: [6.318909805063255e+24, 8.232121751062236e+24]<\/code><\/pre>\n\n\n\n
Programme final <\/strong>en JavaScript qui utilise la fonction power<\/strong> ci-dessus :<\/p>\n\n\n\n
lapins = (n, b) =>  power([[1, b],[1, 0]], n)[1][0]\n\n>> lapins(8, 12)\n8425<\/code><\/pre>\n\n\n\n
Version APL<\/h2>\n\n\n\n
Reprenons l’id\u00e9e du calcul matriciel. En APL, on d\u00e9finit une matrice en pr\u00e9cisant ses dimensions<\/strong> suivi de \u2374 et des valeurs<\/strong> :<\/p>\n\n\n\n
      m \u2190 2 2 \u2374 1 3 1 0     \u235d  Matrice 2 x 2\n1 3\n1 0<\/code><\/pre>\n\n\n\n
Pour la mettre au carr\u00e9<\/strong> on utilise le produit interne<\/strong> (ici somme des produits) :<\/p>\n\n\n\n
      m +.\u00d7 m\n4 3\n1 3<\/code><\/pre>\n\n\n\n
Et avec une r\u00e9duction<\/strong> on peut obtenir par exemple m^4<\/strong> :<\/p>\n\n\n\n
      +.\u00d7\/ m m m m\n\u250c\u2500\u2500\u2500\u2500\u2500\u2510\n\u250219 21\u2502\n\u2502 7 12\u2502\n\u2514\u2500\u2500\u2500\u2500\u2500\u2518<\/code><\/pre>\n\n\n\n
Pour g\u00e9n\u00e9raliser<\/strong> \u00e0 une puissance quelconque r<\/strong>, il va falloir dupliquer la matrice r<\/strong> fois, exemple avec r = 4<\/strong> :<\/p>\n\n\n\n
      4 \u2374 \u2282 m\n\u250c\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2510\n\u25021 3\u25021 3\u25021 3\u25021 3\u2502\n\u25021 0\u25021 0\u25021 0\u25021 0\u2502\n\u2514\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2518<\/code><\/pre>\n\n\n\n
D’o\u00f9 cette fonction pour mettre une matrice m<\/strong> \u00e0 la puissance r<\/strong> :<\/p>\n\n\n\n
      power \u2190 {+.\u00d7\/ \u237a \u2374 \u2282 \u2375}\n\n      4 power m\n\u250c\u2500\u2500\u2500\u2500\u2500\u2510\n\u250219 21\u2502\n\u2502 7 12\u2502\n\u2514\u2500\u2500\u2500\u2500\u2500\u2518\n      1 power m\n\u250c\u2500\u2500\u2500\u2510\n\u25021 3\u2502\n\u25021 0\u2502\n\u2514\u2500\u2500\u2500\u2518\n      0 power m\nDOMAIN ERROR<\/code><\/pre>\n\n\n\n
Cette alternative sugg\u00e9r\u00e9e par Dyalog APL sur Twitter<\/a> a l’avantage de g\u00e9rer le cas r = 0<\/strong> :<\/p>\n\n\n\n
      power \u2190 {+.\u00d7 \u2363 (\u237a - 1) \u2368 \u2375}\n\n      4 power m\n19 21\n 7 12\n      1 power m\n1 3\n1 0\n      0 power m      \u235d On obtient bien la matrice identit\u00e9\n1 0\n0 1<\/code><\/pre>\n\n\n\n
\u2363 permet de r\u00e9p\u00e9ter<\/strong> une op\u00e9ration plusieurs fois et \u2368 d’inverser<\/strong> les param\u00e8tres :<\/p>\n\n\n\n
      \u00d7\u23633 \u2368 2       \u235d 2 \u2192 2 \u00d7 2 = 4 \u2192 4 \u00d7 4 = 16\n16\n      +\u23633 \u2368 2       \u235d 2 \u2192 2 + 2 = 4 \u2192 4 + 4 = 8\n8\n      +\u2218\u00f7\u2363 20 \u23681    \u235d 1 + 1 \/ (1 + 1 \/ (1 + ...)) \u2243 Nombre d'or\n1.618033985<\/code><\/pre>\n\n\n\n
Une fois que l’on aura calcul\u00e9 la puissance de la matrice, il faut r\u00e9cup\u00e9rer<\/strong> l’\u00e9l\u00e9ment \u00e0 la ligne 2 et colonne 1. Pour cela, on utilise \u2283 (pick<\/strong>) et on accole (laminate<\/strong>) les lignes de la matrice :<\/p>\n\n\n\n
      m \u2190 2 2  \u2374 7 9 5 8     \u235d Matrice 2 x 2\n      ,\/ m                   \u235d Laminage (on accole les lignes)\n\u250c\u2500\u2500\u2500\u252c\u2500\u2500\u2500\u2510\n\u25027 9\u25025 8\u2502\n\u2514\u2500\u2500\u2500\u2534\u2500\u2500\u2500\u2518\n      2 \u2283 ,\/ m               \u235d 2e terme\n5 8\n      2 1 \u2283 ,\/ m             \u235d 1er terme du 2e terme\n5\n\n\u235d On peut \u00e9galement utiliser \u2337 (index)\n\n      2 1 \u2337 m\n5<\/code><\/pre>\n\n\n\n
Programme final<\/strong> en APL :<\/p>\n\n\n\n
      lapins \u2190  {2 1 \u2337 +.\u00d7 \u2363 (\u237a - 1) \u2368 2 2 \u2374 1 \u2375 1 0} \n\n      8 lapins 12\n8425\n      0 lapins 4\n0\n      4 lapins 0\n1\n      7 lapins 4\n181<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
R\u00e9sum\u00e9 en fran\u00e7ais : Des lapins naissent et deviennent matures au bout de 1 mois, \u00e2ge auquel ils pourront se reproduire.Cr\u00e9ez une fonction qui d\u00e9termine le nombre de paires de lapins matures apr\u00e8s n mois en commen\u00e7ant par un unique … Continuer la lecture →<\/span><\/a><\/p>\n","protected":false},"author":4913,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-358","post","type-post","status-publish","format-standard","hentry","category-twitter"],"_links":{"self":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/358","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/users\/4913"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/comments?post=358"}],"version-history":[{"count":38,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/358\/revisions"}],"predecessor-version":[{"id":658,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/posts\/358\/revisions\/658"}],"wp:attachment":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/media?parent=358"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/categories?post=358"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/tags?post=358"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}