보고서#2 (due 3/29)
제출 방법:
대학 학습플랫폼(Lms)에 명시된 기간내 제출
설정된 제출 기간( 3/29 12:00 pm)이 지나면 제출할 수 없음에 유의 하기 바람
1
문제 #1
다음에 답하시오.
크기가 n*n인 두 행렬 A, B를 매개변수로 전달받아서, 두 행렬을 곱 한 결과를 포함하는 C 행렬을 (즉, A * B = C) 매개변수로 반환하는 알고리즘 mult를 작성하라.
위 알고리즘 mult에 포함된 연산 회수를 계산하여 시간 복잡도 함수 T(n)을 구하라.
위에서 구한 T(n)을 빅오 표기법으로 나타내라. 그 이유를 주라.
문제 #2
문제 #1의 알고리즘 mult()를 C 함수로 작성하라.
mult() 함수의 실행시간을 다음 main() 함수를 이용하여 측정하고 , 행렬의 크기 n 대비 함수의 실행시간을 테이블 및 그래프로 각 각 나타내라. n의 크기를 10, 20, 30, 40, 50으로 설정하라.
3
main() {
행렬의 크기 n을 입력
A, B의 2개 행렬 초기화 // getMat(A) 함수 작성 (1~10의 난수 // 발생하여 행렬을 채운다)
// A, B의 행렬 크기는 n*n으로 설정 mult(A, B, C);
A, B, C의 행렬 출력 // printMat(A) 함수 작성 }
문제 #3
크기가 n인 배열 a에서 임의의 위치 loc(0≤ loc ≤ n-1)에 위치 한 원소를 삭제하는 다음 C 함수 delete()를 작성하라. 원소가 삭 제되면, 그 뒤에 있는 정수들은 한 칸씩 앞으로 당겨져야 한다.
void delete(int a[], int n, int loc)
// n은 배열 크기, loc는 삭제 위치
위의 함수의 최악, 최선, 평균적인 경우의 시간 복잡도는 각각 무 엇인가? 빅오 표기법으로 나타내라.
문제 #4
다음은 두 수 u, v에 대한 최대공약수를 구하는 C 함수 gcd()이다.
이 함수를 재귀적 버전인 gcd_rec()를 작성하라.
위에서 작성한 함수를 main() 함수를 작성하여 테스트하라.
5
int gcd(int u, v) {
while (u != v) { if (u > v)
u = u-v;
else
v = v-u;
}
return u;
}
문제 #5
한 개의 정수 n을 전달받아서, 이 수에 포함된 숫자(digit)의 개수 를 반환하는 순환 함수 count()를 작성하라. 가령, n = 12345이면 , 12345에 포함된 숫자가 1, 2, 3, 4, 5의 5개 숫자를 포함하므로 5를 반환한다. 단, 함수 작성시에 지역 변수를 사용하면 안된다.
위에서 작성한 함수를 main() 함수를 작성하여 테스트하라.
문제 #6
2보다 크거나 같은 한 개의 정수를 전달받아서, 이 수가 소수
(prime number)인지를 판단하고, 소수이면 1을, 그렇지 않으면 0 을 반환하는 순환 함수 isPrime()을 작성하라. 이 함수는 main() 에서 다음과 같이 호출된다: isPrime(n, 2);
위에서 작성한 함수를 main() 함수를 작성하여 테스트하라.
7
문제 #7
Ackermann 함수는 다음과 같이 정의된다. 다음에 답하시오.
a. A(3,2)와 A(2,3)의 값을 각각 구하시오. 그 과정을 보여야 한다.
b. Ackermann 함수의 재귀적 C 함수 Acker(m, n)을 작성하라.
c. 위에서 작성한 Acker()를 호출하는 main()을 작성하고, 실행을 통해 서 A(3,2), A(2,3을 테스트하라.
A(0, n) = n+1
A(m, 0) = A(m-1,1)
A(m, n) = A(m-1, A(m,n-1)) m, n >= 1
