当前位置：首页 → 问答吧 → How to solve this problem using FP?

How to solve this problem using FP?

时间：2013-09-24

来源：互联网

I employed C++ to solve the following problem using imperative paradigm:
http://www.spoj.com/problems/ULM02/
I have no ideas how to solve it using functional paradigm.

Can anyone give me some advice? Thanks.

[ 本帖最后由 fitcat07 於 2013-8-30 11:20 AM 编辑 ]

作者: fitcat07 发布时间: 2013-09-24

If you write it in Haskell, your function should be something like:

Int -> [String]

i.e. It turn a number into a list of string representing the output. Use recursion to construct larger output from smaller one. You most likely need some auxiliary functions to pad spaces on the left and right.

作者: code4food 发布时间: 2013-09-24

My C++ solution did it reversely:
First draw the biggest one and then recursively draw the smaller ones.

This is why I was stuck when thinking in FP.

How to draw it reversely? I need some time to think about it.
Thanks for the reply.

作者: fitcat07 发布时间: 2013-09-25

正确但慢，应该会TLE。慢嘅原因系用string同list concatenation。

复制内容到剪贴板代码:import Control.Monad

sierpinski :: Int -> [String]
sierpinski n
| n == 1 = [" /\\",
"/__\\"]
| n > 1 = let sub = sierpinski $ n - 1
h = 2 ^ (n-1)
top_pad = replicate h ' '
top = map (top_pad ++) sub
bot_pad = map (\l -> replicate l ' ') [h-1,h-2..0]
bot = zipWith (\x y -> x ++ y ++ x) sub bot_pad
in top ++ bot
| otherwise = error "n must be positive"

main :: IO ()
main = do n <- liftM read getLine
if n /= 0
then do forM_ (sierpinski n) putStrLn
main
else return ()

I probably can speed this up a little to use a tree of string instead of string list.

[ 本帖最后由 code4food 於 2013-8-31 10:26 PM 编辑 ]

作者: code4food 发布时间: 2013-09-25

Cool. I can't think of such an elegant solution.

Glad for learning something new.

Thanks for sharing.

作者: fitcat07 发布时间: 2013-09-25

Your solution got AC!
Haskell is amazing.

作者: fitcat07 发布时间: 2013-09-25

引用:原帖由 fitcat07 於 2013-8-31 09:12 PM 发表
Your solution got AC!
Haskell is amazing.

o下，啖都得？

不过我用部MacBookPro试，做1-10加埋都系0.7秒。可能系lazy evaluation嘅关系。

作者: code4food 发布时间: 2013-09-25

For fun, you can also solve this problem using another approach. You can compute the character at row i, column j of a Sierpinski fractal with recursion depth n.

复制内容到剪贴板代码:sierpinski :: Int -> Int -> Int -> Char
sierpinski n i j = .....

[ 本帖最后由 code4food 於 2013-8-31 09:35 PM 编辑 ]

作者: code4food 发布时间: 2013-09-25

引用:原帖由 code4food 於 2013-9-1 01:25 PM 发表
o下，啖都得？

不过我用部MacBookPro试，做1-10加埋都系0.7秒。可能系lazy evaluation嘅关系。

SPOJ 嘅 AC solutions 唔少用 Haskell 嘅时间都超快，Lazy evaluation 真系正！
不过，暂时 tail recursion removal 好似唔系 Haskell 嘅 compiler's requirement...

作者: fitcat07 发布时间: 2013-09-25

引用:原帖由 code4food 於 2013-9-1 01:34 PM 发表
For fun, you can also solve this problem using another approach. You can compute the character at row i, column j of a Sierpinski fractal with recursion depth n.

sierpinski :: Int -> Int -> Int -> ...

My C++ solution works in this way. So, I initially considered the FP solution in this way but I was stuck...

作者: fitcat07 发布时间: 2013-09-25

引用:原帖由 fitcat07 於 2013-8-31 10:29 PM 发表
My C++ solution works in this way. So, I initially considered the FP solution in this way but I was stuck...

You can do this in a purely functional manner until the I/O.

作者: code4food 发布时间: 2013-09-25

I found that my solution could be shortened a bit still. 1) map is sufficient for padding the top half, since the padding is constant. There is no need for repeat and zipWith 2). using n can be read in one expression using n <- liftM read getLine.

作者: code4food 发布时间: 2013-09-25

Good post. By the way anyone tried Scala?

作者: ricyik 发布时间: 2013-09-25

How to solve this problem using FP?

热门阅读

热门下载