- 1 -
데이터 구조 실습 (4주차)
2021. 3. 24
학번: 성명:
1. 다음에 답하시오.
a. Hanoi Tower 문제를 기술하라.
b. 여러분의 스마트폰에서 Hanoi Tower 어플을 설치하라.
c. Hanoi Tower 어플에서 원판의 개수를 4로 설정하고, 게임을 수행하라. 게임이 종료되었을 때 원판을 옮 긴 회수는 몇 번인가?
d. c)에서 원판의 개수를 5로 설정하고, 게임을 수행하고, 게임 종료시에 원판을 옮긴 회수는 몇 번인가?
e. Hanoi Tower 문제에서, 원판의 개수가 n일 때, n개의 원판을 다른 막대로 옮기는데 필요한 최소 회수를 구하는 알고리즘 hanoi()를 작성하라.
f. d)에서 작성한 알고리즘을 C 함수로 작성하고, 다음 n의 값에 따른 함수의 실행 시간을 측정하라. n 대 비 실행시간을 그래프로 나타내라.
n 5 10 15 20 25 30 35
hanoi 함수 실행시간 (초단위)
- 2 - 2. 다음 두 다항식에 대한 덧셈을 고려한다:
p = 8x^3 + 7x + 1, q = 10x^5 + 3x^2+ 6x
a. 다항식을 배열 coef와 정수 변수 degree로 구성하여 표현한다. 여기서 coef는 다항식의 각 항의 계수만 을 고차항부터 순서대로 저장하는 배열이고, degree는 다항식의 최고 차수를 포함한다. 이와 같이 다항식을 표현하도록 다항식을 타입을 정의하라.
b. a)에서 정의된 다항식의 타입 이름을 poly로 설정하라.
c. 변수 p q를 poly 타입으로 선언하면서, 위의 다항식으로 각각 초기화하라.
d. a)와 같이 표현된 2개의 다항식 p, q를 전달받고, 이를 더하여 그 결과를 반환하는 알고리즘 poly_add(p, q)를 작성하라.
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;
}
