4.1.2 高精度运算
程序设计语言所能表示和处理的整数和实数的精度通常是有限的，例如，在双精度方式下，计算机最多只能输出16位有效的十进制数，17位有效数字的正确性为90%（Double类型数据）。如果超过了这个范围，计算机就无法正确表示。在这种情况下，只能通过编程来解决。对于高精度数，有两个基本问题：
·高精度数的表示；
·高精度数的基本运算。
1.高精度数的表示
用一个数组来表示一个高精度数：将数字按十进制位进行分离，将每位十进制数依次存储到一个数组中。在具体的实现中，先采用字符串来接收数据，然后将字符串中的各位字符转换为对应的十进制数，并按十进制位的顺序存储到一个数组中。例如，对于一个高精度正整数，接收与存储的程序段如下：
int a[100]={0}; // 数组a用来按位存储高精度正整数，初值全为0
int n; // n用来存储高精度正整数的位数
string s; // 字符串s用来接收数据
cin>>s; //输入数串
n=s.length(); //计算位长
for (i=0; i<n; i++) // 数组a从右向左，按位存储高精度正整数
a[i]=s[n-i-1]-'0';
由上可见，高精度数按照十进制位的顺序存储在整数数组a中，数组下标对应高精度数的位序号，下标变量的元素值对应当前位的十进制数。因此a是一种典型的直接存取类线性表。
2.高精度数的基本运算
高精度数的基本运算包括加、减、乘和除运算。
（1）高精度数的加减运算
高精度数最基本的运算是加和减。和算术的加减规则一样，程序中高精度数的加运算要考虑进位处理，高精度数的减运算则要考虑借位处理。
例如，求两个非负的高精度整数x和y相加的和。x和y按如上的形式存储在数组a和数组b中，n1为x的位数，n2为y的位数，程序段如下：
for (i=0; i<( n1>n2 ? n1 : n2 ); i++ ){ //进行max{n1, n2}位加法
a[i]=a[i]+b[i]; //逐位相加
if (a[i]>9) { // 进位处理
a[i]=a[i]-10;
a[i+1]++;
}
}
再例如，求两个高精度正整数x和y（x>y）相减的差。x和y按如上的形式存储在数组a和数组b中，n为x的位数。若x<y，则a和b对换，相减后的差取负。数组a和数组b相减的程序段如下：
for (i=0; i<n; i++) {
if (a[i]>=b[i]) a[i]=a[i]-b[i]; //若对应位够减，则直接相减，否则借位相减
else { a[i]=a[i]+10-b[i];
a[i+1]--;
}
}
（2）高精度数的乘运算
在高精度数的加减运算的基础上，可以实现高精度数的乘运算。
要进行高精度数的乘法运算，首先要确定积的位数。设两个高精度正整数a和b，LA为a的位数，LB为b的位数。a和b乘积的位数至少为LA+LB-1，若乘后的第LA+LB-1位有进位，则乘积位数为LA+LB。所以，高精度正整数a和b的乘积的位数上限为LA+LB。
高精度数乘运算的算法思想和算术的乘法规则一样：首先计算被乘数与乘数的每位数字的乘积，其中a[i]乘b[j]的积累加到数组c[i+j]上，然后对累加结果c做一次性进位。
for (i=0; i<=LA-1; i++) //被乘数a与乘数b的每位数字的乘积累加到积数组c的对应位上
for (j=0; j<=LB-1; j++)
c[i+j] += a[i]*b[j];
for (i=0; i<LA+LB; i++) //累加结果做一次性进位
if(c[i] >= 10)
{
c[i+1] += c[i]/10;
c[i] %=10;
}
【4.1.2.1 Adding Reversed Numbers】
Malidinesia的古典喜剧演员（Antique Comedians of Malidinesia，ACM）喜欢演喜剧，而不太喜欢演悲剧。但不幸的是，大多数古典戏剧是悲剧。所以ACM的戏剧导演决定将一些悲剧改编为喜剧。显然，虽然所有的事物都改成了它们的反面，但因为必须保持剧本原有的意义，所以这项工作是很困难的。
反向数是将一个阿拉伯数字按相反的顺序写。把第一个数字写成最后一个数字，反之亦然。例如，在悲剧中主人公有1245只草莓，现在则有5421只草莓。在本题中，数字的所有前导零都要被省略。所以，如果数字结尾有零，写反向数时零要被略去（例如，1200的反向数是21）。此外，在本题中，反向数没有零结尾。
ACM需要对反向数进行计算。请你将两个反向数相加，并输出它们的反向和。当然，结果不是唯一的，因为一个数可以是几个数的反向形式（例如21在反向前可以是12、120或1200）。为此，本题设定没有0因为反向而丢失（例如，设定原来的数是12）。
输入
输入由N个测试用例组成。输入的第一行仅给出正整数N，然后给出若干测试用例。每个测试用例一行，由2个由空格分开的正整数组成。这是要相加的要被反向的数。
输出
对每个测试用例，输出一行，该行仅包含一个整数，将两个反向数进行求和，之后再反向。在输出时把前导0略去。
试题来源：ACM Central Europe 1998
在线测试：POJ 1504，ZOJ 2001，UVA 713
试题解析
设Num[0][0]为被加数的长度，被加数按位存储在Num[0][1..Num[0][0]]之中；Num[1][0]为加数的长度，加数按位存储在Num[1][1..Num[1][0]]之中；Num[2][0]为和的长度，和按位存储在Num[2][1..Num[2][0]]之中。
首先，分别输入被加数和加数的数串，在舍去尾部的无用0后将它们存入Num[0]和Num[1]，再将它们反向存储。然后，Num[0]和Num[1]相加得出和数组Num[2]。最后反向输出Num[2]，注意略去尾部的无用0。
参考程序
#include <iostream> //预编译命令
#include <cstdio>
#include <cstring>
#include <string>
using namespace std; //使用 C++标准程序库中的所有标识符
int Num[3][1000]; //Num[0][0]为被加数的长度，被加数为Num[0][1..Num[0][0]]；Num[1][0]
//为加数的长度，加数为Num[1][1..Num[1][0]]； Num[2][0]为和的长度，和为Num[2][1..
//Num[2][0]]
void Read(int Ord) // Ord==0，输入和处理被加数；Ord==1，输入和
//处理加数
{
int flag=0;
string Tmp;
cin>>Tmp; //读数串
for(int i=Tmp.length()-1;i>=0;i--) //由右而左分析每个数字符
{
if (Tmp[i]>'0') flag = 1; //舍去尾部的无用0后存入高精度数组Num[Ord]
if (flag) Num[Ord][++Num[Ord][0]] = Tmp[i] - '0';
}
for(int i=Num[Ord][0],j=1;i>j;i--,j++) //计算反向数Num[Ord]
{
flag = Num[Ord][i];
Num[Ord][i] = Num[Ord][j];
Num[Ord][j] = flag;
}
}
void Add()
{
Num[2][0] = max(Num[0][0],Num[1][0]); //加数和被加数的最大长度作为相加次数
for(int i=1;i<=Num[2][0];i++) //逐位相加
Num[2][i] = Num[0][i] + Num[1][i];
for(int i=1;i<=Num[2][0];i++) //进位处理
{
Num[2][i+1] += Num[2][i]/10;
Num[2][i] %= 10;
}
if(Num[2][Num[2][0]+1] > 0) //处理最高位的进位
Num[2][0] ++;
int flag = 0;
for(int i=1;i<=Num[2][0];i++) //反向输出和（去除前导0）
{
If (Num[2][i]>0) flag = 1;
if (flag) printf("%d",Num[2][i]);
}
printf("\n");
}
int main() //主函数
{ //主函数开始
int N; //输入测试用例数
cin>>N;
for(N;N;N--) //输入和处理每个测试用例
{
memset(Num,0,sizeof(Num)); //高精度数组初始化为0
Read(0); //输入处理和被加数
Read(1); //输入处理和加数
Add(); //相加后反向输出
}
return 0;
}
有时候，同类的高精度运算需要反复进行（例如计算乘幂或多项式）。在这种情况下，采用面向对象的程序设计方法可使程序结构更清晰、运算更简便。
【4.1.2.2 VERY EASY!!!】
输入
输入有若干行，在每一行中给出整数N和A的值(1≤N≤150，0≤A≤15)。
输出
对于输入的每一行，在一行中输出级数
的整数值。
试题来源：THE SAMS’CONTEST
在线测试：UVA 10523
试题解析
由级数
中项数N的上限（150）、底数A的上限（15）可以看出，计算乘幂、当前项以及数的和要采用高精度运算。由于计算过程需要反复进行高精度的乘法和加法，因此采用面向对象的程序设计方法是比较适合的。
定义一个名称为bigNumber的类，其私有（private）部分为长度一个为len的高精度数组a，被bigNumber类的对象和成员函数访问；其公共（public）界面包括：
·bigNumber()——高精度数组a初始化为0。
·int length()——返回高精度数组a的长度。
·int at(int k)——返回a[k]。
·void setnum(char s[])——将字符串s[]转换成长度为len的高精度数组a。
·bool isZero()——判断高精度数组a是否为0。
·void add(bigNumber & x)——高精度加法运算：a←a+x。
·void multi(bigNumber & x)——高精度乘法运算：a←a×x。
它们是程序可使用的全局函数。
有了上述类的定义，计算
的过程就变得非常简洁和清晰了。
1）首先，定义底数a和乘幂ap为bigNumber类的对象（bigNumber a,ap）；将底数串s转化为高精度数组a（a.setnum(s)）；乘幂数组ap初始化为1（ap.setnum(“1”)）；定义数的和sum为bigNumber类的对象（bigNumber sum）。
2）然后循环n次，每次循环计算当前项i*Ai，并累加入数的和sum：
·定义当前项num为bigNumber类的对象（bigNumber num）；
·num初始化为i（sprintf(s,"%d",i;num.setnum(s))；
·计算乘幂ap←ap×a和当前项num←num×ap（ap.multi(a)；num.multi(ap)；）；
·累加当前项sum←sum+num（sum.add(num)）。
3）输出级数
。
参考程序
（3）高精度数的除运算
对于求解高精度正整数A÷高精度正整数B的商和余数，其算法思想如下。
先比较A和B，如果A<B，则商为0，余数为A；否则基于高精度正整数的减法开始整除，根据A和B的位数之差d1看A能够减
的次数a1，得到余数y1=A-a1×B×
；然后计算y1和B的位数之差d2，看y1能够减
的次数a2，得到余数y2=y1-a2×B×
；……，以此类推，直至得出yk-1够减B的次数ak为止。最后得到余数y=yk-1-ak×B，a1()a2…()ak即商（注：()表示若di-di+1>1，则ai+1前须补di-di+1-1个0，2≤i≤k-1）。
比如A=12 345，B=12，位数之差d1=3，则12 345够减（12×103）的次数a1=1，得到余数y1=12 345-12×103=345；345与12的位数之差d2=1，345够减（12×101）的次数a2=2，得到余数y2=345-2×12×101=105；y2能够减12的次数a3=8，最终得到余数y=105-8×12=9和商1028。
高精度整数除以高精度整数的计算比较复杂，而高精度整数除以整数的运算直接模拟除法规则就可以了。【4.1.2.3 Persistent Numbers】是一个高精度整数除以整数的实验。
【4.1.2.3 Persistent Numbers】
Neil Sloane定义一个数的乘法持久性
（multiplicative persistence of a number）如下：将这个数各位数相乘，并重复这一步骤，最后达到个位数；所经历的步骤数被称为这个数的乘法持久性。例如：679->378（6×7×9）->168（3×7×8）->48（1×6×8）->32（4×8）->6（3×2）。
也就是说，679的乘法持久性是6。个位数的乘法持久性为0。人们知道有数的乘法持久性为11的数字，并不知道是否存在数的乘法持久性为12的数字，但是我们知道，如果有这样的数存在，那么它们中的最小数也将超过3000位。
本题请你解决的问题是：找到一个符合下述条件的最小数，使这个数各位数连续相乘的结果是题目所给的数，即该数的乘法持久性的第一步就得到给定的数。
输入
每个测试用例一行，给出一个最多可达1000位数字的十进制数。在最后一个测试用例后的一行给出-1。
输出
对每个测试用例，输出一行，给出一个满足上述条件的整数；或者输出一个语句，说明没有这样的数，格式如样例输出所示。
试题来源：Waterloo local 2003.07.05
在线测试：POJ 2325，UVA10527
试题解析
由于输入的数字最多可以达到1000位，因此数字以字符串形式输入；然后模拟除法运算规则，将这个大整数从高位到低位依次对9～2的数i整除：
·如果当前整数除以i的最后余数非零，则说明不能整除i，换下一个除数；
·如果能够整除（即除以i的最后余数为零），则将i存入一个规模为3000的数组num[]，并且将整除i后的整商作为新的被除数。
重复上述运算，直至9～2间的所有数整除完毕。若最后整商的位数大于1，则说明找不到满足上述条件的整数，失败退出；否则逆序输出数组num[]。
参考程序
#include<stdio.h>
#include<string.h>
#define N 1010
char str[N],ans[N]; //数串str[]；整商串ans[]
int num[3*N]; //存储满足条件的整数
int count(int i) //计算和返回str[]代表的整数除以i的结果：若能够整
//除，则返回1和整商串str[]；若不能整除，则返回0
{
int j,mod=0,k=0; //当前余数为mod，ans[]的指针为k
char *q; //商对应的数串
for(j = 0;str[j]!='\0';j ++) //模拟除法运算过程
{
mod = mod*10+str[j]-'0'; //计算商的当前位，送入ans[]
ans[k++] = mod/i +'0';
mod%=i; //计算余数
}
ans[k] = '\0'; //形成商对应的数串q
q = ans;
while(*q=='0') //规整：去掉q前导的无用0
q++;
if(mod!=0) //若最后余数非零，则说明不能整除，返回失败信息0
return 0;
for(j = 0; *q!='\0';j++,q++) //将商串转赋给str，作为下一次运算的被除数
str[j] = *q;
str[j] = '\0';
return 1; //返回成功信息1
}
int main()
{
int i,j;
while(scanf("%s",str),str[0]!='-') //反复输入十进制整数，直至输入-1为止
{
j=0;
if(str[1]=='\0') //若输入一位数字'x'，则直接输出结果'1x'
{
printf("1%s\n",str);
continue; //继续处理下一个测试用例
}
for(i = 9; i > 1; i--) //依次整除9~2
while(count(i)) //若当前数（即上一次运算的整商）能够整除i，则i
//进入num[]，直至当前数无法整除i为止
{
num[j++] = i;
}
if(strlen(str)>1) //若整商长度大于1，则说明不能被除尽，继续下一个测
//试用例
{
printf("There is no such number.\n");
continue;
}
while(j>0) //逆序输出num[]中的数字
printf("%d",num[--j]);
printf("\n");
}
return 0;
}
[1] 定义见：Neil J.A.Sloane in The Persistence of a Number published in Journal of Recreational Mathematics 6,1973,pp.97-98。——编者注