当前位置: 首页 > news >正文

【算法】高精度

作者:指针不指南吗
专栏:算法篇

🐾不能只会思路,必须落实到代码上🐾

文章目录

  • 前言
  • 一、高精度加法
  • 二、高精度减法
  • 三、高精度乘法
  • 四、高精度除法

前言

​ 高精度即很大很大的数,超过了 long long 的范围,不能直接读取进行运算,需要用 string 读入,然后存储在数组中去。

​ 高精度算法即把每一位上的数单独拿出来,分别计算,再跟每一位之间的关系,再研究,最后结果仍然存在数组中并输出。


一、高精度加法

  1. 思路

    • 大整数的存储
      • 使用 vector 存储,a[0] 存储个位,依次往后最后存储最高位
    • 代码思想
      • 从个位数开始依次,让a,b每一位相加,结果取模存在结果数组C中,t 表示进位
      • 每次两个数a,b的各个位相加再加上进位t
      • 直到加到最高位
  2. 模板

    #include<bits/stdc++.h>
    using namespace std;//C=A+B
    vector<int> add(vector<int> &A,vector<int> &B)//引用减少时间,不使用引用即把原数据copy一遍,费时间 
    {vector<int> C;  //定义一个结果答案if(A.size()<B.size()) return add(B,A);int t=0;   //t表示进位,个位开始,无需+进位,即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(1);  //离开循环时,t没有加 return C;
    }int main()
    {string a,b;vector<int> A,B;cin>>a>>b;  //输入123456//存储大整数  倒着存储 for(int i=a.size()-1;i>=0;i--) A.push_back(a[i]-'0');   //存储 6,5,4,3,2,1for(int i=b.size()-1;i>=0;i--) B.push_back(b[i]-'0');   //注意这里是字符串的长度aauto C=add(A,B);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);  //注意 倒序输出return 0;
    }
    

二、高精度减法

  1. 思路

    • 大整数的存储
    • 核心思想
      • 确保是大数减小数,首先从个位开始作差,取模存储在C中,t 表示借位(这里很巧妙具体看下面的代码
      • 每次各个位上的数作差 - 借位 t ,取模存起来,有借位 t=1,没有t=0;
      • 直到 大整数.size( ) 去前导0
  2. 模板

    #include<bits/stdc++.h>
    using namespace std;//判断两个大整数的大小 
    bool cmp(vector<int> &A,vector<int> &B){  if(A.size()!=B.size()) return A.size()>B.size();  //位数不同时 if(A.size()==B.size())   //位数相同时 for(int i=0;i<A.size();i++)if(A[i]!=B[i]) return A[i]>B[i];
    }//C=A-B
    vector<int> sub(vector<int> &A,vector<int> &B)
    {if(!cmp(A,B)) {cout<<'-';    //如果小减去大数:注意加个 - 负号 return sub(B,A);  //交换 }vector<int> C;int t=0;  //t表示借位 for(int i=0;i<A.size();i++){t=A[i]-t;  //各个位上的数,先减去借位if(i<B.size()) t-=B[i];    //B还有数的话,减去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();  //去掉前导0 如003 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=sub(A,B);for(int i=C.size()-1;i>=0;i--) printf("%d",C[i]);return 0;} 
    

三、高精度乘法

高精度乘法一般是 一个大整数乘一个比较小的数

  1. 思路

    • 大整数的存储

    • 核心思想

      • 小的数b不拆,让b依次和大数A的每一位相乘从A的个位开始,t表示进位;
      • 对每次计算A[i]*b+t的结果取模,存在结果数组中,借位除10即可,t可以任意大,比如可以进位22
      • 直到 大数的最高位&&t==0去掉前导0
    1. 模板
    #include<bits/stdc++.h>
    using namespace std;//C=A*b
    vector<int> mul(vector<int> &A,int b)
    {vector<int> C;int t=0;  //t表示进位for(int i=0;i<A.size()||t;i++){   //两个条件都满足才能退出来,否则没有计算完t=A[i]*b+t;   //A的每一位与b相乘加上进位C.push_back(t%10);   //对计算结果取模,存在结果数组中t/=10;  }while(C.size()>1&&C.back()==0) C.pop_back();  //去掉前导0return C;
    }int main()
    {string a;int b;   // 小的数用int 来存就OKvector<int> A;cin>>a>>b;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;} 
    

四、高精度除法

高精度除法一般是一个大的整数除以一个小的整数

  1. 思路

    • 大整数的存储
    • 核心思想
      • 从最高位开始,最高位除以除数,余数r剩下;
      • r*10+大整数的下一位,再除以除数,余数r剩下;
      • 重复,直到个位去掉前导0
  2. 模板

#include<bits/stdc++.h>
using namespace std;//A➗b=C...r
vector<int> div(vector<int> &A,int b,int &r)
{vector<int> C;r=0;  //r表示余数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();  //去掉前导0return C;
}int main()
{string a;int b;vector<int> A;cin>>a>>b;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]);printf("\n");printf("%d",r);return 0;}
http://www.lryc.cn/news/4589.html

相关文章:

  • 计算机网络-基本概念
  • 你评论,我赠书~【哈士奇赠书 - 13期】-〖Python程序设计-编程基础、Web开发及数据分析〗参与评论,即可有机获得
  • 【设计模式】我终于读懂了代理模式。。。
  • 每天10个前端小知识 【Day 2】
  • 帮助中心在线制作工具推荐这4款,很不错哟!
  • rabbitMQ相关文章汇总
  • 【C++】异常
  • @Validated注解不生效问题汇总
  • 华科万维C++章节练习2_4
  • 17万字数字化医院信息化建设大数据平台建设方案WORD
  • Android 11系统签名修改
  • 亚马逊、沃尔玛卖家自养号退款经验和测评技术
  • Spring Security in Action 第十一章 SpringSecurity前后端分离实战
  • 高级前端二面vue面试题(持续更新中)
  • 七大设计原则之依赖倒置原则应用
  • Dubbo面试题2023
  • Swift(5)
  • [Java 进阶面试题] CAS 和 Synchronized 优化过程
  • 算法思想 - 贪心算法
  • 解决需求变更难题的8大方案
  • NSSROUND#8[Basic]
  • Vue3代码初体验找不同
  • opencv调取摄像头录制
  • html标签手册
  • SpringMVC--视图、RESTful案例、处理AJAX请求
  • 一个同学升了leader,今年活还没干,他就已经想好组里成员的两次绩效考核怎么打了,还说:leader都是这样的!...
  • Docker 面试知识点
  • C++高级篇学习笔记
  • gentoo基本安装过程
  • 【LeetCode】1234. 替换子串得到平衡字符串