C++中怎么實(shí)現(xiàn)一個(gè)高精度算法

這期內(nèi)容當(dāng)中小編將會(huì)給大家?guī)?lái)有關(guān)C++中怎么實(shí)現(xiàn)一個(gè)高精度算法，文章內(nèi)容豐富且以專(zhuān)業(yè)的角度為大家分析和敘述，閱讀完這篇文章希望大家可以有所收獲。

1. 高精度加法

以3479957928375817 + 897259321544245為例：

+897      +2593      +2154      +4245              =      =      =      =              4376      12172      4991      10062              進(jìn)位0      進(jìn)位1      進(jìn)位0      進(jìn)位1              4377      2172      4992      0062

C語(yǔ)言實(shí)現(xiàn)代碼如下：

#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 200//整數(shù)乘冪運(yùn)算函數(shù)int Pow(int a, int b){  int i = 0, result = 1;  for(i = 0; i < b; ++i)  {    result *= a;  }  return result;}//High Precision Of Additionint main(){  char stra[N], strb[N];   //字符串?dāng)?shù)組，以字符形式儲(chǔ)存兩個(gè)大數(shù)；  int i = 0, step = 4, carry = 0; //step表示塊長(zhǎng)，carry為進(jìn)位位；  int lengtha, lengthb, maxlength, resultsize;  //maxlength表示stra和strb二者長(zhǎng)度較大的那個(gè)；  int numa[N], numb[N],numc[N];  //依次儲(chǔ)存被加數(shù)，加數(shù)，和；  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);   //計(jì)算兩個(gè)大數(shù)的長(zhǎng)度  //字符數(shù)字轉(zhuǎn)為四位一塊的整數(shù)數(shù)字  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;  //逐塊相加，并進(jìn)位  for(i = 0; i <= maxlength/step; ++i)  {    numc[i] = (numa[i] + numb[i])%Pow(10, step) + carry;  //計(jì)算和    carry = (numa[i] + numb[i])/Pow(10, step); //計(jì)算進(jìn)位  }  //計(jì)算最后和的塊的總數(shù)  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]);  //右對(duì)齊，補(bǔ)零輸出；  }  printf("\n");  return 0;}

2. 高精度減法

與加法類(lèi)似，不同的是要注意正負(fù)號(hào)和顯示位數(shù)的變化。以99999037289799 - 100004642015000為例：

先判斷被減數(shù)和減數(shù)哪個(gè)大，顯然這里減數(shù)大，故輸出結(jié)果為負(fù)數(shù)。在用大數(shù)減去小數(shù)，（若某一塊相減為負(fù)數(shù)，則要向高位塊借位）如下表

-99      -9990      -3728      -9799              1      56      473      5201              借位0      借位1      借位0      借位1              0      56      472      5201

C語(yǔ)言實(shí)現(xiàn)代碼如下：

#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 200//整數(shù)乘冪運(yùn)算函數(shù)int Pow(int a, int b){  int i = 0, result = 1;  for(i = 0; i < b; ++i)  {    result *= a;  }  return result;}//High Precision Of Subtractionint main(){  char stra[N], strb[N];   //字符串?dāng)?shù)組，以字符形式儲(chǔ)存兩個(gè)大數(shù)；  int i = 0, step = 4, borrow = 0, mark = 0; //step表示塊長(zhǎng)，borrow為借位位, mark為結(jié)果符號(hào)位；  int lengtha, lengthb, maxlength, resultsize;  //maxlength表示stra和strb二者長(zhǎng)度較大的那個(gè)；  int numa[N], numb[N],numc[N], *maxnum, *minnum;  //依次儲(chǔ)存被減數(shù)，減數(shù)，和；  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);   //計(jì)算兩個(gè)大數(shù)的長(zhǎng)度  maxlength = lengtha >= lengthb ? lengtha : lengthb;  //字符數(shù)字轉(zhuǎn)為四位一塊的整數(shù)數(shù)字  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);  }  //找出較大的數(shù)  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);  //計(jì)算差    borrow = (maxnum[i] - minnum[i] + Pow(10, step) + borrow)/Pow(10, step) - 1; //計(jì)算借位  }  //計(jì)算最后和的塊的總數(shù)  resultsize = maxlength/step;  while(!numc[resultsize])  --resultsize;  printf("%d", mark*numc[resultsize]);  for(i = resultsize-1; i >= 0; --i)  {    printf("%04d", numc[i]);  //右對(duì)齊，補(bǔ)零輸出；  }  printf("\n");  return 0;}

3. 高精度乘法

乘法可以看作是乘數(shù)每一位與被乘數(shù)相乘后再相加，以4296556241 x 56241為例：

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              進(jìn)位（從低位向高位）      241      54304      35100

C語(yǔ)言實(shí)現(xiàn)代碼如下：

#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 200//整數(shù)乘冪運(yùn)算函數(shù)int Pow(int a, int b){  int i = 0, result = 1;  for(i = 0; i < b; ++i)  {    result *= a;  }  return result;}//High Precision Of Multiplicationint main(){  char stra[N], strb[N];   //字符串?dāng)?shù)組，以字符形式儲(chǔ)存兩個(gè)大數(shù)；  int i = 0, j = 0, k = 0, step = 4, carry = 0; //step表示塊長(zhǎng)，carry為進(jìn)位位；  int lengtha, lengthb, resultsize, tmpsize, eachnum; //resultsize儲(chǔ)存塊的總數(shù)，eachnum用來(lái)儲(chǔ)存乘數(shù)的每一位  int numa[N], numb[N], numc[N], tmp[N];  //依次儲(chǔ)存被乘數(shù)數(shù)&積，乘數(shù)；  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);   //計(jì)算兩個(gè)大數(shù)的長(zhǎng)度  //將被乘數(shù)字符數(shù)字轉(zhuǎn)為四位一塊的整數(shù)數(shù)字  for(i = lengtha-1; i >= 0; --i)  {    numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);  }  //將乘數(shù)數(shù)字字符數(shù)字轉(zhuǎn)為一位一塊的整數(shù)數(shù)字  for(i = lengthb-1; i >= 0; --i)  {    numb[lengthb-1-i] = strb[i]-'0';  }  resultsize = tmpsize = (lengtha-1)/step;  //取乘數(shù)的每一位與被乘數(shù)的逐塊相乘，并進(jìn)位；  for(i = 0; i < lengthb; ++i)  {    memcpy(tmp, numa, sizeof(numa));  //將numa數(shù)組賦值給tmp數(shù)組；    k = i/step;   //k儲(chǔ)存每一塊需要向高位塊移動(dòng)的次數(shù)；    if(k)    {      for(j = tmpsize; j >= 0; --j)      {        tmp[j+k] = tmp[j];        tmp[j] = 0;      }      tmpsize += k;    }    //乘以乘數(shù)每一位擴(kuò)展成的塊；    eachnum = numb[i]*Pow(10, i%step);    for(j = 0; j <= tmpsize; ++j)    {      tmp[j] *= eachnum;    }    //大數(shù)相加    carry = 0; //進(jìn)位置零；    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]);  //右對(duì)齊，補(bǔ)零輸出；  }  printf("\n");  return 0;}

4. 高精度除法

高精度除法有兩種，一種是高精度除以低精度，另一種是高精度除以高精度。前者只需將每一塊除以低精度除數(shù)即可；后者則考慮用高精度減法來(lái)實(shí)現(xiàn)，即每次減去高精度除數(shù)，直到減到小于除數(shù)，則減的次數(shù)即為商，剩余的即為余數(shù)。

高精度除以低精度以9876342876 / 343為例：

商      0      2879      4002

C語(yǔ)言代碼實(shí)現(xiàn)如下：

#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 200//整數(shù)乘冪運(yùn)算函數(shù)int Pow(int a, int b){  int i = 0, result = 1;  for(i = 0; i < b; ++i)  {    result *= a;  }  return result;}//High Precision Of pision//(1)高精度除以低精度int main(){  char stra[N];   //字符串?dāng)?shù)組，以字符形式儲(chǔ)存高精度被除數(shù)；  int i = 0, step = 4, carry = 0; //step表示塊長(zhǎng)，carry為高位向低位進(jìn)位位；  int lengtha, resultsize;  int numa[N], numb, numc[N], numd;  //依次儲(chǔ)存被除數(shù)，除數(shù)，商, 余數(shù)；  memset(numa, 0, sizeof(numa));  memset(numc, 0, sizeof(numc));     //初始化為零；  scanf("%s%d", stra, &numb);  lengtha = strlen(stra);  //計(jì)算被除數(shù)的長(zhǎng)度  //字符數(shù)字轉(zhuǎn)為四位一塊的整數(shù)數(shù)字  for(i = lengtha-1; i >= 0; --i)  {    numa[(lengtha-1-i)/step] += (stra[i]-'0')*Pow(10,(lengtha-1-i)%step);  }  carry = 0; //高位向低位進(jìn)位位置零  resultsize = (lengtha-1)/step;  //逐塊相除，高位向低位進(jìn)位  for(i = resultsize; i >= 0; --i)  {    numc[i] = (numa[i] + carry*Pow(10,step))/numb;  //計(jì)算商    carry = (numa[i] + carry*Pow(10,step))%numb; //計(jì)算進(jìn)位  }  numd = carry;  //最低位塊的余數(shù)即為整個(gè)除法的余數(shù)  //計(jì)算最后和的塊的總數(shù)  while(!numc[resultsize])  --resultsize;  //輸出商  printf("%d", numc[resultsize]);  for(i = resultsize-1; i >= 0; --i)  {    printf("%04d", numc[i]);  //右對(duì)齊，補(bǔ)零輸出；  }  //輸出余數(shù)  printf("\n%d\n", numd);  return 0;}

高精度除以高精度以176342876 / 3453452為例：

- (51 x除數(shù))      51 x 3453452              余數(shù)      216824              商      51

C語(yǔ)言代碼實(shí)現(xiàn)如下：

#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 200//整數(shù)乘冪運(yùn)算函數(shù)int Pow(int a, int b){  int i = 0, result = 1;  for(i = 0; i < b; ++i)  {    result *= a;  }  return result;}//High Precision Of pision//(2)高精度除以高精度int main(){  char stra[N], strb[N];   //字符串?dāng)?shù)組，以字符形式儲(chǔ)存兩個(gè)大數(shù)；  int i = 0, step = 4, borrow = 0; //step表示塊長(zhǎng)，borrow為進(jìn)位位；  int lengtha, lengthb, tmpnum, numbsize, numcsize, numdsize, maxsize, mark;  //maxlength表示stra和strb二者長(zhǎng)度較大的那個(gè)；  int numa[N], numb[N], numc[N], numd[N];  //依次儲(chǔ)存被除數(shù)數(shù)，除數(shù)數(shù)，商，余數(shù)；  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);   //計(jì)算兩個(gè)大數(shù)的長(zhǎng)度  //字符數(shù)字轉(zhuǎn)為四位一塊的整數(shù)數(shù)字  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;    //計(jì)算剩余數(shù)是否小于除數(shù)    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;      }    }    //判斷是否余數(shù)已經(jīng)小于除數(shù)    if(!(mark+1))  break;    borrow = 0; //借位置零；    //逐塊相減，并借位    for(i = 0; i <= maxsize; ++i)    {      tmpnum = (numd[i] - numb[i] + Pow(10, step) + borrow)%Pow(10,step);  //計(jì)算差      borrow = (numd[i] - numb[i] + Pow(10, step) + borrow)/Pow(10,step) - 1; //計(jì)算借位      numd[i] = tmpnum;    }    while(!numd[numdsize]) --numdsize;    //每減一個(gè)除數(shù)，商加一；    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]);  //右對(duì)齊，補(bǔ)零輸出；  }  printf("\n");  printf("%d", numd[numdsize]);  for(i = numdsize-1; i >= 0; --i)  {    printf("%04d", numd[i]);  //右對(duì)齊，補(bǔ)零輸出；  }  printf("\n");  return 0;}

上述就是小編為大家分享的C++中怎么實(shí)現(xiàn)一個(gè)高精度算法了，如果剛好有類(lèi)似的疑惑，不妨參照上述分析進(jìn)行理解。如果想知道更多相關(guān)知識(shí)，歡迎關(guān)注億速云行業(yè)資訊頻道。