C/C++고정 밀 알고리즘 의 실현

ACM 문 제 를 풀 때 큰 수의 덧셈 과 곱셈,곱셈,곱셈 의 계산 을 자주 만 나 는데 이때 주어진 데이터 유형 은 마지막 결 과 를 나타 내지 못 하기 때문에 이때 높 은 정밀도 알고리즘 을 사용 해 야 한다.고정 밀 알고리즘 의 본질은 대 수 를 약간의 고정 길이 의 블록 으로 분해 한 다음 에 각 조각 에 대해 상응하는 연산 을 하 는 것 이다.여기 서 4 자리 숫자 를 한 조각 으로 예 를 들 어 입력 한 대 수 는 모두 정수(다른 비트 도 고려 할 수 있 지만 각 조각 이 해당 하 는 연산 을 할 때 데이터 형식의 수치 범 위 를 초과 해 서 는 안 된다 는 것 을 주의해 야 한다.음정 수가 있 으 면 읽 을 때 양음 호 를 판단 하여 연산 을 결정 한다.
1.고밀도 덧셈
3479957928375817+897259321544245 를 예 로 들 면:
3479
9579
2837
5817
+897
+2593
+2154
+4245
=
=
=
=
4376
12172
4991
10062
진위
진위
진위
진위
4377
2172
4992
0062
C 언어 구현 코드 는 다음 과 같 습 니 다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//        
int Pow(int a, int b)
{
  int i = 0, result = 1;
  for(i = 0; i < b; ++i)
  {
    result *= a;
  }
  return result;
}


//High Precision Of Addition
int main()
{
  char stra[N], strb[N];   //     ,           ;
  int i = 0, step = 4, carry = 0; //step    ,carry    ;
  int lengtha, lengthb, maxlength, resultsize;  //maxlength  stra strb         ;
  int numa[N], numb[N],numc[N];  //       ,  , ;
  memset(numa, 0, sizeof(numa));
  memset(numb, 0, sizeof(numb));
  memset(numc, 0, sizeof(numc));     //     ;
  scanf("%s%s", stra, strb);
  lengtha = strlen(stra);
  lengthb = strlen(strb);   //         
  //               
  for(i = lengtha-1; i >= 0; --i)
  {
    numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
  }
  for(i = lengthb-1; i >= 0; --i)
  {
    numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
  }
  maxlength = lengtha > lengthb ? lengtha : lengthb;

  //    ,   
  for(i = 0; i <= maxlength/step; ++i)
  {
    numc[i] = (numa[i] + numb[i])%Pow(10, step) + carry;  //   
    carry = (numa[i] + numb[i])/Pow(10, step); //    
  }

  //          
  resultsize = numc[maxlength/step] > 0 ? maxlength/step : maxlength/step - 1;
  printf("%d", numc[resultsize]);
  for(i = resultsize-1; i >= 0; --i)
  {
    printf("%04d", numc[i]);  //   ,    ;
  }
  printf("
"); return 0; }
2.고밀도 감법
덧셈 과 유사 하 게 양음 호 와 자릿수 변 화 를 주의해 야 한다.99999037289799-10000464215000 을 예 로 들 면:
먼저 피 감수 와 감수 가 어느 것 이 큰 지 판단 하고 여기 서 감수 가 큰 것 이 분명 하기 때문에 수출 결 과 는 마이너스 이다.대수 로 소 수 를 빼 면 다음 과 같다.
100
0046
4201
5000
-99
-9990
-3728
-9799
1
56
473
5201
자리
차석
자리
차석
0
56
472
5201
C 언어 구현 코드 는 다음 과 같 습 니 다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//        
int Pow(int a, int b)
{
  int i = 0, result = 1;
  for(i = 0; i < b; ++i)
  {
    result *= a;
  }
  return result;
}

//High Precision Of Subtraction
int main()
{
  char stra[N], strb[N];   //     ,           ;
  int i = 0, step = 4, borrow = 0, mark = 0; //step    ,borrow    , mark      ;
  int lengtha, lengthb, maxlength, resultsize;  //maxlength  stra strb         ;
  int numa[N], numb[N],numc[N], *maxnum, *minnum;  //       ,  , ;
  memset(stra, 0, sizeof(stra));
  memset(strb, 0, sizeof(strb));
  memset(numa, 0, sizeof(numa));
  memset(numb, 0, sizeof(numb));
  memset(numc, 0, sizeof(numc));     //     ;
  scanf("%s%s", stra, strb);
  lengtha = strlen(stra);
  lengthb = strlen(strb);   //         
  maxlength = lengtha >= lengthb ? lengtha : lengthb;

  //               
  for(i = lengtha-1; i >= 0; --i)
  {
    numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
  }
  for(i = lengthb-1; i >= 0; --i)
  {
    numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
  }

  //      
  maxnum = numa;
  minnum = numb;
  mark = 1;
  for(i = (maxlength-1)/step; i >= 0; --i)
  {
    if(numa[i] > numb[i])
    {
      maxnum = numa;
      minnum = numb;
      mark = 1;
      break;
    }
    else if(numa[i] < numb[i])
    {
      maxnum = numb;
      minnum = numa;
      mark = -1;
      break;
    }
  }

  //    ,   
  for(i = 0; i <= maxlength/step; ++i)
  {
    numc[i] = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)%Pow(10,step);  //   
    borrow = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)/Pow(10, step) - 1; //    
  }

  //          
  resultsize = maxlength/step;
  while(!numc[resultsize])  --resultsize;
  printf("%d", mark*numc[resultsize]);
  for(i = resultsize-1; i >= 0; --i)
  {
    printf("%04d", numc[i]);  //   ,    ;
  }
  printf("
"); return 0; }
3.고밀도 곱셈
곱셈 은 곱셈 의 한 사람과 피 곱셈 을 곱 한 후에 더 한 것 으로 볼 수 있 으 며 4296556241 x 56241 을 예 로 들 수 있다.
피승수
42
9655
6241
승수
5
6
2
4
1
피승수 x 승수
42
9655
6241
1
42
9655
6241
4
168*10
38620*10
24964*10
2
84*100
19310*100
12482*100
6
252*1000
57930*1000
37446*1000
5
210*10000
48275*10000
31205*10000
누가화
2362122
543006855
351000081
진입(낮은 위치 에서 높 은 위치 로)
241
54304
35100
쌓이다
241
6426
1955
0081
C 언어 구현 코드 는 다음 과 같 습 니 다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//        
int Pow(int a, int b)
{
  int i = 0, result = 1;
  for(i = 0; i < b; ++i)
  {
    result *= a;
  }
  return result;
}


//High Precision Of Multiplication
int main()
{
  char stra[N], strb[N];   //     ,           ;
  int i = 0, j = 0, k = 0, step = 4, carry = 0; //step    ,carry    ;
  int lengtha, lengthb, resultsize, tmpsize, eachnum; //resultsize      ,eachnum          
  int numa[N], numb[N], numc[N], tmp[N];  //        & ,  ;
  memset(numa, 0, sizeof(numa));
  memset(numb, 0, sizeof(numb));
  memset(numc, 0, sizeof(numc)); //     ;
  scanf("%s%s", stra, strb);
  lengtha = strlen(stra);
  lengthb = strlen(strb);   //         
  //                   
  for(i = lengtha-1; i >= 0; --i)
  {
    numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
  }
  //                    
  for(i = lengthb-1; i >= 0; --i)
  {
    numb[lengthb-1-i] = strb[i]-'0';
  }

  resultsize = tmpsize = (lengtha-1)/step;
  //                ,   ;
  for(i = 0; i < lengthb; ++i)
  {
    memcpy(tmp, numa, sizeof(numa));  // numa     tmp  ;

    k = i/step;   //k                ;
    if(k)
    {
      for(j = tmpsize; j >= 0; --j)
      {
        tmp[j+k] = tmp[j];
        tmp[j] = 0;
      }
      tmpsize += k;
    }

    //            ;
    eachnum = numb[i]*Pow(10, i%step);
    for(j = 0; j <= tmpsize; ++j)
    {
      tmp[j] *= eachnum;
    }

    //    
    carry = 0; //    ;
    for(j = 0; j <= resultsize; ++j)
    {
      numc[j] += tmp[j] + carry;
      carry = numc[j]/Pow(10,step);
      numc[j] %= Pow(10, step);
    }
    if(carry)
    {
      ++resultsize;
      numc[j] += carry;
    }
  }

  //  
  printf("%d", numc[resultsize]);
  for(i = resultsize-1; i >= 0; --i)
  {
    printf("%04d", numc[i]);  //   ,    ;
  }
  printf("
"); return 0; }
4.고정 밀 제법
높 은 정밀도 나 누 기 는 두 가지 가 있 는데 하 나 는 높 은 정밀도 로 낮은 정밀도 로 나 누 는 것 이 고 다른 하 나 는 높 은 정밀도 로 높 은 정밀도 로 나 누 는 것 이다.전 자 는 각 조각 을 저 정밀도 로 나 누 면 된다.후 자 는 높 은 정밀도 의 감법 으로 실현 하 는 것 을 고려 했다.즉,매번 높 은 정밀도 의 나 누 기 를 줄 이 고 나 누 기 보다 적 을 때 까지 줄 이 는 횟수 는 바로 상업 이 고 나머지 는 나머지 이다.
고밀도
9876342876/343 을 예 로 들 면:
피제수
98
7634
2876
제수
343
낮은 블록 으로 진입
98
137
190
상의 하 다.
0
2879
4002
나머지
190
C 언어 코드 는 다음 과 같다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//        
int Pow(int a, int b)
{
  int i = 0, result = 1;
  for(i = 0; i < b; ++i)
  {
    result *= a;
  }
  return result;
}

//High Precision Of division
//(1)        
int main()
{
  char stra[N];   //     ,             ;
  int i = 0, step = 4, carry = 0; //step    ,carry         ;
  int lengtha, resultsize;
  int numa[N], numb, numc[N], numd;  //       ,  , ,   ;
  memset(numa, 0, sizeof(numa));
  memset(numc, 0, sizeof(numc));     //     ;
  scanf("%s%d", stra, &numb);
  lengtha = strlen(stra);  //        

  //               
  for(i = lengtha-1; i >= 0; --i)
  {
    numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
  }

  carry = 0; //          
  resultsize = (lengtha-1)/step;
  //    ,       
  for(i = resultsize; i >= 0; --i)
  {
    numc[i] = (numa[i] + carry*Pow(10,step))/numb;  //   
    carry = (numa[i] + carry*Pow(10,step))%numb; //    
  }
  numd = carry;  //                

  //          
  while(!numc[resultsize])  --resultsize;
  //   
  printf("%d", numc[resultsize]);
  for(i = resultsize-1; i >= 0; --i)
  {
    printf("%04d", numc[i]);  //   ,    ;
  }
  //    
  printf("
%d
", numd); return 0; }
고밀도
176342876/3453453452 를 예 로 들 면:
피제수
176342876
- (51 x 나눗셈
51 x 3453452
나머지
216824
상의 하 다.
51
C 언어 코드 는 다음 과 같다.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200

//        
int Pow(int a, int b)
{
  int i = 0, result = 1;
  for(i = 0; i < b; ++i)
  {
    result *= a;
  }
  return result;
}

//High Precision Of division
//(2)        
int main()
{
  char stra[N], strb[N];   //     ,           ;
  int i = 0, step = 4, borrow = 0; //step    ,borrow    ;
  int lengtha, lengthb, tmpnum, numbsize, numcsize, numdsize, maxsize, mark;  //maxlength  stra strb         ;
  int numa[N], numb[N], numc[N], numd[N];  //        ,   , ,  ;
  memset(stra, 0, sizeof(stra));
  memset(strb, 0, sizeof(strb));
  memset(numa, 0, sizeof(numa));
  memset(numb, 0, sizeof(numb));
  memset(numc, 0, sizeof(numc));
  memset(numd, 0, sizeof(numd));   //     ;
  scanf("%s%s", stra, strb);
  lengtha = strlen(stra);
  lengthb = strlen(strb);   //         

  //               
  for(i = lengtha-1; i >= 0; --i)
  {
    numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);
  }
  for(i = lengthb-1; i >= 0; --i)
  {
    numb[(lengthb-1-i)/step] += (strb[i]-'0')*Pow(10,(lengthb-1-i)%step);
  }
  memcpy(numd, numa, sizeof(numa));
  numbsize = (lengthb-1)/step;
  numcsize = 0;
  numdsize = (lengtha-1)/step;

  do
  {
    maxsize = numdsize > numbsize ? numdsize : numbsize;
    //           
    mark = 1;
    for(i = maxsize; i >= 0; --i)
    {
      if(numd[i] > numb[i])
      {
        mark = 1;
        break;
      }
      else if(numd[i] < numb[i])
      {
        mark = -1;
        break;
      }
    }

    //            
    if(!(mark+1))  break;

    borrow = 0; //    ;
    //    ,   
    for(i = 0; i <= maxsize; ++i)
    {
      tmpnum = (numd[i] - numb[i] + Pow(10, step) + borrow)%Pow(10,step);  //   
      borrow = (numd[i] - numb[i] + Pow(10, step) + borrow)/Pow(10,step) - 1; //    
      numd[i] = tmpnum;
    }
    while(!numd[numdsize]) --numdsize;

    //      ,   ;
    borrow = 1;
    for(i = 0; i <= numcsize; ++i)
    {
      numc[i] += borrow;
      borrow = numc[i]/Pow(10,step);
      numc[i] %= Pow(10,step);
    }
    if(borrow)
    {
      ++numcsize;
      numc[i] += borrow;
    }
  }while(1);

  printf("%d", numc[numcsize]);
  for(i = numcsize-1; i >= 0; --i)
  {
    printf("%04d", numc[i]);  //   ,    ;
  }
  printf("
"); printf("%d", numd[numdsize]); for(i = numdsize-1; i >= 0; --i) { printf("%04d", numd[i]); // , ; } printf("
"); return 0; }
이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.

좋은 웹페이지 즐겨찾기