高精度(加减乘除)
高精度的核心思想就是利用数组去储存大数,然后通过模拟手动计算的方式,来进行计算。
主要分三个模块:
1.读入数据并转换为(int)类型储存
高精度加法
核心思想:将每个位上的数字都+起来,如果大于10就进位。
核心代码如下:
c[i]+=a[i]+b[i];//两数相加
c[i+1]+=c[i]/10;//进位
c[i] = c[i]%10;//保留
完整代码及解析如下:
string x, y;//两个string类用来接收大数
//a接收x中的每一位数字,b用来接收y中的每一位数组,计算之后,储存到c数组中
int a[999], b[999], c[999];
int main()
{
cin >> x >> y;//读入
//将大数的每一位数转换为(int)类型,然后倒序储存
for (int i = 0; i < x.length(); i++)
{
a[i] = x[x.length() - 1 - i]-'0';
}
for (int i = 0; i < y.length(); i++)
{
b[i] = y[y.length() - 1 - i]-'0';
}
//核心:开始计算
//位数问题:两个数相加,和的位数等于max(x.length(), y.length(),或者是其+1;
for (int i = 0; i < max(x.length(), y.length()); i++)
{
c[i] += a[i] + b[i];//对应位数求和
c[i + 1] += c[i] / 10;//进位
c[i] = c[i] % 10;//保留
}
//下面开始消除前导0
int k = 0;//利用k来修正位数
if (c[max(x.length(), y.length())] == 0)//如果最高位==0
{
k = 1;//k++输出位数-1
}
//注意看k是如何控制位数的
for (int i = max(x.length(), y.length())-k; i >=0 ; i--)
{
cout << c[i];
}
cout << endl;
//完美落幕
return 0;
}
高精度减法
减法核心:只使用大数减小数,如果某一位小于0,就向前一位借1
核心代码如下:
c[i]+=a[i]-b[i];//两数相减,储存到c
if(c[i]<0)//如果小于0
{
//借1
c[i+1]--;
c[i]+=10;
}
完整代码及解析如下:
string x, y;//x和y用来接收大数
//a,b用来储存大数的每一位数
int a[20000], b[20000], c[20000];
bool cmp(string x, string y)//比较x,y
{
//先比较位数,位数长的一定是较大数
if (x.size() != y.size())
{
return x.size() > y.size();
}
else//如果位数相同就从高到低比较每一位
{
for (int i = 0; i < x.size(); i++)
{
//如果某一位数字不相同就退出函数
if (x[i] > y[i])
{
return true;
}
else if(x[i]<y[i])
{
return false;
}
}
//如果一直相等就返回true
return true;
//注意返回值不能用return 0/1来写
//必须用return true/false
}
}
int main()
{
cin >> x >> y;
//因为x-y有负数存在,所以我们只用大数减小数,最后补全-号就行
//下面进行比较:如果y比x大,就交换位置,并输出-号
if (cmp(x, y) == false)//详见上方的cmp函数
{
swap(x, y);
cout << "-";
}
//转换为Int类型并倒序储存
for (int i = 0; i < x.length(); i++)
{
a[i] = x[x.length() - 1 - i]-'0';
}
for (int i = 0; i < y.length(); i++)
{
b[i] = y[y.length() - 1 - i]-'0';
}
//核心代码
//位数问题:两个数相减,差的位数最多是max(x.length(), y.length()
for (int i = 0; i < max(x.length(), y.length()); i++)
{
c[i] += a[i] - b[i];
if (c[i] < 0)//借1
{
c[i + 1] -= 1;
c[i] += 10;
}
}
int k = 0;
//除0
for (int i = max(x.length(), y.length()); i > 0; i--)
{
if (c[i] == 0)
{
k++;
}
else
{
break;
}
}
for (int i = max(x.length(), y.length())-k; i >= 0; i--)
{
cout << c[i];
}
cout << endl;
return 0;
}
高精度乘法
核心思想:利用两数相乘的特点确定c的位置,之后同加法
位数问题:两个数相乘,积的位数最多是两个数的位数之和
核心代码如下:
for (int i = 1; i <=x.length(); i++)
{
for (int j = 1; j <= y.length(); j++)
{
c[i + j - 1]+= a[i] * b[j];//c的下标等于a,b的下标之和-1
c[i + j] += c[i + j - 1] //10;进位
c[i + j - 1] %= 10;//保留
}
}
完整代码及解析如下:
string x, y;
int a[99999], b[99999], c[99999];
int main()
{
cin >> x >> y;
for (int i = 0; i < x.length(); i++)
{
a[i+1] = x[x.length() - 1 - i]-'0';
}
for (int i = 0; i < y.length(); i++)
{
b[i+1] = y[y.length() - 1 - i]-'0';
}
//核心代码
for (int i = 1; i <=x.length(); i++)
{
for (int j = 1; j <= y.length(); j++)
{
c[i + j - 1]+= a[i] * b[j];
c[i + j] += c[i + j - 1] / 10;
c[i + j - 1] %= 10;
}
}
//除0
int k = 0;
for (int i = x.length()+ y.length(); i >=2; i--)
{
if (c[i] == 0)
{
k++;
}
else
{
break;
}
}
for (int i = x.length()+ y.length()-k; i >=1 ; i--)
{
cout << c[i];
}
cout << endl;
return 0;
}
高精度除法(高精度除以低精度)
核心思想:利用手动除法的特点,将除法转化为减法,再进行计算
核心代码如下:
for (int i = 0; i < s.size(); i++)
{
c[i] += (x * 10 + a[i]) / b;//将每次除法之后的余数+a[i]之后再去除除数
x = (x * 10 + a[i]) % b;//x为每次除法之后的余数
}
完整代码及解析如下
string s;
long long b;
long long a[99999], c[99999],x;
int main()
{
cin >> s >> b;
//注意除法时是正序输入
for (int i = 0;i<s.size();i++)
{
a[i] = s[i] - '0';
}
//核心代码
for (int i = 0; i < s.size(); i++)
{
c[i] += (x * 10 + a[i]) / b;
x = (x * 10 + a[i]) % b;
}
//除0
int k = 0;
for (int i = 0; i < s.size()-1; i++)
{
if (c[i] == 0)
{
k++;
}
else
{
break;
}
}
for (int i = k; i < s.size(); i++)
{
cout << c[i];
}
cout << endl;
return 0;
}
版权声明:除特别声明外,本站所有文章皆是本站原创,转载请以超链接形式注明出处!