일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- 항진명제
- 모순명제
- Sentiment Analysis
- Gate
- Circuit
- GPT-1
- statement equivalence
- 진리표
- Contradiction
- Tautology
- 십진법
- dnf
- CNF
- 명제 동치
- 이진법 십진법 변환
- ermodel
- 모두의네트워크요약
- 모두의네트워크
- truth table
- 모두의네트워크정리
- 명제
- cnn
- relationaldatabaseschema
- Binary notation
- full adder
- Decimal notation
- Digital Logic Circuits
- Logical statement
- half adder
- 써킷
- Today
- Total
NLP Learner in Switzerland
[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;
}
출력결과
'Algorithm in C > Exercise' 카테고리의 다른 글
[C] Asymptotic tight bound ::: 점근적 하한 계산하기 (0) | 2021.04.05 |
---|---|
[C] Running time and Asymptotic complexity ::: 시간복잡도(정확한 수행시간 및 점근적 표기) (0) | 2021.04.04 |
[C] Iteration and Recursion ::: 문자열에서 첫번째 대문자 찾아 인덱스를 반환하기 (0) | 2021.04.02 |
[C] Multiple Recursion ::: 재귀호출이 2번 이상 일어나는 경우 (0) | 2021.04.01 |
[C] Basic Recursion ::: 재귀함수로 거듭제곱 나타내기 (0) | 2021.03.31 |