网站做关键词首页,专业网站设计服务在线咨询,杭州市拱墅区网站建设,某互联网公司开发官网的首页目录 前言
1 题目描述
2 分析
2.1 关键代码
2.2 关键代码分析
3 代码 前言
详细的代码里面有自己的理解注释
1 题目描述
给定两个非负整数#xff08;不含前导 00#xff09; A 和 B#xff0c;请你计算 AB 的值。
输入格式
共两行#xff0c;第一行包含整数 A不含前导 00 A 和 B请你计算 A×B 的值。
输入格式
共两行第一行包含整数 A第二行包含整数 B。
输出格式
共一行包含 A×B 的值。
数据范围
1≤A的长度≤100000, 0≤B≤10000
输入样例 123
12
输出样例
1476
2 分析
这个题和前面对高精度-加-高精度和高精度-减-高精度的分析有细微差别因为前面的加减法都是高精度和高精度的运算这题是高精度和低精度的运算所以只要对A用先采用string存储然后换成int数字并且按照数组下标的低位存储数值低位存储数值B采用int存储即可。
2.1 关键代码
//C A * b
vint mult1(vint A,int b) {vint C;int t 0;for(int i 0; i A.size(); i ) {//相当于// 1 2 3// * 1 2// 36 * 10^0 24 * 10^1 12 * 10^2 1476// 进位初始 t0 0// 3 * 12 t0 36 0 36 保留 6 进位 t1 3// 2 * 12 t1 24 3 27 保留 7 进位 t2 2// 1 * 12 t2 12 2 14保留 4 进位 t3 1// (36%10 t0)*10^0 (24%10 t1)*10^1 (12%10 t2)*10^2 t3*10^3// (6 0 ) * 10^0 (4 3) * 10^1 (2 2) * 10^2 1 * 10^3 1476//最后有个进位// 6 * 10^0 (4 3) * 10^1 (2 2) * 10^2 1 * 10^3 1476t A[i] * b t;C.push_back(t % 10);t t / 10;}
// if(t){
// C.push_back(t);
// }
//不能用 if(t) 必须使用 while(t) 因为最后可能 t 不止 1 位
//比如 99 * 99 9801 最后 t 98 如果用 if(t) 实际上 C [98,0,1] 而不是 [9,8,0,1]
//也可以不用下面的代码在for循环里面改为 i A.size() ||t并且加上 if(iA.size()) t A[i]*b twhile(t) {C.push_back(t%10);t t / 10;}//记得去前导 0 while(C.size() 1 C.back() 0) C.pop_back();return C;
}
2.2 关键代码分析
代码实现的乘法运算和平常我们做题的计算是不一样的代码里面它是按照A的每位乘B存储的这样其实也是对的只是我们一般学的时候是两个数每位相乘再相加进位。当iA.size()时每位值结果为A[i]*B[i]%10进位为A[i]*B[i]/10其实理解起来比较简单比如123*12按平常我们的计算个位是3*26十位由两个部分构成1*32*27。而在代码里面我们直接用3*1236其中这个3*12的3先看作是个位36的3就是1*3那部分权重是106即是结果的个位下一步2*1224其中这个2*12的2先看作是十位24的2权重是1004就是2*2那部分也就是十位所以十位就是337百位的进位为2其他的依次类推即可。详细的计算说明在上面的关键代码里面有
3 代码
#includeiostream
#includevectorusing namespace std;
typedef long long LL;
typedef vectorint vint;const int N 1e5 10;//C A * b
vint mult1(vint A,int b) {vint C;int t 0;for(int i 0; i A.size(); i ) {//相当于// 1 2 3// * 1 2// 36 * 10^0 24 * 10^1 12 * 10^2 1476// 进位初始 t0 0// 3 * 12 t0 36 0 36 保留 6 进位 t1 3// 2 * 12 t1 24 3 27 保留 7 进位 t2 2// 1 * 12 t2 12 2 14保留 4 进位 t3 1// (36%10 t0)*10^0 (24%10 t1)*10^1 (12%10 t2)*10^2 t3*10^3// (6 0 ) * 10^0 (4 3) * 10^1 (2 2) * 10^2 1 * 10^3 1476//最后有个进位// 6 * 10^0 (4 3) * 10^1 (2 2) * 10^2 1 * 10^3 1476t A[i] * b t;C.push_back(t % 10);t t / 10;}
// if(t){
// C.push_back(t);
// }
//不能用 if(t) 必须使用 while(t) 因为最后可能 t 不止 1 位
//比如 99 * 99 9801 最后 t 98 如果用 if(t) 实际上 C [98,0,1] 而不是 [9,8,0,1]
//也可以不用下面的代码在for循环里面改为 i A.size() ||t并且加上 if(iA.size()) t A[i]*b twhile(t) {C.push_back(t%10);t t / 10;}//记得去前导 0 while(C.size() 1 C.back() 0) C.pop_back();return C;
}int main() {string a;int b;cinab;//a 123,b 12vint A;//A[3 , 2 , 1]因为可能需要进位个位放数组低位方便在数组高位加上进位for(int i a.size() - 1 ; i 0 ; i --) {A.push_back(a[i] - 0);}if(b 0) {cout0;} else {vint C mult1(A,b);for(int i C.size() - 1 ; i 0 ; i --) {coutC[i];}//coutC.size();}return 0;
}
