Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.

Presentation on theme: "Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다."— Presentation transcript:

1 Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다. 이 타입은 행과 열의 크기, 0이 아닌 원소의 개수와 이들을 포함한 배열을 포함한다. 또한, 원소는 (행, 열, 값)으로 표현된다. add_sparse_matrix()를 IOPE 챠트를 이용하여 분석하라. 위의 분석을 이용하여 알고리즘을 작성하라. main() 함수를 작성하여 테스트하라.

2 Report #3 - due: 4/6 다음과 같이 main() 함수를 작성하여 테스트하라. get_sparse_matrix()
각 원소의 값 (행, 열, 값)을 난수를 발생시켜 결정. 그 범위는 0<= 행, 열 <=99, 1<= 값 <= 10. #define SIZE 100 int main() { sparse_matrix A, B, C // 변수 선언 get_sparse_matrix(A, SIZE, SIZE); add_sparse_matrix(A, B, C) print(C, SIZE, SIZE); //C를 100*100의 행렬 형태로 출력한다. return 0; }

3 Refer: 5주차 실습 -solution

4 poly_add2() 2개의 타입 poly, term_type 정의 type poly = record
terms: array [1..maxterms] of term_type; // 항의 정보 num: integer; // 항의 개수 end; type term_type = record coef: real; // 계수 expo: integer; // 차수

5 poly_add2() 분석 구분 내용 I p, q: poly
p = (np, (coefi, expoi)), i=1, 2, …, np q = (nq, (coefj, expoj)), j=1, 2, …, nq O r: poly r = (nr, (coefk, expok)), i=1, 2, …, nr P 0<= r.nr <= p.np + q.nq r.(coefk, expok) = (p.coefi+q.coefj, p.expoi) if э i, j s.t. expok = p.expoi and expok = q.expoj (p.coefi, p.expoi) if э i s.t. expok = p.expoi and ¬э j s.t. expok = q.expoj (q.coefj, q.expoj) if ¬э i s.t. expok = p.expoi and э j s.t. expok = q.expoj E 분석

6 poly_add2(): 알고리즘 알고리즘 procedure poly_add2(p, q: poly) r: poly;
pf <- 0; qf<- 0; rf <-0; // 다항식의 현재 항 인덱스 설정 while pf <= p.num and qf <= q.num do if p[pf].terms.expo = q[qf].terms.expo then r[rf].terms.coef <- p[pf].terms.coef + q[qf].terms.coef; r[rf].terms.expo <- p[pf].terms.expo; rf <- rf +1; pf <- pf+1; qf <- qf+1; // 인덱스 갱신 else if p[pf].terms.expo > q[qf].terms.expo then r[rf].terms.coef <- p[pf].terms.coef; rf <- rf +1; pf <- pf+1; else r[rf].terms.coef <- p[qf].terms.coef; r[rf].terms.expo <- p[qf].terms.expo; rf <- rf +1; qf <- qf+1; end if repeat // 어느 한 쪽이 먼저 소진된 경우 처리 if pf <= p.num then // p의 나머지 항들을 r로 이동 // q의 나머지 항들을 r로 이동 endif end poly_add2 알고리즘