Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라. 사용자로부터 두 수를 입력받아서 이 두수의 최대 공약수를 구하고자 한다. 분석 챠트를 이용하여 위 문제를 분석하라. I a, b: integer O g: inteter P g = max { r | a % r = 0 and b %r = 0 } E A = 4, b = 24 => g = max {2,4} = 4 A = 6, b = 24 => g = max {2,3,6} = 6
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라. 두 정수 a, b를 전달받아서, a, b의 최대 공약수를 구하여 반환하는 알고리즘을 순환 버전 gcd_rec과 반복 버전 gcd_iter으로 각각 작성하라. procedure gcd_rec(a, b) // 가정: a> b Parameter a, b: integer if b = 0 then return a else return gcd_rec(b, a%b) endif end gcd_rec procedure gcd_iter(a, b) // 가정: a> b parameter a, b: integer; local tmp: integer; while b <> 0 do tmp <- b; b <- a mod b; a <- t repeat return a; end gcd_iter
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라. 사용자로부터 두 정수 a, b 를 입력받아서 반환하는 get_data()를 작성하라. void get_data(int *a, int *b) { printf(“input two integers:”); scanf(“%d %d”, a, b); }
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라. gcd_rec, gcd_iter의 알고리즘을 C 함수로 작성하라. 또한, 이러한 함수를 테스트하는 main()을 작성하고 실행시키고, 그 결과를 검증하라. int main() { int *a, *b, g; get_data(a, b); // input data g = gcd_rec(*a, *b); // print result return 0; }
Report #2 - Solution 문제 #2: 3개의 막대 A, B, C와 원판 n개를 전달받아 Hanoi 탑 문제를 해결하면서 원판의 이동 회수를 구하여 반환하는 hanoi_tower(n, A, B, C)를 작성하라. 여기서 원판 n은 막대 A에 쌓여 있고 이를 B를 이용하여 C로 옮긴다고 가정한다. procedure hanoi_tower(n) parameter n: integer if n = 1 then return 1 else return hanoi_tower(n-1) + 1 + hanoi_tower(n-1) endif end hanoi_tower
Report #2 - Solution 문제 #2: 원판의 개수 n을 입력받아서 hanoi_tower()를 호출하고, 이 함수가 실행되는 시간을 측정하여 다음 테이블을 출력하는 main() 함수를 작성하라. n 이동 회수 실행 시간
Report #2 - Solution 문제 #2: 3)의 테이블로부터 n 대비 이동 회수, 실행시간의 추이도를 보여주는 그래프를 각각 그려라. 또한, 1)의 식으로부터 n 대비 소요 시간을 보여주는 그래프를 그리고, 이러한 그래프를 비교하라.
Report #2 - Solution 문제 #2: Hanoi 탑 문제에서 64개 원판을 옮기는데 걸리는 시간을 계산하라. 단, 한 개의 원판을 옮기는데 걸리는 시간을 1초라고 가정한다. 여러분은 계산 과정을 보여야 한다. Hn이 n개의 원판을 옮기는데 걸리는 시간이라고 가정 H1 = 1 (∵원판이 한 개 있으므로, 한 번이동으로 목적 달성) Hn = Hn-1 + 1 + Hn-1 = 2Hn-1 + 1 (알고리즘으로부터) = 2(2Hn-2 + 1) +1 = 2^2Hn-2 + 2 + 1 = 2^2(2Hn-3 + 1) + 2 + 1 = 2^3Hn-3 + 2^2 + 2 + 1 = … = 2^(n-1)H1 + 2^(n-2) + …. + 1 = 2^(n-1) + 2^(n-2) + … + 1 (∵H1 =1) = 2^n - 1