제 3 강.

Presentation on theme: "제 3 강."— Presentation transcript:

1 제 3 강

2 두 다항식의 덧셈 알고리즘 polyAdd(p1, p2) p3←zeroP();
   while (not isZeroP(p1) and not isZeroP(p2)) do {         case {            maxExp(p1) < maxExp(p2) :               p3←addTerm(p3, coef(p2, maxExp(p2)), maxExp(p2));               p2 ←delTerm(p2, maxExp(p2));            maxExp(p1) = maxExp(p2) :                sum←coef(p1, maxExp(p1))+ coef(p2, maxExp(p2));                if (sum≠0) then p3 ← addTerm(p3, sum, maxExp(p1));                p1 ← delTerm(p1, maxExp(p1));                p2 ← delTerm(p2, maxExp(p2)); maxExp(p1) > maxExp(p2) :             p3←addTerm(p3, coef(p1, maxExp(p1)), maxExp(p1));                p1 ← delTerm(p1, maxExp(p1));       } }    if (not isZeroP(p1)) then p1의 나머지 항들을 p3에 복사    else if (not isZeroP(p2)) then p2의 나머지 항들을 p3에 복사;    return p3; end polyAdd()

3 #include <stdio.h> #define SIZE 32 // p의 배열 개수 설정
typedef struct{ int exp; //지수 int coef; //계수 }poly; int count; //항 개수 카운트 poly p[SIZE]; // poly형 타입의 배열 } polys; void main() { polys p1; polys p2; polys p3; p1.count = 0; p2.count = 0; int a,b; exp coef count exp coef

4 printf("P1의 항(계수, 지수)을 입력하세요. (0 0 이면 입력종료)\n");
while (1) { scanf("%d %d",&a,&b); if (a==0 && b==0) break; addTerm(&p1,a,b); } printf("P1 다항식 : "); printPolys(&p1); printf("\n"); printf("P2의 항(계수, 지수)을 입력\n"); while (1){ addTerm(&p2,a,b);} printf("P2 다항식 : "); printPolys(&p2); printf("P3 다항식(P1+P2) : "); p3 = polyAdd(&p1,&p2); printPolys(&p3); }

5 int isZeroP(polys* ps) //남은 항이 있는지 확인
{ int result=0; //항이 있을경우 0 (flase) if (ps->count==0) { result=1; //항이 없을경우 1 (true) } return result; int coef(polys* ps, int e) //e와 같은 계수 int result = 0; //e와 같은 계수가 없으면 "0" for (int i=0; i<ps->count; i++) // e와 같은 계수가 있으면 "해당 계수" 리턴 if (ps->p[i].exp == e){ result = ps->p[i].coef; break;

6 int maxExp(polys* ps) //지수가 가장 큰 항의 지수 {
int result = ps->p[0].exp; //첫번째 번지에 있는 지수를 기본값으로 주고 for (int i=0; i<ps->count; i++) //각 항의 지수비교해서 "최고 지수"를 리턴 if (ps->p[i].exp > result) result = ps->p[i].exp; } return result; void addTerm(polys* ps, int coef, int exp) //항을 추가 ps->p[ps->count].exp = exp; ps->p[ps->count].coef = coef; ps->count++; p1 ps count exp coef

7 void delTerm(polys* ps, int e) //항을 제거
{ int i; int flag = 0; if (isZeroP(ps)) return; for (i=0;i<ps->count;i++) { if (ps->p[i].exp == e) flag = 1; if (flag) ps->p[i] = ps->p[i+1]; } ps->count--; } char compare(int a, int b) // 지수 비교 // a와 b를 비교하여 =, <, > 리턴 if (a == b) return '='; else if (a < b) return '<'; else return '>'; }

8 polys polyAdd(polys* p1, polys* p2) { // p3다항식 = p1다항식 + p2다항식
p3.count = 0; int sum; while(!isZeroP(p1) && !isZeroP(p2)) { //p1,p2에 다항식이 있을경우 switch (compare(maxExp(p1), maxExp(p2))) { //최고지수 비교 case '<' : //p1의 지수가 p2의 지수보다 작으면 addTerm(&p3,coef(p2,maxExp(p2)),maxExp(p2)); delTerm(p2,maxExp(p2)); break; case '=' : //p1,p2의 지수가 같으면 sum = coef(p1,maxExp(p1)) + coef(p2,maxExp(p2)); if (sum != 0) addTerm(&p3,sum,maxExp(p1)); delTerm(p1,maxExp(p1)); case '>' : //p1의 지수가 p2 지수보다 크면 addTerm(&p3,coef(p1,maxExp(p1)),maxExp(p1)); break; } }

9 while(!isZeroP(p1)) { // p1의 나머지 항들을 p3로 복사
addTerm(&p3,coef(p1,maxExp(p1)),maxExp(p1)); delTerm(p1,maxExp(p1)); } while(!isZeroP(p2)) { // p2의 나머지 항들을 p3로 복사 addTerm(&p3,coef(p2,maxExp(p2)),maxExp(p2)); delTerm(p2,maxExp(p2)); return p3;

10 void printPolys(polys* ps) { //다항식 출력
int i; for (i=0;i<ps->count;i++) { if (ps->p[i].coef == 0){ printf(""); //계수 0이면 표시 안함 }else if (ps->p[i].exp == 1){ printf("%d",ps->p[i].coef); //지수가 1이면 계수만 표시 }else{ printf("%dx^%d",ps->p[i].coef,ps->p[i].exp); printf(" + "); //지수가 0이 아니면 계수x^지수 형태로 출력 } printf("\n");

11

12 제 4 강

13 희소 행렬 전치 알고리즘 transposeS(a[]) m ← a[0, 0]; // a의 행 수
   n ← a[0, 1];           // a[]의 열수    t ← a[0, 2];           // a[]의 0이 아닌 원소 수       b[0, 0] ← n;           // b[]의 행 수 ← a[]의 열 수     b[0, 1] ← m;          // b[]의 열 수 ← a[]의 행 수    b[0, 2] ← t;           // b[]의 0이 아닌 원소 수    if (t > 0) then {      p ← 1;               // b[]에 대해 현재 행의 위치를 지시      for (p ← 0; p < n; p ← p+1) do { // a[]의 열 별로 처리         for (i ← 1; i <= t; i ← i+1) do { // 0이 아닌 원소 수에 대해            if a[i, 1] = p then {  // 열 p의 원소 발견              b[p, 0] ← a[i, 1];              b[p, 1] ← a[i, 0];              b[p, 2] ← a[i, 2];              p ← p+1;            } } } }     return b[]; end transposeS()

14 #include <stdio.h>
#define MAX_COL 101 typedef struct triple{ int row; int col; int value; } triple; void main() { int i; triple x[MAX_COL], y[MAX_COL]; x[0].row = 5; x[0].col = 5; x[0].value = 5; x[1].row = 0; x[1].col = 0; x[1].value = 43; x[2].row = 0; x[2].col = 4; x[2].value = 11; x[3].row = 2; x[3].col = 2; x[3].value = 8; x[4].row = 3; x[4].col = 1; x[4].value = -27; x[5].row = 4; x[5].col = 0; x[5].value = 30; transpose( x, y ); for( i=0; i<6; i++) printf("x = %d %d %d \n", x[i].row, x[i].col, x[i].value); }

15 void transpose(triple a[], triple b[]) { int m, n, t, i, j, p;
m = a[0].row; n = a[0].col; t = a[0].value; b[0].row = n; b[0].col = m; b[0].value = t; if (t > 0) { p = 1; for (i = 0; i < n; i++) for (j = 1; j <= t; j++) if (a[j].col == i) { b[p].row = a[j].col; b[p].col = a[j].row; b[p].value = a[j].value; p++; } 행 열 값 행 열 값 a[0] b[0] [1] [1] [2] [2] [3] [3] [4] [4] [5] [5]

16 void transpose(triple a[], triple b[]) { if (t > 0) {
for (i = 0; i < n; i++) row_triples[i] = 0; for (i = 1; i <= t; i++) row_triples[a[i].col]++; start_pos[0] = 1; for (i = 1; i < n; i++) start_pos[i] = start_pos[i-1] + row_triples[i-1]; for (i = 1; i <= t; i++) { j = start_pos[a[i].col]++; b[j].row = a[i].col; b[j].col = a[i].row; b[j].value = a[i].value; } } 행 열 값 행 열 값 a[0] b[0] [1] [1] [2] [2] [3] [3] [4] [4] [5] [5] row: row_triples[]= start_pos[]= [0] [1] [2] [3] 2 1 3 4 5

17