Menu Close

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

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

    triangulares

  • 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

    poligonales_centrados

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

Fuente

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

PeH