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

R\u00e9sum\u00e9 en fran\u00e7ais<\/span> : On vous donne une liste contenant des couleurs<\/strong> de moufles<\/strong> (donc pas de main gauche ou droite \u00e0 distinguer). On vous demande le nombre de paires<\/strong> que vous pouvez constituer<\/strong>, c’est-\u00e0-dire avoir 2 moufles de la m\u00eame couleur<\/strong>. <\/p>\n\n\n\n

Avec le premier exemple<\/strong> donn\u00e9, on peut constituer une paire<\/strong> de moufles rouge<\/strong> (red) et<\/strong> une paire bleue<\/strong> (blue) soit 2 paires<\/strong>.<\/p>\n\n\n\n

Version classique<\/h2>\n\n\n\n

Relisez l’exercice 6<\/a> que j’ai propos\u00e9, vous devriez constater de nombreuses ressemblances.<\/p>\n\n\n\n

Une premi\u00e8re id\u00e9e<\/strong> est de commencer par r\u00e9cup\u00e9rer les diff\u00e9rentes couleurs<\/strong> puis, pour chacune d’elle<\/strong>, de compter combien de fois<\/strong> cette couleur apparait<\/strong>. Il suffira de diviser par 2<\/strong> ce nombre (sans tenir compte des virgules) pour savoir combien de paires<\/strong> on peut constituer<\/strong> avec cette couleur. Finalement, on fera la somme<\/strong> du nombre de paires<\/strong> trouv\u00e9es.<\/em><\/p>\n\n\n\n

python<\/h3>\n\n\n\n

Je reprends la structure classique<\/strong> vue dans l’exercice 6 :<\/p>\n\n\n\n

def nb_paires(gants):\n couleurs = [ ]                   # couleurs distinctes\n for g in gants:                  # on parcourt les gants\n  if g not in couleurs:           # nouvelle couleur ?\n   couleurs.append(g)             # on l'ajoute \u00e0 la liste\n paires = 0                       # nombre de paires possibles\n for c in couleurs:               # on parcourt \u00e0 nouveau les gants\n  paires += gants.count(c) \/\/ 2   # on compte puis \u00f7 enti\u00e8re par 2 \n return paires                    # on renvoie le nombre de paires\n\n>> nb_paires([\"gray\",\"black\",\"purple\",\"purple\",\"gray\",\"black\"])\n3\n>> nb_paires([\"red\",\"green\",\"blue\"])\n0<\/code><\/pre>\n\n\n\n
javascript<\/h3>\n\n\n\n
A nouveau je reprends la structure de l’exercice 6 :<\/p>\n\n\n\n
const nb_paires = gants => \n{\n  couleurs = gants.reduce((a, g) => \n                   a.includes(g) ? a : a.concat(g), []);\n  paires = 0;\n  for (c of couleurs) \n  {\n      paires += Math.floor(gants.filter(g => g == c).length \/ 2)\n  }\n    return paires\n}\n\n>> nb_paires([\"gray\",\"black\",\"purple\",\"purple\",\"gray\",\"black\"])\n3\n>> nb_paires([\"red\",\"green\",\"blue\"])\n0<\/code><\/pre>\n\n\n\n
Remarque<\/span> : La division enti\u00e8re<\/strong> par 2<\/strong> ou des puissances de 2 (c’est-\u00e0-dire 4, 8, 16, 32…) peut se faire autrement. En effet, si un nombre est \u00e9crit en binaire<\/strong>, diviser par 2<\/strong> revient \u00e0 supprimer<\/strong> l’unit\u00e9 (bit<\/strong> le plus \u00e0 droite<\/strong>) :<\/p>\n\n\n\n
>> (13).toString(2)      \/\/ 13 en binaire. Python : bin(13) \u2192 '0b1101'\n'1101'\n>> (6).toString(2)       \/\/ Diviser par 2 = supprimer l'unit\u00e9 \n'110'<\/code><\/pre>\n\n\n\n
La raison est que 13 = 1<\/strong> * 2^3<\/span> + 1<\/strong> * 2^2<\/span> + 0<\/strong> * 2^1<\/span> + 1<\/strong> = 11012<\/sub>. En divisant par 2, toutes les puissances vont diminuer de 1 : 6 = 1<\/strong> * 2^2<\/span> + 1<\/strong> * 2^1<\/span> + 0<\/strong> * 2^0<\/span> = 1102<\/sub><\/p>\n\n\n\n
On utilise >><\/strong> pour d\u00e9caler un bit vers la droite<\/strong> en Python et JavaScript :<\/p>\n\n\n\n
13 >> 1\n6<\/code><\/pre>\n\n\n\n
De la m\u00eame fa\u00e7on, on peut diviser par 4, multiplier par 8 etc :<\/p>\n\n\n\n
13 >> 2        \/\/ Diviser par 4 (c'est-\u00e0-dire \u00f7 2 fois par 2)\n3\n13 << 3        \/\/ Multiplier par 8 (c'est-\u00e0-dire \u00d7 3 fois par 2)\n104<\/code><\/pre>\n\n\n\n
Version ensembliste<\/h2>\n\n\n\n
Comme nous l’avons \u00e9galement vu dans l’exercice 6, nous pouvons utiliser des ensembles<\/strong> (set<\/strong>) pour r\u00e9cup\u00e9rer les \u00e9l\u00e9ments uniques<\/strong>. Les versions sont alors nettement plus courtes :<\/p>\n\n\n\n
Python<\/span>\n\ndef nb_paires(gants):\n    return sum(gants.count(v) \/\/ 2 for v in set(gants))\n\nJavaScript<\/span>\n\nconst nb_paires = gants => [...new Set(gants)]\n    .reduce((a,v) => a + (gants.filter(c => c == v).length >> 1), 0)<\/code><\/pre>\n\n\n\n
apl<\/h3>\n\n\n\n
Toujours dans l’exercice 6, nous avons vu l’utilisation de \u2338 (key<\/strong>), qui permet de synth\u00e9tiser<\/strong> des informations. Ici, nous voulons pour chaque couleur distincte, compter combien de fois elle apparait dans la liste et diviser cette valeur par 2 (sans virgule). Ecrivons cela \u00e9tape par \u00e9tape :<\/p>\n\n\n\n
      gants \u2190 'gray' 'red' 'purple' 'purple' 'gray' 'black'\n\n      {\u237a, \u2375}\u2338 gants        \u235d Positions des couleurs dans le vecteur\n\u250c\u2500\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u252c\u2500\u2500\u2500\u2500\u2500\u2510\n\u2502gray  \u25021\u25025    \u2502\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2524\n\u2502red   \u25022\u2502     \u2502\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2524\n\u2502purple\u25023\u25024    \u2502\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u253c\u2500\u2500\u2500\u2500\u2500\u2524\n\u2502black \u25026\u2502     \u2502\n\u2514\u2500\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2534\u2500\u2500\u2500\u2500\u2500\u2518\n      {\u237a, \u2374\u2375}\u2338 gants       \u235d Nombre d'apparitions de chaque couleur\n\u250c\u2500\u2500\u2500\u2500\u2500\u2500\u252c\u2500\u2510\n\u2502gray  \u25022\u2502\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2524\n\u2502red   \u25021\u2502\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2524\n\u2502purple\u25022\u2502\n\u251c\u2500\u2500\u2500\u2500\u2500\u2500\u253c\u2500\u2524\n\u2502black \u25021\u2502\n\u2514\u2500\u2500\u2500\u2500\u2500\u2500\u2534\u2500\u2518\n      {\u2374\u2375}\u2338 gants            \u235d Uniquement le nombre d'apparitions\n2\n1\n2\n1\n\n      {.5 \u00d7 \u2374\u2375}\u2338 gants       \u235d Division par 2\n1  \n0.5\n1  \n0.5\n      {\u230a .5 \u00d7 \u2374\u2375}\u2338 gants     \u235d avec partie enti\u00e8re\n1\n0\n1\n0\n      +\u233f {\u230a .5 \u00d7 \u2374\u2375}\u2338 gants   \u235d Somme de la colonne\n2<\/code><\/pre>\n\n\n\n
Le programme final<\/strong> APL \u00e0 tester ici<\/a> :<\/p>\n\n\n\n
      nb_paires \u2190 +\u233f {\u230a .5 \u00d7 \u2374\u2375}\u2338\n\n      nb_paires 'red' 'green' 'red' 'blue' 'blue'\n2\n      nb_paires 'red' 'green' 'blue'\n0<\/code><\/pre>\n\n\n\n
Python et JavaScript : Version utilisant une seule boucle et une pile<\/h2>\n\n\n\n
Est-il vraiment n\u00e9cessaire de r\u00e9cup\u00e9rer les couleurs uniques ? Imaginons la situation dans la vie r\u00e9elle<\/strong> avec ‘red’ ‘green’ ‘red’ ‘blue’ ‘blue’<\/strong> :<\/p>\n\n\n\n