파스칼의 세모꼴..

[jahyun]

요새 SICP 문제 풀고 있는데 파스칼의 세모꼴이라는 문제가 나와서 풀어봤습니다. 간만에 작성한 erlang 코드라 올려봅니
다. (elem/2가 tail recursion이 아니라서 쫌 걸리네요..)

-module( pascal_triangle ).
-export( [print/1, all/1] ).

-include_lib("eunit/include/eunit.hrl").

print( N ) ->
print( N, all( N ) ).

print( _, [] ) ->
ok;
print( N, [ H | T ] ) ->
FmtStr = "~" ++ integer_to_list(N) ++ "c~p~n",
io:format( FmtStr, [ $ , H ] ),
print( N - 1, T ).

all( N ) ->
all( N, [] ).

all( 0, Acc ) -> Acc;
all( N, Acc ) ->
all( N - 1, [ set(N) | Acc ] ).

set( N ) ->
[ elem( N, Y ) || Y <- lists:seq( 1, N, 1) ].

elem( _, 1 ) ->
1;
elem( Y, Y ) ->
1;
elem( X, Y ) ->
elem( X - 1, Y) + elem(X - 1, Y - 1).

pascal_test_() ->
[
?_assertEqual( 1, elem( 1, 1 ) ),
?_assertEqual( 1, elem( 5, 5 ) ),
?_assertEqual( [1, 2, 1], set( 3 ) ),
?_assertEqual( [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]],
all( 5 ) )
].


25> pascal_triangle:test().
All 4 tests successful.
ok
26> pascal_triangle:all( 6 ).
[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1]]
27> pascal_triangle:print( 6 ).
[1]
[1,1]
[1,2,1]
[1,3,3,1]
[1,4,6,4,1]
[1,5,10,10,5,1]
ok



(뜬금 없이) 다들 건강하시죠?

[KangSan Lee]

저도 한번 해봤는데, 거의 비슷한 코드가 나왔네요. 전 erlang으로 먼저 만들고, 스킴으로 옮겨야겠습니다... ;-)
근데, 숫자가 커지는 경우 중복계산이 많아질테니 memoization 같은걸 하고싶은데,
어떻게 해야할지 모르겠군요. 그냥 떠오르는 생각은 process dictionary쓰자 인데 좀 싫고...
좀 가르쳐주세요. pascal_triangle(100) 같은거 넣으면 머신이 죽으려고 합니다.


  1 -module(pascal_triangle).
  2 -export([pascal_triangle/1]).
  3
  4 for(N, N, Fun) -> [Fun(N)];
  5 for(I, N, Fun) -> [Fun(I)|for(I+1, N, Fun)].
  6
  7 pascal_triangle(N) -> for(1, N, fun pascal_row/1).
  8
  9 pascal_row(R) ->
 10     lists:map(fun pascal_rowcol/1, [ {R, X} || X <- lists:seq(1, R) ]).
 11
 12 pascal_rowcol({N, N}) -> 1;
 13 pascal_rowcol({1, _}) -> 1;
 14 pascal_rowcol({_, 1}) -> 1;
 15 pascal_rowcol({Row, Col}) -> pascal_rowcol({Row-1, Col-1}) + pascal_rowcol({Row-1, Col}).

08. 3. 4, jahyun <ico...@gmail.com>님이 작성:

--
http://www.deisys.net

[Eung-ju Park]

제가 해본 것.

-module(pascal).
-compile(export_all).

next(S) ->
    next(S, [1]).
next([_], Acc) ->
    [1|Acc];
next([A,B|L], Acc) ->
    next([B|L], [A+B|Acc]).

triangle(N) ->
    triangle(N - 1, [[1]]).
triangle(0, Acc) ->
    lists:reverse(Acc);
triangle(N, [S|L]) ->
    triangle(N - 1, [next(S),S|L]).

이 전 상태로 다음 상태를 만드는 개념으로 짰습니다. 100단 정도는 가뿐하게 되네요 ^^.

2008/3/5 KangSan Lee <fily...@gmail.com>:

--
* LukeSkywalker: Is the dark side stronger?
* MasterYoda: No...no...no. Quicker, easier, more seductive.

[Eung-ju Park]

lists:foldl을 이용해서 함수 선언에서 이름 중복 제거.

next(S) ->
    lists:foldl(fun(A,[B|L]) ->
            [A,A+B|L]
        end, [0], S).

triangle(N) ->
    lists:reverse(lists:foldl(fun(_,[S|_]=Acc) ->
                       [next(S)|Acc]
                   end, [[1]], lists:seq(1, N))).

2008/3/5 Eung-ju Park <eun...@gmail.com>:

[KangSan Lee]

와~ Eungju님 멋져요! >_<=b

08. 3. 5, Eung-ju Park <eun...@gmail.com>님이 작성:

--
http://www.deisys.net

[jahyun]

와우... 응주님 췍오!

list:foldl를 이용한 깔끔한 마무리인건가요..

100단 정도는 가뿐하게 돌려주시는 센스..~

(저도 좀 더 생각해 보고 올릴걸 그랬나봐요..ㅠ_ㅠ)

> > > 2008/3/5 KangSan Lee <filyen...@gmail.com>:

>
> > > 저도 한번 해봤는데, 거의 비슷한 코드가 나왔네요. 전 erlang으로 먼저 만들고, 스킴으로 옮겨야겠습니다... ;-)
> > > > 근데, 숫자가 커지는 경우 중복계산이 많아질테니 memoization 같은걸 하고싶은데,
> > > > 어떻게 해야할지 모르겠군요. 그냥 떠오르는 생각은 process dictionary쓰자 인데 좀 싫고...
> > > > 좀 가르쳐주세요. pascal_triangle(100) 같은거 넣으면 머신이 죽으려고 합니다.
>
> > > > 1 -module(pascal_triangle).
> > > > 2 -export([pascal_triangle/1]).
> > > > 3
> > > > 4 for(N, N, Fun) -> [Fun(N)];
> > > > 5 for(I, N, Fun) -> [Fun(I)|for(I+1, N, Fun)].
> > > > 6
> > > > 7 pascal_triangle(N) -> for(1, N, fun pascal_row/1).
> > > > 8
> > > > 9 pascal_row(R) ->
> > > > 10 lists:map(fun pascal_rowcol/1, [ {R, X} || X <- lists:seq(1,
> > > > R) ]).
> > > > 11
> > > > 12 pascal_rowcol({N, N}) -> 1;
> > > > 13 pascal_rowcol({1, _}) -> 1;
> > > > 14 pascal_rowcol({_, 1}) -> 1;
> > > > 15 pascal_rowcol({Row, Col}) -> pascal_rowcol({Row-1, Col-1}) +
> > > > pascal_rowcol({Row-1, Col}).
>

> > > > 08. 3. 4, jahyun <icom...@gmail.com>님이 작성: