일상 혹은 이상

파스칼의 세모꼴 수를 만드는 프로시저 작성하기 (되도는 프로세스)


일단 파스칼의 세모꼴 수를 함수를 다음과 같이 정의해보았다.

1          => f(1, 1)
1 1        => f(2, 1) f(2, 2)
1 2 1      => f(3, 1) f(3, 2) f(3, 3)
1 3 3 1    => f(4, 1) f(4, 2) f(4, 3) f(4, 4)
1 4 6 4 1  => f(5, 1) f(5, 2) f(5, 3) f(5, 4) f(5, 5)


1 ≤ x, y ≤ n 이라 할 때,

f(x, y) = 1                                 if y = 1 or y = n
f(x, y) = f(x - 1, y) + f(x - 1, y - 1)     otherwise

와 같이 정의해 볼 수 있다. (수학적으로 맞는 표기(notation)인지는 논외로 치고..)

위의 정의를 구현한 scheme 코드는 다음과 같다.

(define (f x y n)
  (if (or (= y 1) (= y n))
      1
      (+ (f (- x 1) y (- n 1))
         (f (- x 1) (- y 1) (- n 1)))))

Scheme에서 모아서 반환하는 방법을 몰라서 그냥 하나씩 리턴 값을 구했다.

입력

(f 1 1 1)
(f 2 1 2)
(f 2 2 2)
(f 3 1 3)
(f 3 2 3)
(f 3 3 3)
(f 4 1 4)
(f 4 2 4)
(f 4 3 4)
(f 4 4 4)

결과

Welcome to DrScheme, version 371 [3m].
Language: Graphical (MrEd, includes MzScheme).
1
1
1
1
2
1
1
3
3
1
>

Scheme 문법을 찾아보긴 귀찮고 해서, Erlang 버전으로 다시 구현해 보았다. (출력할 때 삼각형의 대칭은 맞추지 않았다. 그리고 콘솔창 너비 보다 출력되는 라인이 길면 자동으로 개행되는듯 하다. 별로 개선의 의지는 없다..)

원래 elem/3으로 elem( X, Y, N)의 형식이었는데 X와 N이 항상 같은 값이라서 elem/2로 바꿨다.

 pascal_triangle.erl

-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

간만에 erlang으로 코딩했더니 엄청 헤렸네.. -_-;