El triángulo de Floyd en Haskell

El triángulo de Floyd, llamado así en honor a Robert Floyd, es un triángulo rectángulo formado con números naturales. Para crear un triángulo de Floyd, se comienza con un 1 en la esquina superior izquierda, y se continúa escribiendo la secuencia de los números naturales de manera que cada línea contenga un número más que la anterior. Las 5 primeras líneas del triángulo de Floyd son

 1
 2   3
 4   5   6
 7   8   9  10
11  12  13  14  15

2 3

4 5 6

7 8 9 10

11 12 13 14 15

El triángulo de Floyd tiene varias propiedades matemáticas interesantes:

los números de la hipotenusa es la sucesión de los números triangulares; es decir, los números que puede ser representado como puntos dispuestos en forma de triángulo, empezando por el 1. Los primeros números triangulares son
los números del cateto de la parte izquierda es la sucesión de los números poligonales centrales; donde el n-ésimo número poligonal centrado es el máximo número de piezas que se pueden obtener a partir de un círculo con n líneas rectas. Los primeros números poligonales centrados son

En la siguiente relación de ejercicios (elaborada para I1M) se define en Haskell el triágulo de Floyd y se comprueban algunas de sus propiedades.

-- ---------------------------------------------------------------------
-- § Librerías auxiliares                                             --
-- ---------------------------------------------------------------------

import Test.QuickCheck
import Data.List

-- ---------------------------------------------------------------------
-- § Triágulo de Floyd                                                --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 1. Definir la función
--    siguiente :: [Integer] -> [Integer]
-- tal que (siguiente xs) es la lista de los elementos de la línea xs en
-- el triángulo de Lloyd. Por ejemplo,
--    siguiente [2,3]    ==  [4,5,6]
--    siguiente [4,5,6]  ==  [7,8,9,10]
-- ---------------------------------------------------------------------

siguiente :: [Integer] -> [Integer]
siguiente xs = [a..a+n]
    where a = 1+last xs
          n = genericLength xs

-- ---------------------------------------------------------------------
-- Ejercicio 2. Definir la función        
--    trianguloFloyd :: [[Integer]]
-- tal que trianguloFloyd es el triángulo de Floyd. Por ejemplo,
--    ghci> take 4 trianguloFloyd
--    [[1],
--     [2,3],
--     [4,5,6],
--     [7,8,9,10]]
-- ---------------------------------------------------------------------

trianguloFloyd :: [[Integer]]
trianguloFloyd = iterate siguiente [1]

-- ---------------------------------------------------------------------
-- § Filas del triángulo de Floyd                                     --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 3. Definir la función
--    filaTrianguloFloyd :: Integer -> [Integer]
-- tal que (filaTrianguloFloyd n) es la fila n-ésima del triángulo de
-- Floyd. Por ejemplo,  
--    filaTrianguloFloyd 3  ==  [4,5,6]
--    filaTrianguloFloyd 4  ==  [7,8,9,10]
-- ---------------------------------------------------------------------

filaTrianguloFloyd :: Integer -> [Integer]
filaTrianguloFloyd n = trianguloFloyd `genericIndex` (n-1)

-- ---------------------------------------------------------------------
-- Ejercicio 4. Definir la función
--    sumaFilaTrianguloFloyd :: Integer -> Integer
-- tal que (sumaFilaTrianguloFloyd n) es la suma de los fila n-ésima del
-- triángulo de Floyd. Por ejemplo,
--    sumaFilaTrianguloFloyd 1  ==  1
--    sumaFilaTrianguloFloyd 2  ==  5
--    sumaFilaTrianguloFloyd 3  ==  15
--    sumaFilaTrianguloFloyd 4  ==  34
--    sumaFilaTrianguloFloyd 5  ==  65
-- ---------------------------------------------------------------------

sumaFilaTrianguloFloyd :: Integer -> Integer
sumaFilaTrianguloFloyd = sum . filaTrianguloFloyd

-- ---------------------------------------------------------------------
-- Ejercicio 5. A partir de los valores de (sumaFilaTrianguloFloyd n)
-- para n entre 1 y 5, conjeturar una fórmula para calcular
-- (sumaFilaTrianguloFloyd n). 
-- ---------------------------------------------------------------------

-- Usando Wolfram Alpha (como se indica en http://wolfr.am/19XAl2X )
-- a partir de 1, 5, 15, 34, 65, ... se obtiene la fórmula
--    (n^3+n)/2

-- ---------------------------------------------------------------------
-- Ejecicio 6. Comprobar con QuickCheck la conjetura obtenida en el
-- ejercicio anterior.
-- ---------------------------------------------------------------------

-- La conjetura es
prop_sumaFilaTrianguloFloyd :: Integer -> Property
prop_sumaFilaTrianguloFloyd n =        
    n > 0 ==> sum (filaTrianguloFloyd n) == (n^3+n) `div` 2
  
-- La comprobación es
--    ghci> quickCheck prop_sumaFilaTrianguloFloyd
--    +++ OK, passed 100 tests.

-- ---------------------------------------------------------------------
-- § Hipotenusa del triángulo de Floyd y números triangulares         --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 7. Definir la función
--    hipotenusaFloyd :: [Integer]
-- tal que hipotenusaFloyd es la lista de los elementos de la hipotenusa
-- del triángulo de Floyd. Por ejemplo, 
--    take 5 hipotenusaFloyd  ==  [1,3,6,10,15]
-- ---------------------------------------------------------------------

hipotenusaFloyd :: [Integer]
hipotenusaFloyd = map last trianguloFloyd

-- ---------------------------------------------------------------------
-- Ejercicio 8. Lo números triangulares se forman como sigue
--    *     *      * 
--         * *    * *
--               * * *
--    1     3      6
-- 
-- La sucesión de los números triangulares se obtiene sumando los
-- números naturales. Así, los 5 primeros números triangulares son
--     1 = 1
--     3 = 1+2
--     6 = 1+2+3
--    10 = 1+2+3+4
--    15 = 1+2+3+4+5
-- 
-- Definir la función
--    triangulares :: [Integer]
-- tal que triangulares es la lista de los números triangulares. Por
-- ejemplo, 
--    take 10 triangulares  ==  [1,3,6,10,15,21,28,36,45,55]
-- ---------------------------------------------------------------------

triangulares :: [Integer]
triangulares = 1 : [x+y | (x,y) <- zip [2..] triangulares]

-- 2ª definición (usando scanl):
triangulares2 :: [Integer]
triangulares2 = scanl (+) 1 [2..]

-- 3ª definición (usando la fórmula de la suma de la progresión):
triangulares3 :: [Integer]
triangulares3 = [(n*(n+1)) `div` 2 | n <- [1..]]

-- ---------------------------------------------------------------------
-- Ejercicio 9. Definir la función 
--    prop_hipotenusaFloyd :: Int -> Bool
-- tal que (prop_hipotenusaFloyd n) se verifica si los n primeros
-- elementos de la hipotenusa del triángulo de Floy son los primeros n
-- números triangulares. 
-- 
-- Comprobar la propiedad para los 1000 primeros elementos.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_hipotenusaFloyd :: Int -> Bool
prop_hipotenusaFloyd n = 
    take n hipotenusaFloyd == take n triangulares

-- La comprobación es
--    ghci> prop_hipotenusaFloyd 1000
--    True

-- ---------------------------------------------------------------------
-- § Cateto del triángulo de Floyd y números poligonales centrales    --
-- ---------------------------------------------------------------------

-- ---------------------------------------------------------------------
-- Ejercicio 10. Definir la función
--    catetoFloyd :: [Integer]
-- tal que catetoFloyd es la lista de los elementos del cateto izquierdo
-- del triángulo de Floyd. Por ejemplo, 
--    take 5 catetoFloyd  ==  [1,2,4,7,11]
-- ---------------------------------------------------------------------

catetoFloyd :: [Integer]
catetoFloyd = map head trianguloFloyd

-- ---------------------------------------------------------------------
-- Ejercicio 11. El n-ésimo número poligonal centrado es el máximo
-- número de piezas que se pueden obtener a partir de un círculo con n
-- líneas rectas. Por ejemplo,
--    Triangulo_de_Floyd_poligonales.jpg
--
-- Definir la función
--    poligonalCentrado :: Integer -> Integer
-- tal que (poligonalCentrado n) es el n-ésimo número poligonal
-- centrado. Por ejemplo, 
--    [poligonalCentrado n | n <- [0..5]]  ==  [1,2,4,7,11,16]
-- ---------------------------------------------------------------------

poligonalCentrado :: Integer -> Integer
poligonalCentrado 0 = 1
poligonalCentrado n = n + poligonalCentrado (n-1)

-- ---------------------------------------------------------------------
-- Ejercicio 12. Definir la función
--    poligonalesCentrados :: [Integer]
-- tal que poligonalesCentrados es la lista de los números poligonales
-- centrados. Por ejemplo, 
--    take 10 poligonalesCentrados  ==  [1,3,6,10,15,21,28,36,45,55]
-- ---------------------------------------------------------------------

-- 1ª definición:
poligonalesCentrados1 :: [Integer]
poligonalesCentrados1 = [poligonalCentrado n | n <- [0..]]

-- 2ª definición (usando scanl):
poligonalesCentrados :: [Integer]
poligonalesCentrados = scanl (+) 1 [1..]

-- ---------------------------------------------------------------------
-- Ejercicio 13. Definir la función 
--    prop_catetoFloyd :: Int -> Bool
-- tal que (prop_catetoFloyd n) se verifica si los n primeros
-- elementos del cateto izquierdo del triángulo de Floy son los primeros
-- n números poligonales centrados.
-- 
-- Comprobar la propiedad para los 1000 primeros elementos.
-- ---------------------------------------------------------------------

-- La propiedad es
prop_catetoFloyd :: Int -> Bool
prop_catetoFloyd n = 
    take n catetoFloyd == take n poligonalesCentrados

-- La comprobación es
--    ghci> prop_catetoFloyd 1000
--    True

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

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

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

-- § Librerías auxiliares --

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

import Test.QuickCheck

import Data.List

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

-- § Triágulo de Floyd --

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

-- Ejercicio 1. Definir la función

-- siguiente :: [Integer] -> [Integer]

-- tal que (siguiente xs) es la lista de los elementos de la línea xs en

-- el triángulo de Lloyd. Por ejemplo,

-- siguiente [2,3] == [4,5,6]

-- siguiente [4,5,6] == [7,8,9,10]

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

siguiente :: [Integer] -> [Integer]

siguiente xs = [a..a+n]

where a = 1+last xs

n = genericLength xs

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

-- Ejercicio 2. Definir la función

-- trianguloFloyd :: [[Integer]]

-- tal que trianguloFloyd es el triángulo de Floyd. Por ejemplo,

-- ghci> take 4 trianguloFloyd

-- [[1],

-- [2,3],

-- [4,5,6],

-- [7,8,9,10]]

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

trianguloFloyd :: [[Integer]]

trianguloFloyd = iterate siguiente [1]

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

-- § Filas del triángulo de Floyd --

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

-- Ejercicio 3. Definir la función

-- filaTrianguloFloyd :: Integer -> [Integer]

-- tal que (filaTrianguloFloyd n) es la fila n-ésima del triángulo de

-- Floyd. Por ejemplo,

-- filaTrianguloFloyd 3 == [4,5,6]

-- filaTrianguloFloyd 4 == [7,8,9,10]

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

filaTrianguloFloyd :: Integer -> [Integer]

filaTrianguloFloyd n = trianguloFloyd `genericIndex` (n-1)

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

-- Ejercicio 4. Definir la función

-- sumaFilaTrianguloFloyd :: Integer -> Integer

-- tal que (sumaFilaTrianguloFloyd n) es la suma de los fila n-ésima del

-- triángulo de Floyd. Por ejemplo,

-- sumaFilaTrianguloFloyd 1 == 1

-- sumaFilaTrianguloFloyd 2 == 5

-- sumaFilaTrianguloFloyd 3 == 15

-- sumaFilaTrianguloFloyd 4 == 34

-- sumaFilaTrianguloFloyd 5 == 65

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

sumaFilaTrianguloFloyd :: Integer -> Integer

sumaFilaTrianguloFloyd = sum . filaTrianguloFloyd

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

-- Ejercicio 5. A partir de los valores de (sumaFilaTrianguloFloyd n)

-- para n entre 1 y 5, conjeturar una fórmula para calcular

-- (sumaFilaTrianguloFloyd n).

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

-- Usando Wolfram Alpha (como se indica en http://wolfr.am/19XAl2X )

-- a partir de 1, 5, 15, 34, 65, ... se obtiene la fórmula

-- (n^3+n)/2

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

-- Ejecicio 6. Comprobar con QuickCheck la conjetura obtenida en el

-- ejercicio anterior.

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

-- La conjetura es

prop_sumaFilaTrianguloFloyd :: Integer -> Property

prop_sumaFilaTrianguloFloyd n =

n > 0 ==> sum (filaTrianguloFloyd n) == (n^3+n) `div` 2

-- La comprobación es

-- ghci> quickCheck prop_sumaFilaTrianguloFloyd

-- +++ OK, passed 100 tests.

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

-- § Hipotenusa del triángulo de Floyd y números triangulares --

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

-- Ejercicio 7. Definir la función

-- hipotenusaFloyd :: [Integer]

-- tal que hipotenusaFloyd es la lista de los elementos de la hipotenusa

-- del triángulo de Floyd. Por ejemplo,

-- take 5 hipotenusaFloyd == [1,3,6,10,15]

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

hipotenusaFloyd :: [Integer]

hipotenusaFloyd = map last trianguloFloyd

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

-- Ejercicio 8. Lo números triangulares se forman como sigue

-- * * *

-- * * * *

-- * * *

-- 1 3 6

-- La sucesión de los números triangulares se obtiene sumando los

-- números naturales. Así, los 5 primeros números triangulares son

-- 1 = 1

-- 3 = 1+2

-- 6 = 1+2+3

-- 10 = 1+2+3+4

-- 15 = 1+2+3+4+5

-- Definir la función

-- triangulares :: [Integer]

-- tal que triangulares es la lista de los números triangulares. Por

-- ejemplo,

-- take 10 triangulares == [1,3,6,10,15,21,28,36,45,55]

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

triangulares :: [Integer]

triangulares = 1 : [x+y | (x,y) <- zip [2..] triangulares]

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

triangulares2 :: [Integer]

triangulares2 = scanl (+) 1 [2..]

-- 3ª definición (usando la fórmula de la suma de la progresión):

triangulares3 :: [Integer]

triangulares3 = [(n*(n+1)) `div` 2 | n <- [1..]]

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

-- Ejercicio 9. Definir la función

-- prop_hipotenusaFloyd :: Int -> Bool

-- tal que (prop_hipotenusaFloyd n) se verifica si los n primeros

-- elementos de la hipotenusa del triángulo de Floy son los primeros n

-- números triangulares.

-- Comprobar la propiedad para los 1000 primeros elementos.

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

-- La propiedad es

prop_hipotenusaFloyd :: Int -> Bool

prop_hipotenusaFloyd n =

take n hipotenusaFloyd == take n triangulares

-- La comprobación es

-- ghci> prop_hipotenusaFloyd 1000

-- True

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

-- § Cateto del triángulo de Floyd y números poligonales centrales --

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

-- Ejercicio 10. Definir la función

-- catetoFloyd :: [Integer]

-- tal que catetoFloyd es la lista de los elementos del cateto izquierdo

-- del triángulo de Floyd. Por ejemplo,

-- take 5 catetoFloyd == [1,2,4,7,11]

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

catetoFloyd :: [Integer]

catetoFloyd = map head trianguloFloyd

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

-- Ejercicio 11. El n-ésimo número poligonal centrado es el máximo

-- número de piezas que se pueden obtener a partir de un círculo con n

-- líneas rectas. Por ejemplo,

-- Triangulo_de_Floyd_poligonales.jpg

-- Definir la función

-- poligonalCentrado :: Integer -> Integer

-- tal que (poligonalCentrado n) es el n-ésimo número poligonal

-- centrado. Por ejemplo,

-- [poligonalCentrado n | n <- [0..5]] == [1,2,4,7,11,16]

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

poligonalCentrado :: Integer -> Integer

poligonalCentrado 0 = 1

poligonalCentrado n = n + poligonalCentrado (n-1)

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

-- Ejercicio 12. Definir la función

-- poligonalesCentrados :: [Integer]

-- tal que poligonalesCentrados es la lista de los números poligonales

-- centrados. Por ejemplo,

-- take 10 poligonalesCentrados == [1,3,6,10,15,21,28,36,45,55]

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

-- 1ª definición:

poligonalesCentrados1 :: [Integer]

poligonalesCentrados1 = [poligonalCentrado n | n <- [0..]]

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

poligonalesCentrados :: [Integer]

poligonalesCentrados = scanl (+) 1 [1..]

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

-- Ejercicio 13. Definir la función

-- prop_catetoFloyd :: Int -> Bool

-- tal que (prop_catetoFloyd n) se verifica si los n primeros

-- elementos del cateto izquierdo del triángulo de Floy son los primeros

-- n números poligonales centrados.

-- Comprobar la propiedad para los 1000 primeros elementos.

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

-- La propiedad es

prop_catetoFloyd :: Int -> Bool

prop_catetoFloyd n =

take n catetoFloyd == take n poligonalesCentrados

-- La comprobación es

-- ghci> prop_catetoFloyd 1000

-- True

Fuente

Destino:La anterior relación de ejercicios la ha elaborado para

la asignatura de Informática de 1º del Grado en Matemáticas y
la ampliación del libro Piensa en Haskell.

Se puede imprimir o compartir con