高精度算法(加、减、乘、除,使用c++实现)

简介: 高精度算法(加、减、乘、除,使用c++实现)

一、概念

在我们进行计算的过程中,经常会遇到几十位,甚至几百位的数字的计算问题,也有可能会遇到小数点后几十位,几百位的情况,而我们面对这样的情况下,   和  的数据范围显然是不够使用的了。因此这时,我们就需要引入一个新的算法,叫做高精度算法。


高精度算法:它是处理大数字的数学计算方法,在一般的科学计算中,会经常算到小数点后几百位或者更多,当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数,高精度算法是用计算机对于超大数据的一种模拟加,减,乘,除等运算。


思想:高精度算法本质上是用字符串模拟数字进行计算,再利用类似于数学里的竖式的形式,一位一位进行相关计算 。

注意事项:

高精度加法:

  1. 倒叙输入,倒序输出,但中间是正着运算;
  2. 相加之后的进位处理;

高精度减法:

  1. 考虑结果出现的正情况;
  2. 前导0的处理;
  3. 考虑减法的借位处理;

高精度乘法:

  1. 前导0的处理(0被相乘);
  2. 可以将乘法单个位数相乘再转化成加法的思想;
  3. 此时题目中没有涉及到负数的情况。如出现负数,只需考虑两个字符串第一位是否为负号,然后结尾特殊判断一下即可;

高精度除法:(高精度÷低精度)

  1. 输入、计算、输出、需要同时逆序或同时正序;
  2. 前导0的处理;
  3. 不能考虑进位的情况


二、数据的处理

2.1 数据的存储

当输入的数很长时,可采用字符串方式输入,这样可输入位数很长的数,利用字符串函数和操作运算,将每一位取出,存入数组中 。

void init(int a[]) { // 传入数组
    string s;
    cin >> s; 
    len = s.length(); // s.length --> 计算字符串位数
    for(int i=1; i<=len; i++)     
        a[i] = s[len -i] - '0'; //将字符串s转换为数组a, 倒序存储
}

2.2 借位和进位

// 加法进位: c[i] = a[i] + b[i]
 
code:    if(c[i] >= 10) {
            c[i] %= 10;
            ++c[i++];
         }
 
//减法借位: c[i] = a[i] - b[i]
 
code:    if(a[i] < b[i]) {
             --a[i+1];
             a[i] += 10;   
         } 
 
//乘法进位: c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];
          x = c[i + j - 1] / 10;
          c[i + j - 1] % 10;

三、加法

#include<iostream>
#include<cstring>
#include<vector>
 
using namespace std;
 
int main()
{
  char s1[500], s2[500];
  int a[500] = { 0 }, b[500] = { 0 }, c[501] = { 0 };
  int i = 0;
  vector<int>vec_add;
 
  cin >> s1 >>s2;
  int len_s1 = strlen(s1);//求两个“数字”位数
  int len_s2 = strlen(s2);
  for (i = 0;i < len_s1;i++)
  {
    a[i] = s1[len_s1 - i - 1] - '0';//倒叙存储,方便最高位进位,按字符型输入,按整型的方式存储在数组里面
  }
  for (i = 0;i < len_s2;i++)
  {
    b[i] = s2[len_s2 - i - 1] - '0';
  }
  for (i = 0;i < (len_s1 > len_s2 ? len_s1 : len_s2);i++)
  { 
    vec_add.push_back(a[i] + b[i] + c[i]);
    if (vec_add[i] >= 10)//如果可以进位
    {
      c[i + 1] = vec_add[i] / 10;
      vec_add[i] %= 10;
      if (i == (len_s1 > len_s2 ? len_s1 : len_s2))
      {
        vec_add.push_back(1);
      }
    }
  }
  int len_vec_add = vec_add.size();
  for (i = len_vec_add - 1;i >= 0;i--)
  {
    cout << vec_add[i];
  }
  cout << endl;
 
  return 0;
}

运行示例如下:

四、减法

#include<iostream>
#include<cstring>
#include<vector>
 
int main()
{
  char s1[500], s2[500];
  int a[500] = { 0 }, b[500] = { 0 }, c[501] = { 0 };
  int i = 0;
  vector<int>vec;
 
  cin >> s1 >> s2;
  int len_s1 = strlen(s1);//求两个“数字”位数
  int len_s2 = strlen(s2);
  for (i = 0;i < len_s1;i++)
  {
    a[i] = s1[len_s1 - i - 1] - '0';//倒叙存储,方便最高位进位,按字符型输入,按整型的方式存储在数组里面
  }
  for (i = 0;i < len_s2;i++)
  {
    b[i] = s2[len_s2 - i - 1] - '0';
  }
  for (i = 0;i < (len_s1 > len_s2 ? len_s1 : len_s2);i++)
  {
    if (strcmp(s1, s2) >= 0)
    {
      vec.push_back(a[i] - b[i]);
      if (vec[i] < 0)
      {
        a[i + 1] -= 1;
        a[i] += 10;
        vec[i] += 10;
      }
    }
    else
    {
      vec.push_back(b[i] - a[i]);
      if (vec[i] < 0)
      {
        b[i + 1] -= 1;
        b[i] += 10;
        vec[i] += 10;
      }
      
    }
    
  }
  int len_vec = vec.size();
  if (strcmp(s1, s2) >= 0)
  {
    for (i = len_vec - 1;i >= 0;i--)
    {
      cout << vec[i];
    }
  }
  else
  {
    cout << "-";
    for (i = len_vec - 1;i >= 0;i--)
    {
      cout << vec[i];
    }
  }
  cout << endl;
 
  return 0;
}

运行结果如下:

五、乘法

大数乘法可以看成多个数大数乘以一位的数再相加

    1.输入与初始化

    • 从用户那里接收两个字符串s1和s2,它们代表两个大整数。
    • 将这两个字符串转换为数组a和b,使得数组中的元素是从低位到高位存储的整数。这是通过将字符串中的每个字符减去字符'0'的ASCII值来实现的,因为字符'0'到'9'的ASCII值是连续的。
    • 初始化一个整数数组c,用于存储进位值。
    • 初始化一个std::vector<int>(名为vec),用于存储最终的乘积结果。

    2.计算乘积:

    • 使用两层循环来计算ab中每个元素的乘积,并累加到vec中。
    • 外层循环遍历a中的每个元素,内层循环遍历b中的每个元素。
    • 对于ab中的每对元素,计算它们的乘积,并加上之前的进位值(如果有的话)。
    • 将乘积的个位数加到vec的对应位置,并更新进位值。

    3.处理进位:

    • 进位逻辑在内层循环结束后处理。如果最后一个乘法操作后存在进位,需要将其加到vec的下一个位置。
    • 需要注意,由于vec的大小在循环过程中是变化的,因此直接通过索引访问vec可能会导致越界错误。正确的做法是在需要添加新元素时,使用vec.push_back()

    代码示例如下:

    int main()
    {
      char s1[500], s2[500];
      int a[500] = { 0 }, b[500] = { 0 };
      int i = 0;
      int z = 0;
      vector<int>vec;
     
      cin >> s1 >> s2;
      int len_s1 = strlen(s1);//求两个“数字”位数
      int len_s2 = strlen(s2);
      //初始化vec的大小至少为len_s1 + len_s2,这样可以保证在计算过程中不会越界。
      vec.resize(len_s1 + len_s2, 0);
      for (i = 0;i < len_s1;i++)
      {
        a[i] = s1[len_s1 - i - 1] - '0';//倒叙存储,方便最高位进位,按字符型输入,按整型的方式存储在数组里面
      }
      for (i = 0;i < len_s2;i++)
      {
        b[i] = s2[len_s2 - i - 1] - '0';
      }
     
      for (i = 0; i < len_s1; i++)
      {
        int carry = 0; // 每次循环开始时,进位为0  
        for (int j = 0; j < len_s2; j++)
        {
                // 计算乘积,加上已有的值和进位
          int product = a[i] * b[j] + vec[i + j] + carry;   
          vec[i + j] = product % 10; // 取个位数  
          carry = product / 10; // 更新进位  
        }
        // 检查最后一个乘法操作后的进位  
        if (carry > 0)
        {
          vec[i + len_s2] += carry;
        }
      }
      // 处理vec中可能的前导0 
      while (!vec[vec.size() - 1])
      {
        if (vec[vec.size() - 1] == 0)
        {
          vec.pop_back();
        }
      }
      int len_vec = vec.size();
      for (i = len_vec - 1;i >= 0;i--)
      {
        cout << vec[i];
      }
      cout << endl;
     
      return 0;
    }

    测试输出结果如下:

    六、除法

    高精度除以低精度:

    思路:除法时,每一次的商值都在 0~9 之间,每次求得的余数连接以后的若干位得到新的被除数,继续做除法。因此,在做高精度除法时,要涉及到乘法运算和减法运算,还有移位处理。当然,为了程序简洁,可以避免高精度乘法,用 0~9 次循环减法取代得到商的值。采用按位相除法

    #include<iostream>
     
    int main()
    {
        char n1[100];
        int a[100] = { 0 }, c[100] = { 0 }, i, x = 0, b;
        cin >> n1 >> b;
        int len_a = strlen(n1);
     
        for (i = 1; i <= len_a; i++)
        {
            a[i] = n1[i - 1] - '0'; //除法不需要逆序存放
        }
        for (i = 1; i <= len_a; i++)
        {
            c[i] = (a[i] + x * 10) / b;  // 算上上一位剩下的继续除
            x = (a[i] + 10 * x) % b; // 求余
        }
     
        int len_c = 1;
        while (c[len_c] == 0 && len_c < len_a)
        {
            len_c++;
        }
        for (i = len_c; i < len_a; i++)
        {
            cout << c[i];
        }
        return 0;
    }
    相关文章
    |
    2月前
    |
    算法 测试技术 C++
    【动态规划算法】蓝桥杯填充问题(C/C++)
    【动态规划算法】蓝桥杯填充问题(C/C++)
    |
    2月前
    |
    存储 算法 决策智能
    【算法】博弈论(C/C++)
    【算法】博弈论(C/C++)
    |
    2月前
    |
    存储 算法 C++
    【算法】哈希映射(C/C++)
    【算法】哈希映射(C/C++)
    |
    2月前
    |
    机器学习/深度学习 人工智能 算法
    【算法】最长公共子序列(C/C++)
    【算法】最长公共子序列(C/C++)
    |
    2月前
    |
    人工智能 算法 BI
    一篇带你速通差分算法(C/C++)
    一篇带你速通差分算法(C/C++)
    |
    2月前
    |
    人工智能 算法 C++
    一篇带你速通前缀和算法(C/C++)
    一篇带你速通前缀和算法(C/C++)
    |
    2月前
    |
    存储 算法 C++
    弗洛伊德(Floyd)算法(C/C++)
    弗洛伊德(Floyd)算法(C/C++)
    |
    2月前
    |
    存储 算法 程序员
    迪杰斯特拉(Dijkstra)算法(C/C++)
    迪杰斯特拉(Dijkstra)算法(C/C++)
    |
    2月前
    |
    算法 C++
    【算法解题思想】动态规划+深度优先搜索(C/C++)
    【算法解题思想】动态规划+深度优先搜索(C/C++)
    |
    2月前
    |
    算法 C++
    【算法】DP背包问题(C/C++)
    【算法】DP背包问题(C/C++)