青岛圭谷网站建设公司,wordpress数据库里面改端口,商务网站建设详细流程,专业网站制作公司地址加法#xff1a;
大整数该如何储存#xff1f;
用数组储存#xff1a;
把个位放在数下标为0的位置#xff0c;十位放在数组下标为1的位置#xff08;也就是高位放在数组的后面#xff09;
因为这样#xff0c;如果需要增加一位最高位#xff0c;那我们就可以直接在…加法
大整数该如何储存
用数组储存
把个位放在数下标为0的位置十位放在数组下标为1的位置也就是高位放在数组的后面
因为这样如果需要增加一位最高位那我们就可以直接在vector数组的最后push_back最高位到结果数组即可。如果数组低位存的是数的高位那么我们进行这个操作的时候就需要往后一个一个移动数组效率很慢。
例题: #includebits/stdc.h
using namespace std;
vectorint add(vectorint A,vectorint B)
{vectorint C;int t 0;//用来存每一位的进位以及用来储存每一位相加后的结果for(int i0;i A.size()||i B.size();i){if(i A.size()) t A[i];if(i B.size()) tB[i];C.push_back(t % 10);t/10;//转化为进位数}if(t) C.push_back(t);//如果需要再进位就需要增加最高位return C;
}
int main()
{string a,b;cinab;vectorint A,B;for(int ia.size()-1;i0;i--) A.push_back(a[i] - 0);for(int ib.size()-1;i0;i--) B.push_back(b[i] - 0);auto C add(A,B);for(int iC.size() - 1;i0;i--) coutC[i];return 0;
}
减法
总体思路
减法和加法一样是在数组下标小的位置储存位数小的数字。
首先我们需要先判断数字A和数字B的大小可以从高开始判断。如果大于等于直接计算A-B否则就计算B-A添加一个负号。
在执行减法的算法中我们不难发现如果高位已经为0的时候就会出现前导0例如100-973,在数组中储存的是003所以我们需要去除前导0恰好前导0刚好在数组的末尾也就是C.back()。我们只需要循环执行如果末尾是0就pop()
例题 #includebits/stdc.h
using namespace std;
string a,b;
vectorint A,B;
bool cmp()//判断A是否B
{if(A.size()!B.size()) return A.size()B.size();else{for(int iA.size()-1;i0;i--){if(A[i]!B[i]){return A[i] B[i];}}}return true;
}vectorint sub(vectorint A,vectorint B)
{vectorint C;int t 0;for(int i0;i A.size();i){//减去借位 t A[i] - t;//一定要判断对应要减去的数字是否存在在进行减法 if(i B.size()){t-B[i];}//把每一位的结果转化为正数后加入结果数组中 C.push_back((t 10) % 10);//如果t0说明需要借位t设为1 if(t 0) t 1;else t 0;}//移除前导0最高位都在数组的最后 while(C.size()1C.back()0) C.pop_back();return C;
}
int main()
{cinab;for(int ia.size()-1;i0;i--) A.push_back(a[i] - 0);for(int ib.size()-1;i0;i--) B.push_back(b[i] - 0);//比较A和B的大小如果AB就直接计算A-B的大小否则就计算B-A加上一个负号 if(cmp()){auto C sub(A,B);for(int iC.size() - 1;i0;i--) coutC[i];}else{auto C sub(B,A);cout-;for(int iC.size() - 1;i0;i--) coutC[i];}return 0;
}
除法
整体思路 逐位模拟除法
手工长除法的核心步骤是逐位计算商和余数。为了实现这种逐位的计算过程我们从被除数的最高位开始处理。每次将当前处理的数字即当前位与前一次计算的余数组合构成一个新的“被除数”。 商和余数的计算
每次构成新的“被除数”后将它除以除数得到商的当前位余数则留给下一位继续处理。每一位的商计算完成后商值存储下来余数用于下一轮的计算。 反转商的顺序
由于我们是从被除数的高位向低位处理计算过程中得到的商是倒序的即最低位商最先被计算出。在最终输出时需要将计算得到的商反转才能得到正确的顺序。 去除前导零
计算过程中可能会出现前导零例如当某些高位不足以大于除数时商位可能为零。为了保证输出格式正确需要在最终输出商时移除这些前导零。
例题 #includebits/stdc.h
using namespace std;
string a;
int b,r; //r是余数
vectorint A;vectorint div() {vectorint C;//商 for(int iA.size() - 1;i0;i--){r r*10 A[i];C.push_back(r / b);r r % b;}//由于计算过程从低位到高位逐步推进最初得到的结果向量 C 是倒序的即最高位在最前面。//为了得到一个正常顺序的结果即最高位在最后面需要将 C 中的元素顺序反转reverse(C.begin(),C.end());// 移除结果中的前导零while (C.size() 1 C.back() 0) {C.pop_back();}return C;
}int main() {cin a b;for(int i a.size() - 1; i 0; i--) A.push_back(a[i] - 0);auto C div();for(int i C.size() - 1; i 0; i--) cout C[i];coutendlr\n;//输出余数 return 0;
}乘法
详细思路
逐位相乘
将被乘数的每一位与乘数逐一相乘并且从低位开始处理。这相当于我们手工计算乘法时按位进行乘法运算。
进位处理
每次计算一位的结果时可能会产生一个进位。例如计算某一位时结果可能是 13则当前位为 3进位 1。这个进位要加到下一位的计算中。
移除前导零
乘法运算可能产生一些前导零尤其是在乘数是 0 或者被乘数中某些高位为 0 的情况下。我们需要在输出之前移除这些前导零。
例题 #includebits/stdc.h
using namespace std;
string a;
int b;
vectorint A;
vectorint Mul() {vectorint C;int t 0;//进位 // for(int i 0; i A.size() || t; i) {if(i A.size()) t A[i] * b;C.push_back(t % 10);t / 10;}// 移除结果中的前导零while (C.size() 1 C.back() 0) {C.pop_back();}return C;
}
int main() {cin a b;for(int i a.size() - 1; i 0; i--) A.push_back(a[i] - 0);auto C Mul();for(int i C.size() - 1; i 0; i--) cout C[i];return 0;
}
解释乘法算法的for循环停止条件
当i小于A.size()时循环继续处理A中的每一位数字。
当i等于或大于A.size()时只要t不为0即还有未处理完的进位循环也会继续。这确保了所有的进位都被正确处理直到没有新的进位产生。
