- 1 -
데이터 구조 실습 (4주차)
2021. 3. 24
학번: 성명:
1. 다음에 답하시오.
a. Hanoi Tower 문제를 기술하라.
기둥 3개(A, B, C), 원판 n개. 원판의 크기가 모두 다르고
한 기둥(A)에 n개의 원판이 쌓여 있을 때, 모든 원판을 다른 기둥(C)로 이동하는 문제 단, 한 번에 한 개의 원판만 이동 가능, 작은 원판 위에 큰 원판을 쌓을 수 없다.
b. 여러분의 스마트폰에서 Hanoi Tower 어플을 설치하라.
c. Hanoi Tower 어플에서 원판의 개수를 4로 설정하고, 게임을 수행하라. 게임이 종료되었을 때 원판을 옮 긴 회수는 몇 번인가? 15
d. c)에서 원판의 개수를 5로 설정하고, 게임을 수행하고, 게임 종료시에 원판을 옮긴 회수는 몇 번인가?
31
e. a)의 문제를 해결하는 알고리즘 honai_tower(n, A, B, C)를 작성하라. 단, 한 개의 원판을 옮기는데 move(A, C)를 이용하시오.
hanoi_tower(n, A, B, C) { if n = 1 then
move(A, C) else
hanoi_tower(n-1, A, C, B) move(A, C)
hanoi_tower(n-1, B, A, C) end if
}
- 2 -
f. Hanoi Tower 문제에서, 원판의 개수가 n일 때, n개의 원판을 다른 막대로 옮기는데 필요한 최소 회수를 구하는 알고리즘 hanoi_count()를 작성하라.
hanoi_count(n) = 1 if n=1
= hanoi_count(n-1) + 1 + hanoi_count(n-1) otherwise
hanoi_count(n, A, B, C) { if n = 1 then
return 1 else
return
hanoi_count(n-1, A, C, B) + 1 +
hanoi_count(n-1, B, A, C) end if
}
f. d)에서 작성한 알고리즘을 C 함수로 작성하고, 다음 n의 값에 따른 함수의 실행 시간을 측정하라. n 대 비 실행시간을 그래프로 나타내라.
n 5 10 15 20 25 30 35
이동 회수 31 1023
hanoi 함수 실행시간(초단위)
- 3 - 2. 다음 두 다항식에 대한 덧셈을 고려한다:
p = 8x^3 + 7x + 1, q = 10x^5 + 3x^2+ 6x
a. 다항식을 배열 coef와 정수 변수 degree로 구성하여 표현한다. 여기서 coef는 다항식의 각 항의 계수만 을 고차항부터 순서대로 저장하는 배열이고, degree는 다항식의 최고 차수를 포함한다. 이와 같이 다항식을 표현하도록 다항식을 타입을 정의하고, 이를 C 문장으로 작성하라.
struct poly{
float coef[MAX_DEGREE];
int degree;
} p, q;
b. a)에서 정의된 다항식의 타입 이름을 poly로 설정하라.
typedef struct poly { int degree;
float coef[MAX_DEGREE];
} poly;
타입 이름: struct poly, poly struct poly p;
poly p;
typedef int integer;
int a;
integer a;
c. 변수 p q를 poly 타입으로 선언하면서, 아래 다항식으로 각각 초기화하는 C 문장을 작성하라.
p = 8x^3 + 7x + 1, q = 10x^5 + 3x^2+ 6x
poly p = { 3, {8, 0, 7, 1}}, q = {5, {10, 0, 0, 3, 6, 0}};
int a[] = {1, 2, 3, 4};
struct temp { int a, int b};
struct temp tmp = {1, 2};
- 4 -
d. a)와 같이 표현된 2개의 다항식 p, q를 전달받고, 이를 더하여 그 결과를 반환하는 알고리즘 poly_add(p, q)를 작성하라.
poly p = { 3, {8, 0, 7, 1}}, q = {5 , {10, 0, 0, 3, 6, 0}};
poly r;
r = {5, {10, 0, 8, 3, 13, 1}}
....
r = poly_add(p, q); // in main()
poly_add(p, q: poly) : poly { poly r;
dp = p.degree; dq = q.degree;
ip = iq = ir = 0;
r.degree = max (dp, dq);
while dp >=0 and dq>= 0 do if dp = dq then
q.coef[ir++] <- p. coef[ip++] + q.coef[iq++]
dp--; dq-- else if dp < dq then
q.coef[ir++] <- q.coef[iq++]
dq-- else
q.coef[ir++] <- p.coef[iq++]
dp-- repeat
return r;
}
return r;
}
- 5 -
e. d)에서 작성한 알고리즘을 C 함수로 작성하고, 다음 main() 함수를 작성하여 테스트하라.
int main() {
// p, q의 2개 다항식 선언 및 초기화 r = poly_add(p, q);
// r을 다음과 같이 출력 // degree: 5
// the sequence of coefs: 10, 0, 8, 13, 1, 0 return 0;
}
