- 2022tysc1451 的博客
2.高精度笔记
-
2022tysc1451
LV 9
@
2025-3-19 18:14:05
高精度的概念
在我们进行计算的过程中，经常会遇到几十位，甚至几百位的数字的计算问题，也有可能会遇到小数点后几十位，几百位的情况，而我们面对这样的情况下, long long 和 double的数据范围显然是不够使用的了。因此这时，我们就需要引入一个新的算法，叫做高精度算法 . 我们可以利用程序设计的方法去实现这样的高精度计算 . 介绍常用的几种高精度计算的方法 . 思想
高精度算法本质上是用字符串模拟数字进行计算，再利用类似于数学里的竖式的形式，一位一位进行相关计算 . 处理
高精度计算中需要处理好以下几个问题：
（1）数据的接收方法和存储方法 数据的接收和存储：当输入的数很长时，可采用字符串方式输入，这样可输入位数很长的数，利用字符串函数和操作运算，将每一位取出，存入数组中 .
void init(int a[]) { // 传入数组
string s;
cin >> s;
len = s.length(); // s.length --> 计算字符串位数
for(int i=1; i<=len; i++)
a[i] = s[len -i] - '0'; //将字符串s转换为数组a, 倒序存储
}
（2）进位、借位的处理.
// 加法进位: c[i] = a[i] + b[i]
code: if(c[i] >= 10) {
c[i] %= 10;
++c[i++];
}
//减法借位: c[i] = a[i] - b[i]
code: if(a[i] < b[i]) {
--a[i+1];
a[i] += 10;
}
//乘法进位: c[i + j - 1] = a[i] * b[j] + x + c[i + j - 1];
x = c[i + j - 1] / 10;
c[i + j - 1] % 10;
高精度加法
输入两个数到变量中，然后用赋值语句求它们的和后输出 . But，我们知道，在 C++ 语言中任何数据类型都有一定表示范围. 当两个加数很大时，以前的算法显然不能求出精确解，因此我们需要寻求另一种方法 .在读小学时，我们做加法都采用竖式方法 . 这样我们方便写出两个整数相加的算法 .
#include <cstdio>
#include <cstring>
using namespace std;
int main() {
char a1[5005], b1[5005]; //用字符存储数字
int a[5005], b[5005], c[5005]; //c[i] 用来储存每位相加的结果
int len_a, len_b, len_c = 1, x, i;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
scanf("%s%s", a1, b1); //输入两个加数
len_a = strlen(a1);
len_b = strlen(b1);
for(i=0; i<len_a; i++) a[len_a - i] = a1[i] - '0'; // 将加数放进a数组
for(i=0; i<len_b; i++) b[len_b - i] = b1[i] - '0'; // 将另一个加数放进b数组
x = 0; // x为进位
while(len_c <= len_a || len_c <= len_b) {
c[len_c] = a[len_c] + b[len_c] + x; // 两数相加，再加上前两个数进位的
x = c[len_c] / 10; // 刷新进位
c[len_c] %= 10; // 进位后剩下的
len_c++; //位数加1
}
c[len_c] = x;
if(c[len_c] == 0) { //判断首位是否为0
len_c--; // 不输出此位
}
for(int i=len_c; i>=1; i--) {
printf("%d", c[i]); //输出每一位的数
}
return 0;
}
高精度减法
类似加法，同样使用竖式。在做减法运算时，需要注意的是：需要有借位处理。
#include <iostream>
#include <cstring>
int main() {
int a[5005], b[5005], c[5005];
int lena, lenb, lenc, i;
char n[5005], n1[5005], n2[5005];
std::memset(a, 0, sizeof(a));
std::memset(b, 0, sizeof(b));
std::memset(c, 0, sizeof(c));
std::cin >> n1 >> n2; //输入被减数和减数
lena = std::strlen(n1);
lenb = std::strlen(n2);
for(i=0; i<lena; i++) a[lena - i] = (int)n1[i] - '0';
for(i=0; i<lenb; i++) b[lenb - i] = (int)n2[i] - '0'; //逆序存放排列
i = 1;
while(i <= lena || i <= lenb) {
if(a[i] < b[i]) {
c[i] = a[i] + 10 - b[i];
a[i+1]--; //借位处理
}
else {
c[i] = a[i] - b[i];
}
i++;
}
lenc = i;
while(c[lenc] == 0 && lenc > 1) { //如果最后一位是0，是需要输出的
lenc--; // 不输出首位0
}
for(i=lenc; i>=1; i--) std::cout << c[i];
return 0;
}
高精度乘法
类似加法，使用竖式。在做乘法时，同样也有进位。 分析数组的下标变化规律，可以写出以下关系式:
c[i+j-1]=a[i]+b[j]+x+c[i+j-1]
由此可见，跟乘积有关，跟上次的进位有关，跟还原的值有关，分析下标规律，有:
#include<iostream>
#include<string>
using namespace std;
string y,z;
int a[50001],b[50001],c[50001];
int main(){
cin>>y>>z;
int sa=y.size(),sb=z.size();
for(int i=1;i<=sa;i++)a[i]=y[sa-i]-'0';
for(int i=1;i<=sb;i++)b[i]=z[sb-i]-'0';
for(int i=1;i<=sa;i++){
for(int j=1;j<=sb;j++){
c[i+j-1]+=a[i]*b[j];
}
}
int size=sa+sb;
for(int i=1;i<size;i++){
if(c[i]>9){
c[i+1]+=c[i]/10;
c[i]%=10;
}
}
while(c[size]==0&&size>1)size--;
for(int i=size;i>=1;--i)cout<<c[i];
return 0;
}
除法
(1）高精除以低精 做除法时，每一次的商值都在 0~9 之间，每次求得的余数连接以后的若干位得到新的被除数，继续做除法。因此，在做高精度除法时，要涉及到乘法运算和减法运算，还有移位处理。当然，为了程序简洁，可以避免高精度乘法，用 0~9 次循环减法取代得到商的值。采用按位相除法。
#include <iostream>
int main(){
char n1[100];
int a[100], c[100], lena, i, x = 0, lenc, b;
std::memset(a, 0, sizeof(a));
std::memset(c, 0, sizeof(c));
std::cin >> n1 >> b;
lena = strlen(n1);
for(i=1; i<=lena; i++) {
a[i] = n1[i - 1] - '0'; //除法不需要逆序存放
}
//-------------------------初始化------------------------------
for(i=1; i<=lena; i++) {
c[i] = (a[i] + x * 10) / b; // 算上上一位剩下的继续除
x = (a[i] + 10 * x) % b; // 求余
}
lenc = 1;
while(c[lenc] == 0 && lenc < lena) {
lenc++;
}
for(i=lenc; i<lena; i++) std::cout << c[i];
return 0;
}
(2）高精除以高精 高精除以低精是对被除数的每一位（这里的"一位"包含前面的余数，以下都是如此）都除以除数，而高精除以高精则使用减法模拟除法，对被除数的每一位都减去除数，一直减到当前位置的数字（包含前面的余数）小于除数（由于每一位的数字小于10，所以对每一位最多进行10次运算），代码如下：
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int a[50005], b[50005], c[50005], d;
void init(int a[]) {
char s[50005];
cin >> s;
a[0] = strlen(s); // 字符串存储，表示位数
for (int i=1; i<=a[0]; i++) {
a[i] = s[a[0]-i] - 48; // 正序储存
}
}
void print(int a[]) {
if (a[0] == 0) {
cout << 0 << endl;
return; // 位数为0，输出0
}
for (int i=a[0]; i>=1; i--) {
cout << a[i]; // 输出函数
}
cout << endl;
return;
}
int compare(int a[], int b[]) {
if (a[0] > b[0]) {
return 1; // 被减数大于减数
}
if (a[0] < b[0]) {
return -1; // 被减数小于减数
}
for (int i=a[0]; i>=1; i--) {
if (a[i] > b[i]) {
return 1;
}
if (a[i] < b[i]) {
return -1;
} // 位数相同，找到第一位不同的进行比较
}
return 0;
}
void numcpy(int p[], int q[], int det) {
for (int i=1; i<=p[0]; i++) {
q[i+det-1] = p[i]; //复制p数组到q数组从det开始的地方
}
q[0] = p[0] + det - 1;
}
void jian(int a[], int b[]) {
int flag = compare(a, b);
if (flag == 0) {
a[0] = 0;
return;
}
if (flag == 1) {
for (int i=1; i<=a[0]; i++) {
if (a[i] < b[i]) {
a[i+1]--;
a[i] += 10;
}
a[i] -= b[i];
}
while (a[0]>0 && a[a[0]]==0) {
a[0]--;
}
return;
}
} // 高精减法
void chugao(int a[], int b[], int c[]) {
int tmp[50005];
c[0] = a[0] - b[0] + 1;
for (int i=c[0]; i>0; i--) {
memset(tmp, 0, sizeof(tmp));
numcpy(b, tmp, i);// 清零
while (compare(a, tmp) >= 0) {
c[i]++;
jian(a, tmp); // 用减法模拟
}
}
while (c[0] > 0 && c[c[0]] == 0) {
c[0]--;
}
return;
}
int main() {
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(c, 0, sizeof(c));
init(a);
init(b);
chugao(a,b,c);
print(c);
return 0;
}
高精度模板
#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#pragma GCC optimize(2,3,"Ofast","inline")
const int N=1e6+10,M=1010,P=1e9+7,MOD=998244353,PI=3.1415926;
const int MAXN=1e5+10;
struct HA{
int v[MAXN]={0};
int len=0;
//读入高精度
void read(){string s;cin>>s;if(s=="0")return;len=s.length();for(int i=1;i<=len;i++)v[i]=s[len-i]-'0';}
//输出高精度
void print(){if(len==0)printf("0");for(int i=len;i>=1;i--)printf("%d",v[i]);}
//拷贝高精度
HA cpy()const{HA b;b.len=len;for(int i=1;i<=len;i++)b.v[i]=v[i];return b;}
//将单精度的值赋给高精度
void get(const int &k){len=0;int t=k;while(t>0){len++;v[len]=t%10;t/=10;}}
//高精度ADD加法
HA operator+(const HA &b)const{
HA c;c.len=max(len, b.len);
for(int i=1;i<=c.len;i++){c.v[i]+=v[i]+b.v[i];c.v[i+1]+=c.v[i]/10;c.v[i]%=10;if(c.v[c.len+1]>0)c.len++;}
return c;//返回答案
}
//高精度SUB减法
HA operator-(const HA &b)const{
HA c;c.len=len;
for(int i=1;i<=c.len;i++){c.v[i]+=v[i]-b.v[i]+10;c.v[i+1]+=c.v[i]/10-1;c.v[i]%=10;}
while(c.len>0&&c.v[c.len]==0)c.len--;//退位
return c;
}
//高精度MUL乘法
HA operator*(const HA &b)const{
HA c;if(len==0||b.len==0)return c;//特判乘0
for(int i=1;i<=len;i++)for(int j=1;j<=b.len;j++){c.v[i+j-1]+=v[i]*b.v[j];c.v[i+j]+=c.v[i+j-1]/10;c.v[i+j-1]%=10;}
c.len=len+b.len-1;
while(c.v[c.len+1]>0){c.len++;c.v[c.len+1]+=c.v[c.len]/10;c.v[c.len]%=10;}//删除0
return c;
}
//高精度DIV除法 高精度除高精度
HA operator/(const HA &b)const{
HA c;HA rem;
for(int i=len;i>=1;i--){
rem=rem*10+v[i];
//rem/b使用while->减法实现
while (rem>=b){rem=rem-b;c.v[i]++;}
if(c.v[i]>0&&c.len==0)c.len=i;//找到最高位
}
return c;
}
//高精度MOD取余
HA operator %(const HA &b)const{HA c=this->cpy();return (c-((c/b)*b));}
//高精度加低精度
HA operator+(const int &k)const{
HA c;int t=k;c.len=len;
if(c.len==0&&k>0)c.len=1;//特判初始为0的高精度
for(int i=1;i<=c.len;i++){c.v[i]+=v[i]+t%10;t/=10;c.v[i+1]+=c.v[i]/10;c.v[i]%=10;if(c.v[c.len+1]>0||(i==c.len&&t>0))c.len++;}
return c;
}
//高精度减低精度
HA operator-(const int &k)const{
HA c;c.len=len;int t=k;
for(int i=1;i<=c.len;i++){c.v[i]+=v[i]+10-t%10;t/=10;c.v[i+1]+=c.v[i]/10-1;c.v[i]%=10;}
while(c.len>0&&c.v[c.len]==0)c.len--;
return c;
}
//高精度乘低精度
HA operator*(const int &k)const{
HA c;if(len==0||k==0)return c;c.len=len;
for(int i=1;i<=c.len;i++){c.v[i]+=v[i]*k;c.v[i+1]+=c.v[i]/10;c.v[i]%=10;if(c.v[c.len+1]>0)c.len++;}
return c;
}
//高精度除低精度
HA operator/(const int &k)const{HA c;
long long rem=0;
for (int i=len;i>=1;i--){
rem=rem*10+v[i];c.v[i]=rem/k;rem%=k;
if(c.v[i]>0&&c.len==0)c.len=i;//找到最高位
}
return c;
}
//高精度除低精度
HA operator%(const int &k)const{HA c=this->cpy();return(c-((c/k)*k));}
//高精度bool运算
bool operator==(const HA &b)const{
if(len!=b.len)return 0;
for (int i=1;i<=len;i++)if(v[i]!=b.v[i])return 0;
return 1;
}
bool operator!=(const HA &b)const{HA c=this->cpy();return!(c==b);}
bool operator>(const HA &b)const{
if(len!=b.len)return len>b.len;
for(int i=len;i>=1;i--)if(v[i]!=b.v[i])return(v[i]>b.v[i]);
return 0;
}
bool operator>=(const HA &b)const{HA c=this->cpy();return(c==b||c>b);}
bool operator<(const HA &b)const{HA c=this->cpy();return !(c>=b);}
bool operator <=(const HA &b)const{HA c=this->cpy();return !(c>b);}
};
signed main(){
return 0;
}