컴퓨터자료구조
C언어로 쉽게 풀어쓴 자료구조 - 순환 연습문제 풀이
혀두 ・ 2022. 4. 18. 23:52
URL 복사 이웃추가
본문 기타 기능
신고하기
1. 팩토리얼을 계산하는 순환호출 함수 factorial에서 매개변수로 5를 주었다면 최대 몇 개의 factorial 함수의 활성 레코드가 동시에 존재할 수 있는가?
순환호출이 게속 중첩될수록 시스템 스택에서는 활성 레코드들이 쌓이게 된다. 5개
2.순환 호출을 하였을 경우에 활성 레코드들이 저장되는 위치는 어디인가?
- 복귀주소가 시스템 스택에 저장되고 호출되는 함수를 위한 매개변수와 지역변수는 스택으로부터 저장공간을 할당받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성레코드라 한다.
3. 다음 중 활성 레코드에 저장되지 않는 것은?
순환호출의 순차번호
4. 하나의 함수가 호출할 수 있는 순환호출의 개수는?
- 시스템 스택의 허용한도
5.다음의 순환호출 함수에서 잘못된 점은 무엇인가?
int recursive(int n){ if(n==1) return 0; return n * recursive(n);}
- n > 2 일 경우, 순환을 멈추는 부분이 없다.
6. 다음의 순환호출 함수에서 잘못된 점은 무엇인가?
int recursive(int n){ printf("recursive(%d)\n", n); return n * recursive(n-1);}
- 순환을 끝내는 시점이 없다.
6 ~ 10 문제: 코드
11. 다음 함수에서 asterisk(5)를 호출할 때 출력되는 *의 갯수는?
void asterisk(int i){ if (i > 1) { asterisk(i / 2); asterisk(i / 2); } printf("*");}
******* //7개
12. 다음과 같은 함수를 호출하고 "recursive" 문자열을 입력한 다음, 엔터키를 눌렀다면 화면에 출력되는 것은?
unknown(){ int ch; if ( (ch = getchar()) != '\n') unknown(); putchar(ch); (ch 포함 안되어있음, 문제오류)}
evisrucer
13. 다음을 계산하는 순환적인 프로그램을 작성하시오.
1 + 2 + 3 + ... + n
int sum(int n){ if(n==1) return1; else return(n + sum(n - 1));}
아래는 반복
int sum (int num) { int result = 0; for(int i = 1; i <= num;i++) { result += i; } return reulst; }
14. 다음을 계산하는 순환적인 프로그램을 작성하시오.
1 + 1/2 + 1/3 + ... 1/n
double sum(int n){ if(n == 1) return 1; else return ((double) 1/n + sum(n-1));}
16. 순환 호출되는 것을 이해하기 위하여 fib 함수를 다음과 같이 바꾸어서 실행하여 보라. fib(6)을 호출할 때 화면에 출력되는 내용을 쓰시오.
int fib(int n){ printf("fib(%d) is called\n",n); if(n==0) return 0; if(n==1) return 1; return(fib(n-1) + fib(n-2)); }
fib(6) is calledfib(5) is calledfib(4) is calledfib(3) is calledfib(2) is calledfib(1) is calledfib(0) is calledfib(1) is calledfib(2) is calledfib(1) is calledfib(0) is calledfib(3) is calledfib(2) is calledfib(1) is calledfib(0) is calledfib(1) is calledfib(4) is calledfib(3) is calledfib(2) is calledfib(1) is calledfib(0) is calledfib(1) is calledfib(2) is calledfib(1) is calledfib(0) is called
16. 다음의 순환적인 프로그램을 반복 구조를 사용한 비순환적 프로그램으로 바꾸시오.
int sum(int n){ if(n == 1) return 1; else return (n + sum(n-1));}
int sum(int n){ int i, sum = 0; for(i = 1; i <= n; i++) sum +=i; return sum;}
17. 이항계수를 계산하는 순환함수를 작성하라. 이항계수는 다음모가 같이 순환적으로 정의된다. 반복함수로도 구현해보라.
//순환 함수int binomial_coefficient(int n, int k){ if (k == 0 || k == n) return 1; return (binomial_coefficient(n-1, k-1) + binomial_coefficient(n-1, k);}
//반복 함수int binomial_coefficient(int n, int k){ int fac1, fac2, fac3, result = 0; for(int i = 0; i < n; i++) fac1 *= i; for(int i = 0; i < k; i++) fac2 *= i; for(int i = 0; i < n-k; i++) fac3 *= i; return fac1 / fac2 * fac3;}
18. Ackermann 함수는 다음과 같이 순환적으로 정의된다.
A(0, n) = n + 1A(m, 0) = A(m-1, 1)A(m, n) = A(m-1, A(m, n-1)) (m-2를 m-1로, 문제오류) m, n >= 1
(a) A(3, 2)와 A(2, 3)의 값을 구하시오.
A(3, 2) = 29 / A(2, 3) = 9
(b)Ackermann 함수를 구하는 순환적인 프로그램을 작성하시오.
int Ackermann(int m, int n){if (m == 0) return (n + 1);else if (n == 0) return Ackermann(m-1, 1);else return Ackermann(m-1, Ackermann(m, n - 1));}
19. 본문의 순환적인 피보나치 수열 프로그램과 반복적인 피보나치 수열 프로그램의 수행 시간을 측정하여 비교하라. 어떤 결론?
1. 반복 함수의 시간복잡도는 O(n) / 순환 함수의 시간복잡도는 O(2ⁿ이다. 따라서 순환 함수는 반복 함수보다 훨씬 오래걸린다
2. 반복적인 피보나치 수열 프로그램은 n번째 피보나치 값을 구하는데, (n-1)번의 연산이 필요하다.
하지만, 순환적인 피보나치 수열 프로그램은 n번째 피보나치 값을 구하기위해 (n-1)번쨰, (n-1)번째 피보나치 함수를 다시 호출하고, 또 이 호출된 함수가 2개씩 함수를 더 호출하며 지수적으로 호출 횟수가 증가한다. 따라서, 훨씬 더 오래 걸린다.
20. 순환호출에서는 순환호출을 할때마다 문제의 크기가 작아져야 한다.
(1) 팩토리얼 계산 문제에서 순환호출이 일어날 때마다 문제가 어떻게 작아지는가?
- 크기 n인 문제가 크기가 1씩 작아진다.
(2) 하노이의 탑에서 순환호출이 일어날 때마다 문제의 어떻게 작아지는가?
- 크기 n인 문제가 크기가 (n-1)인 문제 2개와 한번의 연산으로 나누어진다.
21. 컴퓨터 그래픽에서의 영역 채우기 알고리즘은 순환 기법을 사용한다. 흰색 영역이 있을 때 이 영역을 특정한 색으로 채우는 것이다. 영역 안쪽을 검정색으로 채운다고 가정해볼때 어떻게 순환호출을 사용할 수 있을까?
2 2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2
2 2 2 0 0 0 0 2 2 2
2 2 2 2 0 0 0 2 2 2
2 2 2 2 0 0 0 2 2 2
2 2 2 2 X 0 0 0 2 2
2 2 2 2 0 2 2 2 2 2
2 2 2 2 0 2 2 2 2 2
2 2 2 2 0 2 2 2 2 2
2 2 2 2 2 2 2 2 2 2 X : 시작 픽셀
#define WHITE 0#define BLACK 1#define YELLOW 2int screen[WIDTH][HEIGHT]'//char read_pixel(int x, int y){ return screen[x][y];}//void write_pixel(int x, int y, int color){screen[x][y] = color;}//영역 채우기 알고리즘void flood_fill(int x, int y){ if (read_pixel(x, y) == WHITE) { write_pixel(x, y, BLACK); flood_fill(x + 1, y); flood_fill(x - 1, y); flood_fill(x, y + 1); flood_fill(x, y - 1); }}
참 고 자 료
https://blog.naver.com/uoo1325/221910534750
https://travelbeeee.tistory.com/176?category=824560
댓글2 이 글에 댓글 단 블로거 열고 닫기
인쇄
