网站建设注意什么,广告 网站举例,苏州手机网站建设公司,东莞市一建建设工程有限公司作者#xff1a;指针不指南吗 专栏#xff1a;算法篇 #x1f43e;不能只会思路#xff0c;必须落实到代码上#x1f43e; 文章目录前言一、高精度加法二、高精度减法三、高精度乘法四、高精度除法前言
高精度即很大很大的数#xff0c;超过了 long long 的范围… 作者指针不指南吗 专栏算法篇 不能只会思路必须落实到代码上 文章目录前言一、高精度加法二、高精度减法三、高精度乘法四、高精度除法前言
高精度即很大很大的数超过了 long long 的范围不能直接读取进行运算需要用 string 读入然后存储在数组中去。
高精度算法即把每一位上的数单独拿出来分别计算再跟每一位之间的关系再研究最后结果仍然存在数组中并输出。 一、高精度加法 思路 大整数的存储 使用 vector 存储a[0] 存储个位依次往后最后存储最高位 代码思想 从个位数开始依次让a,b每一位相加结果取模存在结果数组C中t 表示进位每次两个数a,b的各个位相加再加上进位t直到加到最高位 模板 #includebits/stdc.h
using namespace std;//CAB
vectorint add(vectorint A,vectorint B)//引用减少时间不使用引用即把原数据copy一遍费时间
{vectorint C; //定义一个结果答案if(A.size()B.size()) return add(B,A);int t0; //t表示进位个位开始无需进位即t0 for(int i0;iA.size();i){ tA[i];if(iB.size()) tB[i]; //各个位上的数 和 进位 相加 C.push_back(t%10); t/10; //求进位 } if(t) C.push_back(1); //离开循环时t没有加 return C;
}int main()
{string a,b;vectorint A,B;cinab; //输入123456//存储大整数 倒着存储 for(int ia.size()-1;i0;i--) A.push_back(a[i]-0); //存储 654321for(int ib.size()-1;i0;i--) B.push_back(b[i]-0); //注意这里是字符串的长度aauto Cadd(A,B);for(int iC.size()-1;i0;i--) printf(%d,C[i]); //注意 倒序输出return 0;
}二、高精度减法 思路 大整数的存储核心思想 确保是大数减小数首先从个位开始作差取模存储在C中t 表示借位这里很巧妙具体看下面的代码每次各个位上的数作差 - 借位 t 取模存起来有借位 t1没有t0;直到 大整数.size( ) 去前导0 模板 #includebits/stdc.h
using namespace std;//判断两个大整数的大小
bool cmp(vectorint A,vectorint B){ if(A.size()!B.size()) return A.size()B.size(); //位数不同时 if(A.size()B.size()) //位数相同时 for(int i0;iA.size();i)if(A[i]!B[i]) return A[i]B[i];
}//CA-B
vectorint sub(vectorint A,vectorint B)
{if(!cmp(A,B)) {cout-; //如果小减去大数注意加个 - 负号 return sub(B,A); //交换 }vectorint C;int t0; //t表示借位 for(int i0;iA.size();i){tA[i]-t; //各个位上的数先减去借位if(iB.size()) t-B[i]; //B还有数的话减去B[i];C.push_back((t10)%10); //巧妙不用分情况正负数一块取成正的if(t0) t1; //判断是否借位 else t0;}while(C.size()1C.back()0) C.pop_back(); //去掉前导0 如003 return C;
}int main()
{string a,b;vectorint A,B;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);auto Csub(A,B);for(int iC.size()-1;i0;i--) printf(%d,C[i]);return 0;} 三、高精度乘法
高精度乘法一般是 一个大整数乘一个比较小的数 思路 大整数的存储 核心思想 小的数b不拆让b依次和大数A的每一位相乘从A的个位开始t表示进位对每次计算A[i]*bt的结果取模存在结果数组中借位除10即可t可以任意大比如可以进位22直到 大数的最高位t0去掉前导0 模板 #includebits/stdc.h
using namespace std;//CA*b
vectorint mul(vectorint A,int b)
{vectorint C;int t0; //t表示进位for(int i0;iA.size()||t;i){ //两个条件都满足才能退出来否则没有计算完tA[i]*bt; //A的每一位与b相乘加上进位C.push_back(t%10); //对计算结果取模存在结果数组中t/10; }while(C.size()1C.back()0) C.pop_back(); //去掉前导0return C;
}int main()
{string a;int b; // 小的数用int 来存就OKvectorint A;cinab;for(int ia.size()-1;i0;i--) A.push_back(a[i]-0);auto Cmul(A,b);for(int iC.size()-1;i0;i--) printf(%d,C[i]);return 0;} 四、高精度除法
高精度除法一般是一个大的整数除以一个小的整数 思路 大整数的存储核心思想 从最高位开始最高位除以除数余数r剩下r*10大整数的下一位再除以除数余数r剩下重复直到个位去掉前导0 模板
#includebits/stdc.h
using namespace std;//A➗bC...r
vectorint div(vectorint A,int b,int r)
{vectorint C;r0; //r表示余数for(int iA.size()-1;i0;i--){rr*10A[i]; //新的除数C.push_back(r/b); //把商存下来r%b; //取余数
}reverse(C.begin(),C.end()); //反正问题现在虽然是正序但是与其他运算保持一致输出的反序所以现在反过来负负得正while(C.size()1C.back()0) C.pop_back(); //去掉前导0return C;
}int main()
{string a;int b;vectorint A;cinab;for(int ia.size()-1;i0;i--) A.push_back(a[i]-0);int r; //除法多个一个余数auto Cdiv(A,b,r);for(int iC.size()-1;i0;i--) printf(%d,C[i]);printf(\n);printf(%d,r);return 0;}
