网站太卡怎么优化,wordpress 域名访问还是临时域名,自己如何建设刷赞网站,南通手机建站模板什么是高精度算法#xff1f;
高精度的意思就是他得名字----高的精度#xff0c;简单说就是位数很大#xff0c;而高精度算法就是将这些高精度数#xff08;位数很大在几百几千几万位的数叫高精度数#xff09;通过计算机的型式模拟出来结果。
为什么要用高精度算法
高精度的意思就是他得名字----高的精度简单说就是位数很大而高精度算法就是将这些高精度数位数很大在几百几千几万位的数叫高精度数通过计算机的型式模拟出来结果。
为什么要用高精度算法 我们都知道c中int的最大值是2^31unsigned int的最大值是2的32次方最大的unsigned long long可以到18446744073709551615 。double是浮点型的最大类型他的最大值是1.7 * 10^308。 这些数据类型对于112或43545*513452235818025这些式子来说绰绰有余但如果是下面的呢---- 15316925693456174563541645690346596769384568196345734813547477864672672675474676754676783587875372274 265464562574318759893457913479346x6524632656224562664? 3466779657942964574257456/432654724567?..? 这些式子的数和结果都非常大long long 和 double 都存不下这时就是要用高精度来计算了
高精度加法
1168大整数加法 P1601 AB Problem高精 因为不能用计算机直接计算只能靠模拟。 让我们回顾一下小学一年级时学的加法。 通过这个竖式我们想想是否可以把高精度加法转换成一道让我们模拟加法竖式的模拟题呢答案是肯定的 带着这个假想我们可以尝试下 首先初始化 注意因为位数较大所以我们要用字符串或字符数组
const int N205; //定义大小
string s1,s2; //俩数
int a[N],b[N],c[N]; //存放俩数及结果数组 好了第二步-------读入read
void read(){cins1s2;
} 好读入结束等下这么草草就结束了a,b数组怎么办。 所以为了照顾a,b数组我们需要把俩字符串数转成整数数组的型式。 但真的是顺着存储吗不对 如果顺着存储就是这样 本来1257934的式子竟然变了而且当你好不容易把他变回去时就会发现如果进位时如123930数组下标竟然需要负数才能存下那个进位的1了所以顺着存不行那试试逆序存呢 大家可以在草稿纸上试试可以发现逆着存是可以的也防止了进位溢出的情况 所以对于存储s1,s2俩数应用整数数组逆着存。
void read(){cins1s2;int len1s1.size(),len2s2.size();for(int i0;ilen1;i) a[i](s1[len1-i-1]-0); //逆序存储。需要字符转整数for(int j0;jlen2;j) b[j](s2[len2-j-1]-0);
} 好的终于到模拟部分了 让我们先考虑一下重点 1.考虑进位 2.考虑该进位多少 3.最重要的一点。前导零该怎么办 4.最高位进位 好的一步步来 第一点。因为单个位最大是9俩9相加才18进位不可能超1所以第一部分和第二部分可以同时考虑。如果结果大于10我们可以将结果-10或直接不判断直接%10当然我们也要考虑到当前的i1位也要1所以我们可以用变量来表示这种情况。第三点我们可以从尾开始遍历碰到0就舍去len-1.如果没碰到就break。第四点我们可以用变量储存模拟完毕后特判下 好分析完毕代码如下
void count(){int jw0;lenmax(s1.size(),s2.size()); //c的长度是俩数中的最大值或1for(int i0;ilen;i){c[i]a[i]b[i]jw; //求当前结果jwc[i]/10; //进位数c[i]%10; //得出当前数} if(jw1){ //处理最高位进位len;c[len-1]1;}while(c[len-1]0) len--; //去前导零
}等下考虑下00的结果 是空不是0吗原来当len1时就算是0也不能舍去 修改如下
void count(){int jw0;lenmax(s1.size(),s2.size());for(int i0;ilen;i){c[i]a[i]b[i]jw;jwc[i]/10;c[i]%10;} if(jw1){len;c[len-1]1;}while(len1c[len-1]0) len--;
}最后到输出部分了应为开始时是逆序存所以也要逆序输出正所谓负负得正
void print(){for(int ilen-1;i0;i--) coutc[i];
}最后总代如下
#includebits/stdc.h
using namespace std;
const int N205;
string s1,s2;
int a[N],b[N],c[N];
int len;
void read(){ //读入cins1s2;int len1s1.size(),len2s2.size();for(int i0;ilen1;i) a[i](s1[len1-i-1]-0);for(int j0;jlen2;j) b[j](s2[len2-j-1]-0);
}
void count(){ //模拟竖式int jw0;lenmax(s1.size(),s2.size());for(int i0;ilen;i){c[i]a[i]b[i]jw;jwc[i]/10;c[i]%10;} if(jw1){len;c[len-1]1;}while(len1c[len-1]0) len--;
}
void print(){ //输出for(int ilen-1;i0;i--) coutc[i];
}
int main(){
read();
count();
print();return 0;
}另外用结构体来计算大整数加法也是常见的这里不做多说明了与上文类似
#includebits/stdc.h
using namespace std;
string str;
struct node{ //定义int len,s[205];node(){len0;memset(s,0,sizeof(s));}
};
node a,b,c;
node operator (const nodea,const nodeb){ //重载加法运算符node c;c.lenmax(a.len,b.len);for(int i1;ic.len;i){c.s[i]a.s[i]b.s[i];c.s[i1]c.s[i]/10;c.s[i]%10;}if(c.s[c.len1]) c.len;return c;
}
node read(){ //读入加去前导零cinstr;int lenstr.size();node a;a.lenlen;for(int i0;ilen;i){a.s[len-i]str[i]-0;}while(a.len1a.s[a.len]0) a.len--;return a;
}void print(node a){//输出for(int ia.len;i1;i--) couta.s[i];
}
int main(){aread(),bread();
cab;
print(c);return 0;
}高精度减法
1169大整数减法 与高精度加法类似也是模拟 初始化读入
string s1,s2;
int a[205],b[205],c[205];
int len;
void read(){cins1s2;int ns1.size(),ms2.size();lenmax(n,m);for(int i0;in;i){a[i]s1[n-i-1]-0;}for(int j0;jm;j){b[j]s2[m-j-1]-0;}
}模拟竖式。 这里也有两项需考虑 1.借位 2.去前导零 第二步相信你们很轻松就能解决。而第一步也很简单我们正常减如果c[i]0,那么需要借位了有加就有减所以c[i]10;c[i1]–; 代码如下
void less(){for(int i0;ilen;i){c[i]a[i]-b[i];if(c[i]0){c[i]10;c[i1]--;}}while(len1c[len-1]0) len--;
}最后逆序输出
void print(){for(int ilen-1;i0;i--) coutc[i];
}总代码
#includebits/stdc.h
using namespace std;
string s1,s2;
int a[205],b[205],c[205];
int len;
void read(){cins1s2;int ns1.size(),ms2.size();lenmax(n,m);for(int i0;in;i){a[i]s1[n-i-1]-0;}for(int j0;jm;j){b[j]s2[m-j-1]-0;}
}
void lss(){for(int i0;ilen;i){c[i]a[i]-b[i];if(c[i]0){c[i]10;c[i1]--;}}while(len1c[len-1]0) len--;
}
void print(){for(int ilen-1;i0;i--) coutc[i];
}
int main(){
read();
lss();
print();return 0;
}这边结构体减法代码就不放了有兴趣可以自己做下。 总结下来只要会高精度加法就会高精度减法。
未完待续。。。。。。
