[C] Pascal Triangle ::: 파스칼 삼각형 출력하기

 

---

까다로운 부분 알아보기

---

[1] Pascal triangle 파스칼 삼각형은 i행j열의 원소가 i-1행j-1열 + i-1행j열로 이루어져 있다고 되어있다.

▶ 예시를 생각해보면 (3,2) = (2,1)+(2,2) 즉, 3=2+1가 되는 것이다.

▶ 다음항이 계속해서 (i-1,j-1)+(i-1,j)로 출력되므로 그대로 Recursive 구현하면 된다.

[2] 삼각형을 살펴보면 0행일때, 0열일때, 그리고 행=열이 같을 때 전부 1을 출력한다는 것을 알 수 있다.

▶ 따라서 이 내용을 Recursion의 Stop condition으로 준다.

 

[3] 첫번째 보기처럼 직각삼각형으로 출력을 하려면 

▶ Pascal함수의 return 값 = 해당 (행,열)의 값을 차례로 읽어오면 되는데, 여기서 row가 끝나면 다음 row로 넘겨줘야 한다. 아니면 일자로 주루룩 나열되버리니까. 따라서 inner loop(열)이 한번 끝날 때마다 \n을 넣어서 줄바꿈을 해준다.

 

[4] 두번째 보기의 삼각형 형태로 출력을 하는게 까다롭다...

 

[5] 각 row마다 앞단 공백의 갯수를 세는 Recursion 함수를 만들어보라고 되어있다.

▶ 따라서 일단은 앞에 공백이 몇개가 있는지를 세본다. 각 row마다 공백이 아래에서부터 0->2->4->6->...으로 2씩 증가함을 알 수 있다.

[5-1] Recursion이니까 동일하게 if statement - stop condition을 떠올린다. 어떻게?

▶ 행을 계속 반복적으로 다음 행으로 옮겨주면서, 그 행이 최종적으로 전체 출력하고자 하는 행과 일치하는 경우 Stop한다. 이 내용을 if에 넣는다.

[5-2] 매 Recursion마다 2를 더해주면 되고, Stop condition에 도달하려면 행을 계속 1씩 증가시키면 된다.

▶ 위의 보기처럼 전체 6행을 출력하고 싶고, 3번째 행(1 2 1 행)의 앞 공백갯수를 알고싶다면, recursive로 (3,6) = 2+(4,6) = 2+2+(5,6) = 2+2+2+(6,6) = 6개(6,6은 stop condition으로 return이 0임)가 된다.

 

[6] 이제 매 row마다 앞 공백의 갯수를 알았으니까, 삼각형을 출력해준다.

[6-1] row시작시마다, 셌던 공백을 넣어주기 위해 공백세는 함수를 호출한다.

▶ 그런데 printf의 형태에 주의해보자. printf("%*c",recursive_find_indent(i,n), ' '); 이 구문의 의미는, printf(출력한다,몇개?,이거를)이다. 왜냐하면 %*c에서 *(asterisk symbol)가 동적으로 넣은 갯수만큼 해당하는 내용을 출력해주는 출력폭을 뜻하기 때문이다. c인 이유는 공백이 문자 1개이기 때문이다. 따라서 이 부분은 인간 언어로 바꾸면 "함수에서 반환된 공백 갯수만큼 ' '(공백)을 출력한다"는 뜻이 된다.

[6-2] 제일 까다로운 부분은 끝났기 때문에 이제 별거 없다.

▶ 직각삼각형에서는 숫자 사이마다 한칸씩 띄워 출력했지만 이번에는 3칸씩 띄워져있는걸 볼 수 있다. 그래서 "%d   "처럼 스페이스를 3번 쳐서 3칸씩 띄워 출력해준다.

 

#include <stdio.h>

int pascal(int i,int j){
    if(j==0||i==0||i==1){ ------------------ [2]
        return 1;
    }
    if(i==j){ ------------------------------ [2]
        return 1;
    }
    return pascal(i-1,j-1)+pascal(i-1,j); -- [1]
}

void printPascal(int n){
    int i,j;
    for(i=0;i<n;i++){
        printf("row %d: ",i);
        for(j=0;j<=i;j++){
            printf("%d ",pascal(i,j)); ----- [3]
        }
        printf("\n");
    }
}

int recursive_find_indent(int current_row, int total_rows){
    if(current_row==total_rows){ -------------------------------- [5-1]
        return 0;
    }
    return 2+recursive_find_indent(current_row+1, total_rows); -- [5-2]
}

void format_print_pascal(int n){
    int i,j;
    for(i=0;i<n;i++){
        printf("%*c",recursive_find_indent(i,n), ' '); ---------- [6-1]
        for(j=0;j<=i;j++){
            printf("%d   ",pascal(i,j)); ------------------------ [6-2]
        }
        printf("\n");
    }
}

int main(){
    int n;
    printf("How many rows you want to print? \n");
    scanf("%d",&n);
    printPascal(n);
    format_print_pascal(n);
    return 0;
}

 

---

출력결과

---