高精度除以高精度の原理and代码及优化
2024-08-15 18:53:05
发布于：浙江
38阅读
0回复
0点赞
高精度除以高精度就是用减法模拟除法，对被除数的每一位都减去除数，一直减到当前位置的数字（包括前面的余数）小于除数（由于每一位数字都小于10，所以每一位最多进行10次运算）
高精度除以高精度的原理主要涉及几个关键步骤，包括数据的接收与存储、算法基本原理、以及具体的计算过程。
数据的接收与存储：
高精度数通常以字符串的形式读入，并保存在字符数组中。
使用strlen函数计算高精度数的位数，并将其存储在整型数组中。
将字符串中的字符逐个转换为数字，并倒序存储在整型数组中，以确保运算从低位开始。
算法基本原理：
高精度除以高精度的基本原理是通过模拟手工除法的步骤，包括试商、减法等步骤。
试商阶段是通过观察被除数和除数的高位数字来估计一个商的值。
减法阶段则是用被除数减去估计的商乘以除数，如果结果为负，则调整商的值，直到得到正确的余数。
具体的计算过程：
在高精度除法中，通常采用倒序的方式进行计算，从被除数的最低位开始，逐位进行除法运算。
在每一步中，将余数左移一位（相当于乘以10），然后加上下一位被除数，再用这个新的“余数”去除以除数，得到商并更新余数。
重复上述步骤，直到被除数的所有位都被处理完，最后得到的商和余数即为高精度除以高精度的结果。
//高精除以高精
#include<bits/stdc++.h>
using namespace std;
const long long N = 1e6+5;
int a[N],b[N],c[N];
string s1,s2;
int lena,lenb;
bool f(int i){
if(a[i+lenb] != 0){
return true;
}
for(int j = lenb - 1; j >= 0; j --){
if(a[j+i] > b[j]){
return true;
}else if(a[j+i] < b[j]){
return false;
}
}
return true;
}
int main(){
cin >> s1 >> s2;
int len = s1.size();
for(int i = 0 ; i < len ; i ++ ){
a[len-i-1] = s1[i] - '0';
}
len = s2.size();
for(int i = 0 ; i < len ; i ++ ){
b[len-i-1] = s2[i] - '0';
}
lena = s1.size();
lenb = s2.size();
for(int i = lena-lenb;i >= 0;i--){
while(f(i)){
for(int j=0;j<len;j++){
a[i+j] = a[i+j] - b[j];
if(a[i+j] < 0){
a[i+j]+=10;
a[i+1+j]--;
}
}
c[i]++;
}
}
len = lena - lenb + 1;
if(len > 1 && c[len-1] == 0){
len -- ;
}
while(lena > 1 && a[lena-1] == 0){
lena--;
}
for(int i = len-1;i >=0;i--){
cout<<c[i];
}
cout<<endl;
for(int i = lena-1;i >=0; i--){
cout<<a[i];
}
return 0;
}
优化方法
这种方法是可以将商10个10个，100个100个甚至100000000个100000000个运算，大大提高了效率。
有帮助，赞一个