분할정복법을 이용한 큰정수의 곱셈

소개글

분할정복법을 이용한 큰정수의 곱셈에 대한 보고서 자료입니다.

본문내용

(char *)malloc(total*sizeof(char));
resultM = (char *)malloc(total*sizeof(char));
//문자열 초기화
strInit(Ah); strInit(Al); strInit(Bh); strInit(Bl);
strInit(result); strInit(resultH); strInit(resultL); strInit(resultM);
//두 숫자중 한자리만 자릿수 범위 내 허용된 숫자가 입력된 경우를 대비해서
for(i=0;i Al[i] = A[i];
Bl[i] = B[i];
}
Al[rem]=0; Bl[rem]=0;//최종 자리는 무조건 null(끝을 확인하기 위해서)
for(i=rem;i Ah[i-rem] = A[i];
Bh[i-rem] = B[i];
}
Ah[exp]=0; Bh[exp]=0;//최종 자리는 무조건 null(끝을 확인하기 위해서)
strrev(Ah);strrev(Al);strrev(Bh);strrev(Bl); //문자열 뒤집어서 저장
//result = ac*10^2m + (ad+bc)*10^m + bd라고 두었을 때,
strcpy(resultH,prod(Ah,Bh)); //윗자리를 곰셈해서 resultH 에 저장(a*b*10^2m에 대한 결과의 임시 저장장소)
resultM = bigIntPlus(prod(Ah,Bl),prod(Bh,Al)); //중간자리를 덧셈해서 저장((ad+bc)*10^m에 대한 결과의 저장장소)
strcpy(resultL,prod(Al,Bl));//아랫자리 곰셈해서 resultL에 저장(bd에 대한 결과의 저장장소)
max = strlen(resultH);
if(resultH[0] == 0||resultH[0] == '0') resultH[0]= 0;
else {
for(i=max;i<(max+2*rem);i++) resultH[i] = '0';//자릿수 맞추기 2*rem
resultH[max+2*rem] = 0;
}
max = strlen(resultM);
if(resultM[0] == 0||resultM[0] == '0') resultM[0] = 0;
else {
for(i=max;i<(max+rem);i++) resultM[i] = '0';//자릿수 맞추기 rem
resultM[max+rem] = 0;
}
result = bigIntPlus((bigIntPlus(resultH, resultM)), resultL); // 각 자리에 대한 최종 결과를 큰수 덧샘을 통해 덧셈.
}
return result;
}
void main()
{
char inA[SMALL], inB[SMALL], result[SMALL*2];
int cnt=0, max;
strInit(inA);
strInit(inB);
printf("첫번째 정수 입력 : ");
scanf("%s",&inA);
printf("두번째 정수 입력 : ");
scanf("%s",&inB);
max = (strlen(inA)>strlen(inB)) ? strlen(inA) : strlen(inB);
strcpy(result,prod(inA,inB)); //결과값 저장 배열
printf("\n---------결과정리----------\n");
printf("첫번째 입력정수: %s\n", inA);
printf("두번째 입력정수: %s\n", inB);
printf("곱셈 결과 :%s\n", result);
}
○ 결과 화면
1) 작은 수 곱셈
2) 큰 정수와 작은 수 곱셈
3) 큰 정수와 큰 정수의 곱셈

키워드

알고리즘,   분할정복,   큰수곱셈,   큰정수곱셈,   단국대