欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C/C++高精度算法的實(shí)現(xiàn)

 更新時(shí)間：2020年02月02日 10:08:20   作者：孤獨(dú)な霊魂  
這篇文章主要介紹了C/C++高精度算法的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧

做ACM題的時(shí)候，經(jīng)常遇到大數(shù)的加減乘除，乘冪，階乘的計(jì)算，這時(shí)給定的數(shù)據(jù)類型往往不夠表示最后結(jié)果，這時(shí)就需要用到高精度算法。高精度算法的本質(zhì)是把大數(shù)拆成若干固定長(zhǎng)度的塊，然后對(duì)每一塊進(jìn)行相應(yīng)的運(yùn)算。這里以考慮4位數(shù)字為一塊為例，且輸入的大數(shù)均為正整數(shù)（也可以考慮其他位，但要注意在每一塊進(jìn)行相應(yīng)運(yùn)算時(shí)不能超出數(shù)據(jù)類型的數(shù)值范圍；有負(fù)整數(shù)的話讀入時(shí)判斷一下正負(fù)號(hào)在決定運(yùn)算）。

1. 高精度加法

以3479957928375817 + 897259321544245為例：

3479 9579 2837 5817
+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語言實(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 Addition
int 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. 高精度減法

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

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

100 0046 4201 5000
-99 -9990 -3728 -9799
1 56 473 5201
借位0 借位1 借位0 借位1
0 56 472 5201

C語言實(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 Subtraction
int 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為例：

被乘數(shù) 42 9655 6241
乘數(shù) 5 6 2 4 1
被乘數(shù)x乘數(shù) 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
進(jìn)位（從低位向高位） 241 54304 35100
積 241 6426 1955 0081

C語言實(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 Multiplication
int 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用來儲(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ù)即可；后者則考慮用高精度減法來實(shí)現(xiàn)，即每次減去高精度除數(shù)，直到減到小于除數(shù)，則減的次數(shù)即為商，剩余的即為余數(shù)。

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

被除數(shù) 98 7634 2876
除數(shù) 343
向低位塊進(jìn)位 98 137 190
商 0 2879 4002
余數(shù) 190

C語言代碼實(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 division
//(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為例：

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

C語言代碼實(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 division
//(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;
}

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

相關(guān)文章

  • 關(guān)于C++友元函數(shù)的實(shí)現(xiàn)講解

    關(guān)于C++友元函數(shù)的實(shí)現(xiàn)講解

    今天小編就為大家分享一篇關(guān)于關(guān)于C++友元函數(shù)的實(shí)現(xiàn)講解，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧
    2018-12-12
  • 關(guān)于C++為什么不加入垃圾回收機(jī)制解析

    關(guān)于C++為什么不加入垃圾回收機(jī)制解析

    C++為什么不加入垃圾回收機(jī)制呢？現(xiàn)在肯定還有很多人不太了解，不過沒關(guān)系，下面小編就為大家詳細(xì)的介紹下究竟C++為什么不加入垃圾回收機(jī)制。一起跟隨小編過來看看吧
    2017-01-01
  • C語言浮點(diǎn)型數(shù)據(jù)在內(nèi)存中的存儲(chǔ)方式詳解

    C語言浮點(diǎn)型數(shù)據(jù)在內(nèi)存中的存儲(chǔ)方式詳解

    任何數(shù)據(jù)在內(nèi)存中都是以二進(jìn)制的形式存儲(chǔ)的,例如一個(gè)short型數(shù)據(jù)1156，其二進(jìn)制表示形式為00000100 10000100,下面這篇文章主要給大家介紹了關(guān)于C語言浮點(diǎn)型數(shù)據(jù)在內(nèi)存中的存儲(chǔ)方式,需要的朋友可以參考下
    2023-03-03
  • C++俄羅斯方塊游戲 無需圖形庫的俄羅斯方塊

    C++俄羅斯方塊游戲 無需圖形庫的俄羅斯方塊

    這篇文章主要為大家詳細(xì)介紹了無需圖形庫的C++俄羅斯方塊游戲，重溫經(jīng)典游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
    2016-06-06
  • VSCode遠(yuǎn)程開發(fā)調(diào)試服務(wù)器c/c++代碼

    VSCode遠(yuǎn)程開發(fā)調(diào)試服務(wù)器c/c++代碼

    語音相關(guān)的好多項(xiàng)目要在linux上跑，但代碼開發(fā)大多是在PC機(jī)上，本篇簡(jiǎn)單介紹一下怎么在個(gè)人電腦上用VSCode遠(yuǎn)程開發(fā)調(diào)試服務(wù)器上的c/c++代碼。感興趣的朋友跟隨小編一起看看吧
    2020-04-04
  • 淺談C++ 虛函數(shù)分析

    淺談C++ 虛函數(shù)分析

    這篇文章主要介紹了淺談C++ 虛函數(shù)分析，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-02-02
  • C++實(shí)現(xiàn)LeetCode(57.插入?yún)^(qū)間)

    C++實(shí)現(xiàn)LeetCode(57.插入?yún)^(qū)間)

    這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(57.插入?yún)^(qū)間),本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-07-07
  • C++異常處理方式實(shí)例詳解(超級(jí)詳細(xì)!)

    C++異常處理方式實(shí)例詳解(超級(jí)詳細(xì)!)

    程序有時(shí)會(huì)遇到運(yùn)行階段錯(cuò)誤,導(dǎo)致程序無法正常執(zhí)行下去,c++異常為處理這種情況提供了一種功能強(qiáng)大的而靈活的工具,下面這篇文章主要給大家介紹了關(guān)于C++異常處理方式的相關(guān)資料,需要的朋友可以參考下
    2023-04-04
  • 使用C++實(shí)現(xiàn)Range序列生成器的示例代碼

    使用C++實(shí)現(xiàn)Range序列生成器的示例代碼

    在C++編程中,經(jīng)常需要迭代一系列數(shù)字或其他可迭代對(duì)象,本文將使用C++來實(shí)現(xiàn)一個(gè)簡(jiǎn)單的Range封裝,文中的示例代碼講解詳細(xì),感興趣的可以了解下
    2023-11-11
  • 利用Matlab復(fù)刻掃雷小游戲

    利用Matlab復(fù)刻掃雷小游戲

    windows自帶的游戲《掃雷》是陪伴了無數(shù)人的經(jīng)典游戲，本程序參考《掃雷》的規(guī)則進(jìn)行了簡(jiǎn)化，用Matlab實(shí)現(xiàn)，感興趣的小伙伴可以學(xué)習(xí)一下
    2022-03-03

最新評(píng)論