高精度||有所更新完善
2024-10-12 20:37:30
发布于:浙江
高精度算法通常被用于解决大数字之间的加减乘除的问题。
高精度算法的操作步骤
1. 存储
假如说现在有一个需要输入存储在计算机当中。为了存储这个数字,我们会采用数组的方式来储存。
使用数组当中的每一格来存储数字的每一位的数值。
通常我们会去使用string的数据类型来存储输入进来的特别大的数字。
在面对加、乘、减的运算的时候,我们是从个位的开始运算的,为了使得两个计算操作数个位对齐,在存储的时候我们还会将其逆序存储到数字数组
int a[MAXN];
int b[MAXN];
string s1,s2;
cin >> s1 >> s2;
int len1 = s1.size() ;
int len2 = s2.size();
for(int i = 0 ; i < len1 ; i ++)
{
a[i] = s1[len1 - i - 1] - '0';
}
for(int i = 0 ; i < len2 ; i ++)
{
b[i] = s2[len2 - i - 1] - '0';
}
在除法的时候,因为计算是从最高位开始,所以则正序存储
string s;
cin >> s;
int len = s.size();
for(int i = 0 ;i < len ; i ++ )
{
a[i] = s[i] - '0';
}
模拟竖式计算
加法: 两两相加,可能出现进位情况
int c[100005];
int len = max(len1,len2); // 获取较**大小
for(int i = 0 ; i < len ; i ++ )
{
// 两两相加
c[i] += a[i] + b[i];
if(c[i] >= 10) { // 进位
c[i] %= 10;
c[i+1] += 1;
}
}
减法: 两两相减,不够借位
for(int i = 0 ; i < len ; i ++ )
{
c[i] = a[i] - b[i];
if(c[i] < 0){
// 借位
c[i] += 10;
c[i+1] -= 1;
}
}
乘法: 两位相乘,结果位数为两位的位数相加开始向前进位
for(int i = 0 ; i < len1 ; i ++ )
{
for(int j = 0 ; j < len2 ; j ++ )
{
c[i + j] += c[i] * c[j] ;
if(c[i + j] >= 10){
// 进位
c[i + j + 1] += c[i + j] / 10 ;
c[i + j] %= 10;
}
}
}
除法: 最高位开始进行除,余数进位与后一位结合继*除,直到全部除完才结束。
long long r = 0 ; // 余数
for(int i = 0 ; i < len ; i ++ )
{
r = r * 10 + a[i]; // 进位 结合后一位
c[i] = r / b ; // b是除数
r %= b;
}
3. 去除前导零/判断进位
4. 正序/逆序输出
这里空空如也
有帮助,赞一个