{"id":122,"date":"2022-03-17T18:44:41","date_gmt":"2022-03-17T17:44:41","guid":{"rendered":"https:\/\/blog.univ-angers.fr\/mathsinfo\/?page_id=122"},"modified":"2023-06-01T12:29:10","modified_gmt":"2023-06-01T11:29:10","slug":"apl-et-rpl-scan","status":"publish","type":"page","link":"https:\/\/blog.univ-angers.fr\/mathsinfo\/apl-et-rpl-scan\/","title":{"rendered":"et RPL : Scan"},"content":{"rendered":"

En APL il existe l’op\u00e9rateur  \\ (appel\u00e9 scan<\/strong> ou balayage <\/strong>ou r\u00e9duction partielle<\/strong>) qui fait penser \u00e0 l’op\u00e9rateur \/ de r\u00e9duction. Voici la diff\u00e9rence :<\/p>\n

f\/ 1 2 3 \u2026 = 1 f 2 f 3 \u2026\nf\\ 1 2 3 \u2026 = (f\/1) (f\/1 2) (f\/1 2 3) \u2026<\/pre>\n
Le n-ieme r\u00e9sultat est \u00e9gal \u00e0 la r\u00e9duction des n premiers \u00e9l\u00e9ments. L’exemple de base est la somme cumul\u00e9e<\/strong> des \u00e9l\u00e9ments d’un vecteur :<\/p>\n
+\\ 2 3 4 8 10\n2 5 9 17 27<\/pre>\n
On peut imaginer une version en RPL utilisant SEQ pour cr\u00e9er ces suites ou rester avec notre trio DOLIST, DOSUBS et STREAM. En effet, si on reprend la r\u00e9duction :<\/p>\n
1: { 2 3 4 8 10 }\n\u00ab + \u00bb\nPRG<\/strong> LIST PROC STREAM\n1: 27<\/pre>\n
Mais si l’on ajoute OVER<\/strong> pour dupliquer \u00e0 chaque fois le r\u00e9sultat pr\u00e9c\u00e9dent :<\/p>\n
1: { 2 3 4 8 10 }\n\u00ab OVER + \u00bb\nPRG<\/strong> LIST PROC STREAM\n5: 2\n4: 5\n3: 9\n2: 17\n1: 27<\/pre>\n
On obtient les bonnes valeurs mais elles seront sur la pile. Pour comprendre le principe, tapez sur votre machine :
\n2 ENTER 3 OVER + 4 OVER + 8 OVER + 10 OVER +<\/strong><\/p>\n
Reste \u00e0 la transformer en liste { 2 5 9 17 27}. On peut  imaginer cette version pour le cas d’une somme cumul\u00e9e :<\/p>\n
\u00ab \u2192 v\n \u00ab v \u00ab OVER + \u00bb STREAM v SIZE \u2192LIST \u00bb\n\u00bb\n'SCUM STO<\/strong>\n\n1: { 2 5 3 4}\nVAR<\/strong> SCUM\n1: {2 7 10 14}<\/pre>\n
Ou, de fa\u00e7on plus g\u00e9n\u00e9rale, d\u00e9finir SCA.<\/strong> (Scan), appel\u00e9 PRED<\/strong> dans le document d’origine de Norman Brenner) :<\/p>\n
\u00ab \u2192 v f\n \u00ab v \u00ab OVER f EVAL \u00bb STREAM v SIZE \u2192LIST \u00bb\n\u00bb\n'SCA. STO<\/strong><\/pre>\n
Exemples :<\/p>\n
1: {1 2 3 4}\n2: \u00ab + \u00bb\nVAR<\/strong> SCA.\n1: {1 3 6 10}\n\n1: {2 5 4 1 8 3 3}\n2: \u00ab MAX \u00bb\nVAR<\/strong> SCA.\n1: {2 5 5 5 8 8 8}  # Maximum progressif\n\nEn APL :\n\n\u2308\\ 2 5 4 1 8 3 3\n2 5 5 5 8 8 8<\/pre>\n
En particulier, lorsque les vecteurs sont binaires, cela permet d’avoir des r\u00e9sultats int\u00e9ressants :<\/p>\n
\u2227\\ 1 1 1 0 1 0 0 1\n   1 1 1 0 0 0 0 0    \u235d = 0 \u00e0 partir du 1er \"0\"\n\u2228\\ 0 0 0 0 1 0 0 1\n   0 0 0 0 1 1 1 1    \u235d = 1 \u00e0 partir du 1er \"1\"\n<\\ 0 0 1 0 1 1 0 0 1\n   0 0 1 0 0 0 0 0 0  \u235d Position du 1er \"1\"<\/pre>\n
En RPL :<\/p>\n
2: {1 1 1 0 1 0 0 1}\n1: \u00ab AND \u00bb\nVAR<\/strong> SCA.\n1: {1 1 1 0 0 0 0 0}\n\n2: {0 0 0 0 1 0 0 1}\n1: \u00ab OR \u00bb\nVAR<\/strong> SCA.\n1: {0 0 0 0 1 1 1 1}<\/pre>\n
Lorsque l’op\u00e9rateur f est commutatif (comme OR, AND, +, MAX…) il n’y a pas de diff\u00e9rence entre le RPL et l’APL. Par contre, pour des op\u00e9rateurs non commutatifs comme \u00ab\u00a0<\u00ab\u00a0, le r\u00e9sultat sera faux.<\/p>\n
APL<\/span> :   f\\ a b c = (a) (a f b) (a f (b f c))<\/code><\/p>\n
RPL<\/span> :   f\\ a b c = (a) (a f b) ((a f b) f c)<\/code><\/p>\n
Pour se convaincre :<\/p>\n
2: {0 0 1 0 1 1 0 0 1}\n1: \u00ab < \u00bb\nVAR<\/strong> SCA.\n1: {0 0 0 0 0 0 0 0 0}\n\nR\u00e9sultat attendu : 0 0 1 0 0 0 0 0 0<\/pre>\n
Exercice – Les immeubles<\/strong><\/p>\n
On vous donne une liste de hauteurs d’immeubles adjacents et on vous demande combien seront visibles si vous les regardez \u00e0 partir de la gauche. Par exemple, si les hauteurs sont 2 3 5 2 1 6 4<\/strong>, en vert ci-dessous les 4<\/strong> seuls immeubles qui seront visibles (les autres sont cach\u00e9s par des b\u00e2timents plus hauts)<\/p>\n
\"imm1\"<\/a><\/p>\n
On supposera dans un premier temps qu’il n’y a pas de zones vides entre les immeubles, c’est-\u00e0-dire que la liste ne contient pas de 0 (immeubles de hauteur nulle).<\/p>\n
IMM 2 3 5 2 1 6 4\nOutput: 4<\/pre>\n
Dans un second temps, consid\u00e9rez le cas g\u00e9n\u00e9ral.<\/p>\n
Corrig\u00e9 version 1<\/span> : Commen\u00e7ons par l’APL. On va d\u00e9j\u00e0 scanner les immeubles pour r\u00e9cup\u00e9rer les hauteurs maximales atteintes :<\/p>\n
       \u2308\\ 2 3 5 2 1 6 4\nOutput:   2 3 5 5 5 6 6<\/pre>\n
Il faut maintenant r\u00e9cup\u00e9rer les hauteurs distinctes :<\/p>\n
       \u222a \u2308\\ 2 3 5 2 1 6 4\nOutput:     2 3 5 6<\/pre>\n
Et les compter :<\/p>\n
\u2374 \u222a \u2308\\ 2 3 5 2 1 6 4\nOutput: 4<\/pre>\n
Le programme final en APL pour la version 1 :<\/p>\n
IMM \u2190 {\u2374\u222a\u2308\\\u2375}<\/pre>\n
Nous pouvons imm\u00e9diatement traduire cela en RPL avec les programmes SCA.<\/strong> (scan), UN.<\/strong> (union) et la fonction SIZE :<\/p>\n
\u00ab \u00ab MAX \u00bb SCA. UN. SIZE \u00bb\n'IMM STO<\/pre>\n
V\u00e9rifions :<\/p>\n
1: { 2 3 5 2 1 6 4 }\nVAR<\/strong> IMM\n1: 4.<\/pre>\n
Corrig\u00e9 de la version g\u00e9n\u00e9rale<\/span> : Si la liste commence par un ou plusieurs 0, le calcul sera faux :<\/p>\n
1: { 0 2 1 }\nVAR<\/strong> IMM\n1: 2.<\/pre>\n
Ceci parce que les maximums progressifs sont { 0 2 2 } dont la r\u00e9union comporte 2 termes {0 2}. Il faut donc filtrer la liste des maximums pour enlever les 0. Une solution possible en APL :<\/p>\n
IMM \u2190 {\u2374\u222a (0 \u2260 n) \/ n \u2190 \u2308\\\u2375}<\/pre>\n
Et nous avions cr\u00e9er en RPL la fonction CL.<\/strong> pour compresser une liste en utilisant un vecteur logique. D’o\u00f9 cette version en RPL :<\/p>\n
\u00ab \u00ab MAX \u00bb SCA. DUP 0 > CL. UN. SIZE \u00bb\n'IMM STO<\/pre>\n
Qui signifie prendre les maximums progressifs, dupliquer cette liste, cr\u00e9er le vecteur logique des termes > 0, \u00e9liminer les \u00e9l\u00e9ments qui sont \u00e0 FAUX, faire la r\u00e9union des \u00e9l\u00e9ments restants et les compter.<\/p>\n
1: { 0 2 1 }\nVAR IMM\n1: 1.<\/pre>\n
Exemple – Les fractions continues<\/strong><\/p>\n
Pour la d\u00e9finition d’une fraction continue<\/a>, voir par exemple Wikipedia.<\/p>\n
En APL, on obtient la valeur approch\u00e9e d’une liste d’\u00e9tages par :<\/p>\n
+\u2218\u00f7\/ 1 2 2 2 2\n1.413793103<\/pre>\n
Qui correspond \u00e0 la valeur 1<\/strong> + 1 \/ ( 2<\/strong> + 1 \/ ( 2<\/strong> + 1 \/ ( 2<\/strong> + 1 \/ 2<\/strong> ) ) )<\/p>\n
Et en utilisant un scan :<\/p>\n
+\u2218\u00f7\\ 1 2 2 2 2\n1 1.5 1.4 1.416666667 1.413793103<\/pre>\n
On obtient les fractions 1, puis 1 + 1 \/ 2 puis
\n1 + 1 \/ (2 + 1 \/ 2)…<\/p>\n
En RPL, on peut obtenir la valeur finale par :<\/p>\n
\u00ab REVLIST \u00ab OVER INV + \u00bb STREAM \u2192NUM \u00bb\n'FC STO<\/strong>\n\n1: { 1 2 2 2 2 }\nVAR<\/strong> FC\n1: 1.41379310345     # \u2243 racine de 2\n\n1: { 1 1 1 1 1 1 1 1 1 1 }\nVAR<\/strong> FC\n1: 1.61818181818     # \u2243 nombre d'or<\/pre>\n
L’op\u00e9ration \u00ab\u00a0Prendre l’inverse plus additionner\u00a0\u00bb n’\u00e9tant pas commutative, on ne pourra pas utiliser notre fonction SCA.<\/strong><\/p>\n\n\n
Lire la suite…<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
En APL il existe l’op\u00e9rateur  \\ (appel\u00e9 scan ou balayage ou r\u00e9duction partielle) qui fait penser \u00e0 l’op\u00e9rateur \/ de r\u00e9duction. Voici la diff\u00e9rence : f\/ 1 2 3 \u2026 = 1 f 2 f 3 \u2026 f\\ 1 2 3 … Continuer la lecture →<\/span><\/a><\/p>\n","protected":false},"author":4913,"featured_media":0,"parent":0,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-122","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/pages\/122","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/types\/page"}],"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=122"}],"version-history":[{"count":1,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/pages\/122\/revisions"}],"predecessor-version":[{"id":1612,"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/pages\/122\/revisions\/1612"}],"wp:attachment":[{"href":"https:\/\/blog.univ-angers.fr\/mathsinfo\/wp-json\/wp\/v2\/media?parent=122"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}