高精度乘法
高精度乘法指的是处理非常大的整数,这些整数超出了标准整数类型的表示范围。为了处理这种乘法,我们需要手动实现乘法算法,通常是通过模拟手工乘法的过程。
下面是一个高精度乘法的详细实现: 高精度乘法1
#include <bits/stdc++.h>
using namespace std;
//高精度乘法
string highPrecisionMultiply(const string &num1, const string &num2) {
vector<int> result(num1.size() + num2.size(), 0); // 初始化结果数组,长度为两个数的长度之和
int i, j;
// 从最低位开始逐位相乘
for (i = num1.size() - 1; i >= 0; --i) {
for (j = num2.size() - 1; j >= 0; --j) {
// 计算当前位的乘积,并加上之前的进位
int product = (num1[i] - '0') * (num2[j] - '0') + result[i + j + 1];
// 计算进位
result[i + j + 1] = product % 10;
// 更新进位
result[i + j] += product / 10;
}
}
// 移除结果前面的0
while (result.size() > 1 && result.back() == 0) {
result.pop_back();
}
// 将结果数组转换为字符串
string resultStr;
for (int digit : result) {
resultStr += (digit + '0');
}
// 如果结果为空,则返回"0"
return resultStr.empty() ? "0" : resultStr;
}
int main() {
string num1 = "123456789";
string num2 = "987654321";
string product = highPrecisionMultiply(num1, num2);
cout << product << endl;
return 0;
}
#include<bits/stdc++.h>
#include<vector>
using namespace std;
/*
当该位的值 %10之后 ,所剩下的数就是该进制下的数。若想进位到前者
则需要/10。上一位的数放到下一位的时候权重就会少10。
'0'=48,'a'=97,'A'=65
*/
vector<int> mul(vector<int> a,int b)
{
vector<int> c;
int t=0;
//y总对算法思路的掌握当真是令我五体投地!!
/*这里||t的运用是我没能想到的,即是对最高位的
的进位。如果不加这一步,总会缺个最高位
*/
for(int i=0;i<a.size()||t;i++)
{
if(i<a.size()) t+=a[i]*b;
//每一位数的值。。如果最后数值已经乘完,只有进位时,按照此规律将其附在后面就行
c.push_back(t%10);
//进位
t/=10;
}
//去前导0(更简洁的做法是特判一下b是否为0)
while(c.size()>1&&c.back()==0) c.pop_back();
return c;
}
int main()
{
string a;
int b;
cin >> a >> b;
//倒序输入,方便运算
vector<int> c;
for(int i=a.size()-1;i>=0;i--) c.push_back(a[i]-'0');
vector<int> sum;
sum=mul(c,b);
//倒序输出
for(int i=sum.size()-1;i>=0;i--) cout << sum[i];
return 0;
}
高精度乘法2 对某一位来说是这样的步骤:取bign的某位与int型整体相乘,再与进位相加,所得结果的个位数作为该结果,高位部分作为新的进位。对于a、b异号的情况只需要一个标志位变量记录,在输出的时候加上负号就行了。
//高精度乘以低精度
bign multi(bign a, int b)
{
bign c;
int carry = 0; //进位
for (int i = 0; i < a.len; i++)
{
int temp = a.d[i] * b + carry;
c.d[c.len++] = temp % 10; //个位作为该结果
carry = temp / 10; //高位部分作为新的进位
}
while (carry != 0) //和加法不一样,乘法的进位可能不止一位,因此用while
{
c.d[c.len++] = carry % 10;
carry /= 10;
}
return c;
}
高精度除法
高精度除法是高精度运算中最为复杂的一种,因为它不仅涉及到商的计算,还涉及到余数的处理。下面是一个高精度除法的实现示例:
#include <bits/stdc++.h>
using namespace std;
//高精度除以低精度
int main(){
string a,b; //a, b表示两个加数
int bl;
int al[10000]={0};
cin>>a>>b;
//输入段
stringstream ss;
ss<<b;
ss>>bl;
//这一段代码是将b数组直接从字符串转为整数
int an=a.length(), bn=b.length();
for (int i=0; i<an; i++){
al[i]=a[an-i-1]-'0';
}
//存储段
int c[10000]={0}, cn=an, y=0; //y存储余数
for (int i=an-1; i>=0; i--){
y=y*10+al[i];
c[i]=y/bl;
y=y%bl;
}//除法段
while (c[cn-1]==0&&cn!=1) cn--;
for (int i=0; i<cn; i++){
cout<<c[cn-i-1];
}//输出段
cout<<endl;
cout<<y;
//这里下方的输出是输出余数
return 0;
}
接下来就是比较难操作的高精度除以高精度了 我们知道,除法的本质是减法,多次的减法就是除法 所以高精度除以高精度的本质方法就是减法: 通过一次次的相减,得到最后的结果
但是—— 我一个数除以另一个数的商太大怎么办? 这样会超时的啊, 所以减法就得精简起来 那么怎么精简呢?——高精除以低精的重要性就在这里了 在高精除以低精中,我们是一位位往下除, 那减法,是不是也一位位往下减就可以了
那么高精除以高精的整个步骤如下:
判断是否能够除 除到不能除 往上一位推 接下来我们来逐步剖析这三个部分:
第一部分就是判断能否除, 那这部分啊-其实很简单,只有一步,就是判断目前退位到的被除数是否比除数大(相等也行) 比较的程序就很简单了: 先判断位数,再从最高位开始比起,以此往下比,比到最后一位,如果相等,那么也可以作除法 完整代码如下:
#include <bits/stdc++.h>
using namespace std;
//高精度除以低精度
string a, b; //a, b表示两个被减数与减数
int al[100]={0}, bl[100]={0};
int an, bn;
int compare(int p){
if (al[p+bn]>0) return 1; //这里判断的方法就是判断a[]中b总共位数的下一位是否有得除
else{
for (int i=bn-1; i>=0; i--){
if (al[p+i]>bl[i]){
return 1;
}else if (al[p+i]<bl[i]){
return 0;
}
}
}
return 1;
}
int main(void){
cin>>a>>b;
an=a.length(), bn=b.length(); //获取a, b的长度
//输入段
for (int i=0; i<an; i++){
al[i]=a[an-i-1]-'0';
}for (int i=0; i<bn; i++){
bl[i]=b[bn-i-1]-'0';
}
//存储段
int c[1000]={0}, cn=an;
for (int i=an-1; i>=0; i--){
while (compare(i)){ //用while循环判断是否能够除
c[i]++; //将c数组的值相加,存下减了几次(这个用不是人话来说就是商)
for (int j=0; j<bn; j++){
al[i+j]=al[i+j]-bl[j];
}for (int j=0; j<bn; j++){
if (al[i+j]<0){
al[i+j+1]--;
al[i+j]+=10;
}
}
}
}
//进位段
while (c[cn-1]==0&&cn!=1){
cn--;
}//调整段
for (int i=0; i<cn; i++){
cout<<c[cn-i-1];
}//输出段
return 0;
}
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> div(vector<int> &A,int &b,int &r)
{
vector<int> C;
/*
高精度的加、减、乘都是从原字符串的个位开始运算,而除法是从高位
向低位进行运算。为了保持四则输入输出的完整性,
在这里牺牲掉函数。
*/
//从最高位开始运算,而由于输入时是逆序输入,所以运算时从
//A容器的最后面开始运算,令i=A.size()-1
for(int i=A.size()-1;i>=0;i--)
{
/*余数r,该位的被除数等于这一位的数值+
上一位余数的十倍 (上一位是高位,降位权值扩大十倍)*/
r=r*10+A[i];
//结果的位数数值等于被除数/除数
C.push_back(r/b);
//取余
r=r%b;
}
//如上所述,为了保持输出(逆序)的一致性,在这里将正序的C再逆序一边。
reverse(C.begin(),C.end());//调用该函数需要包含#include<algorithm>头文件
//去前导0
while(C.size()>1&&C.back()==0) C.pop_back();
return C;
}
int main()
{
string A;
int b;
cin >> A >>b;
vector<int> B,C;
//逆序输入
for(int i=A.size()-1;i>=0;i--) B.push_back(A[i]-'0');
int r=0;
C=div(B,b,r);
//逆序输出
for(int i=C.size()-1;i>=0;i--) cout << C[i];
cout << endl << r;
return 0;
}