高精度计算大楼

admin

C++语言中最常用的数据类型是整数，有short,int,long long 等几种类型，每个还有一个unsign 选项，这些类型对于很大的数据运算来说就很有不足了，虽然实数float等可以表示更大的数但是精度有限，所以要是需要用到很大的整数或者精度很高的实数，我们需要手写高精度算法。比如求2^1000或者计算e精确到小数点后100位代码，等等。
用来表示高精度的数一般就是字符串和数组两种方法了，用字符串来表示高精度数一般用于加减法，字符串的每位存放数字对应的字符，因为计算次数比较少，字符也是有序的序列可以简单进行加减，而且字符串输出输出比较方便；用数组的话存储的就是实际的数字，所以更方便进行更复杂的运算，但是输入输出就不是很方便，输入可能需要字符串然后进行转换，输出的话就一位位输出。

简单训练题：

1、   A+B Problem（高精）  https://www.luogu.com.cn/problem/P1601
2、        P2142 高精度减法  https://www.luogu.com.cn/problem/P2142
3、   P1009 阶乘之和  https://www.luogu.com.cn/problem/P1009
4、   P1303 A*B Problem   https://www.luogu.com.cn/problem/P1303
5、   P1480 A/B Problem   https://www.luogu.com.cn/problem/P1480
6、   P2005 A/B Problem II   https://www.luogu.com.cn/problem/P2005
7、   P1045 麦森数   https://www.luogu.com.cn/problem/P1045
8、   P1015 回文数  https://www.luogu.com.cn/problem/P1015
9、   P1729 计算e  https://www.luogu.com.cn/problem/P1729

admin

高精度加法的例子：假设输入两个很大的正整数，求他们的和。
第一种方法，用字符串直接计算：
分别用s1,s2,s3表示两个加数和他们的和，假设s1="89",s2="12345"；那么模拟我们人的手算方法：
1、发现s1比较短，放在后面，改计算12345+89;
2、列算式，整数都靠右边对齐;
3、从右往左加：9+8=17，留下7往前进1,4+8+1=13，留下3往前进1，**
4、最高位可能还有一个进位。
5、输出s3

翻译成变成操作（这个技能很重要，人的语言和计算机语言是有区别的，就像英文和中文有区别）
1、若s1的长度小于s2的，则交换他们两个。相当于放在后面了。哪里还有这样的例子？if (s1.size()<s2.size()) swap(s1,s2);
2、s2前面补0，让它和s1一样长，相当于对齐了。而且我们人认为没有就是0，但是在字符串里面不是这样的。for(i=1;i<=l1-l2;i++) s2="0"+s2;
3、这个要做好多次，所以需要总结出通用的规律，规律总结的好，程序会简洁一些，规律要是总结错了，程序就会出问题：
     从右往左 (for (i=l1-1;i>=;i--))
     每一位都是加数+被加数+进位 x3=x1+x2+j;
     若和>=10，向前进位  j=x3/10;x3%=10 这个很巧妙
4、最高位可能还设有进位 if (j==1) s3="1"+s3
5、这个简单cout<<s3;

这里面还有一个很大的编程问题，字符串里面存放的9，实际上是数字57，存放的5，实际上是数字53，他们加起来不是等于14的，而且字符只有一个，也不能存放14呀。
好在数字和字符有对应关系，9='9'-'0'，这样字符先转成数字，然后数字相加，处理进位后再转成字符：
x1=s1i-'0'   字符转数字
x2=s2i-'0'   字符转数字
x3=x1+x2+j   数字求和
j=x3/10,x3%=10  进位处理
ch=x3+'0'  数字变字符
s3=ch+s3   字符加进字符串


结合这些分析，写出如下的程序：

1. #include<iostream>
   
2. using namespace std;
   
3. string s1,s2,s3;
   
4. int i,j;
   
5. int  main()
   
6. {
   
7.         cin>>s1>>s2;
   
8.         if (s1.size()<s2.size())  swap(s1,s2);///比较长短
   
9.         int l1=s1.size();
   
10.         int l2=s2.size();
    
11.         for (int i=1; i<=l1-l2; i++) s2="0"+s2;  ///短的前面添0
    
12.         s3="",j=0;///进位，和都清零，准备开始
    
13.         for (i=l1-1; i>=0; i--) ///从右往左
    
14.         {
    
15.                 int x1=s1[i]-'0';///字符转数字
    
16.                 int x2=s2[i]-'0'; ///字符转数字
    
17.                 int x3=x1+x2+j;///加
    
18.                 j=x3/10;x3%=10; ///进位处理
    
19.                 char ch=x3+'0';///数字转字符
    
20.                 s3=ch+s3;///加进总和，注意加在左边
    
21.         }
    
22.         if (j==1)  s3="1"+s3;/// 最高位进位处理
    
23.         cout<<s3;
    
24.         return 0;
    
25. }

复制代码

admin

第二种方法就是把读入的字符串转成数字数组来存放，然后对数组进行操作，操作数组的话，可以一次进行加法然后一次进行进位处理。这样程序会很好理解。
特别注意：数组存放数字请大家把最右边的个数放在a(0)里，十位放在a(1)里，这样符合数学的一般认知，个位（10^0），十位(10^1)，百位(10^2)，在以后做乘法除法的时候也更容易理解。
1、读入字符串，一次存放在数字数组里面 ，注意顺序，字符串的0位在最左边，数字的最低位是在右边的，所以假设是L位数，字符串首位是第0位，对应的数组是第L-1位，字符串的最后一位是L-1位对应的数组是第0位。
for(i=0;i<-l-1;i++) a(l-1-i)=s(i)-'0'
2、若没有最高位的进位，和的位数等于最长的那个加数的位数，先不考虑进位，所有的数字按位加起来
3、从右往左处理进位，
4、若最高位有进位，则和的长度+1
5、从最高位到第0位逆向输出每个数字

1. #include <iostream>
   
2. using namespace std;
   
3. const int mm=110; ///假设最多100位
   
4. int main()
   
5. {
   
6.         string s1,s2;
   
7.         int a[mm],b[mm],c[mm],i,p,x;
   
8.         for (p=0; p<=mm-1; p++) a[p]=b[p]=c[p]=0; ///数组清0
   
9.         cin>>s1>>s2;
   
10.         /// 字符串转存入数组
    
11.         int l1=s1.size();
    
12.         for (p=0; p<=l1-1; p++) a[p]=s1[l1-1-p]-'0';
    
13.         int l2=s2.size();
    
14.         for (p=0; p<=l2-1; p++) b[p]=s2[l2-1-p]-'0';
    
15.         ///输出检查
    
16.         for (p=l1-1; p>=0; p--)  cout<<a[p]<<' ';
    
17.         cout<<endl;
    
18.         for (p=l2-1; p>=0; p--)  cout<<b[p]<<' ';
    
19.         cout<<endl;
    
20.         int l=max(l1,l2);///和的位数暂等于最大的加数的位数
    
21.         for(p=0; p<=l-1; p++) c[p]=a[p]+b[p]; ///按位加
    
22.         for(p=0; p<=l-1; p++) /// 进位三连
    
23.         {
    
24.                 x=c[p];
    
25.                 c[p+1]+=x/10;
    
26.                 c[p]=x%10;
    
27.         }
    
28.         if (c[l]>0)  l++; ///最高位若有进位，长度加1
    
29.     for (p=l-1;p>=0;p--) cout<<c[p]; ///输出
    
30.         return 0;
    
31. }

复制代码

admin

减法和加法其实是类似的，若用字符串来表示数，假设被减数大于减数，那么位数对齐，字转数计算，数转字加入s3等都是一样，只是几个不同：
1、加法有进位，减法是借位，，借位可以这样写： j=(x3<0);  x3=(x3+10)%10; （这种同余的写法以后会经常见到）
2、减法不会有最高位的进位，但是会在高位出现0，输出的时候要去掉这些0；
i=0;while(s3(i)=='0' && i<=l3-2) i++; 可以在0-l3-2之间找到第一个非0的数字，注意不是l3-1，因为最后一个数字是0的话也要时候输出的。然后输出s3.substr(i,l3-1-i)

综合以上，把加法程序稍加改动：

1. #include <iostream>
   
2. using namespace std;
   
3. int main()
   
4. {
   
5.         string s1,s2,s3="";
   
6.         cin>>s1>>s2;
   
7.         int l1=s1.size();
   
8.         int l2=s2.size();
   
9.         for (int i=1; i<=l1-l2; i++) s2="0"+s2;
   
10.         int j=0;///进位标记
    
11.         for (int i=l1-1; i>=0; i--)
    
12.         {
    
13.                 int x1=s1[i]-'0';
    
14.                 int x2=s2[i]-'0';
    
15.                 int x3=x1-x2-j;
    
16.                 j=(x3<0);  /// youdian nan
    
17.                 x3=(x3+10)%10; ///niubi
    
18.                 char ch=x3+'0';
    
19.                 s3=ch+s3;
    
20.         }
    
21.         ///去掉前面的0
    
22.         int i=0;
    
23.         while (s3[i]=='0' && i<=l1-1) i++; ///从左往右找第一个非0
    
24.         cout<<s3.substr(i,l1-i);  ///输出 s3从i开始的l-i位
    
25.         return 0;
    
26. }

复制代码

考虑的更完美一点，要是被减数小于减数的话，可以输出负号然后交换他们在求差。
加上这么一段

1. bool b1=s1.size()<s2.size();
   
2.         bool  b2=(s1.size()==s2.size()) && (s1<s2) ;
   
3.         if (b1||b2) ///宇宙总统还记得吧 若数值上s1<s2则交换并输出负号。
   
4.         {
   
5.                 cout<<'-';
   
6.                 swap(s1,s2);
   
7.         }

复制代码

admin

乘法分两种，一种是大整数乘小整数，这个见得比较多，比如99^99，100！这样的，每次是一个很大的数字乘以一个比较小的乘数，另一种是两个很大的整数相乘，前者有点像我们一般人计算时候的583*9 ，一轮按位乘法和进位处理就可以了，后者有点像 583*789，需要多轮计算。
先说以一种情况吧，和上面的数组加法一样，用a 数组存放被乘数。int k存放乘数，我们人在做多位数乘法的时候是一边乘一边进位，但是编程也可以先一次乘完，再一次处理进位。这和边乘边进位是没有区别的。注意最高位的是没法进位的，所以第二个循环终值和第一个不同。

1. ///.  99^99
   
2. #include <iostream>
   
3. using namespace std;
   
4. const int mm=210; ///假设200位
   
5. int a[mm],i,p,x;
   
6. int main()
   
7. {
   
8.         for (p=0; p<=mm-1; p++) a[p]=0;a[0]=1; /// 初始值
   
9.         for (i=1; i<=99; i++)
   
10.         {
    
11.                 for  (p=0; p<=mm-1; p++) a[p]*=99;///按位乘
    
12.                 for  (p=0; p<=mm-2; p++) ///进位三连
    
13.                 {x=a[p];a[p+1]+=x/10;a[p]=x%10;}
    
14.         }
    
15.         ///  从左往右找第一个非0
    
16.         p=mm-1;while  (a[p]==0 && p>0) p--;
    
17.         for (; p>=0; p--) cout<<a[p];
    
18.         return 0;
    
19. }

复制代码

admin

1. #include <iostream>
   
2. using namespace std;
   
3. const int mm=110; ///假设都是100位
   
4. int a[mm],b[mm],c[2*mm];  ///和是200位
   
5. int l1,l2,l3,i,j,p,x;
   
6. int main()
   
7. {
   
8.         ///读入字符串转存在数组里面
   
9.         string s1,s2;
   
10.         cin>>s1>>s2;
    
11.         for (p=0; p<=mm-1; p++) a[p]=b[p]=c[p]=c[mm+p]=0;
    
12.         l1=s1.size();
    
13.         for (p=0; p<=l1-1; p++) a[p]=s1[l1-1-p]-'0';
    
14.         l2=s2.size();
    
15.         for (p=0; p<=l2-1; p++) b[p]=s2[l2-1-p]-'0';
    
16. 
    
17.         ///输出检查
    
18.         for (p=l1-1; p>=0; p--)  cout<<a[p]<<' ';
    
19.         cout<<endl;
    
20.         for (p=l2-1; p>=0; p--)  cout<<b[p]<<' ';
    
21.         cout<<endl;
    
22. 
    
23.         ///cheng
    
24.         for(i=0; i<=l1-1; i++)
    
25.                 for(j=0; j<=l2-1; j++)
    
26.                         c[i+j]+=a[i]*b[j];
    
27. 
    
28.         ///jinwei
    
29.         l3=l1+l2-1; ///积一般是两个乘数的位数的和减一位或者不减，这里预设不减
    
30.         for(p=0; p<=l3-1; p++) /// 进位三连
    
31.         {
    
32.                 x=c[p];
    
33.                 c[p+1]+=x/10;
    
34.                 c[p]=x%10;
    
35.         }
    
36.         if (a[l3]>0) l3++; ///若最高位有进位
    
37.         for (p=l3-1; p>=0; p--) cout<<c[p]<<' ';
    
38.         return 0;
    
39. }

复制代码