高精度算法详解

这篇具有很好参考价值的文章主要介绍了高精度算法详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

首先要知道为什么需要高精度算法:

高精度算法是处理大数字的数学计算方法,当数字过大不能用intlong long存储时,我们就可以使用string和vector类型来存储他们的每一位,然后进行计算。

一、高精度加法

1.1 思路

我们可以先把要输入的两个数字放到vector中存储,注意要反着存(后边做加法的时候最后有进位就可以直接push_back),接下来就是加法:
设置一个add变量表示进位,创建一个res保存每一位,add 加上两个数字,把add % 10放入res中,再把add /= 10
在最后要注意循环完且add不为0的情况。

1.2 例题:高精度加法

题目链接

题目描述

给定两个正整数(不含前导 0),计算它们的和。

输入格式

共两行,每行包含一个整数。

输出格式

共一行,包含所求的和。

数据范围

1≤整数长度≤100000

输入样例:

12
23

输出样例:

35

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> add(const vector<int>& a, const vector<int>& b)
{
    int add = 0;
    vector<int> res;
    for(int i = 0; i < a.size() || i < b.size() || add; i++)
    {
        if(i < a.size()) add += a[i];
        if(i < b.size()) add += b[i];
        res.push_back(add % 10);
        add /= 10;
    }
    return res;
}

int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> 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');
    }
    vector<int> res = add(A, B);
    for(int i = res.size() - 1; i >= 0; i--)
    {
        printf("%d", res[i]);
    }
    return 0;
}

这里要注意最后打印结果的时候如果直接计算不管是用int或long long都不够,所以直接打印每位了。

二、高精度减法

思路分析

2.1 思路

这里要注意有可能为小 - 大,所以需要写一个判断函数来判断大小。
减法:
定义一个变量del表示借位,res存储每一位,每次del = a[i] - b[i] - del,把(del + 10) % 10push_back到res中。再判断del是否小于0,如果小于0,就令del = 1,否则del = 0。

最后还要注意消掉后置0,比如1000 - 999时(反过来存)结果就为1000,需要消掉后面的三个0。

2.2 例题:高精度减法

题目描述

给定两个正整数(不含前导 0),计算它们的差,计算结果可能为负数。

输入格式

共两行,每行包含一个整数。

输出格式

共一行,包含所求的差。

数据范围

1≤整数长度≤105

输入样例:

32
11

输出样例:

21

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// a >= b ?
bool cmp(const vector<int>& a, const vector<int>& b)
{
    int n = a.size(), m = b.size();
    if(n != m)
    {
        return n >= m;
    }
    for(int i = n - 1; i >= 0; i--)
    {
        if(a[i] != b[i])
        {
            return a[i] > b[i];
        }
    }
    return true;
}

vector<int> del(vector<int>& a, vector<int>& b)
{
    if(!cmp(a, b)) return del(b, a);
    vector<int> res;
    int del = 0;
    for(int i = 0; i < a.size(); i++)
    {
        if(i < b.size()) del += b[i];
        del = a[i] - del;
        res.push_back((del + 10) % 10);
        if(del < 0) del = 1;
        else del = 0;
    }
    while(res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}

int main()
{
    string a, b;
    cin >> a >> b;
    vector<int> 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');
    vector<int> res = del(A, B);
    if(!cmp(A, B))
    {
        printf("-");
    }
    for(int i = res.size() - 1; i >= 0; i--)
    {
        printf("%d", res[i]);
    }
    return 0;
}

三、高精度乘法

3.1 思路

用123 * 12 来举例子:
高精度算法,百炼成钢,算法,c++,c语言
高精度算法,百炼成钢,算法,c++,c语言
高精度算法,百炼成钢,算法,c++,c语言
高精度算法,百炼成钢,算法,c++,c语言

这也要注意去除后置0:1000 * 0 = 0000(消掉后三个0)

3.2 例题:高精度乘法

题目描述

题目描述

给定两个非负整数(不含前导 0) A 和 B,请你计算 A×B 的值。

输入格式

共两行,第一行包含整数 A,第二行包含整数 B。

输出格式

共一行,包含 A×B 的值。

数据范围

1≤A的长度≤100000,
0≤B≤10000

输入样例:

2
3

输出样例:

6

#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> mul(const vector<int>& a, int b)
{
    int add = 0;
    vector<int> res;
    for(int i = 0; i < a.size() || add; i++)
    {
        if(i < a.size()) add = a[i] * b + add;
        res.push_back(add % 10);
        add /= 10;
    }
    while(res.size() > 1 && res.back() == 0) res.pop_back();
    return res;
}

int main()
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    vector<int> res = mul(A, b);
    for(int i = res.size() - 1; i >= 0; i--)
    {
        printf("%d", res[i]);
    }
    return 0;
}

四、高精度除法

4.1 思路

这里我们可以发现我们在做除法的时候不需要把数据逆置,但是为了保持统一,还是逆置再做除法,除法过程:
他需要返回余数,设变量r为余数, r = r * 10 + a[i],把r / b尾插入res数组,再让r %= 10即可。
最后再把res数组逆置,消除后置0。

4.2 例题:高精度除法

题目链接

题目描述

给定两个非负整数(不含前导 0) A,B,请你计算 A/B 的商和余数。

输入格式

共两行,第一行包含整数 A,第二行包含整数 B。

输出格式

共两行,第一行输出所求的商,第二行输出所求余数。

数据范围

1≤A的长度≤100000,
1≤B≤10000,
B 一定不为 0

输入样例:

7
2

输出样例:

3
1文章来源地址https://www.toymoban.com/news/detail-796840.html

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

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

int main()
{
    string a;
    int b;
    cin >> a >> b;
    vector<int> A;
    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    int r = 0;
    vector<int> res = div(A, b, r);
    for(int i = res.size() - 1; i >= 0; i--)
    {
        printf("%d", res[i]);
    }
    printf("\n%d", r);
    return 0;
}

到了这里,关于高精度算法详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【算法】模拟,高精度

      P1601 A+B Problem(高精) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 思路就是模拟,值得注意的就是要用字符串类型输入。存进自己的int数组时要倒着存,因为如果是正着存的话,进位会有点trouble。 时间复杂度O(max(m,n))    P1303 A*B Problem - 洛谷 | 计算机科学教育新生态 (lu

    2024年02月09日
    浏览(53)
  • 高精度算法笔记·····························

    加法 减法 乘法 除法 高精度加法的步骤: 1.高精度数字利用字符串读入 2.把字符串 翻转 存入两个整型数组A、B 3.从低位到高位,逐位求和,进位,存余 4.把数组C从高位到低位依次输出         1.2为准备         3为加法具体实现(0按位取反为-1,即-1时结束等价于=0)  

    2024年01月21日
    浏览(60)
  • C++高精度算法

    目录 前言:  思路: 高精度加法: 高精度减法: 高精度乘法: 高精度除法:  代码: 一、高精度加法 二、高精度减法  三、高精度乘法  四、高精度除法 最后         计算机最初、也是最重要的应用就是数值运算。在编程进行数值运算时,有时会遇到运算的精度要求特

    2024年02月14日
    浏览(54)
  • C++ 算法 高精度(较详细.)

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

    2023年04月10日
    浏览(39)
  • C++基础算法高精度篇

    📟作者主页:慢热的陕西人 🌴专栏链接:C++算法 📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言 主要讲解了高精度算法的四种常用的计算 以下数字均指位数 ①A + B(精度均在10^6) ②A - B (精度均在10^6) ③A * b (len(A) = 10^6, a = 1000); ④A / b (len(A) = 10^6, a = 1000); Ⅲ. Ⅰ . A

    2024年02月16日
    浏览(36)
  • 基于matlab的高精度信号峰值检测算法

    目录 1.算法描述 2.仿真效果预览 3.MATLAB核心程序 4.完整MATLAB        峰值检验是示波表中数据采集方式之一, 这种技术起源于存储深度不能满足捕获毛刺的需要。如果用模拟示波器去观察, 只有当毛刺信号是重复性的并且和主信号同步时, 才能看到毛刺信号 。由于毛刺源于其

    2024年02月12日
    浏览(53)
  • C++基础算法①——高精度加减法计算

    当我们利用计算机进行数值计算,有时候会遇到这样的问题: n!的精确结果是多少? 当n小于30的时候,我们当然可以通过电脑自带的计算器计算出来。但是当我们遇到 100! 的时候就没有办法直接计算出精确的结果。再比如,求两个20000位的数的和。 那怎么解决精度缺失的问

    2024年02月16日
    浏览(50)
  • 洛谷题单算法1-1模拟与高精度

    发文章只是为了督促自己做题,双非大二刚转科班的菜菜一枚,代码仅供参考,不足之处望理解。         这题太恶心了,看完题解发现三种情况没有考虑,后来给补上了,我的 if-else 思路可能写的不太好,但是能过         注意结构体在函数中的传参(下学期c语言II要好

    2024年02月19日
    浏览(44)
  • 【c++】算法:高精度(经典加减乘除){含解析(图解)}

    Hi~ o(* ̄▽ ̄*)ブ,今天来一起看看c++算法之高精度 之后会持续更新有关c++算法系列,欢迎观看!(#^.^#) 目录 前言 使用高精度的目的: 基本方法介绍:   一、A+B problem 基本思路解析: 具体步骤: 代码如下: 二、A-B problem 基本思路解析: ​编辑 具体步骤:  代码如下:  三

    2024年01月23日
    浏览(55)
  • 每周一算法:高精度乘法(二)大整数乘大整数

    高精度乘法是采用模拟算法对上百位甚至更多位的数字进行乘法运算。具体应用时一般分为两类: 大整数数乘整数 大整数乘大整数 大整数乘大整数的基本思想是模拟竖式计中算多位数乘多位数,一般分为下面几步: 将乘数 A A A 的每一位 A i A_i A i ​ 分别与乘数 B B B 的每一

    2023年04月14日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包