华师一附中OI组

标题: 高精度计算大楼 [打印本页]

作者: admin 时间: 2020-2-2 14:20
标题: 高精度计算大楼
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 时间: 2020-2-3 09:53
高精度加法的例子：假设输入两个很大的正整数，求他们的和。
第一种方法，用字符串直接计算：
分别用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 字符加进字符串

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

#include<iostream>
using namespace std;
string s1,s2,s3;
int i,j;
int main()
{
cin>>s1>>s2;
if (s1.size()<s2.size()) swap(s1,s2);///比较长短
int l1=s1.size();
int l2=s2.size();
for (int i=1; i<=l1-l2; i++) s2="0"+s2; ///短的前面添0
s3="",j=0;///进位，和都清零，准备开始
for (i=l1-1; i>=0; i--) ///从右往左
{
int x1=s1[i]-'0';///字符转数字
int x2=s2[i]-'0'; ///字符转数字
int x3=x1+x2+j;///加
j=x3/10;x3%=10; ///进位处理
char ch=x3+'0';///数字转字符
s3=ch+s3;///加进总和，注意加在左边
}
if (j==1) s3="1"+s3;/// 最高位进位处理
cout<<s3;
return 0;
}

复制代码

作者: admin 时间: 2020-2-5 21:25
第二种方法就是把读入的字符串转成数字数组来存放，然后对数组进行操作，操作数组的话，可以一次进行加法然后一次进行进位处理。这样程序会很好理解。
特别注意：数组存放数字请大家把最右边的个数放在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位逆向输出每个数字

#include <iostream>
using namespace std;
const int mm=110; ///假设最多100位
int main()
{
string s1,s2;
int a[mm],b[mm],c[mm],i,p,x;
for (p=0; p<=mm-1; p++) a[p]=b[p]=c[p]=0; ///数组清0
cin>>s1>>s2;
/// 字符串转存入数组
int l1=s1.size();
for (p=0; p<=l1-1; p++) a[p]=s1[l1-1-p]-'0';
int l2=s2.size();
for (p=0; p<=l2-1; p++) b[p]=s2[l2-1-p]-'0';
///输出检查
for (p=l1-1; p>=0; p--) cout<<a[p]<<' ';
cout<<endl;
for (p=l2-1; p>=0; p--) cout<<b[p]<<' ';
cout<<endl;
int l=max(l1,l2);///和的位数暂等于最大的加数的位数
for(p=0; p<=l-1; p++) c[p]=a[p]+b[p]; ///按位加
for(p=0; p<=l-1; p++) /// 进位三连
{
x=c[p];
c[p+1]+=x/10;
c[p]=x%10;
}
if (c[l]>0) l++; ///最高位若有进位，长度加1
for (p=l-1;p>=0;p--) cout<<c[p]; ///输出
return 0;
}

复制代码

作者: admin 时间: 2020-2-6 21:46
减法和加法其实是类似的，若用字符串来表示数，假设被减数大于减数，那么位数对齐，字转数计算，数转字加入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)

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

#include <iostream>
using namespace std;
int main()
{
string s1,s2,s3="";
cin>>s1>>s2;
int l1=s1.size();
int l2=s2.size();
for (int i=1; i<=l1-l2; i++) s2="0"+s2;
int j=0;///进位标记
for (int i=l1-1; i>=0; i--)
{
int x1=s1[i]-'0';
int x2=s2[i]-'0';
int x3=x1-x2-j;
j=(x3<0); /// youdian nan
x3=(x3+10)%10; ///niubi
char ch=x3+'0';
s3=ch+s3;
}
///去掉前面的0
int i=0;
while (s3[i]=='0' && i<=l1-1) i++; ///从左往右找第一个非0
cout<<s3.substr(i,l1-i); ///输出 s3从i开始的l-i位
return 0;
}

复制代码

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

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

复制代码

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

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

复制代码

作者: admin 时间: 2020-2-7 19:05

#include <iostream>
using namespace std;
const int mm=110; ///假设都是100位
int a[mm],b[mm],c[2*mm]; ///和是200位
int l1,l2,l3,i,j,p,x;
int main()
{
///读入字符串转存在数组里面
string s1,s2;
cin>>s1>>s2;
for (p=0; p<=mm-1; p++) a[p]=b[p]=c[p]=c[mm+p]=0;
l1=s1.size();
for (p=0; p<=l1-1; p++) a[p]=s1[l1-1-p]-'0';
l2=s2.size();
for (p=0; p<=l2-1; p++) b[p]=s2[l2-1-p]-'0';
///输出检查
for (p=l1-1; p>=0; p--) cout<<a[p]<<' ';
cout<<endl;
for (p=l2-1; p>=0; p--) cout<<b[p]<<' ';
cout<<endl;
///cheng
for(i=0; i<=l1-1; i++)
for(j=0; j<=l2-1; j++)
c[i+j]+=a[i]*b[j];
///jinwei
l3=l1+l2-1; ///积一般是两个乘数的位数的和减一位或者不减，这里预设不减
for(p=0; p<=l3-1; p++) /// 进位三连
{
x=c[p];
c[p+1]+=x/10;
c[p]=x%10;
}
if (a[l3]>0) l3++; ///若最高位有进位
for (p=l3-1; p>=0; p--) cout<<c[p]<<' ';
return 0;
}

复制代码

欢迎光临华师一附中OI组 (http://hsyit.cn/)