You are viewing a single comment's thread. Return to all comments →
In haskell -- perimeter of a pentagon with side n is -- 5*(n-1) except for n = 1 -- and nodes of case n is calculated as -- P(n) = perimeter(n) - (2n-3) + P(n-1) -- with P(1) = 1. perimeter(n) - (2n-3) is the perimeter -- of the big pentagon minus the inner pentagons. -- which are given by P(n-1) recursively -- more compactly (perimeter(n) = 5*(n-1)) -- P(n) = 3n -2 + P(n-1) and P(1) = 1 -- So here we can either -- 1) do recursion which is time inefficient -- 2) make P(n) using DP which is space efficient -- 3) Cheating: make a closed form equation for P(1) -- by doing algebra. Or cheat even more by goind -- on wolfram alpha typing P(n) = 3n -2 + P(n-1) -- and taking the solution which is -- P(n) = 1/2 * n * (3n-1) -- and the problem is solved in O(1) import Control.Monad comb n = (n * (3*n - 1)) `div` 2 main = do test_cases <- readLn :: IO Int forM_ [1..test_cases] $ \n_itr -> do num <- readLn :: IO Int putStrLn $ show $ comb num
Seems like cookies are disabled on this browser, please enable them to open this website
Pentagonal Numbers
You are viewing a single comment's thread. Return to all comments →