Books by Example/SICP2007.11.10 16:11

파스칼의 세모꼴(Pascal's Triangle) 문제는 널리 잘 알려진 문제입니다. 하지만 안타깝게도 이 책을 읽기 전에 저는 이 문제를 함수형 언어에서는 풀어본 적이 없습니다. 파스칼의 세모꼴 모양은 흔히 알려져 있는 대로, 다음과 같습니다.

http://www.mathsisfun.com/pascals-triangle.html

출처: http://www.mathsisfun.com/pascals-triangle.html


이 문제를 저는 이렇게 풀기로 했습니다. 우선 위에서 부터 아래쪽으로, 1부터 증가하는 번호를 매깁니다. 이것을 x라고 했습니다. 그리고 왼쪽에서 오른쪽으로 역시 1부터 증가하는 번호를 매깁니다. 이것을 y라고 합니다. 그렇다면 x와 y의 값에 따라서, 모든 수는 (x, y)의 유일한 좌표 값을 가집니다. 이 x, y 사이의 관계를 알 수 있으면 어떤 좌표에 있는 값이 무엇인지 알 수 있습니다.

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


그 값을 알아내는 공식은 위와 같습니다. 이 공식을 만든 다음에, 이 공식을 사용해서 파스칼 삼각형을 화면에 출력하도록 했습니다. 안타깝게도 출력에 관한 사항을 어떻게 처리할 지는 그다지 배운 바가 없어서, 대충 출력하도록 만들었습니다. 적당히 잘 뜯어고치면, 이것보다는 더 나은 출력을 만들 수 있을 거라 믿습니다.

(define (pascal n)
  (define (pascal-iter x y)
    (cond ((and (= x n) (= y (+ n 1))) (display ""))
          ((= y (+ x 1)) (display "\n") (pascal-iter (+ x 1) 1))
          (else (display (f x y)) (display " ") (pascal-iter x (+ y 1)))))
  (pascal-iter 1 1))


이 코드를 다음과 같이 하여 실행합니다.

(pascal 5)

그러면 아래의 삼각형을 얻습니다. (5 보다 큰 수를 입력하면 출력이 영 볼썽 사납습니다 ㅋㅋ)

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1


그런데 문제를 풀고보니 화면 출력에 대한 내용까지를 풀 필요는 없고, 각 좌표의 수가 무엇인지를 알수만 있으면 되는 것 같습니다. (괜히 삽질했구나 하는 생각이 듭니다 -_-;;)

화면 출력에 관한 코드를 만들 때 곤란했던 부분은, 흔히 C++에서는 다음과 같이 표현되는 루프를 어떻게 만들 것이냐 하는 점이었습니다.

for ( int i = 1; i <= n; ++i ) {
    for ( int j = 1; j <= n; ++j ) {
        ...
    }
}


뭐 보시다시피 대충 해결했습니다. ^O^;;

신고
Posted by 이병준

소중한 의견, 감사합니다. ^^

  1. estel

    정보 감사합니다!

    2016.01.21 19:53 신고 [ ADDR : EDIT/ DEL : REPLY ]