首页 > > 程序设计 > C/C++ >

高精度计算（一）：大整数加法

2019-08-16 07:49:25来源：博客园阅读 ()

高精度计算（一）：大整数加法

C/C++中的int 类型能表示的范围是-2³¹~2³¹ – 1。unsigned 类型能表示的范围是 0 ~2³²

– 1，即 0~4294967295。所以，int 和unsigned 类型变量，都不能保存超过10 位的整数。
有时我们需要参与运算的数，可能会远远不止10 位，例如要求100！的精确值。即便使用能表示的很大数值范围的double 变量，但是由于double变量只有64 位，double 变量的精度也不足以表示一个超过100 位的整数。一般我们称这种基本数据类型无法表示的整数为大整数。如何表示和存放大整数呢？最简单的思想就是：用数组存放和表示大整数。一个数组元素，存放大整数中的一位。

【例1】大整数加法。

输入两个不超过200位的非负大整数a和b，求a+b的值。

（1）编程思路。

首先要解决的就是存储 200 位整数的问题。显然，任何C/C++固有类型的变量都无法保
存它。最直观的想法是可以用一个字符串来保存它。

由于字符串本质上是一个字符数组，因此为了编程更方便，可以用数组unsigned a[200]来保存一个200 位的整数，让a[0]存放个位数，a[1]存放十位数，a[2]存放百位数……。
实现两个大整数相加的方法很简单，就是模拟小学生列竖式做加法，从个位
开始逐位相加，超过或达到10 则进位。

（2）源程序。

#include <stdio.h>
#include <string.h>
#define MAX_LEN 201
void bigNumAdd(char a[],char b[],char c[])
{
int i,j,n1,n2,n;
int num1[MAX_LEN]={0},num2[MAX_LEN]={0};
// 将a和b中存储的字符串形式的整数转换到num1和num2中去，
// num1[0]对应于个位、num1[1]对应于十位、……
n1 = strlen(a);
j = 0;
for (i = n1 - 1;i >= 0 ; i --)
num1[j++] = a[i] - '0';
n2 = strlen(b);
j = 0;
for (i = n2 - 1;i >= 0 ; i --)
num2[j++] = b[i] - '0';
n=n1>n2?n1:n2;
for (i = 0;i < n ; i ++ )
{
num1[i] += num2[i]; // 逐位相加
if (num1[i] >= 10 ) // 处理进位
{
num1[i] -= 10;
num1[i+1] ++;
}
}
j=0;
if (num1[n]!=0) c[j++]=num1[n]+'0';
for(i=n-1; i>=0; i--)
c[j++]=num1[i]+'0';
c[j]='\0';
}
int main()
{
char a[MAX_LEN],b[MAX_LEN],c[MAX_LEN+1];
scanf("%s",a);
scanf("%s",b);
bigNumAdd(a,b,c);
printf("%s\n",c);
return 0;
}

【例2】Integer Inquiry （POJ 1503）

Description

One of the first users of BIT's new supercomputer was Chip Diller. He extended his exploration of powers of 3 to go from 0 to 333 and he explored taking various sums of those numbers.
``This supercomputer is great,'' remarked Chip. ``I only wish Timothy were here to see these results.'' (Chip moved to a new apartment, once one became available on the third floor of the Lemon Sky apartments on Third Street.)
Input

The input will consist of at most 100 lines of text, each of which contains a single VeryLongInteger. Each VeryLongInteger will be 100 or fewer characters in length, and will only contain digits (no VeryLongInteger will be negative).

The final input line will contain a single zero on a line by itself.
Output

Your program should output the sum of the VeryLongIntegers given in the input.
Sample Input

123456789012345678901234567890
123456789012345678901234567890
123456789012345678901234567890
0
Sample Output

370370367037037036703703703670

（1）编程思路1。

直接调用例1中设计的函数void bigNumAdd(char a[],char b[],char c[])完成。

（2）源程序1。

#include <stdio.h>
#include <string.h>
#define MAX_LEN 201
void bigNumAdd(char a[],char b[],char c[])
{
int i,j,n1,n2,n;
int num1[MAX_LEN]={0},num2[MAX_LEN]={0};
// 将a和b中存储的字符串形式的整数转换到num1和num2中去，
// num1[0]对应于个位、num1[1]对应于十位、……
n1 = strlen(a);
j = 0;
for (i = n1 - 1;i >= 0 ; i --)
num1[j++] = a[i] - '0';
n2 = strlen(b);
j = 0;
for (i = n2 - 1;i >= 0 ; i --)
num2[j++] = b[i] - '0';
n=n1>n2?n1:n2;
for (i = 0;i < n ; i ++ )
{
num1[i] += num2[i]; // 逐位相加
if (num1[i] >= 10 ) // 处理进位
{
num1[i] -= 10;
num1[i+1] ++;
}
}
j=0;
if (num1[n]!=0) c[j++]=num1[n]+'0';
for(i=n-1; i>=0; i--)
c[j++]=num1[i]+'0';
c[j]='\0';
}
int main()
{
char a[MAX_LEN],c[MAX_LEN]={'0'};
scanf("%s",a);
while (1)
{
if(strlen(a)==1 && a[0]=='0')
break;
bigNumAdd(c,a,c);
scanf("%s",a);
}
printf("%s\n",c);
return 0;
}

（3）编程思路2。

在上面的程序中，每次调用函数都需要将被加数和加数字符串转换成数值，还需要将计算出的和转换成字符串。下面的程序不调用函数，直接通过循环完成多个数的累加。

（4）源程序2。

#include <stdio.h>
#include <string.h>
#define MAX_LEN 201
int main()
{
char a[MAX_LEN];
int sum[MAX_LEN]={0},tmp[MAX_LEN]={0};
int i,j,n=0,n1;
scanf("%s",a);
while (1)
{
if(strlen(a)==1 && a[0]=='0')
break;
n1 = strlen(a);
j = 0;
for (i = n1 - 1;i >= 0 ; i --)
tmp[j++] = a[i] - '0';
if (n<n1) n=n1+1;
for (i = 0;i < n ; i ++ )
{
sum[i] += tmp[i]; // 逐位相加
if (sum[i] >= 10 ) // 处理进位
{
sum[i] -= 10;
sum[i+1] ++;
}
}
scanf("%s",a);
}
bool isBeginZero = false;
for( i = n; i >= 0; i -- )
if(isBeginZero)
printf("%d", sum[i]);
else if (sum[i])
{
printf("%d", sum[i]);
isBeginZero = true;
}
if(! isBeginZero)
printf("0");
printf("\n");
return 0;
}

【例3】序列（POJ 3982）

Description

数列A满足An = An-1 + An-2 + An-3, n >= 3

编写程序，给定A0, A1 和 A2, 计算A99
Input

输入包含多行数据

每行数据包含3个整数A0, A1, A2 (0 <= A0, A1, A2 <= 32767)
数据以EOF结束
Output

对于输入的每一行输出A99的值
Sample Input

1 1 1
Sample Output

69087442470169316923566147

（1）编程思路。

直接调用例1中设计的函数void bigNumAdd(char a[],char b[],char c[])完成大整数的相加。

（2）源程序。

#include <stdio.h>

#include <string.h>

#define MAX_LEN 201
void bigNumAdd(char a[],char b[],char c[])
{
int i,j,n1,n2,n;
int num1[MAX_LEN]={0},num2[MAX_LEN]={0};
// 将a和b中存储的字符串形式的整数转换到num1和num2中去，
// num1[0]对应于个位、num1[1]对应于十位、……
n1 = strlen(a);
j = 0;
for (i = n1 - 1;i >= 0 ; i --)
num1[j++] = a[i] - '0';
n2 = strlen(b);
j = 0;
for (i = n2 - 1;i >= 0 ; i --)
num2[j++] = b[i] - '0';
n=n1>n2?n1:n2;
for (i = 0;i < n ; i ++ )
{
num1[i] += num2[i]; // 逐位相加
if (num1[i] >= 10 ) // 处理进位
{
num1[i] -= 10;
num1[i+1] ++;
}
}
j=0;
if (num1[n]!=0) c[j++]=num1[n]+'0';
for(i=n-1; i>=0; i--)
c[j++]=num1[i]+'0';
c[j]='\0';
}
int main()
{
char a[MAX_LEN],b[MAX_LEN],c[MAX_LEN],sum[MAX_LEN];
while (scanf("%s%s%s",a,b,c)!=EOF)
{
for (int i=3;i<=99;i++)
{
bigNumAdd(a,b,a);
bigNumAdd(a,c,sum);
strcpy(a,b);
strcpy(b,c);
strcpy(c,sum);
}
printf("%s\n",sum);
}
return 0;
}