Mdelamor en 22:19 17 nov 2021

2021-11-17T22:19:31Z

Mdelamor: Protegió «Examen 07/09/2021» ([Editar=Solo administradores] (indefinido) [Trasladar=Solo administradores] (indefinido))

2021-11-17T22:18:52Z

Protegió «Examen 07/09/2021» ([Editar=Solo administradores] (indefinido) [Trasladar=Solo administradores] (indefinido))

← Revisión anterior	Revisión del 22:18 17 nov 2021
(Sin diferencias)

Mdelamor: Página creada con « -- Informática (1º del Grado en Matemáticas) -- 2ª convocatoria -- ===================================================================== -- No…»

2021-11-17T22:18:44Z

Página creada con «<source lang='haskell'> -- Informática (1º del Grado en Matemáticas) -- 2ª convocatoria -- ===================================================================== -- No…»

Página nueva

<source lang='haskell'>

-- Informática (1º del Grado en Matemáticas)
-- 2ª convocatoria

-- =====================================================================
-- Nombre:
-- Apellidos:
-- UVUS:
-- =====================================================================

-- ---------------------------------------------------------------------
-- Importación de librerías --
-- ---------------------------------------------------------------------

import Data.Matrix
import qualified Data.Set as S
import qualified Data.Vector as V
import Data.List
import Data.Numbers.Primes
import I1M.Cola

-- ---------------------------------------------------------------------
-- Ejercicio ?. Una permutación de n se representa como una lista de los
-- elementos 1..n. Por ejemplo, la lista [3,1,2,4] representa la
-- permutación tal que corresponde con la transformación:
-- 1 -> 3
-- 2 -> 1
-- 3 -> 2
-- 4 -> 4

-- Definir la función
-- compPermutaciones :: [Int] -> [Int]
-- tal que (compPermutaciones p q) es composición de las permutaciones p
-- y q. Por ejemplo, si p = [1,3,4,2] y q = [3,1,2,4], la composición
-- es:
-- 1 -> 1 -> 3
-- 2 -> 3 -> 2
-- 3 -> 4 -> 4
-- 4 -> 2 -> 1

-- compPermutaciones [1,3,4,2] [3,1,2,4] == [3,2,4,1]

compPermutaciones :: [Int] -> [Int] -> [Int]
compPermutaciones p q =
map snd (comp (zip [1..n] p) (zip [1..n] q))
where n = length p
comp r s = [(x,z) | (x,y) <- r, (y',z) <-s, y == y']

-- ---------------------------------------------------------------------
-- Ejercicio ?. Se tienen n cartas numeradas en un único montón en orden
-- creciente desde arriba hacia abajo; es decir, la carta de más arriba
-- es la número 1, luego sigue la número 2, ...
--
-- Se hace lo siguiente:
-- + se coloca la carta número 1 debajo de todas,
-- + se quita de arriba la carta número 2,
-- + se coloca la carta número 3 debajo de todas,
-- + se quita de arriba la carta número 4,
-- + ...
--
-- El proceso continúa siempre de la misma manera: se coloca la carta de
-- más arriba debajo de todas y se quita la que ha quedado arriba, hasta
-- que quede una única carta.
--
-- Definir la función
-- cartaFinal :: Int -> Int
-- tal que (cartaFinal n) es la carta final que queda en el montón. Por
-- ejemplo,
-- cartaFinal 4 == 1
-- cartaFinal 7 == 7
-- cartaFinal 10 == 5
-- cartaFinal 20 == 9
-- cartaFinal 100 == 73
-- ---------------------------------------------------------------------

-- Usando listas:

cartaFinal :: Int -> Int
cartaFinal n = head (until pred paso [1..n])
where paso (x:xs) = tail (xs++[x])
pred (x:xs) = null xs

-- Usando colas:

cartaFinalC :: Int -> Int
cartaFinalC n = primero (until pred paso cInicial)
where cInicial = foldr inserta vacia [n,n-1..1]
pred c = not (esVacia c) && esVacia (resto c)
paso c = resto (inserta (primero c) (resto c))

-- ---------------------------------------------------------------------
-- Ejercicio ?. Dada una matriz A, de dimensión n×n , sea X_i el
-- conjunto de elementos de la fila i, e Y_j el conjunto de elementos de
-- la columna j, 1 ≤ i, j ≤ n. Decimos que A es dorada si
-- X_1,...,X_n,Y_1,...,Y_n son conjuntos distintos.

-- Definir la función
-- esMatrizDorada :: Ord a => Matrix a -> Bool
-- tal que (esMatrizDorada A) verifique si A es dorada. Por ejemplo,
-- esMatrizDorada (fromLists [[1,2,1],[1,1,1],[2,2,2]]) == False
-- esMatrizDorada (fromLists [[1,2,1],[1,1,1],[3,3,4]]) == True
-- ---------------------------------------------------------------------

esMatrizDorada :: Ord a => Matrix a -> Bool
esMatrizDorada p =
conjDistintosLista (filas p ++ columnas p)
where n = nrows p
filas p = [S.fromList (V.toList (getRow i p)) | i <-[1..n]]
columnas p = [S.fromList (V.toList (getCol i p)) | i <-[1..n]]

conjDistintosLista :: Ord a => [S.Set a] -> Bool
conjDistintosLista [] = True
conjDistintosLista (xs:xss) =
all (not . ((==) xs)) xss && conjDistintosLista xss

-- ---------------------------------------------------------------------
-- Ejercicio ?. Consideremos el problema de construir los árboles
-- etiquetados en las hojas, a partir de una lista xs, de forma que el
-- borde del árbol consista en los elementos de esta lista. Por ejemplo,
-- si xs = [1,2,3], los árboles que se obtienen son los siguientes:

-- . .
-- / \ / \
-- 1 . . 3
-- / \ / \
-- 2 3 1 2

-- Definir la función
-- arboles:: [Int] -> [Arbol]
-- tal que (arboles xs) es la lista de los árboles que se pueden
-- construir de forma que los elementos que constituyen su borde es la
-- lista xs. Por ejemplo,
-- arboles [1..3] = [Nodo (Hoja 1) (Nodo (Hoja 2) (Hoja 3)),
-- Nodo (Nodo (Hoja 1) (Hoja 2)) (Hoja 3)]
-- ----------------------------------------------------------------------------

data Arbol = Hoja Int | Nodo Arbol Arbol
deriving Show

-- Definimos la función arboles, de forma recursiva

arboles:: [Int] -> [Arbol]
arboles [x] = [Hoja x]
arboles (x:xs) = concatMap (prefijos x) (arboles xs)

-- (prefijos x a) es la lista de todas las formas en la que x puede ser
-- insertada como la hoja más a la izquierda en el árbol a. Por ejemplo,
-- si el árbol es
-- .
-- / \
-- 2 3
--
-- hay dos formas de insertar 1 de forma que sea la hoja más a la
-- izquierda:

-- . .
-- / \ / \
-- 1 . . 3
-- / \ / \
-- 2 3 1 2

prefijos:: Int -> Arbol -> [Arbol]
prefijos x a@(Hoja y) = [Nodo (Hoja x) a]
prefijos x a@(Nodo i d) =
(Nodo (Hoja x) a):[Nodo i' d | i' <- prefijos x i]

-- prefijos 1 (Nodo (Hoja 2) (Hoja 3))
-- [Nodo (Hoja 1) (Nodo (Hoja 2) (Hoja 3)),
-- Nodo (Nodo (Hoja 1) (Hoja 2)) (Hoja 3)]

-- arboles [1..3]
-- [Nodo (Hoja 1) (Nodo (Hoja 2) (Hoja 3)),
-- Nodo (Nodo (Hoja 1) (Hoja 2)) (Hoja 3)]

-- ---------------------------------------------------------------------

</source>

← Revisión anterior		Revisión del 22:19 17 nov 2021
Línea 22:		Línea 22:

	-- ---------------------------------------------------------------------		-- ---------------------------------------------------------------------
	-- Ejercicio ?. Una permutación de n se representa como una lista de los		-- Ejercicio 1. Una permutación de n se representa como una lista de los
	-- elementos 1..n. Por ejemplo, la lista [3,1,2,4] representa la		-- elementos 1..n. Por ejemplo, la lista [3,1,2,4] representa la
	-- permutación tal que corresponde con la transformación:		-- permutación tal que corresponde con la transformación:
Línea 50:		Línea 50:

	-- ---------------------------------------------------------------------		-- ---------------------------------------------------------------------
	-- Ejercicio ?. Se tienen n cartas numeradas en un único montón en orden		-- Ejercicio 2. Se tienen n cartas numeradas en un único montón en orden
	-- creciente desde arriba hacia abajo; es decir, la carta de más arriba		-- creciente desde arriba hacia abajo; es decir, la carta de más arriba
	-- es la número 1, luego sigue la número 2, ...		-- es la número 1, luego sigue la número 2, ...
Línea 94:		Línea 94:

	-- ---------------------------------------------------------------------		-- ---------------------------------------------------------------------
	-- Ejercicio ?. Dada una matriz A, de dimensión n×n , sea X_i el		-- Ejercicio 3. Dada una matriz A, de dimensión n×n , sea X_i el
	-- conjunto de elementos de la fila i, e Y_j el conjunto de elementos de		-- conjunto de elementos de la fila i, e Y_j el conjunto de elementos de
	-- la columna j, 1 ≤ i, j ≤ n. Decimos que A es dorada si		-- la columna j, 1 ≤ i, j ≤ n. Decimos que A es dorada si
Línea 119:		Línea 119:

	-- ---------------------------------------------------------------------		-- ---------------------------------------------------------------------
	-- Ejercicio ?. Consideremos el problema de construir los árboles		-- Ejercicio 4. Consideremos el problema de construir los árboles
	-- etiquetados en las hojas, a partir de una lista xs, de forma que el		-- etiquetados en las hojas, a partir de una lista xs, de forma que el
	-- borde del árbol consista en los elementos de esta lista. Por ejemplo,		-- borde del árbol consista en los elementos de esta lista. Por ejemplo,

Examen 07/09/2021 - Historial de revisiones

Mdelamor en 22:19 17 nov 2021

Mdelamor: Protegió «Examen 07/09/2021» ([Editar=Solo administradores] (indefinido) [Trasladar=Solo administradores] (indefinido))

Mdelamor: Página creada con « -- Informática (1º del Grado en Matemáticas) -- 2ª convocatoria -- ===================================================================== -- No…»