开发者社区> 辰Chen> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

高精度运算

简介: 复习acwing算法基础课的内容,本篇为讲解基础算法:高精度运算,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上
+关注继续查看

文章目录

前言

一、高精度运算概述

二、高精度算法

1. 高精度加法

AcWing791. 高精度加法

高精度加法模板

AC代码

2.高精度减法

AcWing 792. 高精度减法

高精度减法模板

AC代码

3.高精度乘法

AcWing 793. 高精度乘法

高精度乘法模板

AC代码

4.高精度除法

AcWing 794. 高精度除法

高精度除法模板

AC代码

三、时间复杂度

前言

复习acwing算法基础课的内容,本篇为讲解基础算法:高精度运算,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上


一、高精度运算概述

我们都知道,我们定义一个数,不论是整数还是浮点数,它都是有范围的都是有限的,就拿unsigned long long为例,它的最大值也就1e19,意思是最多只有19位,而我们想要进行40位,50位甚至更多位数的运算,显然就不能简单的定义int,long long等类型进行计算了,这时候我们就可以运用到高精度算法,把每一位上的数都存到数组之中,本博客的高精度算法中,用到了STL中的vector,关于vector,详见:vector


二、高精度算法

1. 高精度加法

AcWing791. 高精度加法

本题链接:AcWing791. 高精度加法

本博客给出题目截图:

image.png

高精度加法模板

本模板来自ACWing算法基础课

vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);      //保证A的长度始终 ≥ B的长度,因为下面的for循环是通过遍历A的每个元素

    vector<int> C;
    //C中存储的就是A + B后的结果
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);                          //有可能最高位加法存在进位,如果t存在,就加入到C
    return C;
}
vector<int> add(vector<int> &A, vector<int> &B)
{
    if (A.size() < B.size()) return add(B, A);      //保证A的长度始终 ≥ B的长度,因为下面的for循环是通过遍历A的每个元素

    vector<int> C;
    //C中存储的就是A + B后的结果
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);                          //有可能最高位加法存在进位,如果t存在,就加入到C
    return C;
}

AC代码

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

vector <int> A, B, C;

void add(vector <int> &A, vector <int> &B)
{
    if (A.size() < B.size()) add (B, A);
    
    int t = 0;
    for (int i = 0; i < A.size(); i ++ )
    {
        t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    
    if (t) C.push_back(t);
}

int main()
{
    string a, b;
    cin >> a >> b;
    
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');    //a[i] - '0',就把char类型的数字变成了int类型的a[i]
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
    
    add(A, B);
    
    for (int i = C.size() - 1; i >= 0; i -- ) printf("%d", C[i]);
    
    return 0;
}

2.高精度减法

AcWing 792. 高精度减法

本题链接:AcWing 792. 高精度减法

本博客给出题目截图:

image.png

高精度减法模板

本模板来自ACWing算法基础课

// C = A - B, 满足A >= B, A >= 0, B >= 0
vector<int> sub(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    for (int i = 0, t = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);        //因为t可能是负的
        //举个例子,我们计算10 - 8,对于个位而言就是-8,我们通过(t + 10) % 10的方法就可以得到2
        if (t < 0) t = 1;                  //证明存在借位,即像高位借1
        else t = 0;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();   //去除前导0
    //比如111111118 - 111111117 = 000000001,而我们要输出1,通过这一步骤可以实现,要求C.size() > 1是因为有可能答案就是0
    return C;
}

AC代码

保证始终是绝对值大的数去减绝对值小的数:

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

vector <int> A, B, C;

bool cmp(vector <int> &A, vector <int> &B)                 //比较A和B谁大
{
    if (A.size() != B.size()) return A.size() > B.size();
    
    else 
    {
        for (int i = A.size() - 1; i >= 0; i -- )
            if (A[i] != B[i]) return A[i] > B[i];
    }
    
    return true;
}

void sub(vector <int> &A, vector <int> &B)
{
    int t = 0;
    
    for (int i = 0; i < A.size(); i ++ )
    {
        t = A[i] - t;
        if (i < B.size()) t -= B[i];
        C.push_back((t + 10) % 10);            
        if (t < 0) t = 1;
        else t = 0;
    }    
    
    while (C.size() > 1 && C.back() == 0) C.pop_back();
}

int main()
{
    string a, b;
    cin >> a >> b;
    
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    for (int i = b.size() - 1; i >= 0; i -- ) B.push_back(b[i] - '0');
    
    if (cmp(A, B)) sub (A, B);
    else
    {
        sub (B, A);
        printf("-");
    }
    
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    
    return 0;
}

3.高精度乘法

AcWing 793. 高精度乘法

本题链接:AcWing 793. 高精度乘法

本博客给出题目截图:

image.png

高精度乘法模板

本模板来自ACWing算法基础课

vector<int> mul(vector<int> &A, int b)
{
    vector<int> C;

    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back();   //去除前导0
    //比如 123 * 0,按照这个运算的话是 0000,答案是0,故需要去除前导0
    return C;
}

AC代码

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector <int> A, B;

void mul(vector <int> &A, int b)
{
    int t = 0;
    for (int i = 0; i < A.size() || t; i ++ )
    {
        t += A[i] * b;
        B.push_back(t % 10);
        t /= 10;
    }
    
    while (B.size() > 1 && B.back() == 0) B.pop_back();
}

int main()
{
    string a;
    int b;
    cin >> a >> b;
    
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    
    mul(A, b);
    
    for (int i = B.size() - 1; i >= 0; i -- ) cout << B[i];
    
    return 0;
}

4.高精度除法

AcWing 794. 高精度除法

本题链接:AcWing 794. 高精度除法

本博客给出本题截图:

image.png

高精度除法模板

本模板来自ACWing算法基础课

vector<int> div(vector<int> &A, int b, int &r)    //传入的是r的地址,所以可以直接对r的值进行修改
{
    vector<int> C;
    r = 0;
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    reverse(C.begin(), C.end());               
    //除法和加法,减法,乘法运算都不一样的是除法运算是高位向低位进行,而其他三种运算是从低位到高位运算
    //所以除法运算的前导0其实是在开头而不是尾部,而我们只能从尾部删除一个元素,所以我们要把C翻转
    while (C.size() > 1 && C.back() == 0) C.pop_back();   //去除前导0
    return C;
}

AC代码

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

vector <int> A, C;
int r;

void div(vector <int> A, int b)
{
    for (int i = A.size() - 1; i >= 0; i -- )
    {
        r = r * 10 + A[i];
        C.push_back(r / b);
        r %= b;
    }
    
    reverse (C.begin(), C.end());
    while (C.size() > 1 && C.back() == 0) C.pop_back();
}

int main()
{
    string a;
    int b;
    cin >> a >> b;
    
    for (int i = a.size() - 1; i >= 0; i -- ) A.push_back(a[i] - '0');
    
    div(A, b);
    
    for (int i = C.size() - 1; i >= 0; i -- ) cout << C[i];
    cout << endl << r;
    
    return 0;
}

三、时间复杂度

关于高精度算法的时间复杂度以及证明,后续会给出详细的说明以及证明过程,目前先鸽了。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
【7. 高精度除法】
思路: > - 高精度整数除以低精度的整数,商为C,余数为r。 > - 从高位依次除以低精度整数。商(C)存在数组中,`r * 10 + 后一位`,继续除以低精度整数。一直循环结束。 > - 去掉前导0
16 0
高精度加法
高精度加法 高精度加法
20 0
选择排序、冒泡排序、异或运算(下)
选择排序、冒泡排序、异或运算(下)
44 0
逻辑运算
基本逻辑运算 image.png 其他逻辑运算 image.png 运算公式 image.png 变量的证明可以代入常数来进行运算,在逻辑运算中,变量的取值不是0就是1 image.
775 0
从零开始学算法:高精度计算
注:转载请注明:http://www.cnblogs.com/ECJTUACM-873284962/  前言:由于计算机运算是有模运算,数据范围的表示有一定限制,如整型int(C++中int 与long相同)表达范围是(-2^31~2^31-1),unsigned long(无符号整数)是(0~2^32-1),都约为几十亿.
740 0
C++高精度实现计算程序运行时间
//C++高精度实现计算程序运行时间#include      #include      using namespace std;        void Test()//测试程序   {        for(int i=0; i
1038 0
+关注
辰Chen
CSDN人工智能领域优质创作者,华为云&middot;云享专家,CCF-TYUT President-designate
719
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载