高精度算法

简介: 本文详细介绍了高精度算法的实现,涵盖加法、减法、乘法、除法及取模等操作。通过字符串与数组结合的方式,解决了大数运算中超出数据类型范围的问题。每种运算均提供完整的C++代码示例,包括输入处理、位运算模拟、进位/借位逻辑以及结果输出。其中,高精度加法和减法通过逆序存储数字简化计算;乘法利用双重循环模拟手算过程;除法分为低精度和高精度两种情况,分别采用逐位试商与减法模拟;取模则通过逐位累加求余实现。这些方法为处理大规模数值运算提供了有效工具,适用于竞赛编程与实际开发场景。

高精度算法

作者:blue

时间:2024.9

1.高精度加法(整数部分模板)

#include <iostream>
#include <string>
using namespace std;
int a1[1000],a2[1000],ans[1000];
int main()
{
   
    string s1,s2;
    cin>>s1>>s2;//字符串存放大数
    //逆序存放在数组中 
    for(int i=0;i<s1.size();i++) a1[s1.size()-i-1]=s1[i]-'0';
    for(int i=0;i<s2.size();i++) a2[s2.size()-i-1]=s2[i]-'0';
    int len=max(s1.size(),s2.size());
    //先相加 
    for(int i=0;i<len;i++){
   
        ans[i]=a1[i]+a2[i];
    }
    //后处理进位 
    for(int i=0;i<len;i++){
   
        ans[i+1]=ans[i+1]+ans[i]/10;
        ans[i]=ans[i]%10;
    }
    //逆序输出先判断len位为不为0(因为最高位可能进位,所以最长到len位)
    for(int i=len;i>=0;i--){
   
        if(i==len&&ans[len]==0) continue;
        cout<<ans[i];
    }
    return 0;
}

2.高精度减法(整数部分模板)

#include <iostream>
#include <string>
using namespace std;
const int N=1e6+10;
int a1[N],a2[N],ans[N];
int main()
{
   
    string s1,s2;
    cin>>s1>>s2;
    char flag='+';//符号判断 
    //判断两个数谁大谁小,大的那个放置在s1,如果交换了位置,就将符号置为'-'
    if(s1.size()<s2.size()||s1.size()==s2.size()&&s1<s2){
   
        swap(s1,s2);
        flag='-';
    } 
    //倒序存放 
    for(int i=0;i<s1.size();i++) a1[i]=s1[s1.size()-i-1]-'0';
    for(int i=0;i<s2.size();i++) a2[i]=s2[s2.size()-i-1]-'0';
    for(int i=0;i<s1.size();i++){
   
        if(a1[i]<a2[i]){
   //模拟借位的过程 
            a1[i]+=10;
            a1[i+1]--;
        }
        ans[i]=a1[i]-a2[i];
    }
    //注意此处index的值设置为0是有考究的,当是两个相等大数相减的话,那就只用输出1位0 
    int index=0;//找答案中第一个不为0的位置,为输出做准备 
    for(int i=s1.size()-1;i>=0;i--){
   
        if(ans[i]>0){
   
            index=i;
            break;
        }
    } 
    if(flag=='-') cout<<flag;
    for(int i=index;i>=0;i--) cout<<ans[i];
    return 0;
}

3.高精度乘法

image-20241019090817352.png

#include <iostream>
#include <string>
using namespace std;
const int N=1e8+10;
int a1[N],a2[N],ans[N];
int main()
{
   
    string s1,s2;
    cin>>s1>>s2;
    //反转两个数 
    for(int i=0;i<s1.size();i++) a1[i]=s1[s1.size()-i-1]-'0'; 
    for(int i=0;i<s2.size();i++) a2[i]=s2[s2.size()-i-1]-'0'; 
    int len=s1.size()+s2.size();//乘法最终的长度不会长于两个常数长度的和 
    //模拟乘法过程
    for(int i=0;i<s1.size();i++){
   
        for(int j=0;j<s2.size();j++){
   
            ans[i+j]+=a1[i]*a2[j];//注意这里不是赋值语句 
            ans[i+j+1]+=ans[i+j]/10;//进位 
            ans[i+j]=ans[i+j]%10;//保留本位 
        }
    } 
    //消除前导0 
    int index=0;
    for(int i=len;i>=0;i--){
   
        if(ans[i]!=0){
   
            index=i;
            break;
        }
    }
    //倒序输出 
    for(int i=index;i>=0;i--){
   
        cout<<ans[i];
    }
    return 0;
}

4.高精度除法

高精度除以低精度

image-20241019092848282.png

#include <iostream>
#include <string>
using namespace std;
const int N=1e8+10;
int ans[N],a[N];
long long b;
int main()
{
   
    string s;
    long long x=0;//用以承接每次的余数,初始应当为0,因为没有余数,注意这里余数也要开long long 防止余数很大的情况 
    cin>>s>>b;//输入一个高精度数和一个低精度数
    //这里不用倒序存放,因为除法本身就是一个从高位计算到低位的过程 
    for(int i=0;i<s.size();i++) a[i]=s[i]-'0';
    //模拟逐位试商的过程 
    for(int i=0;i<s.size();i++){
   
        ans[i]=(x*10+a[i])/b;
        x=(x*10+a[i])%b;
    }
    int index=0;
    //消除前导0,注意此处,index不能超过被除数的长度 
    while(ans[index]==0&&index<s.size()) index++;
    for(int i=index;i<s.size();i++) cout<<ans[i];
    if(index==s.size()) cout<<"0";//如果index等于被除数的长度,那么说明商就为0,要打印0
    //cout<<" "<<x;//有需要还可以打印余数 
    return 0;
}

高精度除以高精度

高精度除高精度要用减法模拟除法

image-20241019145033990.png

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
const int N=1e6+10;
int a[N],b[N],c[N],tmp[N];
void init(int a[]){
   
    string s;
    cin>>s;
    a[0]=s.size();//a[0]存储字符串的长度 
    for(int i=1;i<=s.size();i++) a[i]=s[s.size()-i]-'0';//逆序存储 
}
void print(int a[]){
   
    if(a[0]==0){
   
        cout<<"0";
        return;
    }
    for(int i=a[0];i>0;i--) cout<<a[i];
    return;
}
int compare(int a[],int b[]){
   //比较两个数的大小,如果a大返回1,如果b大返回-1,一样大返回0 
    if(a[0]>b[0]) return 1;
    if(a[0]<b[0]) return -1;
    for(int i=a[0];i>0;i--){
   
        if(a[i]>b[i]) return 1;
        if(a[i]<b[i]) return -1; 
    }
    return 0;
}
void minu(int a[],int b[]){
   //高精度减法 
    for(int i=1;i<=a[0];i++)
    {
   
        if(a[i]<b[i]){
   
            a[i]+=10;
            a[i+1]--;
        }
        a[i]=a[i]-b[i];
    }
    while(a[a[0]]==0&&a[0]>0) a[0]--;//删除前导0 
    return; 
}
void numcpy(int b[],int tmp[],int n){
   //
    for(int i=1;i<=b[0];i++) tmp[i+n]=b[i];
    tmp[0]=b[0]+n;
}
int main()
{
   
    init(a);
    init(b);
    c[0]=a[0]-b[0]+1;//两位数相除,商最长的长度 
    if(c[0]<0) c[0]=0;
    for(int i=c[0];i>=1;i--){
   
        memset(tmp,0,sizeof(tmp));
        numcpy(b,tmp,i-1);//减法模拟除法,扩展减数,和被减数一样长 
        while(compare(a,tmp)>=0){
   //减干净 
            c[i]++;
            minu(a,tmp);
        }
    }
    while(c[c[0]]==0&&c[0]>0) c[0]--;//消去前导0 
    print(c);
    //print(a);//余数 
}

5.高精度取模

蛐蛐取mod,直接拿下

4.字符串加法【算法赛】 - 蓝桥云课 (lanqiao.cn)

#include <iostream>
#include <string>
#define int long long
using namespace std;
const int mod=1e9+7;
long long long_mod(string a)
{
   
  int ans=0;
  for(int i=0;i<a.size();i++){
   
    ans=(ans*10+(a[i]-'0'))%mod;
  }
  return ans;
}

signed main()
{
   
  string a,b,res;
  cin>>a>>b;
  res=a+b;
  cout<<long_mod(res);
  return 0;
}

6.高精度

第十五届蓝桥杯C/C++B组题解——R格式_第十五届蓝桥杯c语言b组答案-CSDN博客

目录
相关文章
|
存储 算法 编译器
【C++ 函数尾部返回】C++中的尾返回类型:探究auto func() -> ReturnType的魔力
【C++ 函数尾部返回】C++中的尾返回类型:探究auto func() -> ReturnType的魔力
442 1
|
存储 测试技术 区块链
阿里云、百度云及移动云对象存储横向性能对比测试
在企业的数字化转型进程中,我们观察到越来越多的公司将其IT基础设施迁移到云端。随着企业业务的持续运营,无论是储存、处理、分享还是删除,都会产生大量的数据,这就要求有一个既可靠又高效的系统来管理和存储这些信息。对象存储产品在这个场景中扮演了至关重要的角色。它们以一种可扩展、安全、持久的方式,有效地满足了对大规模非结构化数据存储的需求。 尽管市场上云计算提供商众多,各自都有自己独特的对象存储产品,面对这样的丰富选择,如何寻找最符合企业需求的产品呢?这正是企业今天寻求解答的问题。 在本篇文章中,我们将深入进行一项横向对比测试,专门对阿里云OSS、百度云BOS和移动云EOS这三大云服务提供商的对象
3407 0
|
小程序
微信小程序 定时器setInterval、setTimeout,简单易用
微信小程序 定时器setInterval、setTimeout,简单易用
1783 0
|
11月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
2348 0
高精度算法(加、减、乘、除,使用c++实现)
|
存储 Shell 网络安全
|
7月前
|
机器学习/深度学习 存储 缓存
LLM高效推理:KV缓存与分页注意力机制深度解析
随着大型语言模型(LLM)规模和复杂性的增长,高效推理变得至关重要。KV缓存和分页注意力是优化LLM推理的两项关键技术。KV缓存通过存储键值对减少重复计算,而分页注意力则通过将序列分割成小块来降低内存消耗,从而有效处理长序列。本文深入剖析这些技术的工作原理及其在仅解码器模型中的应用,探讨其优势与挑战,并展示其实现示例。
327 16
LLM高效推理:KV缓存与分页注意力机制深度解析
|
存储 算法 Java
【DFS(深度优先搜索)详解】看这一篇就够啦
本文介绍了深度优先搜索(DFS)算法及其应用。DFS从某个顶点出发,深入探索图的每条路径,直到无法前进为止,然后回溯。文章详细解释了DFS的基本思想,并通过示例图展示了其执行过程。此外,文中还探讨了三种枚举方式:指数型枚举、排列型枚举和组合型枚举,并提供了具体的代码实现。最后,文章通过几道练习题帮助读者更好地理解和应用DFS算法。
8761 19
【DFS(深度优先搜索)详解】看这一篇就够啦
ROS2教程 09 bag
本文是一篇关于ROS2中bag工具使用的教程,介绍了如何记录、回放和查看话题信息的命令和步骤。
781 5
|
存储 安全 Unix
并发编程基础:使用POSIX线程(pthread)进行多线程编程。
并发编程基础:使用POSIX线程(pthread)进行多线程编程。