当前位置：首页 > java >正文

算法的几大模块

java 2025/6/17 13:55:33

在我们学习c++中，算法是一个非常重要的一个模块。；

一下就是算法的几大模块。

一、高精度计算模块

高精度计算模块用于处理超大整数（如超过 10^1000 位）的精确运算，核心模块包括：

数据存储与转换
- 倒序存储：将数字字符串反转后存入数组（如 a[i] = s[len-1-i] - '0'），实现个位对齐，便于进位操作。
- 动态容器：常用 vector 或数组存储，支持动态扩展位数。
运算核心逻辑
高精度加法：逐位相加并处理进位（c[i] = a[i] + b[i] + carry; carry = c[i]/10），最高位可能新增进位。

#include <bits/stdc++.h>//有进位
using namespace std;
int a1[10005],b1[10005],s[100005];
int main(){string a,b;cin>>a>>b;//获取长度int la=a.size();int lb=b.size();int ls=la+lb;//逆序存储(因为要从个位开始加) for(int i=0;i<la;i++){//存到数组下标la-1的位置上 a1[la-i]=a[i]-'0';}for(int i=0;i<lb;i++){//存到数组下标lb-1的位置上 b1[lb-i]=b[i]-'0';}//使用for循环帮助我们进行加法运算，每一位对应相加for(int i=1;i<ls;i++){s[i]=a1[i]+b1[i];}//处理进位 for(int i=1;i<ls;i++){s[i+1]+=s[i]/10;s[i]=s[i]%10;}//删除多余的0while(s[ls]==0&&ls>1){ls--;}for(int i=ls;i>=1;i--){cout<<s[i];}return 0;
}

#include <bits/stdc++.h>//无进位
using namespace std;
int a1[1005],b1[1005],s[1005];
int main(){string a,b;cin>>a>>b;int la=a.size();int lb=b.size();int ls=max(la,lb);for(int i=0;i<la;i++){a1[la-i]=a[i]-'0';} for(int i=0;i<lb;i++){b1[lb-i]=b[i]-'0';}for(int i=1;i<=ls;i++){s[i]=a1[i]+b1[i];}for(int i=ls;i>=1;i--){cout<<s[i];}return 0;
}

高精度减法：逐位相减并处理借位（若 c[i] < 0 则 c[i] += 10; c[i+1]--）。预处理比较大小，确保被减数 ≥ 减数，否则交换并标记负号。

#include <bits/stdc++.h>
using namespace std;
int a1[10005],b1[10005],s[10005];
int main(){//高精度减法string a,b;cin>>a>>b;//考虑a<b的情况if(a.size()<b.size()||a.size()==b.size()&&a<b){cout<<"-";swap(a,b);}//转换为数字逆序存入数组int la=a.size();//la肯定更大 int lb=b.size();for(int i=0;i<la;i++){a1[la-i]=a[i]-'0';}for(int i=0;i<lb;i++){b1[lb-i]=b[i]-'0';}//逐位进行减法运算for(int i=1;i<=la;i++){//结束条件以数字较长的为准 //考虑a1[i]<b1[i] ,则需要借位 if(a1[i]<b1[i] ){s[i]=a1[i]+10-b1[i];a1[i+1]=a1[i+1]-1;}else{s[i]=a1[i]-b1[i];}}//删除高位0while(s[la]==0&&la>1){la--;}//逆序输出for(int i=la;i>=1;i--){cout<<s[i];} return 0;
}

高精度乘法：双层循环模拟竖式（c[i+j] += a[i] * b[j]），再统一处理进位。

#include <bits/stdc++.h>
using namespace std;
int a1[10005],b1[10005],s[10005];
int main(){//高进度乘法string a,b;cin>>a>>b;int la=a.size();int lb=b.size();int ls=la+lb;for(int i=0;i<la;i++){a1[la-i]=a[i]-'0';}for(int i=0;i<lb;i++){b1[lb-i]=b[i]-'0';}//逐位相乘for(int i=1;i<=la;i++){for(int j=1;j<=lb;j++){s[i+j-1]+=a1[i]*b1[j];}}//处理进位for(int i=1;i<=ls;i++){s[i+1]+=s[i]/10;s[i]%=10;} //s删除多余的0 while(s[ls]==0&&ls>1){ls--;}for(int i=ls;i>=1;i--){cout<<s[i];}return 0;
}

高精度除法：
- 高精度除以高精度：通过减法模拟试商过程。
- 高精度除以低精度：逐位试商，保留余数。

#include <bits/stdc++.h>
using namespace std;
int a1[10005],s[10005];
int main(){//高精度/低精度 string a;//被除数 long long b;//除数 cin>>a>>b;//把字符串里的字符转换成数字int la=a.size();for(int i=0;i<la;i++){//从下标1的位置 a1[i+1]=a[i]-'0';}//模拟除法运算for(int i=1;i<=la;i++){s[i]=a1[i]/b;int yu=a1[i]%b;a1[i+1]=a1[i+1]+yu*10;} //删除多余的0int ks=1;while(s[ks]==0&&ks<la){ks++;}//输出for(int i=ks;i<=la;i++){cout<<s[i];} return 0;
}

结果优化
- 去除前导零：如 while (c[l-1] == 0 && l > 1) l--。
- 处理符号与零值：减法结果可能为负，加法需处理最高位进位。

其中还有高精度求阶乘

以下是代码展示

#include <bits/stdc++.h>
using namespace std;
int a[400000];//用来存我们每次相乘的结果，结果的每一位放入一个对应的编号中 
int main(){int n,wei=1;cin>>n;a[1]=1;for(int k=1;k<=n;k++){//让存在数组中的每一位依次与k相乘 for(int i=1;i<=wei;i++){a[i]=a[i]*k;}//处理进位问题,最后一位单独处理 for(int i=1;i<wei;i++){a[i+1]=a[i+1]+a[i]/10;a[i]=a[i]%10;}//处理最后一位的进位问题while(a[wei]>9){a[wei+1]=a[wei+1]+a[wei]/10;a[wei]=a[wei]%10;wei++;} }for(int i=wei;i>=1;i--){cout<<a[i];}return 0;
}

二、前缀和与差分模块

前缀和与差分模块用于高效处理区间查询与更新问题：

前缀和（Prefix Sum）
- 定义数组 S[i] = a[0] + a[1] + ... + a[i]。
- 应用：快速计算区间和（S[r] - S[l-1]）。
差分（Difference）
- 定义数组 d[i] = a[i] - a[i-1]（d[0] = a[0]）。
- 应用：区间增减操作（如 d[l] += v, d[r+1] -= v），再通过前缀和还原数组。