第十一章：高精度算法

高精度算法高精度加法例题1：高精度加法1157

题目描述

计算两个非负整数之和

输入输出格式

输入

从键盘上输入两个非负整数，每个数占一行，每个数的位数不超过240.

输出

输出只有一行为两个数之和。

样例

输入1

12
13

Copy

输出1

Copy

时间及空间限制

1s, 256MB.

解题分析：

很明显在题目中提到了每个数的位数不超过240，显然题目的输出结果肯定会超出了unsigned long long的取值范围。因此简单的将两个超大数加起来是行不通的，实际生活例如这样的例子有很多，那么如何解决两个超大数相加的问题呢？我相信很多同学都会想到利用字符串去实现，实际上我们的确是运用字符串的方法，那么具体又该如何利用字符串的知识去实现两个超大数的相加问题呢？这就是本节课的重点。

用字符串来模拟非常长的整数，这意味着可以用字符数组的每位记录那个数字上的每一位。

解决了存储问题之后，再来回顾一下竖式加法：

整式加法的实质就是模拟每一位的加法与进位，对于十进制加法来说，某-位上的和超过9附会产生进位现象，进位就是保留那处数字的个位数，然后把十位上的数字加给下一位去，详见下图：

思考：假设正整数A的长度为n，正整数B的长度为m，那么A+B的长度最大为多少?最小为多少?

答∶ ①max(n,m)+ 1; ②max(n,m); 

高精度加法的解题步骤：

①高精度数的读取与存储∶使用字符串方式读取，然后转换为整数，逆向存储到整型数组

②高精度数的加法∶通过数组下标模拟两个加数中每一个位上数的加法 

③去除前导0后，逆向输出。 

完整代码如下：

#include
using namespace std;
int c[1005],d[1005],e[1005];
//c，d分别存2个加数，e存和 
int main()
{
  //1--把2个加数存放到字符串中，再倒置到int 数组中（c,d） 
  string a,b;
  cin>>a>>b;
  int cxb=1,dxb=1,len1=a.size(),len2=b.size();
  for(int i=len1-1;i>=0;i--)
  {
    c[cxb]=a[i]-48;//a[i]-'0'
    cxb++;
  }
  for(int i=len2-1;i>=0;i--)
  {
    d[dxb]=b[i]-48;
    dxb++;
  }
  //2--确定一下和的终点下标
  int zd=max(len1,len2)+1;
  //3--进行逐位的求和
  for(int i=1;i<=zd;i++)
  {
     int t=c[i]+d[i];
     e[i]+=t;
     e[i+1]+=e[i]/10;
     e[i]%=10;
  } 
  //4--讨论终点下标
  if(e[zd]==0)  zd--;
  //5--逆序输出e数组
  for(int i=zd;i>=1;i--)
  {
    cout< 
Copy 
例题2：A+B Problem（主题库2607） 
题目描述 
高精度加法。输入两个正整数，求它们的和。 
输入输出格式 
输入 
输入两行，每行为一个高精度整数（非负数，长度不超过255）。 
输出 
输出一行，相加的结果。 
样例 
输入1 
2222555555555555
8888999999999999
 
Copy 
输出1 
11111555555555554
 
Copy 
时间及空间限制 
1s, 256MB.
 说明：本题加数可能带若干个前导0 
代码解析： 
#include 
using namespace std;

string add(string a, string b)
{
    string ans;
    // 翻转，使个位在前
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    // 预处理，方便后面按位相加
    a.push_back('0');  b.push_back('0');
    if(a.size() < b.size()) swap(a, b);
    // 短的数字高位补零
    while(b.size() < a.size()) b.push_back('0');
    // 按位累加，模拟加法
    int c[1000]={0}, k = a.size();
    for(int i = 0; i < a.size(); i++)
    {
        int s = c[i] + a[i]-'0' + b[i] - '0';
        c[i] = s%10;
        c[i+1] += s/10;
    }
    // 去除高位零
    while(c[k]==0 && k>=0) k--;
    // 输出
    while(k >= 0)
        ans.push_back(c[k--]+'0');
    return ans;
}

int main()
{
    string a, b;
    cin >> a >> b;
    cout << add(a, b);
    return 0;
}
 
Copy 
高精度减法 
例题1：高精度减法 
题目描述 
计算两个非负整数之差 
输入输出格式 
输入 
从键盘上输入两个非负整数，每个数占一行，每个数的位数不超过240. 
输出 
输出只有一行为两个数之差。 
样例 
输入1 
12
13
 
Copy 
输出1 
-1
 
Copy 
时间及空间限制 
1s, 256MB. 
解题思路： 
已知大正整数a和b，且a>b。求a-b的值。 

 
 
①如果a[i] 
②模拟减法∶c[i]= a[i] -b[i]; 
思考：如果a[i+1] == 0，这样借位是否会出问题? 
不会。因为最多借1位，即使a[i+1]被借位后等于-1，因为a>b，a[i+1]还可以向a[i+2]借位。借位后a[i+1]等于9，而b[i+1]最大为9。 
高精度减法解题步骤： 
①高精度数的读取存储∶ 使用字符串方式读取，然后转成整型数组，为方便计算，进行逆向存储。 
②模拟竖式进行减法∶ 相同位置进行相减，不够减时进行借位 
③去除前导0后，逆向输出。 
思考：两个正整数a和b，且a>b，a的长度为n，b的长度为m，那么c= a-b最长为多少? 
答案： n 
思考：两个正整数a和b，如果判断a和b的大小? 
答案：(a.size() 
思考：如果a 
答案：交换a和b的值，后计算a-b，结果输出一个负号 
思考：在大整数加法中，如果有一个数是负数如何处理? 
转换为大整数减法处理。 
思考：在大整数加法中，两个数都是负数如何处理? 
转换为正高精度正整数加法，输出结果时加上负号 
完整代码如下： 
#include
using namespace std;
int c[1005],d[1005],e[1005];
//c被减数，d减数，e差 
int main()
{
  //1--将两个减数存放到字符串中
  string a,b;
  cin>>a>>b;
  //2--讨论a，b的大小关系，并进行相应的处理
  if(a==b)
  {
    cout<<0;return 0; 
  } 
  if(a.size()=0;i--)
  {
    c[cxb]=a[i]-48;cxb++;
  }
  for(int i=len2-1;i>=0;i--)
  {
    d[dxb]=b[i]-48;dxb++;
  }
  //4--确定差的终点下标
  int zd=len1;
  //5--从最低位开始减
  int k=0;//1代表借了一位，0代表没有借位 
  for(int i=1;i<=zd;i++)
  {
     e[i]=c[i]-d[i]-k;
     if(e[i]<0)
     {
        k=1;
        e[i]+=10;
     }
     else
     {
        k=0;
     } 
 } 
 //6--讨论最高位为0的情况 
 while(e[zd]==0 && zd>=1) 
 {
    zd--;
 }
 //7--逆序输出e数组
 for(int i=zd;i>=1;i--) cout< 
Copy 
例题2：A-B Problem（高精度减法）（主题库2608） 
题目描述 
高精度减法。输入两个正整数，求它们的差。 
输入输出格式 
输入 
输入两行，每行为一个高精度整数，长度不超过255。 
输出 
输出相减的结果。 
样例 
输入1 
12345
45678
 
Copy 
输出1 
-33333
 
Copy 
时间及空间限制 
1s, 256MB. 
完整代码如下： 
#include
#include
using namespace std;

const int N = 1e6+5;

string sub(string a, string b)
{
    string ans;
    bool flag = false;
    if(a.size() < b.size() || (a.size()==b.size() && a < b))
    {
        swap(a, b);
        flag = true;    
    }
    // 翻转，使个位在前
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    // 预处理，方便后面按位相减
    a.push_back('0');  b.push_back('0');
    if(a.size() < b.size()) swap(a, b);
    // 短的数字高位补零
    while(b.size() < a.size()) b.push_back('0');
    // 按位相减，模拟减法
    int c[1000]={0}, k = a.size();
    for(int i = 0; i < a.size(); i++)
    {
        if(a[i] < b[i]) a[i]+=10, a[i+1]--;
        c[i] = a[i] - b[i];
    }
    // 去除高位零
    while(c[k]==0 && k>=0) k--;
    // 输出
    if(flag) ans.push_back('-');
    while(k >= 0)
        ans.push_back(c[k--]+'0');
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    string a, b;
    cin >> a >> b;
    string c = sub(a,b);
    cout << c;
    return 0;
}
 
Copy 
高精度乘法 
例题：高精度乘法 
题目描述 
求两个正整数之积 
输入输出格式 
输入 
共两行，每行一个正整数，每个数小于1000位 
输出 
求两整数的积 
样例 
输入1 
12
12
 
Copy 
输出1 
144
 
Copy 
时间及空间限制 
1s, 256MB. 
完整代码如下： 
#include
using namespace std;
int c[1000],d[1000],e[2000];
int main()
{
   //1-将2个乘数存放到字符串中 
   string a,b;
   cin>>a>>b;
   int cxb=1,dxb=1;
   //2-将字符串分别倒置在c,d两个数组中 
   for(int i=a.size()-1;i>=0;i--) 
   {
        c[cxb]=a[i]-48;cxb++;
   }
   for(int i=b.size()-1;i>=0;i--)
   {
        d[dxb]=b[i]-48;dxb++;
   }
   //3-找到乘积结果最小的终点值。
   //结果的长度要么是a.size()+b.size()-1，要么是再加一 
   int zd=a.size()+b.size()-1;
   for(int i=1;i<=a.size();i++)
   {
        for(int j=1;j<=b.size();j++)
        {
            //第i位和第j位相乘的结果一定是对应在i+j-1位
            //一定要注意是+=，因为某一位上可能存放着多组乘积 
            e[i+j-1]+=c[i]*d[j];
        }
   }
   //4-将每一位上的进位情况处理好 
   for(int i=1;i<=zd;i++)
   {
    
        e[i+1]+=e[i]/10;
        e[i]%=10;
   }
   //5-讨论存不存在第 a.size()+b.size()位 
   if(e[zd+1]) zd++;
   //6-倒置输出结果的答案 
   for(int i=zd;i>=1;i--) cout< 
Copy 
例题：A*B Problem（高精度乘法）（主题库2609） 
题目描述 
高精度乘法。输入两个正整数，求它们的积。 
输入输出格式 
输入 
输入两行，每行为一个高精度正整数，长度不超过255。 
输出 
输出一行，相乘的结果。 
样例 
输入1 
1234567890
9876543210
 
Copy 
输出1 
12193263111263526900
 
Copy 
时间及空间限制 
1s, 256MB. 
完整代码如下： 
#include
#include
using namespace std;

const int N = 1e6+5;

string div(string a, string b)
{
    string ans;
    // 翻转，使个位在前
    reverse(a.begin(), a.end());
    reverse(b.begin(), b.end());
    // 按位相乘，模拟乘法
    int c[1000]={0}, k = a.size()+b.size()+1;
    for(int i = 0; i < a.size(); i++)
        for(int j = 0; j < b.size(); j++)
        {
            c[i+j] += (a[i]-'0')*(b[j]-'0');  // 乘，写上去
            c[i+j+1] += c[i+j]/10;      // 进位
            c[i+j] %= 10;       // 保留个位
        }
    // 去除高位零
    while(c[k]==0 && k>=0) k--;
    // 输出
    while(k >= 0)
        ans.push_back(c[k--]+'0');
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);
    string a, b;
    cin >> a >> b;
    string c = div(a,b);
    cout << c;
    return 0;
}
 
Copy 
高精度除法 
例题1：A/B Problem（高精除以低精）（主题库2610） 
题目描述 
高精度除以低精。输入两个正整数，求它们的商（做整除）。 
输入输出格式 
输入 
输入两行，第一行为高精度整数 a，第二行低精度整数 m，（a>=0，长度不超过255，m 在 long long 范围内）。 
输出 
输出一行，两数整除的结果。 
样例 
输入1 
12345678900
99
 
Copy 
输出1 
124703827
 
Copy 
时间及空间限制 
1s, 256MB. 
完整的代码如下： 
#include 
using namespace std;

string div(string a, long long b)
{
    // z 数组保存计算结果
    int z[256] = {0}, d = 0;  // d 存余数
    
    // 计算相乘
    for(int i = 0; i < a.size(); i++)
    {
        d = 10*d + a[i] - '0';
        z[i] = d / b;    // 计算商
        d %= b;              // 计算余数
    }
    
    // 处理计算结果
    string ans;   // 作为返回值
    int len = 0;
    while(z[len] == 0 && len < a.size()-1)    // 去掉高位的0
        len++;
    for(int i = len; i < a.size(); i++)
    {
        // 将结果放到 ans 字符串中，如果
        ans.push_back(z[i]+'0');
    }
    return ans;
}       

int main()
{
    string a;
    long long b;
    cin >> a >> b;
    cout << div(a, b);
    return 0;
}
 
Copy

第十一章：高精度算法

C/C++/C#相关栏目本月热门文章