1
12 4
11 24 9
10 22 36 16
9 20 33 48 25
8 18 30 44 60 36
7 16 27 40 55 72 49
6 14 24 36 50 66 84 64
5 12 21 32 45 60 77 96 81
4 10 18 28 40 54 70 88 108 100
3 8 15 24 35 48 63 80 99 120 121
2 6 12 20 30 42 56 72 90 110 132 144
- Input: n
- Output:
combination(n+1, 2)numbers in an (equilateral) triangle
For example, when n = 12, generate combination(13, 2)
= 13!/(2!11!) = 78 numbers.
n = 1, combination(2,2) = 1.
1
n = 2, combination(3,2) = 3.
1
2 4
n = 3, combination(4,2) = 6.
1
3 4
2 6 9
n = 4, combination(5,2) = 10.
1
4 4
3 8 9
2 6 12 16
See the pattern?
1^2
4 2^2
3 4*2 3^2
2 3*2 4*3 4^2
Rotating the triangle counter clockwise might reveal something:
1^2 2^2 3^3 4^2
4*1 4*2 4*3
3*1 3*2
2*1
In general, for input n,
1^2 2^2 ..................................... n^2
n*1 n*2 ....................... n*(n-1)
(n-1)*1 (n-1)*2 ... (n-1)*(n-1-1)
.....................
2
Let's implement it in Haskell, an obscure language.
module Main where
First, declare a module.
import qualified System.IO as Sys
import qualified IO
Then, import stuff needed.
main :: IO ()
main = do
IO.hSetBuffering IO.stdout IO.NoBuffering
Sys.putStr "Enter n (>=1): "
num <- Sys.getLine
let n :: Integer
n = read num
print' $ consul n (*)
main function definition. It disables stdout buffering
so that the prompt is displayed immediately without waiting for the
buffer to be flushed (probably flushed when new line is printed).
Then it reads an integer from user and prints the triangle.
consul :: (Integral a) => a -> (a -> a -> a) -> [[a]]
consul n func = (map reverse . diagonals) $ consul' n func
consul just calls consul' then applies
diagonals to the output. Then, it applies
reverse on each element of the output.
consul' :: Integral a => a -> (a -> a -> a) -> [[a]]
consul' n func = [map (^2) [1..n]]
++ [zipWith func (repeat x) [1..x-1] | x <- [n,n-1..2]]
consul' constructs the upside down triangle described
above. The triangle is expressed as a list of list of integers.
[[1^2, 2^2, ....................................., n^2]
, [n*1, n*2, ......................., n*(n-1)]
, [(n-1)*1, (n-1)*2, ..., (n-1)*(n-1-1)]
, .....................
, [2]]
diagonals :: [[a]] -> [[a]]
diagonals [[]] = [[]]
diagonals ([]:ls) = diagonals ls
diagonals ((x:xs):ls) = [x] : zipWith (:) xs (diagonals ls)
diagonals takes elements along the diagonal (NE to
SW). Essentially, it rotates the upside triangle clockwise and
flips. Since the output triangle is flipped, reverse
should be applied for each element list to re-flip the triangle.
print' :: (Show a) => [[a]] -> IO ()
print' [] = return ()
print' (l:ls) = do
putStrLn $ replicate (length ls) ' ' ++ show l
print' ls
print' prints the list of list of integers as a
triangle by appending spaces in front of each row.
