I1M2011: Examen final

Hoy se ha realizado el examen de la convocatoria de julio de Informática de 1º del Grado en Matemáticas

A continuación se muestra el examen junto con su solución:

-- Informática (1º del Grado en Matemáticas)
-- Examen de la 1ª convocatoria (29 de junio de 2012)
-- ---------------------------------------------------------------------

import Data.List
import Data.Array

-- ---------------------------------------------------------------------
-- Ejercicio 1. [2 puntos] Definir la función
--    paresOrdenados :: [a] -> [(a,a)]
-- tal que (paresOrdenados xs) es la lista de todos los pares de
-- elementos (x,y) de xs, tales que x ocurren en xs antes que y. Por
-- ejemplo,  
--    paresOrdenados [3,2,5,4] == [(3,2),(3,5),(3,4),(2,5),(2,4),(5,4)]
--    paresOrdenados [3,2,5,3] == [(3,2),(3,5),(3,3),(2,5),(2,3),(5,3)]
-- ---------------------------------------------------------------------

-- 1ª definición:
paresOrdenados :: [a] -> [(a,a)]
paresOrdenados []     = []
paresOrdenados (x:xs) = [(x,y) | y <- xs] ++ paresOrdenados xs

-- 2ª definición:
paresOrdenados2 :: [a] -> [(a,a)]
paresOrdenados2 [] = []
paresOrdenados2 (x:xs) = 
    foldr (\y ac -> (x,y):ac) (paresOrdenados2 xs) xs

-- 3ª definición (con repeat):
paresOrdenados3 :: [a] -> [(a,a)]
paresOrdenados3 []     = []
paresOrdenados3 (x:xs) = zip (repeat x) xs ++ paresOrdenados3 xs

-- ---------------------------------------------------------------------
-- Ejercicio 2. [2 puntos] Definir la función 
--    sumaDeDos :: Int -> [Int] -> Maybe (Int,Int)
-- tal que (sumaDeDos x ys) decide si x puede expresarse como suma de
-- dos elementos de ys y, en su caso, devuelve un par de elementos de ys
-- cuya suma es x. Por ejemplo,
--    sumaDeDos 9 [7,4,6,2,5]  ==  Just (7,2)
--    sumaDeDos 5 [7,4,6,2,5]  ==  Nothing
-- ---------------------------------------------------------------------

sumaDeDos :: Int -> [Int] -> Maybe (Int,Int)
sumaDeDos _ []  =  Nothing
sumaDeDos _ [_] =  Nothing
sumaDeDos y (x:xs) | y-x `elem` xs = Just (x,y-x)
                   | otherwise     = sumaDeDos y xs

-- 2ª definición (usando paresOrdenados):
sumaDeDos2 :: Int -> [Int] -> Maybe (Int,Int)
sumaDeDos2 x xs 
    | null ys   = Nothing
    | otherwise = Just (head ys)
    where ys = [(a,b) | (a,b) <- paresOrdenados xs , a+b == x]

-- ---------------------------------------------------------------------
-- Ejercicio 3. [2 puntos] Definir la función
--    esProductoDeDosPrimos :: Int -> Bool
-- tal que (esProductoDeDosPrimos n) se verifica si n es el producto de
-- dos primos distintos. Por ejemplo,
--    esProductoDeDosPrimos 6  ==  True
--    esProductoDeDosPrimos 9  ==  False
-- ---------------------------------------------------------------------

esProductoDeDosPrimos :: Int -> Bool
esProductoDeDosPrimos n =
    [x | x <- primosN, 
         mod n x == 0, 
         div n x /= x, 
         elem (div n x) primosN] /= []
    where primosN = takeWhile (<=n) primos

primos :: [Int]
primos = criba [2..]
    where criba []     = []
          criba (n:ns) = n : criba (elimina n ns)
          elimina n xs = [x | x <- xs, x `mod` n /= 0]

-- ---------------------------------------------------------------------
-- Ejercicio 4. [2 puntos] La expresiones aritméticas se pueden
-- representar mediante el siguiente tipo 
--    data Expr = V Char 
--              | N Int 
--              | S Expr Expr
--              | P Expr Expr
--              deriving Show
-- por ejemplo, representa la expresión "z*(3+x)" se representa por
-- (P (V 'z') (S (N 3) (V 'x'))). 
--
-- Definir la función
--    sustitucion :: Expr -> [(Char, Int)] -> Expr
-- tal que (sustitucion e s) es la expresión obtenida sustituyendo las
-- variables de la expresión e según se indica en la sustitución s. Por
-- ejemplo, 
--    ghci> sustitucion (P (V 'z') (S (N 3) (V 'x'))) [('x',7),('z',9)]
--    P (N 9) (S (N 3) (N 7))
--    ghci> sustitucion (P (V 'z') (S (N 3) (V 'y'))) [('x',7),('z',9)]
--    P (N 9) (S (N 3) (V 'y'))
-- ---------------------------------------------------------------------
                   
data Expr = V Char 
          | N Int 
          | S Expr Expr
          | P Expr Expr
          deriving Show

sustitucion :: Expr -> [(Char, Int)] -> Expr
sustitucion e [] = e
sustitucion (V c) ((d,n):ps) | c == d = N n
                             | otherwise = sustitucion (V c) ps
sustitucion (N n) _ = N n                                 
sustitucion (S e1 e2) ps = S (sustitucion e1 ps) (sustitucion e2 ps)
sustitucion (P e1 e2) ps = P (sustitucion e1 ps) (sustitucion e2 ps)

-- ---------------------------------------------------------------------
-- Ejercicio 5. [2 puntos] (Problema 345 del proyecto Euler) Las
-- matrices puede representarse mediante tablas cuyos índices son pares
-- de números naturales:   
--    type Matriz = Array (Int,Int) Int
-- Definir la función 
--    maximaSuma :: Matriz -> Int
-- tal que (maximaSuma p) es el máximo de las sumas de las listas de
-- elementos de la matriz p tales que cada elemento pertenece sólo a una
-- fila y a una columna. Por ejemplo, 
--    ghci> maximaSuma (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])
--    17
-- ya que las selecciones, y sus sumas, de la matriz
--    |1 2 3|
--    |8 4 9|
--    |5 6 7|
-- son
--    [1,4,7] --> 12
--    [1,9,6] --> 16
--    [2,8,7] --> 17
--    [2,9,5] --> 16
--    [3,8,6] --> 17
--    [3,4,5] --> 12
-- Hay dos selecciones con máxima suma: [2,8,7] y [3,8,6].
-- ---------------------------------------------------------------------

type Matriz = Array (Int,Int) Int

maximaSuma :: Matriz -> Int
maximaSuma p = maximum [sum xs | xs <- selecciones p]

-- (selecciones p) es la lista de las selecciones en las que cada
-- elemento pertenece a un única fila y a una única columna de la matriz
-- p. Por ejemplo,
--    ghci> selecciones (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])
--    [[1,4,7],[2,8,7],[3,4,5],[2,9,5],[3,8,6],[1,9,6]]
selecciones :: Matriz -> [[Int]]
selecciones p = 
    [[p!(i,j) | (i,j) <- ijs] | 
     ijs <- [zip [1..n] xs | xs <- permutations [1..n]]] 
    where (_,(m,n)) = bounds p

-- Nota: En la anterior definición se ha usado la función pernutations
-- de Data.List. También se puede definir mediante
permutaciones :: [a] -> [[a]]
permutaciones []     = [[]]
permutaciones (x:xs) = 
    concat [intercala x ys | ys <- permutaciones xs]

-- (intercala x ys) es la lista de las listas obtenidas intercalando x
-- entre los elementos de ys. Por ejemplo, 
--    intercala 1 [2,3]  ==  [[1,2,3],[2,1,3],[2,3,1]]
intercala :: a -> [a] -> [[a]]
intercala x [] = [[x]]
intercala x (y:ys) = (x:y:ys) : [y:zs | zs <- intercala x ys]

-- 2ª solución (mediante submatrices):
maximaSuma2 :: Matriz -> Int
maximaSuma2 p 
    | (m,n) == (1,1) = p!(1,1)
    | otherwise = maximum [p!(1,j) + maximaSuma2 (submatriz 1 j p) | j <- [1..n]]
    where (m,n) = dimension p

-- (dimension p) es la dimensión de la matriz p.
dimension :: Matriz -> (Int,Int)
dimension = snd . bounds

-- (submatriz i j p) es la matriz obtenida a partir de la p eliminando
-- la fila i y la columna j. Por ejemplo, 
--    ghci> submatriz 2 3 (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])
--    array ((1,1),(2,2)) [((1,1),1),((1,2),2),((2,1),5),((2,2),6)]
submatriz :: Int -> Int -> Matriz -> Matriz
submatriz i j p = 
    array ((1,1), (m-1,n -1))
          [((k,l), p ! f k l) | k <- [1..m-1], l <- [1.. n-1]]
    where (m,n) = dimension p
          f k l | k < i  && l < j  = (k,l)
                | k >= i && l < j  = (k+1,l)
                | k < i  && l >= j = (k,l+1)
                | otherwise        = (k+1,l+1)

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

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

-- Examen de la 1ª convocatoria (29 de junio de 2012)

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

import Data.List

import Data.Array

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

-- Ejercicio 1. [2 puntos] Definir la función

-- paresOrdenados :: [a] -> [(a,a)]

-- tal que (paresOrdenados xs) es la lista de todos los pares de

-- elementos (x,y) de xs, tales que x ocurren en xs antes que y. Por

-- ejemplo,

-- paresOrdenados [3,2,5,4] == [(3,2),(3,5),(3,4),(2,5),(2,4),(5,4)]

-- paresOrdenados [3,2,5,3] == [(3,2),(3,5),(3,3),(2,5),(2,3),(5,3)]

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

-- 1ª definición:

paresOrdenados :: [a] -> [(a,a)]

paresOrdenados [] = []

paresOrdenados (x:xs) = [(x,y) | y <- xs] ++ paresOrdenados xs

-- 2ª definición:

paresOrdenados2 :: [a] -> [(a,a)]

paresOrdenados2 [] = []

paresOrdenados2 (x:xs) =

foldr (\y ac -> (x,y):ac) (paresOrdenados2 xs) xs

-- 3ª definición (con repeat):

paresOrdenados3 :: [a] -> [(a,a)]

paresOrdenados3 [] = []

paresOrdenados3 (x:xs) = zip (repeat x) xs ++ paresOrdenados3 xs

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

-- Ejercicio 2. [2 puntos] Definir la función

-- sumaDeDos :: Int -> [Int] -> Maybe (Int,Int)

-- tal que (sumaDeDos x ys) decide si x puede expresarse como suma de

-- dos elementos de ys y, en su caso, devuelve un par de elementos de ys

-- cuya suma es x. Por ejemplo,

-- sumaDeDos 9 [7,4,6,2,5] == Just (7,2)

-- sumaDeDos 5 [7,4,6,2,5] == Nothing

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

sumaDeDos :: Int -> [Int] -> Maybe (Int,Int)

sumaDeDos _ [] = Nothing

sumaDeDos _ [_] = Nothing

sumaDeDos y (x:xs) | y-x `elem` xs = Just (x,y-x)

| otherwise = sumaDeDos y xs

-- 2ª definición (usando paresOrdenados):

sumaDeDos2 :: Int -> [Int] -> Maybe (Int,Int)

sumaDeDos2 x xs

| null ys = Nothing

| otherwise = Just (head ys)

where ys = [(a,b) | (a,b) <- paresOrdenados xs , a+b == x]

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

-- Ejercicio 3. [2 puntos] Definir la función

-- esProductoDeDosPrimos :: Int -> Bool

-- tal que (esProductoDeDosPrimos n) se verifica si n es el producto de

-- dos primos distintos. Por ejemplo,

-- esProductoDeDosPrimos 6 == True

-- esProductoDeDosPrimos 9 == False

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

esProductoDeDosPrimos :: Int -> Bool

esProductoDeDosPrimos n =

[x | x <- primosN,

mod n x == 0,

div n x /= x,

elem (div n x) primosN] /= []

where primosN = takeWhile (<=n) primos

primos :: [Int]

primos = criba [2..]

where criba [] = []

criba (n:ns) = n : criba (elimina n ns)

elimina n xs = [x | x <- xs, x `mod` n /= 0]

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

-- Ejercicio 4. [2 puntos] La expresiones aritméticas se pueden

-- representar mediante el siguiente tipo

-- data Expr = V Char

-- | N Int

-- | S Expr Expr

-- | P Expr Expr

-- deriving Show

-- por ejemplo, representa la expresión "z*(3+x)" se representa por

-- (P (V 'z') (S (N 3) (V 'x'))).

-- Definir la función

-- sustitucion :: Expr -> [(Char, Int)] -> Expr

-- tal que (sustitucion e s) es la expresión obtenida sustituyendo las

-- variables de la expresión e según se indica en la sustitución s. Por

-- ejemplo,

-- ghci> sustitucion (P (V 'z') (S (N 3) (V 'x'))) [('x',7),('z',9)]

-- P (N 9) (S (N 3) (N 7))

-- ghci> sustitucion (P (V 'z') (S (N 3) (V 'y'))) [('x',7),('z',9)]

-- P (N 9) (S (N 3) (V 'y'))

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

data Expr = V Char

| N Int

| S Expr Expr

| P Expr Expr

deriving Show

sustitucion :: Expr -> [(Char, Int)] -> Expr

sustitucion e [] = e

sustitucion (V c) ((d,n):ps) | c == d = N n

| otherwise = sustitucion (V c) ps

sustitucion (N n) _ = N n

sustitucion (S e1 e2) ps = S (sustitucion e1 ps) (sustitucion e2 ps)

sustitucion (P e1 e2) ps = P (sustitucion e1 ps) (sustitucion e2 ps)

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

-- Ejercicio 5. [2 puntos] (Problema 345 del proyecto Euler) Las

-- matrices puede representarse mediante tablas cuyos índices son pares

-- de números naturales:

-- type Matriz = Array (Int,Int) Int

-- Definir la función

-- maximaSuma :: Matriz -> Int

-- tal que (maximaSuma p) es el máximo de las sumas de las listas de

-- elementos de la matriz p tales que cada elemento pertenece sólo a una

-- fila y a una columna. Por ejemplo,

-- ghci> maximaSuma (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])

-- 17

-- ya que las selecciones, y sus sumas, de la matriz

-- |1 2 3|

-- |8 4 9|

-- |5 6 7|

-- son

-- [1,4,7] --> 12

-- [1,9,6] --> 16

-- [2,8,7] --> 17

-- [2,9,5] --> 16

-- [3,8,6] --> 17

-- [3,4,5] --> 12

-- Hay dos selecciones con máxima suma: [2,8,7] y [3,8,6].

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

type Matriz = Array (Int,Int) Int

maximaSuma :: Matriz -> Int

maximaSuma p = maximum [sum xs | xs <- selecciones p]

-- (selecciones p) es la lista de las selecciones en las que cada

-- elemento pertenece a un única fila y a una única columna de la matriz

-- p. Por ejemplo,

-- ghci> selecciones (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])

-- [[1,4,7],[2,8,7],[3,4,5],[2,9,5],[3,8,6],[1,9,6]]

selecciones :: Matriz -> [[Int]]

selecciones p =

[[p!(i,j) | (i,j) <- ijs] |

ijs <- [zip [1..n] xs | xs <- permutations [1..n]]]

where (_,(m,n)) = bounds p

-- Nota: En la anterior definición se ha usado la función pernutations

-- de Data.List. También se puede definir mediante

permutaciones :: [a] -> [[a]]

permutaciones [] = [[]]

permutaciones (x:xs) =

concat [intercala x ys | ys <- permutaciones xs]

-- (intercala x ys) es la lista de las listas obtenidas intercalando x

-- entre los elementos de ys. Por ejemplo,

-- intercala 1 [2,3] == [[1,2,3],[2,1,3],[2,3,1]]

intercala :: a -> [a] -> [[a]]

intercala x [] = [[x]]

intercala x (y:ys) = (x:y:ys) : [y:zs | zs <- intercala x ys]

-- 2ª solución (mediante submatrices):

maximaSuma2 :: Matriz -> Int

maximaSuma2 p

| (m,n) == (1,1) = p!(1,1)

| otherwise = maximum [p!(1,j) + maximaSuma2 (submatriz 1 j p) | j <- [1..n]]

where (m,n) = dimension p

-- (dimension p) es la dimensión de la matriz p.

dimension :: Matriz -> (Int,Int)

dimension = snd . bounds

-- (submatriz i j p) es la matriz obtenida a partir de la p eliminando

-- la fila i y la columna j. Por ejemplo,

-- ghci> submatriz 2 3 (listArray ((1,1),(3,3)) [1,2,3,8,4,9,5,6,7])

-- array ((1,1),(2,2)) [((1,1),1),((1,2),2),((2,1),5),((2,2),6)]

submatriz :: Int -> Int -> Matriz -> Matriz

submatriz i j p =

array ((1,1), (m-1,n -1))

[((k,l), p ! f k l) | k <- [1..m-1], l <- [1.. n-1]]

where (m,n) = dimension p

f k l | k < i && l < j = (k,l)

| k >= i && l < j = (k+1,l)

| k < i && l >= j = (k,l+1)

| otherwise = (k+1,l+1)

Se puede imprimir o compartir con