Mdelamor: Protegió «Examen 21/06/21» ([Editar=Solo administradores] (indefinido) [Trasladar=Solo administradores] (indefinido))

2021-11-17T22:17:45Z

Protegió «Examen 21/06/21» ([Editar=Solo administradores] (indefinido) [Trasladar=Solo administradores] (indefinido))

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

Mdelamor: Página creada con « -- Informática (1º del Grado en Matemáticas) -- 4º examen de evaluación continua (21 de junio de 2021) Grupos A, B y C -- ==============…»

2021-11-17T22:17:38Z

Página creada con «<source lang='haskell'> -- Informática (1º del Grado en Matemáticas) -- 4º examen de evaluación continua (21 de junio de 2021) Grupos A, B y C -- ==============…»

Página nueva

<source lang='haskell'>

-- Informática (1º del Grado en Matemáticas)
-- 4º examen de evaluación continua (21 de junio de 2021) Grupos A, B y C
-- ============================================================================

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

-- ============================================================================

import qualified Data.Vector as V
import qualified Data.Array as A
import Data.Numbers.Primes
-- Selecciona de estas dos librerías la que hayas utilizado en clase
import GrafoConMatrizDeAdyacencia
-- import I1M.Grafo

import Data.List

-- ============================================================================
-- Ejercicio 1. (2.5 ptos) El complemento de un número positivo N se calcula
-- por el siguiente rocedimiento:
-- Si N es mayor que 9, se toma cada dígito por su valor posicional y se
-- resta del mayor los otros dígitos. Por ejemplo, el complemento de 1448 es
-- 1000 - 400 - 40 - 8 = 552. Cuando N es menor que 10, su complemento es N.
--
-- Definir las funciones
-- cadena :: Integer -> [Integer]
-- conCadena :: Int -> [Integer]
-- tales que
-- + '(cadena n)' es la cadena de primos a partir del número 'n' tal que cada
-- uno es el complemento del anterior. Por ejemplo,
-- cadena 8 == []
-- cadena 7 == [7]
-- cadena 13 == [13,7]
-- cadena 643 == [643,557,443]
-- cadena 18127 == [18127,1873,127,73,67,53,47]
-- cadena 18181213 == [18181213,1818787,181213,18787,1213,787,613,587]
-- + '(conCadena n)' es la lista de números cuyas cadenas tienen 'n'
-- elementos. Por ejemplo,
-- take 6 (conCadena 3) == [23,31,61,67,103,307]
-- [head (conCadena n) | n <- [4..8]] == [37,43,157,18127,181873]
-- ----------------------------------------------------------------------------

complemento :: Integer -> Integer
complemento n =
let c = 10^(length (show n)-1)
in (div n c)*c - (mod n c)

cadena :: Integer -> [Integer]
cadena n
| n < 10 && isPrime n = [n]
| isPrime n = n : cadena (complemento n)
| otherwise = []

conCadena :: Int -> [Integer]
conCadena n =
filter ((==n).length.cadena) primes

-- ============================================================================
-- Ejercicio 2. (2.5 puntos) Un número es innombrable si es divisible por 7 o
-- alguno de sus dígitos es un 7. Un juego infantil consiste en contar
-- saltándose los números innombrables:
-- 1 2 3 4 5 6 ( ) 8 9 10 11 12 13 ( ) 15 16 ( ) 18 ...
--
-- La sucesión de Cantor se obtiene llenando los huecos de la sucesión
-- anterior con la propia sucesión:
-- 1 2 3 4 5 6 (1) 8 9 10 11 12 13 (2) 15 16 (3) 18 19 20 (4) 22 23
-- 24 25 26 (5) (6) 29 30 31 32 33 34 (1) 36 (8) 38 39 40 41 (9) 43
-- 44 45 46 (10) 48 (11) 50 51 52 53 54 55 (12) (13) 58 59 60 61 62
-- (2) 64 65 66 (15) 68 69 (16) (3) (18) (19) (20) (4) (22) (23) (24)
-- (25) 80 81 82 83 (26) 85 86 (5) 88 89 90 (6) 92 93 94 95 96 (29)
-- (30) 99 100
--
-- Definir la lista
-- sucCantor :: [Integer]
-- cuyo valor es la sucesión de Cantor. Por ejemplo,
-- take 100 sucCantor ==
-- [1,2,3,4,5,6, 1 ,8,9,10,11,12,13, 2 ,15,16, 3 ,18,19,20, 4 ,22,23,
-- 24,25,26, 5,6 ,29,30,31,32,33,34, 1 ,36, 8 ,38,39,40,41, 9 ,43,44,
-- 45,46, 10 ,48, 11 ,50,51,52,53,54,55, 12,13 ,58,59,60,61,62, 2 ,64,
-- 65,66, 15 ,68,69, 16,3,18,19,20,4,22,23,24,25, 80,81,82,83, 26 ,85,
-- 86, 5 ,88,89,90, 6 ,92,93,94,95,96, 29,30 ,99,100]
-- sucCantor !! (5+10^6) == 544480
-- sucCantor !! (6+10^6) == 266086
-- ============================================================================

sucCantor :: [Integer]
sucCantor =
mezclaCantor [1..] sucCantor

mezclaCantor :: [Integer] -> [Integer] -> [Integer]
mezclaCantor (x:xs) ys =
if x`mod`7 == 0 || elem '7' (show x)
then (head ys) : mezclaCantor xs (tail ys)
else x : mezclaCantor xs ys

-- ============================================================================
-- Ejercicio 3. (2.5 ptos) Consideremos grafos en los que cada arista está
-- etiquetada con un valor que representa un color (en lugar de un peso). Un
-- camino alternado en este tipo de grafos es un camino que no pasa por dos
-- aristas consecutivas del mismo color.
--
-- Definir la función
-- caminoAlternado :: (A.Ix v, Num p, Eq p) => Grafo v p -> [v] -> Bool
-- tal que '(caminoAlternado g vs)' comprueba que la secuencia de nodos 'vs'
-- del grafo 'g', forma un camino alternado en el grafo. Por ejemplo,
-- caminoAlternado grafo [1,2,4,3,5] == True
-- caminoAlternado grafo [3,1,2,4,6] == False
-- donde 'grafo' es el grafo que se define a continuación (selecciona de las
-- siguientes definiciones de grafos la que hayas utilizado en clase):

-- grafo :: Grafo Int Int
-- grafo = creaGrafo ND (1,6) [(1,2,3),(1,3,1),(1,5,1),(3,5,2),
-- (2,4,1),(2,6,2),(3,4,3),(4,6,1)]

-- grafo :: Grafo Int Int
-- grafo = asignaPesos (creaGrafo ND (1,6) [(1,2),(1,3),(1,5),(3,5),
-- (2,4),(2,6),(3,4),(4,6)])
-- [((1,2),3),((1,3),1),((1,5),1),((3,5),2),
-- ((2,4),1),((2,6),2),((3,4),3),((4,6),1)]

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

caminoAlternado :: (A.Ix v, Num p, Eq p) => Grafo v p -> [v] -> Bool
caminoAlternado g vs =
let as = zip vs (tail vs)
in (all (aristaEn g) as) && -- vs es un camino en g
(and [peso g a1 /= peso g a2 | (a1,a2) <- zip as (tail as)])

-- ============================================================================
-- Ejercicio 4. (2.5 ptos) En una rejilla de 2xN cuadros de longitud se pueden
-- colocar de distintas formas piezas de 2 cuadros de longitud, en horizontal y
-- vertical, de forma que no quede espacio libre en la rejilla. Por ejemplo,
-- una rejilla de 2x12 cuadros de longitud se puede rellenar de la siguiente
-- forma:
--
-- ╔═══╦═╦═╦═╦═══╦═══╦═╦═══╗
-- ╠═══╣ ║ ║ ╠═══╬═══╣ ╠═══╣
-- ╚═══╩═╩═╩═╩═══╩═══╩═╩═══╝
--
-- Definir la función
-- rejillas2N :: Int -> Integer -> Integer
-- tal que '(rejillas2N n m)' es el número de formas distintas de rellenar una
-- rejilla de '2xn' cuadros de longitud con piezas de 2 cuadros de longitud de
-- 'm' colores distintos, calculado mediante la técnica de programación
-- dinámica. Tened en cuenta que no hay ninguna restricción acerca de cómo
-- colocar las piezas de distintos colores. Por ejemplo,
-- rejillas2N 2 2 == 8
-- rejillas2N 2 3 == 18
-- rejillas2N 3 2 == 24
-- rejillas2N 3 3 == 81
-- rejillas2N 20 5 == 1043891906738281250
-- length (show (rejillas2N 100 7)) == 106
-- length (show (rejillas2N 1000 9)) == 1164
-- ----------------------------------------------------------------------------

-- rejillas2N n m =
-- m * (rejillas2N (n-1) m) + m^2 * (rejillas2N (n-2) m)

-- Versión recursiva

rejillas2NR :: Int -> Integer -> Integer
rejillas2NR 0 m = 1
rejillas2NR 1 m = m
rejillas2NR n m =
m * (rejillas2NR (n-1) m) + m^2 * (rejillas2NR (n-2) m)

-- Versión usando programación dinámica

rejillas2N :: Int -> Integer -> Integer
rejillas2N n m =
let v = V.generate (n+1) (\ i -> generaRejillas2N v m i)
in v V.! n

generaRejillas2N :: V.Vector Integer -> Integer -> Int -> Integer
generaRejillas2N v m 0 = 1
generaRejillas2N v m 1 = m
generaRejillas2N v m i =
m * (v V.! (i-1)) + m^2 * (v V.! (i-2))

-- ============================================================================

</source>

Examen 21/06/21 - Historial de revisiones

Mdelamor: Protegió «Examen 21/06/21» ([Editar=Solo administradores] (indefinido) [Trasladar=Solo administradores] (indefinido))

Mdelamor: Página creada con « -- Informática (1º del Grado en Matemáticas) -- 4º examen de evaluación continua (21 de junio de 2021) Grupos A, B y C -- ==============…»