基础算法(8)：高精度加减乘除

目录

1.高精度加法

模板：

例题：

2.高精度减法

模板：

例题：

3.高精度乘法

3.1 高精度乘低精度

模板：

例题：

3.2 高精度乘高精度

模板：

例题：

​编辑 

 4.高精度除法

模板：

例题：

     为什么要有这么一种算法？因为当我们想需要对两个很大的数进行运算，比如两个很大的数相加相乘或相除38149194919814894819(+ - * /)89198481314819，结果很显然超出了int范围能表示的整数，我们这时候就要用到高精度算法，高精度算法通过用数组来存储数字的每一位，然后进行运算进位，最后通过数组来输出结果

1.高精度加法

模板：

// C = A + B, A >= 0, B >= 0
vector<int> add(vector<int> &A, vector<int> &B)
{
    vector<int> C;
    int t = 0;
    for (int i = 0; i < A.size()||i < B.size(); i ++ )//判断A和B的大小
    {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }

    if (t) C.push_back(t);
    return C;
}

例题：

2

#include<iostream>
#include<vector>
using namespace std;
vector<int> add(vector<int> &A,vector<int> &B)
{
    vector<int>C;
    int t=0;
    for(int i=0;i<A.size()||i<B.size();i++)
    {
        if(i<A.size())t+=A[i];
        if(i<B.size())t+=B[i];
        C.push_back(t%10);
        t/=10;
    }
    if(t)C.push_back(1);
    return C;
}
int main()
{
    string a,b;
    vector<int>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');
    auto C=add(A,B);
    for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);//因为是逆序存储，输出的的时候也要从最后开始输出
    return 0;
    
}

2.高精度减法

模板：

//C=A-B 且A>B
vector<int> sub(vector<int>& A,vector<int>& B)
{
    vector<int> C;
    for(int i=0,t=0;i<A.size();i++)
    {
        //每次循环进行A[i]-B[i]-t运算
        t=A[i]-t;//减去上次运算借的位，没有借位就减去0，借位就减去1
        if(i<B.size())t-=B[i];//判断B[i]是否存在，如果存在，上一步算完A[i]减去进位的值
        //等于t,t=t-B[i]，算的就是该位两数相减的值
        C.push_back((t+10)%10);//有两种情况，一种算完t<0,这时候向前借一位，即t+10，就是这一位的值；还有一种是t>0，为了减少代码，我们也+10再%10,就抵消了
        if(t<0)t=1;//t<10.说明借位了，t=1
        else t=0;//t?10.不用借位，t=0
    }
    while(C.size()>1&&C.back()==0)C.pop_back();//去除前导0
    return C;
}

       减去上次运算借的位，没有借位就减去0，借位就减去1
       接下来判断B[i]是否存在，如果存在，上一步算完A[i]减去进位的值等于t,t=t-B[i]，算的就是该位两数相减的值
       C.push_back((t+10)%10)有两种情况，一种算完t<0,这时候向前借一位，即t+10，就是这一位的值；还有一种是t>0，为了减少代码，我们也+10再%10,就抵消了。

      最后如果t<0，说明借位了，t=1;否则没借位，t=0。

例题：

#include<iostream>
#include<vector>
using namespace std;

//判断是否有A>B
bool cmp(vector<int>& A,vector<int>& B)
{
    if(A.size()!=B.size())return A.size()>B.size();
    for(int i=A.size()-1;i>=0;i--)
        if(A[i]!=B[i])
           return A[i]>B[i];
    return true;
}

//C=A-B 且A>B
vector<int> sub(vector<int>& A,vector<int>& B)
{
    vector<int> C;
    for(int i=0,t=0;i<A.size();i++)
    {
        //每次循环进行A[i]-B[i]-t运算
        t=A[i]-t;//减去上次运算借的位，没有借位就减去0，借位就减去1
        if(i<B.size())t-=B[i];//判断B[i]是否存在，如果存在，上一步算完A[i]减去进位的值
        //等于t,t=t-B[i]，算的就是该位两数相减的值
        C.push_back((t+10)%10);//有两种情况，一种算完t<0,这时候向前借一位，即t+10，就是这一位的值；还有一种是t>0，为了减少代码，我们也+10再%10,就抵消了
        if(t<0)t=1;//t<10.说明借位了，t=1
        else t=0;//t?10.不用借位，t=0
    }
    while(C.size()>1&&C.back()==0)C.pop_back();//去除前导0
    return C;
}

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

     我们首先要判断A和B的大小，要用大的减去小的，如果A<B,那我们用B-A,输出时候加上负号即可，判断完之后就是套模板了，最后逆序输出。

3.高精度乘法

3.1 高精度乘低精度

模板：
//大数乘小数 高精度乘低精度
vector<int> mul(vector<int>& A,int b)
{
    vector<int>C;
    
    int t=0;
    for(int i=0;i<A.size()||t;i++)//如果i>=A.size()且t!=0，就要处理剩余的t,也就是最后一次进位
    {
        if(i<A.size())t+=A[i]*b;//判断A是否已经乘完
        C.push_back(t%10);
        t/=10;
    }
    return C;
}
例题：

#include<iostream>
#include<vector>
using namespace std;

//大数乘小数 高精度乘低精度
vector<int> mul(vector<int>& A,int b)
{
    vector<int>C;
    
    int t=0;
    for(int i=0;i<A.size()||t;i++)//如果i>=A.size()且t!=0，就要处理剩余的t,也就是最后一次进位
    {
        if(i<A.size())t+=A[i]*b;//判断A是否已经乘完
        C.push_back(t%10);
        t/=10;
    }
    return C;
}

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');
    
    auto C=mul(A,b);
    
    for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
    
    return 0;
}

3.2 高精度乘高精度

模板：
//高精度*高精度 以43*876为例
vector<int> mul(vector<int> &A, vector<int> &B) 
{
    vector<int> C(A.size() + B.size() + 7, 0); // 初始化为 0，C的size大一点

    for (int i = 0; i < A.size(); i++)
        for (int j = 0; j < B.size(); j++)
            C[i + j] += A[i] * B[j];

    int t = 0;
    for (int i = 0; i < C.size(); i++) 
    { 
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back(); // 必须要去前导 0，因为最高位很可能是 0
    return C;
}

       借用Acwing的一张图来说明这种方法：

例题：
 
#include <iostream>
#include <vector>

using namespace std;

vector<int> mul(vector<int> &A, vector<int> &B)
{
    vector<int> C(A.size() + B.size() + 7, 0);

    for (int i = 0; i < A.size(); i++)
        for (int j = 0; j < B.size(); j++)
            C[i + j] += A[i] * B[j];

    int t = 0;
    for (int i = 0; i < C.size(); i++)
   {
        t += C[i];
        C[i] = t % 10;
        t /= 10;
    }

    while (C.size() > 1 && C.back() == 0) C.pop_back(); 
    return C;
}

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');

    auto C = mul(A, B);

    for (int i = C.size() - 1; i >= 0; i--)cout << C[i];

    return 0;
}

 4.高精度除法

模板：

//A/b,商是C，余数是r
vector<int> div(vector<int>& A,int b,int &r)
{
    vector<int>C;
    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();
    return C;
}
例题：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

//A/b,商是C，余数是r
vector<int> div(vector<int>& A,int b,int &r)
{
    vector<int>C;
    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();
    return C;
}


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;
    auto C=div(A,b,r);
    
    for(int i=C.size()-1;i>=0;i--)printf("%d",C[i]);
    cout<<endl<<r<<endl;
 
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/286042.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

2024年山东省某市建筑类中级职称评审安利

2024年山东省某市建筑类中级职称评审安利

2024年山东省某市建筑类中级职称评审安利 之所以安利山东烧烤市建筑类中级职称是因为2023年申报评审情况比较乐观。如果你2023年申报评审中级职称不顺利&#xff0c;等1-2年还没下来&#xff0c;可以考虑考虑山东省中级职称申报评审。叙后尘来给你们展开说说山东中级职称申报。…
阅读更多...
科普帖：什么是函数即服务 (FaaS)？

科普帖：什么是函数即服务 (FaaS)？

您可能听说过SaaS&#xff0c;您可能听说过PaaS和IaaS&#xff0c;但您听说过函数即服务 (FaaS) 吗&#xff1f; FaaS市场正在快速增长。根据Allied Market Research的数据&#xff0c;2018年市场价值30.1亿美元 。预计到2026年&#xff0c;这一数字将增长到240亿美元——这意…
阅读更多...
gitee创建仓库

gitee创建仓库

描述 本文章记录了怎么在gitee上创建项目&#xff0c;以及使用vscode提代码到远程呢个仓库&#xff0c;如何创建一个新分支&#xff0c;并将新分支提交到远程仓库。 1、创建远程仓库 在创建远程仓库之前要先进行ssh密钥的设置 &#xff08;1&#xff09;打开黑窗口&#xff…
阅读更多...
SpringBoot整合多数据源，并支持动态新增与切换

SpringBoot整合多数据源，并支持动态新增与切换

SpringBoot整合多数据源&#xff0c;并支持动态新增与切换 一、概述 在项目的开发过程中&#xff0c;遇到了需要从数据库中动态查询新的数据源信息并切换到该数据源做相应的查询操作&#xff0c;这样就产生了动态切换数据源的场景。为了能够灵活地指定具体的数据库&#xff0…
阅读更多...
图解Kafka Producer常用性能优化配置参数

图解Kafka Producer常用性能优化配置参数

1 基本参数 bootstrap.servers&#xff1a;Kafka broker服务器地址列表&#xff0c;,分开&#xff0c;可不必写全&#xff0c;Kafka内部有自动感知Kafka broker的机制 client.dns.lookup&#xff1a;客户端寻找bootstrap地址的方式&#xff0c;支持两种方式&#xff1a; resol…
阅读更多...
现在学鸿蒙开发有前途吗？能找到工作吗？

现在学鸿蒙开发有前途吗？能找到工作吗？

鸿蒙开发前景肯定是有的&#xff0c;我们可以从市场的情况来分析。 1、鸿蒙开发不兼容安卓 23年9月举办的华为新品发布会中&#xff0c;华为方面宣布开始启用原生鸿蒙应用&#xff0c;并不再提供安卓代码的兼容性。涵盖了资讯、社交、工具、金融、生活、美食、游戏等多品类的…
阅读更多...
多技术融合在生态系统服务功能社会价值评估中的应用及论文写作、拓展分析

多技术融合在生态系统服务功能社会价值评估中的应用及论文写作、拓展分析

生态系统服务是人类从自然界中获得的直接或间接惠益&#xff0c;可分为供给服务、文化服务、调节服务和支持服务4类&#xff0c;对提升人类福祉具有重大意义&#xff0c;且被视为连接社会与生态系统的桥梁。自从启动千年生态系统评估项目&#xff08;Millennium Ecosystem Asse…
阅读更多...
【Bootstrap学习 day8】

【Bootstrap学习 day8】

加载器 使用Bootstrap读取图标以表示元件加载状态&#xff0c;这些读取图标完全使用HTML,CSS。要创建spinner/加载器&#xff0c;可以使用.spinner-border类 <div class"spinner-border"></div>可以使用文本颜色类设置不同的颜色&#xff1a; <div …
阅读更多...
关于Github部分下载的方法

关于Github部分下载的方法

一、问题 在Github中&#xff0c;我需要下载部分文件&#xff0c;而github只有下载最原始文件夹和单独文件的功能。 比如我想下载头四个文件&#xff0c;难以操作。 二、方法 推荐使用谷歌浏览器&#xff0c;进入扩展程序界面&#xff1a; 在应用商店获取GitZip for github…
阅读更多...
Python数据科学应用从入门到精通--Python读取、合并SPSS数据文件

Python数据科学应用从入门到精通--Python读取、合并SPSS数据文件

在很多情况下&#xff0c;我们需要调用SPSS软件产生的数据&#xff0c;下面通过示例来进行讲解。首先需要将本书提供的数据文件存储在安装spyder-py3的默认路径位置&#xff08;C:/Users/Administrator/.spyder-py3/&#xff0c;注意具体的安装路径可能与此不同&#xff09;&am…
阅读更多...
PDF文档转换工具箱流量主小程序开发

PDF文档转换工具箱流量主小程序开发

PDF转换小助手&#xff0c;不仅是文件格式转换的利器&#xff0c;更是一位得力的助手。它精通PDF与各类文档间的自由转换&#xff0c;如Word、Excel、PowerPoint等。 转换选项丰富多样&#xff0c;满足您对文件保护、页面设置、图像品质等细致要求。处理大量文件&#xff1f;…
阅读更多...
canvas绘制圆点示例

canvas绘制圆点示例

查看专栏目录 canvas示例教程100专栏&#xff0c;提供canvas的基础知识&#xff0c;高级动画&#xff0c;相关应用扩展等信息。canvas作为html的一部分&#xff0c;是图像图标地图可视化的一个重要的基础&#xff0c;学好了canvas&#xff0c;在其他的一些应用上将会起到非常重…
阅读更多...
格式转换工具，一键转换文件格式

格式转换工具，一键转换文件格式

有时候&#xff0c;为了满足工作或学习的需要&#xff0c;我们需要将文件从一种格式转换为另一种格式。传统的单文件转换方式不仅费时&#xff0c;而且容易出错。有没有便捷的方法可以解决这个问题&#xff1f;答案是肯定的&#xff0c;那就是使用【文件批量改名高手】来批量操…
阅读更多...
Python实现简单的JS逆向解密, 实现翻译软件+语音播报

Python实现简单的JS逆向解密, 实现翻译软件+语音播报

嗨喽~大家好呀&#xff0c;这里是魔王呐 ❤ ~! python更多源码/资料/解答/教程等 点击此处跳转文末名片免费获取 环境使用: python 3.8 pycharm 第三方模块使用: requests --> pip install requests execjs --> pip install PyExecJS ttkbootstrap --> pip inst…
阅读更多...
时隔五天，重温Redis基础总结

时隔五天，重温Redis基础总结

目录 字符串操作命令 Redis 字符串类型常用命令SET key value 设置指定key的值 ​编辑GET key 获取指定key的值 ​编辑SETEX key seconds value 设置指定key的值&#xff0c;并将 key 的过期时间设为 seconds 秒 SETNX key value 只有在key不存在时设置key的值 哈希操作命…
阅读更多...
epoll原理及服务器代码实现

epoll原理及服务器代码实现

epoll 是 Linux 下用于实现高性能事件通知机制的系统调用。它相对于传统的 select 和 poll 具有更好的性能和可伸缩性&#xff0c;特别适用于需要处理大量并发连接的场景&#xff0c;比如网络编程中的服务器。 #include <sys/epoll.h> // 创建一个新的epoll实例。在内核中…
阅读更多...
安全与认证Week3

安全与认证Week3

Key Management 密钥管理 密钥交换、证书 密钥的类别 密钥管理方面 密钥分发问题 密钥分发方案 简单的密钥分发&#xff1a;允许安全通信&#xff0c;但不存在先前或之后的密钥。 带机密性和身份验证的密钥分发&#xff1a;提供更高级别的安全性。 混合密钥分发 公钥分发 公开…
阅读更多...
Node.js使用jemalloc内存分配器显著减少内存使用

Node.js使用jemalloc内存分配器显著减少内存使用

前言 Node.js 默认使用的是 ptmalloc(glibc) 内存分配器&#xff0c;而&#xff1a; 在服务端领域「不会选择默认的 malloc」是一个常识。&#xff08; 来源 &#xff09; ptmalloc 的分配效率较低&#xff08; 来源 &#xff09;&#xff0c;对于 长时间、多核 / 多线程 运行…
阅读更多...
惠普打印机---共享打印机安装 --连接

惠普打印机---共享打印机安装 --连接

1. 远程连接 输入 winR ,再输入共享打印机的连接的IP 2.进入 连接 界面 3.右击打印机 &#xff0c;点击连接 &#xff0c;就可以添加打印机设备 ![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/ba03aea8156642d58982fd2ce0934b45.png 方法二、 添加打印机 2.…
阅读更多...
金和OA jc6 ntko-upload 任意文件上传漏洞复现

金和OA jc6 ntko-upload 任意文件上传漏洞复现

0x01 产品简介 金和OA协同办公管理系统软件（简称金和OA），本着简单、适用、高效的原则，贴合企事业单位的实际需求，实行通用化、标准化、智能化、人性化的产品设计，充分体现企事业单位规范管理、提高办公效率的核心思想，为用户提供一整套标准的办公自动化解决方案，以帮助…
阅读更多...
最新文章

Copyright @ 2022~2023