1. polynomial addition
두 다항식 A(x)와 B(x)를 더하여 다항식 D(x)를 구한다고 하자. 만약 다항식을 항 배열로 표현하되 교재의 Figure 2.3과 같이 여러 다항식들을 하나의 통합된 배열에 저장할 경우 이를 C로 구현한 것이 교재의 Program 2.6과 Program 2.7이다. 다항식을 계수 배열로 표현할 경우 계수가 0인 것도 모두 저장하므로 다항식 더하기 프로그램은 매우 간단히 작성될 수 있다. 다항식 A(x), B(x), D(x)를 각각 교재 2.4.2절에 기술된 계수 배열 표현 방법으로 저장할 경우 다항식 더하기를 수행하는 C 프로그램을 작성하시오.
다항식 표현 방법 :
교재 2.4.2절에 기술된 내용 및 관련 C 코드를 일체의 수정 없이 그대로 사용한다.
main 함수 및 변수선언 :
main 함수에서 함수 padd를 호출한다. padd는 polynomial padd(polynomial A, polynomial B); 로 정의한다. 즉, 두 다항식을 받아서 더한 결과 다항식을 반환한다. 따라서 main 함수에서는 A, B, D를 지역변수 polynomial A, B, D; 로 선언하고 D = padd(A, B); 를 수행한다.
다항식 입력 :
A, B 다항식의 항들은 지수값으로 내림순 정렬되어 주어진다고 가정하며, 아래 예시와 같이 입력용 계수 및 지수 배열을 통해 입력되도록 한다. 입력용 계수 배열의 값은 양수 또는 음수이고 자료형은 float. 입력용 지수 배열의 값은 0보다 크거나 같으며 자료형은 int. define문의 설정값 및 입력용 계수 및 지수 배열의 값은 아래 예시로 한정하지 않고 임의의 값으로 변경 가능하도록 한다. 채점 시 아래 라인들을 값만 변경된 라인들로 대체하고 컴파일 및 실행한다.
#define A_nonzero_terms 3 // A(x) 다항식의 nonzero 항의 수
#define B_nonzero_terms 4 // B(x) 다항식의 nonzero 항의 수
float A_coef[A_nonzero_terms] = {2.0, 2.0, 3.0}; int A_exp[A_nonzero_terms] = {7, 3, 2};
// A(x) = 2x7 + 2x3 + 3x2
float B_coef[B_nonzero_terms] = {4.0, 3.0, 7.0, 7.0}; int B_exp[B_nonzero_terms] = {5, 3, 1, 0};
// B(x) = 4x5 + 3x3 + 7x + 7
j = 0;
for (i = MAX_DEGREE - 1; i >= 0; i--) {
if (i == A_exp[j]) {
A.coef[MAX_DEGREE - i - 1] = A_coef[j];
j++;
}
else {
A.coef[MAX_DEGREE - i - 1] = 0.0;
}
}주어진 다항식 배열을 위와 같이 계수배열로 저장한다. 계수가 0이 아닌 항을 coef 배열에서 가져와 저장하기 위해 if문으로 exp 배열에 해당 차수의 항이 있는지 검사하여 저장한다. 계수가 0인 항은 계수배열에 0으로 저장한다.
polynomial padd(polynomial A, polynomial B)
{
polynomial D;
int i; int deg_fixed = 0;
D.degree = A.degree > B.degree ? A.degree : B.degree;
for (i = MAX_DEGREE - D.degree - 1; i < MAX_DEGREE; i++) {
D.coef[i] = A.coef[i] + B.coef[i];
if (deg_fixed == 0 && D.coef[i] !=0) {
D.degree = MAX_DEGREE - i - 1;
deg_fixed = 1;
}
}
return D;
}결과 다항식 D의 차수는 A 다항식과 B 다항식의 최고 차수가 된다. 계수배열에 0을 포함한 계수들이 저장되어 있기 때문에 for문을 통해 같은 차수에 해당하는 항끼리 계수를 더하여 D 다항식에 계수배열로 저장한다. 계수의 합이 0이어서 최고차수가 바뀔 경우를 고려한다.
printf("%d차 : ", D.degree);
for (i = MAX_DEGREE - D.degree - 1; i < MAX_DEGREE; i++) {
if (i == MAX_DEGREE - 1) printf("%f\n", D.coef[i]);
else if (D.coef[i]) printf("%fx^%d + ", D.coef[i], 9 - i);
}저장된 계수배열을 다항식 형태로 출력한다.
#include <stdio.h>
#define MAX_DEGREE 10
#define A_nonzero_terms 3
#define B_nonzero_terms 4
float A_coef[A_nonzero_terms] = { 2.0, 2.0, 3.0 }; int A_exp[A_nonzero_terms] = { 7, 3, 2 };
float B_coef[B_nonzero_terms] = { 4.0, 3.0, 7.0, 7.0 }; int B_exp[B_nonzero_terms] = { 5, 3, 1, 0 };
typedef struct {
int degree;
float coef[MAX_DEGREE];
} polynomial;
polynomial padd(polynomial A, polynomial B);
int main()
{
polynomial A, B, D;
int i, j;
A.degree = A_exp[0]; B.degree = B_exp[0];
j = 0;
for (i = MAX_DEGREE - 1; i >= 0; i--) {
if (i == A_exp[j]) {
A.coef[MAX_DEGREE - i - 1] = A_coef[j];
j++;
}
else {
A.coef[MAX_DEGREE - i - 1] = 0.0;
}
}
j = 0;
for (i = MAX_DEGREE - 1; i >= 0; i--) {
if (i == B_exp[j]) {
B.coef[MAX_DEGREE - i - 1] = B_coef[j];
j++;
}
else {
B.coef[MAX_DEGREE - i - 1] = 0.0;
}
}
D = padd(A, B);
printf("%d차 : ", D.degree);
for (i = MAX_DEGREE - D.degree - 1; i < MAX_DEGREE; i++) {
if (i == MAX_DEGREE - 1) printf("%f\n", D.coef[i]);
else if (D.coef[i]) printf("%fx^%d + ", D.coef[i], 9 - i);
}
return 0;
}
polynomial padd(polynomial A, polynomial B)
{
polynomial D;
int i; int deg_fixed = 0;
D.degree = A.degree > B.degree ? A.degree : B.degree;
for (i = MAX_DEGREE - D.degree - 1; i < MAX_DEGREE; i++) {
D.coef[i] = A.coef[i] + B.coef[i];
if (deg_fixed == 0 && D.coef[i] !=0) {
D.degree = MAX_DEGREE - i - 1;
deg_fixed = 1;
}
}
return D;
}
2. sparse matrix addition
a) 4x4 matrix
11 0 0 0
0 0 0 7
0 0 0 0
-1 0 0 0
b) bit[4][4] 배열
1 0 0 0
0 0 0 1
0 0 0 0
1 0 0 0
c) B[16] 배열
1000000100001000
d) 8 bits of B[]
10000001 = 129
00001000 = 8
e) P[], V[]
row=4
col=4
t=3
P[]={129, 8}
V[]={11, 7, -1}
위 그림의 (a)는 n×m sparse matrix로 n=m=4인 예이다. (b)는 (a)의 matrix에서 nonzero element는 1로 zero element는 0으로 표현한 2차원 비트 배열이다. (c)는 (b)의 2차원 비트 배열을 비트 스트링으로 변환한 것으로 bit[i][j]를 B[i*n+j]에 저장하였다. (d)는 B[] 배열의 첫 8 bit와 두번째 8 bit를 각각 10진수로 나타낸 것이다. (e)는 (a)의 sparse matrix를 표현한 것으로 row와 col은 matrix의 row수와 column수이다. t는 nonzero element의 수이다. P[] 배열은 (d)의 8 bit 단위 십진수 값을 차례로 저장하고, V[] 배열은 nonzero element의 값을 교재의 표현체계에서와 동일한 순서로 저장한 것이다. sparse matrix를 위 그림 (e)와 같은 체계로 표현할 경우 두 sparse matrix A와 B를 더하여 D를 구하는 C 프로그램을 작성하시오. 편의상 row×col은 8의 배수라고 가정한다.
sparse matrix 입력 :
입력 값은 아래 예시로 한정하지 않고 임의의 값으로 변경 가능하도록 한다. 채점 시 아래 라인들을 값만 변경된 라인들로 대체하고 컴파일 및 실행한다.
#define Row 4
#define Col 4
#define A_nonzero_elements 3 // A matrix의 nonzero element의 수
int AP[(Row*Col)/8] = {129, 8}; int AV[A_nonzero_elements] = {11, 7, -1};
#define B_nonzero_elements 4 // B matrix의 nonzero element의 수
int BP[(Row*Col)/8] = {65, 136}; int BV[B_nonzero_elements] = {5, 2, 4, 1};
sparse matrix 더하기 결과 출력 :
row: 4
col: 4
t: 4
DP[]: 193, 128
DV[]: 11, 5, 9, 4
주어진 희소행렬 입력방식을 그대로 활용하여 덧셈을 수행하기 위해 다음과 같은 순서를 진행하였다.
1) OR 연산을 통해 결과 행렬의 DP[](10진수화 한 8bit 요소 binary)를 계산한다.
2) AV[]와 BV[]의 값들로 덧셈을 수행하기 위해 각각의 요소가 8bit 상 어느 인덱스의 값인지 표시하는 배열 Apos, Bpos를 계산한다.
3) 8bit 범위 안에서 순서에 맞게 값들을 이동 또는 같은 index의 값을 더한다.
4) Dpos를 찾는다.
5) 새로 생성된 결과 값에 0이 존재하는지 확인하여 해당 index를 0으로 바꾼다. (10진수 상에서는 2^index만큼 값을 빼줌. (뒤에서부터 검사, 계산))
for (k = 0; k < (Row * Col) / 8; k++) DP[k] = AP[k] | BP[k];(Row * Col) / 8의 크기, 즉 주어진 배열을 8bit의 크기로 나눈 개수만큼 OR 연산을 실행한다. DP[] 배열에는 AP[]와 BP[]처럼 10진수화된 8bit 2진 값이 저장된다.
findpos(AP, AV, Apos, Apos_num, A_nonzero_elements);
findpos(BP, BV, Bpos, Bpos_num, B_nonzero_elements);findpos는 Apos와 Bpos 값을 찾아(looking for)주는 함수이다.
void findpos(int XP[], int XV[], int Xpos[], int Xpos_num[], int X_nonzero)
{
int last, cnt = 0;
int i, j;
for (i = 0; i < (Row * Col) / 8; i++) {
last = XP[i];
Xpos_num[i] = 0;
for (j = 0; j < 8; j++) {
if (last >= bin[j]) {
Xpos[cnt] = j;
cnt++;
Xpos_num[i] ++;
last = last - bin[j];
if (!last) break;
}
}
}
}위 함수는 10진수를 2진수로 변형시키지 않고 어느 위치에 1이 있는지 계산한다. 2의 거듭제곱으로 이루어진 배열 bin[]과 해당 10진수를 비교하여 1이 있는 위치를 pos[]에 저장하고,(0~7 사이의 값으로만 구성) 해당 8bit 바이너리가 어느 index까지를 구성하는지 표시하기 위해 pos_num[]을 사용한다. 도식화하면 다음과 같다.
| 행렬 | P[] | pos_num[] | pos[] (한 배열) | V[] (한 배열) |
| A | AP[0] = 129 | Apos_num[0] = 2 | { 0, 7, | { 11, 7, |
| AP[1] = 65 | Apos_num[1] = 1 | 4 } | -1 } | |
| B | BP[0] = 65 | Bpos_num[0] = 2 | { 1, 7, | { 5, 2, |
| BP[1] = 136 | Bpos_num[1] = 2 | 0, 4 } | 4, 1 } |
그 다음, 첫번째 8bit끼리, 두번째 8bit 끼리, pos의 순서에 맞추어 DV[]를 생성한다. 이때, pos[]는 이미 pos_num의 범위 안에서 정렬된 값이기 때문에, 맨 앞 값끼리 비교하여 계산하면 정렬된 순서의 DV[] 값을 얻을 수 있다.
for (k = 0; k < (Row * Col) / 8; k++) {
Apos_srv = Apos_num[k];
Bpos_srv = Bpos_num[k];
while (Apos_srv != 0 || Bpos_srv != 0) {
if (Apos_srv == 0) {
DV[cnt] = BV[j];
cnt++; j++; Bpos_srv--;
continue;
}
else if (Bpos_srv == 0) {
DV[cnt] = AV[i];
cnt++; i++; Apos_srv--;
continue;
}
if (Apos[i] < Bpos[j]) {
DV[cnt] = AV[i];
cnt++; i++; Apos_srv--;
}
else if (Apos[i] > Bpos[j]) {
DV[cnt] = BV[j];
cnt++; j++; Bpos_srv--;
}
else { // Apos[i] == Bpos[j]
DV[cnt] = AV[i] + BV[j];
cnt++; i++; j++; Apos_srv--; Bpos_srv--;
}
}
}pos의 값을 비교하여 (해당 값의 2진수 안에서의 위치) 더 앞 pos를 갖는 V값을 DV[]에 넣어주고, 그 다음 pos와 다시 비교한다. 만약 해당 배열의 해당 8bit 내 값을 모두 저장했다면, 다른 한 배열의 해당 8bit 내 남은 값을 모두 저장하고 다음 8bit로 넘어간다. 값을 저장할 때마다 cnt++.
Dt = cnt;
findpos(DP, DV, Dpos, Dpos_num, Dt);
D행렬도 Dpos와 Dpos_num을 계산한다. 이 함수 실행이 끝난 후 :
| 행렬 | P[] | pos_num[] | Dpos[] | DV[] |
| D | DP[0] = 193 | Dpos_num[0] = 3 | { 0, 1, 7, | { 11, 5, 9, |
| DP[1] = 136 | Dpos_num[1] = 2 | 0, 4 } | 4, 0 } |
그 다음, DV[]에 0이 있는지 검사한다. (편의를 위해 뒤에서부터)
for (k = 0; k < Dt; k++) {
if (!DV[Dt - k - 1]) {
i = (Row * Col) / 8 - 1;
while (i >= 0) {
if (k < Dpos_num[i]) {
DP[i] -= bin[(Dpos[Dt-k-1])];
cnt--;
break;
}
else {
k -= Dpos_num[i];
i--;
}
}
}
}
DV[]의 값이 0이라면, Dpos_num과 k 값을 비교해 몇번째 8bit binary에 있는 값인지 확인하고, 2의 거듭제곱 배열에서 해당 포지션의 값을 찾아 DP에서 빼준다. 그렇게 하면 DP의 해당 비트가 1에서 0이 된다. 쉽게 말해, 해당 8bit세트를 7~0번 자리라고 생각하고, 요소 값이 0인 자리만큼 거듭제곱한 2의 거듭제곱을 10진수화된 binary 값에서 빼는 것이다. Dt를 대입한 cnt에서 0을 찾을 때마다 1씩 빼주어 실제 t값을 계산한다.
printf("row: %d\n", Row);
printf("col: %d\n", Col);
printf("t: %d\n", cnt);
printf("DP[]: ");
for (k = 0; k < (Row * Col) / 8; k++) {
printf("%d ", DP[k]);
}
printf("\n");
printf("DV[]: ");
for (k = 0; k < Dt; k++) {
if (DV[k] == 0) continue;
printf("%d ", DV[k]);
}
printf("\n");DV[]는 0이 아닌 값만 출력한다. 만약 이 행렬을 똑같이 저장하여 다른 연산을 사용할 것이라면, 0을 배열에서 제거하고 뒤의 요소를 하나씩 앞당겨 다시 저장해주어야 한다.
#include <stdio.h>
#define Row 4
#define Col 4
#define A_nonzero_elements 3 // A matrix의 nonzero element의 수
int AP[(Row * Col) / 8] = { 129, 8 }; int AV[A_nonzero_elements] = { 11, 7, -1 };
#define B_nonzero_elements 4 // B matrix의 nonzero element의 수
int BP[(Row * Col) / 8] = { 65, 136 }; int BV[B_nonzero_elements] = { 5, 2, 4, 1 };
int bin[8] = { 128, 64, 32, 16, 8, 4, 2, 1 };
void findpos(int XP[], int XV[], int Xpos[], int Xpos_num[], int X_nonzero)
{
int last, cnt = 0;
int i, j;
for (i = 0; i < (Row * Col) / 8; i++) {
last = XP[i];
Xpos_num[i] = 0;
for (j = 0; j < 8; j++) {
if (last >= bin[j]) {
Xpos[cnt] = j;
cnt++;
Xpos_num[i] ++;
last = last - bin[j];
if (!last) break;
}
}
}
}
int main()
{
int k;
int DP[(Row * Col) / 8];
int DV[A_nonzero_elements + B_nonzero_elements];
int Dt;
int Apos[A_nonzero_elements]; int Apos_num[(Row * Col) / 8];
int Bpos[B_nonzero_elements]; int Bpos_num[(Row * Col) / 8];
int Dpos[A_nonzero_elements + B_nonzero_elements];
int Dpos_num[(Row * Col) / 8];
int i = 0, j = 0;
int cnt = 0;
int Apos_srv = 0, Bpos_srv = 0;
for (k = 0; k < (Row * Col) / 8; k++) DP[k] = AP[k] | BP[k];
findpos(AP, AV, Apos, Apos_num, A_nonzero_elements);
findpos(BP, BV, Bpos, Bpos_num, B_nonzero_elements);
k = 0;
for (k = 0; k < (Row * Col) / 8; k++) {
Apos_srv = Apos_num[k];
Bpos_srv = Bpos_num[k];
while (Apos_srv != 0 || Bpos_srv != 0) {
if (Apos_srv == 0) {
DV[cnt] = BV[j];
cnt++; j++; Bpos_srv--;
continue;
}
else if (Bpos_srv == 0) {
DV[cnt] = AV[i];
cnt++; i++; Apos_srv--;
continue;
}
if (Apos[i] < Bpos[j]) {
DV[cnt] = AV[i];
cnt++; i++; Apos_srv--;
}
else if (Apos[i] > Bpos[j]) {
DV[cnt] = BV[j];
cnt++; j++; Bpos_srv--;
}
else { // Apos[i] == Bpos[j]
DV[cnt] = AV[i] + BV[j];
cnt++; i++; j++; Apos_srv--; Bpos_srv--;
}
}
}
Dt = cnt;
findpos(DP, DV, Dpos, Dpos_num, Dt);
for (k = 0; k < Dt; k++) {
if (!DV[Dt - k - 1]) {
i = (Row * Col) / 8 - 1;
while (i >= 0) {
if (k < Dpos_num[i]) {
DP[i] -= bin[(Dpos[Dt-k-1])];
cnt--;
break;
}
else {
k -= Dpos_num[i];
i--;
}
}
}
}
printf("row: %d\n", Row);
printf("col: %d\n", Col);
printf("t: %d\n", cnt);
printf("DP[]: ");
for (k = 0; k < (Row * Col) / 8; k++) {
printf("%d ", DP[k]);
}
printf("\n");
printf("DV[]: ");
for (k = 0; k < Dt; k++) {
if (DV[k] == 0) continue;
printf("%d ", DV[k]);
}
printf("\n");
return 0;
}'College Computer Science > Data Structure' 카테고리의 다른 글
| [자료구조 프로그래밍 연습문제] 힙 정렬 (heap sort) (0) | 2022.01.28 |
|---|---|
| [자료구조 프로그래밍 연습문제] 연결 리스트 (linked list) invert 함수, 원형 연결 리스트 (circular linked list) (0) | 2022.01.12 |
| [자료구조 프로그래밍 연습문제] maze 미로 경로 찾기 (0) | 2022.01.11 |
| [자료구조 프로그래밍 연습문제] 희소행렬 전치 (0) | 2022.01.11 |
| [자료구조 프로그래밍 연습문제] 다항식 계수 배열, 다항식 곱하기, 구조체 (0) | 2022.01.11 |
댓글