반응형
17. 순환적인 이항계수 / 반복적인 이항계수 (반복에서는 팩토리얼만 구현 후 이항계수 공식에 대입)
int binomial(int n,int k){
if(k==0 || k==n) return 1;
else return binomial(n-1,k-1)+binomial(n-1,k);
}
int factorial(int n){
int result=1;
for(int i=1;i<=n;i++){
result *= i;
}
return result;
}
int main(void){
int output;
int n=5;
int k=2;
output = factorial(n)/(factorial(k)*factorial(n-k));
printf("%d\n",output);
return 0;
}
18. (a) A(3,2) = 29 A(2,3) = 9
(b)
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));
}
(c) 구현포기
19. 순환적인 피보나치 수열 프로그램 수행 시간 : O(2^n)
반복적인 피보나치 수열 프로그램 수행 시간 : O(n) 이므로 반복적인 피보나치 수열 프로그램이 더 효율적이다.
20.
(1) factorial(n-1) 함수를 사용해 반복할 때 마다 해결해야할 남은 문제가 감소한다.
if(n<=1)에 도달하면 종료하는 함수를 실행한다.
(2) hanoi_tower(n-1 , x.., x...) 를 사용해 반복할 때 마다 해결해야할 남은 문제가 감소한다.
if(n==1)에 도달하면 종료하는 함수를 실행한다.
21.
#define WHITE 0
#define YELLOW 2
#define BLACK 1
#define WIDTH 10
#define HEIGHT 10
int map[WIDTH]][HEIGHT];
void fill(int x,int y){
if(map[x][y]==0){
map[x][y]=1;
}
fill(x+1,y);
fill(x-1,y);
fill(x,y+1);
fill(x,y-1);
}
'CS > Data Structure' 카테고리의 다른 글
[C언어로 쉽게 풀어쓴 자료구조] Chapter4. 스택 (1) (1) | 2023.10.22 |
---|---|
[C언어로 쉽게 풀어쓴 자료구조] 연습문제 3강 (0) | 2023.10.21 |
[C언어로 쉽게 풀어쓴 자료구조] 연습문제 1강 (0) | 2023.10.21 |
[C언어로 쉽게 풀어쓴 자료구조] Chapter3. 배열, 구조체, 포인터 (2) (0) | 2023.10.21 |
[C언어로 쉽게 풀어쓴 자료구조] Chapter3. 배열, 구조체, 포인터 (1) (0) | 2023.10.21 |