Download Boletín 3

Recursión sobre datos
1.- Denir un procedimiento media-arit que calcule la media aritmética de los elementos
de una lista de números
(media-arit '(2 4 6 1))
(media-arit '(34))
(media-arit ())
reales. Si la lista es vacía debe devolver 0.
=> 13/4
=> 34
=> 0
2.- Denir un procedimiento media-geom que calcule la media geométrica de una lista
de números reales positivos. Si la lista es vacía debe devolver 1. Recordemos que
√
dados los números a1 , . . . , an su media geométrica es el valor n a1 · · · an .
(media-geom '(1 3 5 7))
(media-geom '(2.5 1.3))
(media-geom ())
=> 3.2010858729436795
=> 1.8027756377319946
=> 1
3.- Denir un procedimiento min-max que reciba una lista numérica plana no vacía y
devuelva una lista formada por dos pares punteados de la forma (min . numero1 )
y (max . numero2 ), donde numero1 y numero2 son, respectivamente, el mínimo y
el máximo de los elementos de la lista.
(min-max '(1 2 3 4))
=> ((min . 1) (max . 4))
(min-max '(2 82 23 45 2)) => ((min . 2) (max . 82))
(min-max '(4 4 4))
=> ((min . 4) (max . 4))
4.- Denir un procedimiento ultimo que reciba una lista no vacía y devuelva el último
elemento de dicha lista.
(ultimo '(a b c))
(ultimo '((1 2) 3 (4 5)))
(ultimo '(a))
=> c
=> (4 5)
=> a
5.- Denir un procedimiento suc-creciente que reciba un número natural n y devuelva
la lista de los números desde 0 hasta n , en orden creciente.
(suc-creciente 3)
(suc-creciente 5)
=> (0 1 2 3)
=> (0 1 2 3 4 5)
6.- Denir un procedimiento aprox-lim-seno que reciba un número natural n , mayor
que 0, y devuelva una lista cuyos elementos son los términos de la sucesión sin(1/m)
1/m
desde 1 hasta n .
(aprox-lim-seno 1) => (0.8414709848078965)
(aprox-lim-seno 3) => (0.8414709848078965 0.958851077208406 0.9815840903884566)
7.- Denir un procedimiento aprox-e que reciba un número natural n , mayor que 0, y
devuelva una
1 hasta n .
(aprox-e 1)
(aprox-e 3)
(aprox-e 5)
lista cuyos elementos son los términos de la sucesión (1 +
1 m
)
m
desde
=> (2)
=> (2 2.25 2.37037037037037)
=> (2 2.25 2.37037037037037 2.44140625 2.4883199999999994)
1
8.- Denir un procedimiento lista-aleatoria que reciba un número natural n y devuelva
una lista de longitud n cuyos elementos son números aleatorios entre 1 y n . (Nota:
el procedimiento random , aplicado a un número natural n , devuelve un número
aleatorio entre 0 y n-1 .)
(lista-aleatoria 5)
(lista-aleatoria 5)
(lista-aleatoria 5)
=> (1 2 1 2 3)
=> (1 4 5 3 2)
=> (1 5 4 5 4)
9.- Denir un procedimiento resta-a-cada que reciba un número x y una lista numérica
plana l y devuelva la lista en la que a cada elemento de l se le ha restado x .
(resta-a-cada 2 ())
(resta-a-cada 2 '(3 1 5 6))
(resta-a-cada 1.5 '(0.5 0 -0.5))
=> ()
=> (1 −1 3 4)
=> (−1.0 −1.5 −2.0)
10.- Denir un procedimiento quita-ultimo que reciba una lista l , no vacía, y devuelva
la lista resultante de eliminar el último elemento de l .
(quita-ultimo '(1))
=> ()
(quita-ultimo '(a b c d e)) => (a b c d)
(quita-ultimo '(s s s))
=> (s s)
11.- Denir un procedimiento lista->numero que reciba una lista no vacía de dígitos y
devuelva el número formado por dichos dígitos.
(lista->numero '(0))
(lista->numero '(1 3 4 7))
(lista->numero '(0 0 1))
=> 0
=> 1347
=> 1
12.- Denir un procedimiento ciclo que permute cíclicamente los elementos de una lista.
Si la lista es vacía debe devolver ().
(ciclo '(2 5 7 d g))
(ciclo '(yo tu el))
(ciclo '())
=> (g 2 5 7 d)
=> (el yo tu)
=> ()
13.- Denir un procedimiento intercambia que reciba dos datos x e y y una lista l y devuelva la lista resultante de cambiar las ocurrencias de x en l por y , y las ocurrencias
de y en l por x .
(intercambia 'a 'b '(c d b a b (a b) f))
(intercambia 'a 'b ())
(intercambia '(1) '(2) '(1 (1) 2 (2)))
=> (c d a b a (a b) f)
=> ()
=> (1 (2) 2 (1))
14.- Denir un procedimiento bocata que reciba dos datos x e y y una lista l y devuelva
la lista resultante de insertar y a izquierda y derecha de cada ocurrencia de x en l .
(bocata 'a 'b '())
(bocata 'a 'b '(d a))
(bocata 'queso 'pan '(queso tomate queso jamon lechuga))
=> (pan queso pan tomate pan queso pan jamon lechuga)
2
=> ()
=> (d b a b)
15.- Denir un procedimiento dentro-del-intervalo? que reciba dos números x e y , el
primero menor o igual que el segundo, y una lista numérica plana l y devuelva #t
si todos los elementos de l están entre x e y y #f en caso contrario.
(dentro-del-intervalo? 1 5 ())
(dentro-del-intervalo? 1 5 '(3 2 4.5 1.8))
(dentro-del-intervalo? 0.5 6 '(-1 7 4))
=> #t
=> #t
=> #f
16.- Denir un procedimiento estan-en-el-intervalo que reciba dos números x e y , el
primero menor o igual que el segundo, y una lista numérica plana l y devuelva la
lista de los elementos de l que están entre x e y .
(estan-en-el-intervalo 1 5 '(3 2 4.5 1.8))
(estan-en-el-intervalo 0.5 6 '(-1 7 4))
(estan-en-el-intervalo 3 9 '(1 2 17))
=> (3 2 4.5 1.8)
=> (4)
=> ()
17.- Denir un procedimiento elimina-duplicados que reciba una lista l y devuelva la
lista obtenida al eliminar en l los elementos repetidos, salvo la última ocurrencia.
(elimina-duplicados '((1) 1 1 (1)))
(elimina-duplicados '(3 1 2 3 2 1 4))
(elimina-duplicados '(1 3 5 6 d 4 a f))
=> (1 (1))
=> (3 2 1 4)
=> (1 3 5 6 d 4 a f)
18.- Denir un procedimiento union que reciba dos listas l1 y l2 , sin elementos repetidos,
y devuelva una lista formada por los elementos de l1 y de l2 , sin repeticiones.
(union () ())
(union '(q s (3) 1 2) '(f q 4 3 2))
(union '(1 (2)) '((2) 1))
=> ()
=> (q s (3) 1 2 f 4 3)
=> (1 (2))
19.- Denir un procedimiento interseccion que reciba dos listas l1 y l2 , sin elementos
repetidos, y devuelva una lista formada por los elementos comunes a ambas listas.
(interseccion '(1 2 3 4) ())
(interseccion '(1 2 3 4) '(d f t))
(interseccion '(q (4) e (r) 6) '(e 4 r (r) 2 1))
=> ()
=> ()
=> (e (r))
20.- Denir un procedimiento reagrupa que reciba una lista no vacía l cuyos elementos
sean listas de longitud 3 y actúe del siguiente modo:
(reagrupa '((#t #f #t)))
(reagrupa '((1 2 3) (4 5 6) (7 8 9)))
(reagrupa '(((a) (b) (c)) ((1) (2) (3))))
=> ((#t) (#f) (#t))
=> ((1 4 7) (2 5 8) (3 6 9))
=> (((a) (1)) ((b) (2)) ((c) (3)))
21.- Denir un procedimiento suma-listas que, dadas dos listas numéricas planas de la
misma longitud, las sume elemento a elemento.
(suma-listas '() '())
(suma-listas '(2 4) '(2 8))
(suma-listas '(1 4 6) '(3 7 2))
=> ()
=> (4 12)
=> (4 11 8)
3
22.- Denir un procedimiento intercala que reciba dos listas de la misma longitud y
devuelva la lista resultante de intercalar los elementos de cada una de las listas.
(intercala () ())
=> ()
(intercala '(1 2 3) '(a b c))
=> (1 a 2 b 3 c)
(intercala '(#t #t) '(#f #f)) => (#t #f #t #f)
23.- Denir un procedimiento ocurre-prof que reciba un dato x y una lista l y devuelva
el número de veces que ocurre x en l , en cualquier nivel.
(ocurre-prof 1 ())
(ocurre-prof 1 '(1 (y ((1) g))))
(ocurre-prof 1 '(s 7 (9) h))
=> 0
=> 2
=> 0
24.- Denir un procedimiento mult-prof que reciba una lista l y devuelva el producto
de los números que hay en l , en cualquier nivel. Si no hay ningún número, debe
devolver 1.
(mult-prof ())
=> 1
(mult-prof '(1 2 a (3 r)))
=> 6
(mult-prof '(q (1 (3 (a 9) 7)) j)) => 189
25.- Denir un procedimiento extrae-1e-2n que reciba una lista l y devuelva el primer
elemento de segundo nivel de dicha lista.
(extrae-1e-2n '(1 ((2)) (3)))
(extrae-1e-2n '(b (a c) (d e)))
(extrae-1e-2n '(a 3 d ()))
=> (2)
=> a
=> extrae-2e: no hay elementos de segundo nivel
26.- Decimos que un dato es un átomo si no es una lista no vacía. Denir un procedi-
miento cuenta-atomos que reciba una lista l y devuelva el número de átomos que
hay en l , en cualquier nivel.
(cuenta-atomos '(()))
(cuenta-atomos '(a d (e f) g))
(cuenta-atomos '(8 (a b) (() (xy z))))
=> 1
=> 5
=> 6
27.- Denir un procedimiento cuenta-no-listas que reciba una lista l y devuelva el número
de elementos de l que no son listas, en cualquier nivel.
(cuenta-no-listas '(()))
(cuenta-no-listas '(a d (e f) g))
(cuenta-no-listas '(8 (a b) (() (xy z))))
=> 0
=> 5
=> 5
28.- Denir un procedimiento intercambia-prof que haga lo mismo que el procedimiento
intercambia (ejercicio 13), pero en cualquier nivel.
(intercambia-prof 'a 'b '(c d b a b (a b) f))
(intercambia-prof 'a 'b '(((a) (b))))
(intercambia-prof '(1) '(2) '((1) ((1)) (2) ((2))))
4
=> (c d a b a (b a) f)
=> (((b) (a)))
=> ((2) ((2)) (1) ((1)))
29.- Denir un procedimiento inserta-izq-prof que tome dos datos x e y y una lista l y
devuelva la lista que resulta de insertar y a la izquierda de x , en todos los niveles.
(inserta-izq-prof 'd 'i ())
(inserta-izq-prof 'd 'i '(d (d) ((d))))
(inserta-izq-prof 'a 1 '(2 a (w a) d ((a) 6)))
=> ()
=> (i d (i d) ((i d)))
=> (2 1 a (w 1 a) d ((1 a) 6))
30.- Denir un procedimiento nivel que reciba un numero natural n y una lista l y
devuelva la lista de los elementos de l de nivel n .
(nivel 1 '(2 4 (i o u) b (bl) ((bla)) 0)) => (2 4 (i o u) b (bl) ((bla)) 0)
(nivel 2 '(2 4 (i o u) b (bl) ((bla)) 0)) => (i o u bl (bla))
(nivel 3 '(2 4 (i o u) b (bl) ((bla)) 0)) => (bla)
(nivel 4 '(2 4 (i o u) b (bl) ((bla)) 0)) => ()
31.- Denir un procedimiento min-max-it que haga lo mismo que el procedimiento minmax (ejercicio 3) y esté denido por recursión terminal.
32.- Denir un procedimiento aprox-lim-seno-it que haga lo mismo que aprox-lim-seno
(ejercicio 6) y esté denido por recursión terminal.
33.- Denir un procedimiento aprox-e-it que haga lo mismo que aprox-e (ejercicio 7) y
esté denido por recursión terminal.
34.- Denir un procedimiento acumulada que reciba una lista numérica plana l , no vacía,
y devuelva la lista obtenida al sustituir en l cada uno de sus elementos por la suma
de los elementos anteriores a él.
(acumulada '(1))
=> (1)
(acumulada '(4 3 2 1))
=> (4 7 9 10)
(acumulada '(2 4 5 10)) => (2 6 11 21)
35.- Denir un procedimiento mult-prof-it que realice lo mismo que el procedimiento
mult-prof (ejercicio 24) y esté denido por recursión terminal.
36.- Denir un procedimiento ocurre-prof-it que realice lo mismo que el procedimiento
ocurre-prof (ejercicio 23) y esté denido por recursión terminal.
37.- Denir un procedimiento lista-divisores , denido por recursión terminal, que reciba
un número natural n
en orden creciente.
(lista-divisores 6)
(lista-divisores 20)
(lista-divisores 16)
y devuelva la lista de sus divisores (incluido el 1 y excluido n),
=> (1 2 3)
=> (1 2 4 5 10)
=> (1 2 4 8)
38.- Denir un procedimiento cuenta-listas que reciba una lista l y devuelva el número
de listas que pertenecen a l , en cualquier nivel.
(cuenta-listas '(2 4 (i o u) b (bl) ((bla)) 0))
(cuenta-listas '(1 2 3 4 5))
(cuenta-listas '((((a)))))
5
=> 4
=> 0
=> 3
39.- Denir un procedimiento cuenta-planas que reciba una lista l y devuelva el número
de listas planas que son elementos de l , en cualquier nivel.
(cuenta-planas '(2 (f g) h (j k) 2))
(cuenta-planas '((a (b)) (5 (j o)) () 2))
(cuenta-planas '(1 2 3))
=> 2
=> 3
=> 0
40.- Denir un procedimiento ltra que reciba una lista numérica plana l y un número d ,
entre 0 y 100, y devuelva la lista de los elementos de l que se desvían como máximo
un d % de la media de l , es decir, los elementos x de l tales que
Ã
!
Ã
!
d
d
1−
M ≤x≤ 1+
M
100
100
donde M es la media de
(ltra '(1 2 3 4 5) 10)
(ltra '(1 2 3 4 5) 50)
(ltra '(1 2 3 4 5) 75)
los elementos de l .
=> (3)
=> (2 3 4)
=> (1 2 3 4 5)
41.- Denir un procedimiento mas-a-la-izq que reciba una lista l y devuelva el elemento
situado más a la izquierda de l .
(mas-a-la-izq '((a b) (c (d e))))
(mas-a-la-izq '((((c ((e f) g) h)))))
(mas-a-la-izq '(() a))
=> a
=> c
=> ()
42.- Denir un procedimiento mas-a-la-der que reciba una lista l y devuelva el elemento
situado más a la derecha de l .
(mas-a-la-der '((a b) (d (c d (f (g h) i) m n) u) v))
(mas-a-la-der '((((((b (c))))))))
(mas-a-la-der '(a ()))
=> v
=> c
=> ()
43.- Denir un predicado igual-estructura? que reciba dos listas l1 y l2 y devuelva #t
si las listas tienen la misma estructura y #f en caso contrario.
(igual-estructura? '(a (b (c d))) '(1 (2 (3 4))))
(igual-estructura? '(a (b (c d))) '(1 (2 3 4)))
(igual-estructura? '(a b c) '(1 2 3 4))
=> #t
=> #f
=> #f
44.- Denir un procedimiento min-prof que tome como argumento una lista numérica l ,
con al menos un número, y devuelva
nivel.
(min-prof '(1 (2) (3 ())))
(min-prof '((2)((3 4) -1)(0 ((1)))))
(min-prof '((-2) ((-2))))
el mínimo de los elementos de l , en cualquier
=> 1
=> −1
=> −2
45.- Denir un procedimiento injo->prejo que realice lo siguiente:
(injo->prejo
(injo->prejo
(injo->prejo
(injo->prejo
4)
'(2 + 3))
'(((5 ∗ 2) + 11) / 3))
'(7 − ((8 − 4) ∗ (2 − 5))))
6
=>
=>
=>
=>
4
(+ 2 3)
(/ (+ (∗ 5 2) 11) 3)
(− 7 (∗ (− 8 4) (− 2 5)))
46.- Denir un procedimiento prejo->injo que realice lo siguiente:
(prejo->injo
(prejo->injo
(prejo->injo
(prejo->injo
3)
'(+ 2 3))
'(− 7 (∗ (− 8 4) (− 2 5))))
'(/ (+ (∗ 5 2) 11) 3))
=>
=>
=>
=>
3
(2 + 3)
(7 − ((8 − 4) ∗ (2 − 5)))
(((5 ∗ 2) + 11) / 3)
47.- Denir un procedimiento marca-segun-nivel que reciba una lista l y devuelva la lista
obtenida sustituyendo cada elemento de l por un par punteado, formado por dicho
elemento y un número indicando su nivel en l .
(marca-segun-nivel ())
(marca-segun-nivel '(1 w 3))
(marca-segun-nivel '(w ((4) i) (((u)))))
=> ()
=> ((1 . 1) (w . 1) (3 . 1))
=> ((w . 1) (((4 . 3)) (i . 2)) ((((u . 4)))))
48.- Denir un procedimiento suma-valores que reciba una lista l1 , cuyos elementos, en
cualquier nivel, son pares punteados formados por un símbolo y un número, y una
lista de símbolos l2 y devuelva el número obtenido sumando los segundos elementos
de los pares de l1 cuyos primeros elementos estén en l2 .
(suma-valores '((uno . 1) (dos . 2)) '(tres dos))
(suma-valores '((a . 2) ((c . 1) (b . 3) ((d . 4)))) '(a d))
(suma-valores '((a . 2) ((c . 1) (b . 3) ((d . 4)))) '(e f))
49.-
=> 2
=> 6
=> 0
1. Denir un procedimiento prejo? que reciba dos listas l1 y l2 y devuelva #t
si los elementos de la lista l1 son los primeros de l2 y #f en caso contrario.
(prejo? '(1) '(1 2 6))
=> #t
(prejo? '(e i) '(e i o u))
=> #t
(prejo? '(e i) '(a e i o u)) => #f
2. Denir un predicado prejo-rep? que reciba una lista l y devuelva #t si l tiene
repetido el comienzo y #f en caso contrario.
(prejo-rep? '(1 2 3 1 2 3 4 5)) => #t [repite (1 2 3)]
(prejo-rep? '(a a e i o))
=> #t [repite (a )]
(prejo-rep? '(a e e i a))
=> #f
3. Decimos que una lista es buena si no contiene sublistas consecutivas iguales.
Denir un predicado lista-buena? que determine si una lista es buena o no.
(lista-buena? '(a e i o u))
=> #t
(lista-buena? '(a e i e i u)) => #f
(lista-buena? '(1 2 3 1 2)) => #t
50.- Decimos que una expresión expr es del tipo CP si es un número o una lista cumpliendo las siguientes condiciones:
• Está formada por tres elementos.
• El primero de ellos es uno de estos dos símbolos: s ó p .
• Los otros dos elementos son sendas expresiones del tipo CP.
7
Por ejemplo, (s 2 (p (s 5 2) 4)) es una expresión del tipo CP.
Denir un procedimiento calcula que reciba una expresión del tipo CP y devuelva
el resultado de evaluarla, habiendo sustituido s por + y p por ∗.
(calcula 3)
(calcula '(p 6 7))
(calcula '(s 2 (p (s 5 2) 4)))
=> 3
=> 42
=> 30
8